图（Graph）的学习

图的认识

图(Graph)是由顶点和连接顶点的边构成的离散结构。一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。

图是最灵活的数据结构之一，很多问题都可以使用图模型进行建模求解。
树可以说只是图的特例，但树比图复杂很多

注意：顶点有时也称为节点或者交点，边有时也称为链接。

图有各种形状和大小。边可以有权重（weight），即每一条边会被分配一个正数或者负数值。边可以是有方向的。有方向的边意味着是单方面的关系。从顶点 X 到 顶点 Y 的边是将 X 联向 Y，不是将 Y 联向 X。

树和链表，都可以被当成是树，是一种更简单的形式。他们都有顶点（节点）和边（连接）。

图的概念

图是由顶点集合以及顶点间的关系集合组成的一种数据结构。
由顶点 V 集和边 E 集构成，因此图可以表示成 Graph = (V,E)
V是顶点的有穷非空集合；E是顶点之间关系的有穷集合，也叫边集合。

（1）有向图：顶点对<x,y>是有序的；无向图：顶点对<x,y>是无序的。
（2）无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边，用无序偶对(Vi,Vj)来表示

无向图

如果图中任意两个顶点时间的边都是无向边，则称该图为无向图：
　　
上图是无向图，所以连接顶点A与D的边，可以表示为无序对(A,D)，也可以写成(D,A)
对于如上无向图来说，G=(V,{E}) 其中顶点集合V={A,B,C,D}；边集合E={(A,B),(B,C),(C,D),(D,A),(A,C)}

有向图

有向边：若从顶点Vi到Vj的边有方向，则称这条边为有向边，也称为弧。
用有序偶<Vi,Vj>来表示，Vi称为弧尾，Vj称为弧头。

连接顶点A到D的有向边就是弧，A是弧尾，D是弧头，<A,D>表示弧。注意不能写成<D,A>。
对于如上有向图来说，G=(V,{E})其中顶点集合V={A,B,C,D};弧集合E={<A,D>,<B,A>,<C,A>,<B,C>}

（3）完全无向图：若有n个顶点的无向图有n(n-1)/2 条边, 则此图为完全无向图。

（4）完全有向图：有n个顶点的有向图有n(n-1)条边, 则此图为完全有向图。

（5）树中根节点到任意节点的路径是唯一的，但是图中顶点与顶点之间的路径却不是唯一的。路径的长度是路径上的边或弧的数目。
（6）如果对于图中任意两个顶点都是连通的，则成G是连通图。 （7）图按照边或弧的多少分稀疏图和稠密图。
如果任意两个顶点之间都存在边叫完全图，有向的叫有向图。若无重复的边或顶点到自身的边则叫简单图。
（8）图中顶点之间有邻接点。无向图顶点的边数叫做度。有向图顶点分为入度和出度。
（9）图上的边和弧上带权则称为网。
（10）有向的连通图称为强连通图。

有向图：具有方向性，顶点 (u,v)之间的关系和顶点 (v,u)之间的关系不同，后者或许不存在。
加权图：与加权图对应的就是无权图，又叫等权图。如果一张图不含权重信息，我们认为边与边之间没有差别。

邻接(adjacency)：邻接是两个顶点之间的一种关系。如果图包含 (u,v)，则称顶点v 与顶点u邻接。在无向图中，这也意味着顶点 u 与顶点 v 邻接。

关联(incidence)：关联是边和顶点之间的关系。在有向图中，边 (u,v)从顶点 u开始关联到 v，或者相反，从v关联到u。在有向图中，边不一定是对称的，有去无回是完全有可能的。
无向图中，顶点的度就是与顶点相关联的边的数目，没有入度和出度。
路径(path)：依次遍历顶点序列之间的边所形成的轨迹。
简单路径：没有重复顶点的路径称为简单路径。

环：包含相同的顶点两次或者两次以上。上图序列 < 1 , 2 , 4 , 3 , 1 > <1,2,4,3,1> <1,2,4,3,1>，1出现了两次，当然还有其它的环，比如 < 1 , 4 , 3 , 1 > <1,4,3,1> <1,4,3,1>。

无环图：没有环的图，其中，有向无环图有特殊的名称（DAG(Directed Acyline Graph)
下面这个概念很重要：

连通的：无向图中每一对不同的顶点之间都有路径。如果这个条件在有向图里也成立，那么是强连通的。

有向图的连通分支：将有向图的方向忽略后，任何两个顶点之间总是存在路径，则该有向图是弱连通的。有向图的子图是强连通的，且不包含在更大的连通子图中，则可以称为图的强连通分支。

上图， a 、e没有到 { b , c , d } 中的顶点的路径，所以各自是独立的连通分支。因此，上图有三个强连通分支，用集合写出来就是： { { a } , { e } , { b , c , d } }

割点：如果移除某个顶点将使图或者分支失去连通性，则称该顶点为割点。某些特定的顶点对于保持图或连通分支的连通性有特殊的重要意义。

双连通图：不含任何割点的图。
割点的重要性不言而喻。如果你想要破坏互联网，你就应该找到它的关节点。同样，要防范敌人的攻击，首要保护的也应该是关节点
桥(割边)：和割点类似，删除一条边，就产生比原图更多的连通分支的子图，这条边就称为割边或者桥。

图的表示

邻接列表

邻接列表：在邻接列表实现中，每一个顶点会存储一个从它这里开始的边的列表。比如，如果顶点A 有一条边到B、C和D，那么A的列表中会有3条边

邻接列表只描述了指向外部的边。A 有一条边到B，但是B没有边到A，所以 A没有出现在B的邻接列表中。

邻接矩阵

图最常见的表示形式为邻接链表和邻接矩阵

邻接矩阵，顾名思义，是一个矩阵，一个存储着边的信息的矩阵，而顶点则用矩阵的下标表示。对于一个邻接矩阵M，如果M(i,j)=1，则说明顶点i和顶点j之间存在一条边，对于无向图来说，M (j ,i) = M (i, j)，所以其邻接矩阵是一个对称矩阵；对于有向图来说，则未必是一个对称矩阵。邻接矩阵的对角线元素都为0。下图是一个无向图和对应的邻接矩阵：


需要注意的是，当边上有权值的时候，称之为网图，则邻接矩阵中的元素不再仅是0和1了，邻接矩阵M中的元素定义为：

邻接矩阵：在邻接矩阵实现中，由行和列都表示顶点，由两个顶点所决定的矩阵对应元素表示这里两个顶点是否相连、如果相连这个值表示的是相连边的权重。例如，如果从顶点A到顶点B有一条权重为 5.6 的边，那么矩阵中第A行第B列的位置的元素值应该是5.6：

邻接列表在表示稀疏图时非常紧凑而成为了通常的选择，但稀疏图表示时使用邻接矩阵，会浪费很多内存空间，遍历的时候也会增加开销。
如果图是稠密图，可以选择更加方便的邻接矩阵。
还有，顶点之间有多种关系的时候，也不适合使用矩阵。因为表示的时候，矩阵中的每一个元素都会被当作一个表

图的遍历

深度优先遍历

深度优先遍历（Depth_First_Search）,也称为深度优先搜索，简称DFS。

广度优先遍历

广度优先遍历（Breadth_First_Search）,又称为广度优先搜索，简称BFS。
深度遍历类似树的前序遍历，广度优先遍历类似于树的层序遍历。