前言：学习数据结构的图部分
图的概念
图(Graph)是研究数据之间多对多的关系
一个图(G)定义为一个偶对(V,E)，记为G = (V,E)。其中：
- V是顶点的非空有限集合，记为V(G)
- E是无序集V&V的一个子集，记为E(G)，其元素是图的弧
图的形式化定义为：G = (V,E)
- V = {v | v ∈ data object}
- E = { <v,w> |v,w ∈ V ∩ p(v,w)} p(v,w)表示：从顶点v到顶点w有一条直接通路
- 顶点集合为空(V = null)的图为空图
图的相关术语
弧：表示两个顶点V和W之间存在的关系，用顶点偶对<v,w>表示。通常根据图的顶点偶对将图分为有向图和无向图
无向图：若图G的关系集合E(G)中，顶点偶对(v,w)和v与w之间是无序的，称图G是无向图
有向图：v和w之间是有序的，称图G是有向图
有向图中，<v,w> ∈ E(G)：v称为弧尾(tail)或始点(initial node)，w称为弧头(head)或终点(terminal node)
对于无向图来说，<v,w> ∈ E(G)，且<w,v> ∈ E(G)，则E(G)是对称的，用<v,w>表示两者之间的一条边，两个代表的同一条边。
完全无向图：顶点数问n，用e表示边的数目，则e ∈[0,n(n-1)/2]。有n(n-1)/2条边的无向图称为完全无向图
完全有向图：对于有向图，顶点个数为n，e表示弧的数目，则e ∈ [0,n(n - 1)]。具有n(n -1)条边的有向图称为完全有向图
稀疏图、稠密图：有很少边或弧的图，(e < nlogn)称为稀疏图，反之称为稠密图
权：与图的边和弧相关的数。权可以表示从一个顶点到另一个顶点的距离和耗费
子图、生成子图：
顶点的邻接(Adjacent)：
对于无向图，若(v,w) ∈ E，则，称顶点v和w互为邻接点
边(v,w**)依附于**顶点v和w；
对于有向图，若<v,w> ∈ E，则称顶点v”邻接到“顶点w，顶点w”邻接自“顶点v
弧<v,w>与顶点v和w”相关联“
顶点的度(degree)、入度、出度：
无向图中，与这个顶点的相关联的边的个数**(在无向图中，所有顶点度的和是图中边的2倍)**
有向图来说，分为出度和入度：进来的边叫做入度，出去的边叫做出度**(出度和入度之和为度)**
路径(Path)、路径的长度：
对于无向图，一个顶点经过若干个边能到达另一个顶点，称两个顶点是连通(可达)的，又称顶点到顶点有路径
对于有向图，顶点到另一个顶点有有向路径，指的是从顶点**经过若干个有向边(弧)**能到另一个顶点
路径是图G中连接两顶点之间所经过的顶点序列：
路径上边或有向边(弧)的数目称为该路径的长度
回路(Cycle)：
在一条路径中，没有重复相同的顶点，称为简单路径
第一个顶点和最后一个顶点相同的路径称为回路(环)
在一个回路中，若除第一个与顶点外不再出现重复的回路称为简单回路(简单环)
连通图、图的连通分量：
在无向图中，任何两个顶点都是可达的，则称为连通图，反之成为非连通图
- 若G是非连通图，则极大的连通子图称为G的连通分量
在有向图中，任意一个顶点作为起点，一个顶点作为终点，形成的有向路径，称为图G是强连通图，反之非强连通图
- 若G是非强连通图，则极大的强连通图称为G的强连通分量
生成树、生成森林：对于极小连通子图。包含图中全部n个顶点和只有足以构成一棵树的n-1条边，称为图的生成树
- 一棵有n个顶点的生成树有且仅有n - 1条边
- 如果一个图有n个顶点和小于n - 1条边，则非连通图
- 如果多于n - 1条边，则一定有环；
- 有n - 1条边的图不一定是生成树
有向图的生成森林的特点：由若干有向图组成且含有图中全部结点
有向树：是只有一个顶点的入度为0，其余顶点的入度均为1的有向图
网：
每个边(或弧)都附加一个权值的图，称为带权图
带权的连通图(包括弱连通图的有向图)称为网或网络
图的存储结构
图的存储结构比较复杂，常用的存储结构有：邻接矩阵、邻接[链]表、十字[链]表、邻接多重表和边表