文档介绍：第7章图
图是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继。
.
2021/4/4
1
【重点掌握】：
图的两种遍历方法：遍历的定义、深度优先搜索遍历和广度优先搜索遍历的算法；
应用图的遍历算法判断图的连通性及求图的生成树；
用Prim、Kruskal算法求图的最小生成树；
用Dijkstra算法求解单源最短路径问题；用Floyd算法求所有顶点间的最短路径问题；
利用AOV网进行拓扑排序；利用AOE网求关键路径问题；
【掌握】：
掌握图的定义和术语；
图的各种存储结构及其构造算法、在实际问题中的求解效率。
.
2
图的遍历
图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。
图结构的遍历复杂性：
（1）在图结构中，没有一个“自然”的首结点，图中的任意一个顶点都可以作为第一个被访问的结点
（2）在非连通图中，从一个顶点出发，只能访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中的其余连通分量
（3）在图结构中，如果有回路存在，那么一个顶点被访问后，有可能沿回路又回到该顶点，考虑如何避免重复访问
（4）在图结构中，一个顶点可以和其他多个顶点邻接，当这样的顶点访问过后，考虑如何选取下一个要访问的顶点的问题
.
3
图的遍历方法有深度优先遍历和广度优先遍历两种。
深度优先搜索
方法：
（1）从图的某一顶点V0出发，访问此顶点；
（2）依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问到。
.
4
V0
V7
V6
V5
V4
V3
V2
V1
若图的存储结构为邻接表，则
访问邻接点的顺序不唯一，
深度优先序列不是唯一的
V0
V1
V3
V2
V7
V6
V5
V4
V0,V1,V3,V4,V7,V2,V5,V6,
※求图G以V0为起点的的深度优先序列（设存储结构为邻接矩阵）
.
5
void DFS(Graph G, int v)
{/* 从第v个顶点出发，递归地深度优先遍历图G*/
/* v是顶点在一维数组中的位置，假设G是非空图*/
visited[v] =1;
Visit(v); /*访问第v个顶点*/
for ( w=FirstAdjVex(G, v); w; w=NextAdjVex(G, v, w) )
if (!visited[w]) DFS(G, w);
/*对v的尚未访问的邻接顶点w递归调用DFS*/
}
辅助数组：int visited[Max_Vertex_Num] ;
访问标志数组,全局变量，初始时所有分量全为0，visited[v]=1表示顶点v已被访问.
visited
0
1
2
3
4
……
0
0
0
0
0
深度优先遍历算法:
图的遍历
.
6
图的遍历
在邻接表存储结构上实现深度优先搜索:
void DFSTraverseAL(ALGraph G)
/*深度优先遍历以邻接表存储的图G*/
{int i;
for (i=0;i<; ++ i)
visited[i]=0; /*标志数组初始化*/
for(i=0;i<;++i)
if (!visited[i]) DFSAL(G,i);
/*Vi未访问过，从Vi开始DFS搜索*/
}
.
7
void DFSAL(ALGraph G, int i)
{/*从第v个顶点出发，递归地深度优先遍历图G*/
/* v是顶点的序号，假设G是用邻接表存储*/
EdgeNode *p; int w;
visited[i] =1; Visit(i); /*访问第v个顶点*/
for (p=[i].firstarc;p;p=p->nextarc)
{w=p->adjvex; /*w是v的邻接顶点的序号*/
if (!visited[w]) DFSAL(G, w);
/*若w尚未访问, 递归调用DFS*/
}
}/*DFSAL*/
图的遍历
.