6.1 什么是图
6.1.1 什么是图——定义
表示多对多的关系
包含
- 一组顶点：通常用V(Vertex)表示顶点集合
- 一组边：通常用E(Edge)表示边的集合
- 边是顶点对：(v,w)属于E，其中v,w属于V
- 有向边表示从v指向w的边(单行线)
- 不考虑重边和自回路
抽象数据类型定义
- 类型名称：图(Graph)
- 数据对象集：G(V,E)由一个非空的有限顶点集合V和一个有限边集合E组成(可以一条边都没有，但不能一个顶点都没有)
- 操作集：对于任意图G属于Graph，以及v属于V，e属于E
1.GraphCreate()：建立并返回空图
2.GraphInsertVertex(GraphG, Vertexv)：将v插入G
3.GraphInsertEdge(GraphG, Edgee)：将e插入G;
4.voidDFS(GraphG,Vertexv)：从顶点v出发深度优先遍历图G;
5.voidBFS(GraphG,Vertexv)：从顶点v出发宽度优先遍历图G;
6.voidShortestPath(GraphG,Vertexv,intDist[])：计算图G中顶点v到任意其他顶点的最短距离
7.voidMST(GraphG)：计算图G的最小生成树
常见术语
- 无向图：无所谓方向的
- 有向图：在图中，若用箭头标明了边是有方向性(单向或者双向)的，则称这样的图为有向图，否则称为无向图。
- 权重：边上显示的数字，可以有各种各样的现实意义
- 网络：有带权重的图
6.1.2 什么是图——邻接矩阵表示法
怎么在程序中表示一个图
-
网络异常，图片无法展示|
-
邻接矩阵——有什么好处？网络异常，图片无法展示|
- 直观、简单、好理解
- 方便检查任意一对顶点间是否存在边
- 方便找任一顶点的所有"邻接点"(有边直接相连的顶点)
- 方便计算任一顶点的"度"(从该点出发的边数为"出度"，指向该点的边数为"入度")有向图的概念
- 邻接矩阵——有什么不好?
- 浪费空间——存稀疏图(点很多而边很少)有大量无效元素
但对稠密图(特别是完全图)还是很合算的 - 浪费时间——统计稀疏图中一共有多少条边
无向图
对应行(或列)非0元素的个数
有向图
对应行非0元素的个数是"出度";对应列非0元素的个数是"入度"
6.1.3 什么是图——邻接表表示法
邻接表：G[N]为指针数组，对应矩阵每行一个的链表，只存非0元素
上图的顺序是无所谓的，可以随意排列。使用这个表需要足够稀疏才合算
优点：
- 方便找任一顶点的所有"邻接点"
- 节约稀疏图的空间
需要N个头指针+2E个结点(每个结点至少2个域) - 方便计算任一顶点的"度"
对无向图：是的
对有向边：只能计算"出度";需要构造"逆邻接表"(存指向自己的边)来方便计算"入度" - 方便检查任意一对顶点间是否存在边？NO
对于网络，结构中要增加权重的域
6.2 图的遍历
6.2.1 图的遍历——DFS
遍历：把图里面每个顶点都访问一遍而且不能有重复的访问
深度优先搜索(DFS)
当访问完了一个节点所有的灯后，一定原路返回对应着堆栈的出栈入栈的一个行为
深度优先搜索的算法描述
voidDFS(VertexV)//从迷宫的节点出来
{
visited[V] =true;//给每个节点一个变量，true相当于灯亮了，false则是熄灭状态
for(V的每个邻接点W)//视野看得到的灯
if(!visited[W])//检测是否还有没点亮的
DFS(W);//递归调用
}
//类似树的先序遍历
若有N个顶点、E条边，时间复杂度是
用邻接表存储图，有O(N+E)//对每个点访问了一次，每条边也访问了一次
用邻接矩阵存储图，有O(N²)//V对应的每个邻接点W都要访问一遍
6.2.2 图的遍历——BFS
广度优先搜索(Breadth First Search,BFS)
voidBFS(VertexV)
{
visited[V] =true;
Enqueue(V,Q);//压到队列里
while(!IsEmpty(Q)){
V=Dequeue(Q);//每次循环弹出一个节点
for(V的每个邻接点W)
if(!visited[W]){//没有访问过的去访问将其压入队列中
visited[W] =true;
Enqueue(W,Q);
}
}
}
若有N个顶点，E条边，时间复杂度是
用邻接表存储图，有O(N+E)
用邻接矩阵存储图，有O(N²)
下面进行说明：
第1步：访问A。
第2步：访问(A的邻接点)C。在第1步访问A之后，接下来应该访问的是A的邻接点，即"C,D,F"中的一个。但在本文的实现中，顶点ABCDEFG是按照顺序存储，C在"D和F"的前面，因此，先访问C。
第3步：访问(C的邻接点)B。在第2步访问C之后，接下来应该访问C的邻接点，即"B和D"中一个(A已经被访问过，就不算在内)。而由于B在D之前，先访问B。
第4步：访问(C的邻接点)D。在第3步访问了C的邻接点B之后，B没有未被访问的邻接点；因此，返回到访问C的另一个邻接点D。
第5步：访问(A的邻接点)F。 前面已经访问了A，并且访问完了"A的邻接点B的所有邻接点(包括递归的邻接点在内)"；因此，此时返回到访问A的另一个邻接点F。
第6步：访问(F的邻接点)G。
第7步：访问(G的邻接点)E。
因此访问顺序是：A -> C -> B -> D -> F -> G -> E。
当然，上图是基于无向图，具体的代码在文章后面实现。
广度优先搜索
广度优先搜索算法(Breadth First Search)，又称为"宽度优先搜索"或"横向优先搜索"，简称BFS。
它的思想是：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。
换句话说，广度优先搜索遍历图的过程是以v为起点，由近至远，依次访问和v有路径相通且路径长度为1,2…的顶点。
第1步：访问A。
第2步：依次访问C,D,F。在访问了A之后，接下来访问A的邻接点。前面已经说过，在本文实现中，顶点ABCDEFG按照顺序存储的，C在"D和F"的前面，因此，先访问C。再访问完C之后，再依次访问D,F。
第3步：依次访问B,G。在第2步访问完C,D,F之后，再依次访问它们的邻接点。首先访问C的邻接点B，再访问F的邻接点G。
第4步：访问E。在第3步访问完B,G之后，再依次访问它们的邻接点。只有G有邻接点E，因此访问G的邻接点E。
因此访问顺序是：A -> C -> D -> F -> B -> G -> E。
6.2.3 图的遍历——为什么需要两种遍历
在不同的情况下效率不同
广度跟深度的区别
- 深度是直接一条路走到黑，碰壁没路走了在返回
- 广度是一圈一圈的扫描过去，虽然前面还有路也不会强行深入
6.2.4 图的遍历——图不连通怎么办
连通：如果从V到W存在一条(无向)路径，则称V与W是连通的
路径：V到W路径是一系列顶点{V,v1,v2,....,vn,W}的集合，其中任一对相邻的顶点间都有图中的边。路径的长度是路径中的边数(如果带权(带权图)，则是所有边的权重和)。如果V到W之间的所有顶点都不同，则称为简单路径(有回路就不是简单路径)
回路：起点等于终点的路径
连通图：图中任意两顶点均连通
连通分量：无向图的极大连通子图
- 极大顶点数：再加1个顶点就不连通了
- 极大边数：包含子图中所有顶点相连的所有边
对有向图：
//强连通：有向图中顶点V和W之间存在双向路径，则称V和W是强连通的(路径可以不同同一条，但是一定是连通的)
//强连通图：有向图中任意两顶点均强连通
//强连通分量：有向图的极大强连通子图
//弱连通图：将强连通图的所有边的方向抹掉变成无向图就是连通的了
每调用一次DFS(V)，就把V所在的连通分量遍历了一遍,BFS也一样
voidDFS(VertexV)
{
visited[V] =true;
for(V的每个邻接点W)
if(!visited[W])
DFS(W);
}
遍历分量
voidListComponents(GraphG)
{
for(eachVinG)
if(!visited[V]){
DFS(V);//or BFS(V)
}
}
