搞定第六章图的玩儿法:基础操作与遍历全覆盖!
1. 图的基本操作
• Adjacent(G,x,y):判断图G是否存在边<x,y>或(x, y)。
• Neighbors(G,x):列出图G中与结点x邻接的边。
无向图:
有向图:
• InsertVertex(G,x):在图G中插入顶点x。
• DeleteVertex(G,x):从图G中删除顶点x。
无向图:
有向图:
• AddEdge(G,x,y):若无向边(x, y)或有向边不存在,则向图G中添加该边。
• RemoveEdge(G,x,y):若无向边(x, y)或有向边存在,则从图G中删除该边。
• FirstNeighbor(G,x):求图G中顶点x的第一个邻接点,若有则返回顶点号。若x没有邻接点 或图中不存在x,则返回-1。
无向图:
有向图:
• NextNeighbor(G,x,y):假设图G中顶点y是顶点x的一个邻接点,返回除y之外顶点x的下一 个邻接点的顶点号,若y是x的最后一个邻接点,则返回-1。
无向图:
• Get_edge_value(G,x,y):获取图G中边(x, y)或对应的权值。
• Set_edge_value(G,x,y,v):设置图G中边(x, y)或对应的权值为v。
后两个 与Adjacent(G,x,y) 雷同,核心在于找到边:
2. 广度优先遍历BFS
2.1 ⼴度优先遍历(Breadth-First-Search, BFS)要点:
- 找到与⼀个顶点相邻的所有顶点
- 标记哪些顶点被访问过
- 需要⼀个辅助队列
- FirstNeighbor(G,x):求图G中顶点x的第⼀个邻接点,若有则返回顶点号。 若x没有邻接点或图中不存在x,则返回-1。
- NextNeighbor(G,x,y):假设图G中顶点y是顶点x的⼀个邻接点,返回除y之外 顶点x的下⼀个邻接点的顶点号,若y是x的最后⼀个邻接点,则返回-1。
2.2 代码实现
①确定一个起始顶点v,将节点入队
②将对头元素v出队,依此访问v的各个未被访问的邻接节点,并将这些节点依此入队
③依此以各个邻接节点为起始节点重复步骤①②,直到整个图都遍历(队空+利用辅助数组标记各节点访问情况,防止出现非连通图未遍历的情况)
bool visited[Max_Vertex_Num];
void BFSTraverse(Graph G)
{
for(int i=0; i<G.vexnum; i++)
{
visited[i] = false;
}
InitQueue(Q);
for(int i=0; i<G.vexnum; i++)
{
if(!visited[i])
BFS(G, i); //对无向图调用BFS函数次数 = 连通分量数
}
}
//BFS
void BFS(Graph G, int v)
{
visit(v);
visited[v] = true;
EnQueue(Q, v);
while(!isEmpty(Q))
{
DeQueue(Q);
for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G, v, w))
{
if(!visited[w])
{
visit(w);
visited[w] = true;
EnQueue(Q, w);
}
}
}
}
2.3 复杂度分析:
(1)空间复杂度: 最坏情况,辅助队列大小为 。
(2)对于邻接矩阵存储的图,访问个顶点需要的时间,查找每个顶点的邻接点都需要 的时间,而总共有个顶点,时间复杂度为。
(3)对于邻接表存储的图,访问个顶点需要的时间,查找各个顶点的邻接点共需要的时间,时间复杂度为。
2.4 遍历序列的可变性
- 同⼀个图的邻接矩阵表示⽅式唯⼀,因此⼴度优先遍历序列唯⼀
- 同⼀个图邻接表表示⽅式不唯⼀,因此⼴度优先遍历序列不唯⼀
2.5 ⼴度优先⽣成树
- ⼴度优先⽣成树由⼴度优先 遍历过程确定。由于邻接表 的表示⽅式不唯⼀,因此基 于邻接表的⼴度优先⽣成树 也不唯⼀。
- 对⾮连通图的⼴度优先遍历,可得到⼴度优先⽣成森林
3. 深度优先遍历DFS
深度优先遍历(Depth First Search),也有称为深度优先搜索,简称为DFS。
3.1 与树的深度优先遍历之间的联系
3.2 图的深度优先遍历
3.2.1 代码实现
bool visited[MAX_VERTEX_NUM]; //访问标记数组
/*从顶点出发,深度优先遍历图G*/
void DFS(Graph G, int v){
int w;
visit(v); //访问顶点
visited[v] = TRUE; //设已访问标记
//FirstNeighbor(G,v):求图G中顶点v的第一个邻接点,若有则返回顶点号,否则返回-1。
//NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点,返回除w外顶点v
for(w = FirstNeighbor(G, v); w>=0; w=NextNeighor(G, v, w)){
if(!visited[w]){ //w为u的尚未访问的邻接顶点
DFS(G, w);
}
}
}
/*对图进行深度优先遍历*/
void DFSTraverse(MGraph G){
int v;
for(v=0; v<G.vexnum; ++v){
visited[v] = FALSE; //初始化已访问标记数据
}
for(v=0; v<G.vexnum; ++v){ //从v=0开始遍历
if(!visited[v]){
DFS(G, v);
}
}
}
3.2.2 复杂度分析:
空间复杂度:来⾃函数调⽤栈,时间复杂度=访问各结点所需时间+探索各条边所需时间
(1)空间复杂度主要来自来⾃函数调⽤栈,最坏情况下递归深度为 ;最好情况为
(2)对于邻接矩阵存储的图,访问个顶点需要的时间,查找每个顶点的邻接点都需要 的时间,而总共有个顶点,时间复杂度为。
(3)对于邻接表存储的图,访问个顶点需要的时间,查找各个顶点的邻接点共需要的时间,时间复杂度为。
3.2.3 深度优先遍历序列
- 同⼀个图的邻接矩阵表示⽅式唯⼀,因此深度优先遍历序列唯⼀
- 同⼀个图邻接表表示⽅式不唯⼀,因此深度优先遍历序列不唯⼀
- 从 2 出发的深度优先遍历序列:2, 1, 5, 6, 3, 4, 7, 8
- 从 3 出发的深度优先遍历序列:3, 4, 7, 6, 2, 1, 5, 8
- 从 1 出发的深度优先遍历序列:1, 2, 6, 3, 4, 7, 8, 5
3.2.4 深度优先⽣成树:
- 同⼀个图的邻接矩阵表示⽅式唯⼀,因此深度优先遍历序列唯⼀,深度优先⽣成树也唯⼀
- 同⼀个图邻接表表示⽅式不唯⼀,因此深度优先遍历序列不唯⼀,深度优先⽣成树也不唯⼀
3.2.5 图的遍历与图的连通性
- 对⽆向图进⾏BFS/DFS遍历 调⽤BFS/DFS函数的次数=连通分量数 对于连通图,只需调⽤1次 BFS/DFS
- 对有向图进⾏BFS/DFS遍历 调⽤BFS/DFS函数的次数要具体问题具体分析 若起始顶点到其他各顶点都有路径,则只需调⽤1次 BFS/DFS 函数 对于强连通图,从任⼀结点出发都只需调⽤1次 BFS/DFS
扩展:有 ABCDEF 六个城市,每一个城市都和其他所有城市直接相连,问从 A — B 有多少种连接方式,路径不允许在两个城市之间往返。
算法A到B,最多经过4个城市,按照经过城市个数分类:途径k个中间城市:从4个里面挑k个出来,,k个地点进行排列,第一步右k种选择,第二步有k-1种,共有k!种选择,所以总数为1*4!+4*3!+6*2!+4*1!+1*0!=65.