数据结构 -- 图的遍历

图的遍历

广度优先遍历

树VS图

树：不存在“回路”，搜索相邻结点时，不可能搜到已经访问过的结点

图：搜索相邻结点时，有可能搜到已经访问过的结点

代码实现

广度优先遍历要点：

Q1.找到与一个顶点相邻的所有顶点

Q2.标记哪些顶点被访问过

Q3.需要一个辅助队列

A1：FirstNeighbor(G,x):求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x,则返回-1。

NextNeighbor(G,x,y):假设图G中顶点y是顶点x的一个邻接点，返回除y外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。

A2：bool visited[MAX_VARTEX_NUM] //标记访问数组

bool visited[MAX_VERTEX_NUM];			//访问标记数组//广度优先遍历
void BFS(Graph G,int v){				//从顶点v出发，广度优先遍历图Gvisit(v);							//访问初始顶点vvisited[v] = true;					//对v做已访问标记EnQueue(Q,v);while(!isEmpty(Q)){DeQueue(Q,v);					//顶点v出队列for(w = FirstNeighbor(G,v);w>=0;w = NextNeighbor(G,v,w))//检测v的所有邻接顶点if(!visited[w]){			//w尚未被访问visit(w);				//访问顶点wvisited[w] = true;		//对w做已访问标记EnQueue(Q,w);			//顶点w入队列}}
}

算法存在的问题

如果是非连通图，则无法遍历完所有节点

当调用一次BFS算法后，检查visit数组中是否还存在值为false的结点（未访问结点），从第一个值为false的结点出发，再执行一次BFS算法，直到所有结点全部被访问过一遍

改进后算法

bool visited[MAX_VERTEX_NUM];			//访问标记数组void BFSTraverse(Graph G){for(i = 0;i<G.vexnum;++)visited[i] = false;InitQueue(Q);for(i = 0;i<G.vexnum;++i)if(!visited[i])	BFS(G,i);
}//广度优先遍历
void BFS(Graph G,int v){				//从顶点v出发，广度优先遍历图Gvisit(v);							//访问初始顶点vvisited[v] = true;					//对v做已访问标记EnQueue(Q,v);while(!isEmpty(Q)){DeQueue(Q,v);					//顶点v出队列for(w = FirstNeighbor(G,v);w>=0;w = NextNeighbor(G,v,w))//检测v的所有邻接顶点if(!visited[w]){			//w尚未被访问visit(w);				//访问顶点wvisited[w] = true;		//对w做已访问标记EnQueue(Q,w);			//顶点w入队列}}
}

对于无向图：调用BFS的次数 = 连通分量的数量

复杂度分析

邻接矩阵存储的图：

访问|V|个顶点需要O(|V|)的时间

查找每个顶点的邻接点都需要O(|V|)的时间，而总共有|V|个顶点

时间复杂度 = O(|V|²)

邻接矩阵存储的图：

访问|V|个顶点需要O(|V|)的时间

查找每个顶点的邻接点都需要O(|E|)的时间，而总共有|E|个顶点

时间复杂度 = O(|V|+|E|)

广度优先生成树和生成森林

广度优先生成树/森林由广度优先遍历过程确定。由于邻接表的表示方式不唯一，因此基于邻接表的广度优先生成树/森林也不唯一

深度优先遍历

与树的深度优先遍历之间的联系

与树的先根遍历思路相同

算法实现

bool vsited[MAX_VERTEX_NUM];		//访问标记数组void DFSTraverse(Graph G){for(v = 0;v<G.vexnum;++v)visited[v] = false;for(v = 0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);
}void DFS(Graph G,int v){		//从顶点v出发 深度优先遍历图Gvisit(v);visited[v] = true;for(w = FirstNeighbor(G,v);w>=0;w = NextNeighbor(G,v,w)){if(!visited[w])DFS(G,w);}
}

复杂度分析

空间复杂度：来自于函数调用栈，最坏情况，递归深度为O(|V|)

空间复杂度：最好情况，O(1)

时间复杂度：访问各个结点所需时间+探索各条边所需时间

邻接矩阵存储的图：

访问|V|个顶点需要O(|V|)的时间

查找每个顶点的邻接点都需要O(|V|)的时间，而总共有|V|个顶点

时间复杂度 = O(|V|²)

邻接矩阵存储的图：

访问|V|个顶点需要O(|V|)的时间

查找每个顶点的邻接点都需要O(|E|)的时间，而总共有|E|个顶点

时间复杂度 = O(|V|+|E|)

深度优先生成树

深度优先生成树/森林由深度优先遍历过程确定。由于邻接表的表示方式不唯一，因此基于邻接表的深度优先生成树/森林也不唯一

图的遍历和图的连通性

对于无向图进行BFS/DFS遍历，调用BFS/DFS函数的次数 = 连通分量数

对于连通图，只需要调用一次BFS/DFS

对于有向图进行BFS/DFS遍历

调用BFS/DFS函数的次数要具体问题具体分析

若起始顶点到其他顶点都有路径，则只需要调用1次BFS/DFS函数

对于强连通图，从任一结点出发都只需要调用1次BFS/DFS