复习 图的定义和术语 图(Graph)、有向图、无向图、子图、有向完全图 、完全图、稀疏图、稠密图、权、网、邻接点、相关边、度、路径、路径长度、回路、简单路径、简单回路、连通、连通图、连通分量、强连通图、强连通分量、生成树 图的存储方法 给定一个图，画出邻接矩阵、邻接表 图的邻接矩阵和邻接表的存储算法

第六章 图 6.1 图的定义和术语 6.2 图的存储结构 6.3 图的遍历 6.4 图的连通性问题 6.5 有向无环图及其应用 6.6 最短路径

6.3 图的遍历 遍历定义：从图中指定顶点出发，按照某种规则将图中的每一个顶点访问且仅访问一次的过程。 6.3 图的遍历 遍历定义：从图中指定顶点出发，按照某种规则将图中的每一个顶点访问且仅访问一次的过程。 回路问题：在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。

怎样避免重复访问？ 解决思路：可设置一个辅助数组 visited [n ]，用来标记每个被访问过的顶点。它的初始状态为0，在图的遍历过程中，一旦某一个顶点i 被访问，就立即改 visited [i]为1，防止它被多次访问。 图常用的遍历： 一、深度优先搜索 二、广度优先搜索

6.3.1 深度优先遍历(DFS) 方法：从图的某一顶点V出发，访问此顶点；然后依次从V的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止. V1 V2 V4 V5 V3 V7 V6 V8 例 深度遍历：V1 V2 V4  V8 V5 V3 V6 V7

V1 V2 V4 V5 V3 V7 V6 V8 例 深度遍历：V1 V2 V4  V8 V5 V6 V3 V7 例 V1 V2 V4 V5 V3 V7 V6 V8 深度遍历：V1 V2 V4  V8 V5 V6 V3 V7

V1 V2 V4 V5 V3 V7 V6 V8 例 深度遍历：V1 V2 V4  V8 V3 V6 V7 V5

6.3 图的遍历 V0 V1 V3 V4 V2 V6 V5 V7 例 6.3.1 深度优先遍历算法（递归算法）：在链式存储结构（邻接表）上实现 深度遍历：V0 V2  V6  V5  V1  V4  V7  V3 1 2 3 v0 v2 v3 v1 vexdata firstarc 6 7 ^ adjvex next 4 v4 5 v5 v6 v7

V0 V1 V3 V4 V2 V6 V5 V7 例 深度遍历：V0 V2  V6  V5  V1  V3  V7  V4 1 2 3 v0 v2 v3 v1 vexdata firstarc 6 7 ^ adjvex next 4 v4 5 v5 v6 v7

6.3 图的遍历 6.3.1 深度优先遍历算法（递归算法）：在链式存储结构（邻接表）上实现 开始 开始 标志数组初始化 访问V0,置标志 6.3 图的遍历 6.3.1 深度优先遍历算法（递归算法）：在链式存储结构（邻接表）上实现 开始 标志数组初始化 Vi=1 Vi访问过 DFS Vi=Vi+1 Vi==Vexnums 结束 N Y 开始 访问V0,置标志 求V0邻接点 有邻接点w 求下一邻接点 wV0 W访问过 结束 N Y DFS

6.3.1 深度优先遍历算法（无向图的递归算法）：在链式存储结构（邻接表）上实现 #include "stdio.h" #include "stdlib.h" #define n 5 /*顶点个数*/ #define e 3 /*边的条数*/ int visited[n]; /*访问标志数组*/ typedef struct node1{ int info; int adjvertex; struct node1 *nextarc;}glinklistnode; /*定义边结点的结构*/ typedef struct node2{int vertexinfo;glinklistnode *firstarc;}glinkheadnode; /*定义邻接表的表头类型*/

6.3.1 深度优先遍历算法（无向图的递归算法）：在链式存储结构（邻接表）上实现 void createadjlist(glinkheadnode g[ ]) { /*创建无向图的邻接表*/ int i,j,k; glinklistnode *p; for(i=0;i<n;i++) {g[i].vertexinfo=i; g[i].firstarc=0;} /*赋初值*/ for(k=0;k<e;k++) { scanf("%d,%d",&i,&j); p=(glinklistnode *)malloc(sizeof(glinklistnode)); p->adjvertex=j; p->nextarc=g[i].firstarc; g[i].firstarc=p; p->adjvertex=i; p->nextarc=g[j].firstarc; g[j].firstarc=p; }

6.3.1 深度优先遍历算法（无向图的递归算法）：在链式存储结构（邻接表）上实现 void dfs(glinkheadnode g[ ], int v) { /*从顶点v出发，深度优先搜索遍历图 */ int i=0; glinklistnode *p; printf("%d\t",v); visited[v]=1; p=g[v].firstarc; while(p!=0){ if(visited[p->adjvertex]==0) dfs(g,p->adjvertex); p=p->nextarc; } main( ) { glinkheadnode g[n]; int i; createadjlist(g); for(i=0;i<n;i++) visited[i]=0; for(i=0;i<n;i++) { if(visited[i]==0) dfs(g,i); }

6.3.1 深度优先遍历算法（无向图的递归算法）：在链式存储结构（邻接表）上实现 分析：在遍历图时，对图中每个顶点至多调用一次dfs过程，因为一旦某个 顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个 顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。 当以邻接表作图的存储结构时，找邻接点所需时间为O（e），其中e为无向图中边 的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复 杂度为O（n＋e）。

6.3.2 广度优先遍历(BFS) 方法：从图的某一顶点V0出发，访问此顶点后，依次访问V0的各个未曾访问过的邻接点；然后分别从这些邻接点出发，广度优先遍历图，直至图中所有已被访问的顶点的邻接点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止 V1 V2 V4 V5 V3 V7 V6 V8 例 广度遍历：V1 V2 V3  V4 V5 V6 V7 V8

V1 V2 V4 V5 V3 V7 V6 V8 例 广度遍历：V1 V2 V3  V4 V5 V6 V7 V8 例 V1 V2 V4 V5 V3 V7 V6 V8 广度遍历：V1 V2 V3  V4 V5 V6 V7 V8

V1 V2 V4 V5 V3 V7 V6 V8 例 广度遍历：V1 V2 V3  V4 V6 V7 V8 V5

若从顶点1 出发，广度优先搜索序列为：1，2，3，4，5， 6，7，8。 6.3.2 广度优先遍历算法（无向图的非递归算法）：在顺序存储结构（邻接矩阵）上的实现 若从顶点1 出发，广度优先搜索序列为：1，2，3，4，5， 6，7，8。

在广度优先遍历中,为使“先被访问的顶点,其邻接点亦先被访问” ,需附设队列Q保存被访问过的顶点，并控制遍历顶点的顺序。 以后,当Q不空时就从Q中删除一个顶点,每删除一个顶点,就依次访问它的每一个未被访问过的邻接点,并令其进队。这样,当Q为空时,表明所有与起始点有路径相通的顶点都已访问完毕。 Q V0 V7 V6 V5 V4 V3 V2 V1 V0 V1 V0 V1 V2 V3 V4 V5 V6 V7 V2 V2 V0 V1 V2 V3 V4 V5 V6 V7 V3 V4 V5 V6 V7

6.3.2 广度优先遍历算法（无向图的非递归算法）：在顺序存储结构（邻接矩阵）上的实现 和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，为了顺次访 问路径长度为2、3、…的顶点，需附设队列以存储已被访问的路径长度为1，2，…的顶点。广 度优先遍历的算法如下所示。 #include "stdio.h“ #define n 5 #define e 3 int visited[n]; typedef struct {int vertex[n]; int edge[n][n];}gadjmatrix; void createadjmatrix(gadjmatrix *g) { int i,j,k; for(i=0; i<n; i++) g->vertex[i]=i; for(i=0; i<n; i++) for(j=0; j<n; j++) g->edge[i][j]=0; for (k=0;k<e;k++){ scanf("%d,%d",&i,&j); g->edge[i][j]=1;g->edge[j][i]=1;} }

6.3.2 广度优先遍历算法（无向图的非递归算法）：在顺序存储结构（邻接矩阵）上的实现 void bfs(gadjmatrix g, int v) { struct {int front; int rear; int q[n];}queue; int i,j; printf("%d\t",v); visited[v]=1; queue.front=queue.rear=0; queue.rear=(queue.rear+1)%n; queue.q[queue.rear]=v; while( queue.front!=queue.rear) { queue.front=(queue.front+1)%n; i=queue.q[queue.front]; for(j=0;j<n;j++) if (g.edge[i][j]==1 && visited[j]==0) { printf("%d\t",j); visited[j]=1; queue.rear=(queue.rear+1)%n; queue.q[queue.rear]=j; }

6.3.2 广度优先遍历算法（无向图的非递归算法）：在顺序存储结构（邻接矩阵）上的实现 main( ) { int i; gadjmatrix g; createadjmatrix(&g); for(i=0;i<n;i++) visited[i]=0; for(i=0;i<n;i++) { if(visited[i]==0) bfs(g,i); } }

6.3.2 广度优先遍历算法（无向图的非递归算法）：在顺序存储结构（邻接矩阵）上的实现 分析上述过程，每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接 点的过程、因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之 处仅仅在于对顶点访问的顺序不同

小结 图的深度优先和广度优先遍历思想 图的深度优先遍历算法（用邻接表作为存储结构） 图的广度优先遍历算法（用邻接矩阵作为存储结构） 核心：递归思想 图的广度优先遍历算法（用邻接矩阵作为存储结构） 核心：循环队列

作业 1.设计图的深度优先遍历算法（用邻接表作为存储结构）。 2. 设计图的广度优先遍历算法（用邻接矩阵作为存储结构）。