图的遍历：
- 从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traversing Graph）。
- 树的遍历中由于根节点只有一个，遍历都是从根结点开始。但是图比较复杂，任一顶点都可能和其余的所有顶点相邻接，极有可能存在沿着某条路径搜索后，又回到原顶点，而有些顶点还没有遍历到。因此需要在遍历的过程中打上标记，避免同一个顶点访问多次，可以设置一个访问数组visited[n]，n是图中顶点的个数，初值为false，访问过后设置为true。
- 对于图的遍历来说，通常包括深度优先遍历(DFS)和广度优先遍历(BFS)两种方法。
深度优先遍历（Depth First Search，DFS）：
从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。对于非连通图，只需要对它的连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点做起始点，重复上述过程，直至图中所有顶点都被访问到位置。
广度优先遍历：（Breadth First Search，BFS）:
我们可以发现图的深度优先遍历类似于树的前序遍历，而广度优先遍历类似于树的层序遍历。两者在存储结构相同的情况下时间复杂度是一样的，仅仅是对顶点访问的顺序不同。
代码示例
此处分别使用图的邻接矩阵和邻接表结构实现DFS和BFS，图的结构创建可查看https://www.jianshu.com/p/b50ba1b3c327
MGraph.h
//DFS(深度优先搜索遍历)
void DFS(MGraph G, int v);
//BFS(广度优先搜索遍历)
void BFS(MGraph G, int v);
MGraph.cpp
//DFS(深度优先搜索遍历,使用邻接矩阵的时间复杂度为O(n^2))
void DFS(MGraph G, int v)
{
cout << G.vexs[v] << " ";
visited[v] = true; //标志已经遍历过
for (int i = 0; i < G.numVertexes; i++)
{
if (G.arc[v][i] && !visited[i]) //未遍历过的邻接点
{
DFS(G, i); //遍历第i个邻接点
}
}
}
//BFS(广度优先搜索遍历 O(n^2)---与存储结构相关)
void BFS(MGraph G, int v)
{
cout << G.vexs[v] << " "; //先遍历当前顶点
visited[v] = true;
queue<int> q;
q.push(v);
while (!q.empty()) //如果队列不为空
{
int u = q.front(); //取队列第一个元素
q.pop(); //出队
for (int i = 0; i < G.numVertexes; i++)
{
if (G.arc[u][i] && !visited[i]) //未遍历过的邻接点
{
cout << G.vexs[i] << " ";
visited[i] = true;
q.push(i);
}
}
}
}
ALGraph.h
//DFS（深度优先搜索遍历）
void DFS(GraphAdjList G, int v);
//BFS（广度优先搜索遍历）
void BFS(GraphAdjList G, int v);
ALGraph.cpp
//DFS（深度优先搜索遍历）
void DFS(GraphAdjList G, int v)
{
cout << G.adjList[v].data << " "; //输出顶点名称
visited1[v] = true;
EdgeNode* p = G.adjList[v].firstEdge; //顶点的第一条边
while (p)
{
if (!visited1[p->adjvex])
{
DFS(G, p->adjvex);
}
p = p->next;
}
}
//BFS（广度优先搜索遍历 O(n+e)--与存储结构相关 ）
void BFS(GraphAdjList G, int v)
{
cout << G.adjList[v].data << " "; //输出顶点名称
visited1[v] = true;
queue<int> q;
q.push(v);
EdgeNode* p;
while (!q.empty()) //顶点还有邻接点
{
int u = q.front();
q.pop(); //出队
p = G.adjList[u].firstEdge;
while (p) //如果该顶点的边存在
{
if (!visited1[p->adjvex])
{
cout << G.adjList[p->adjvex].data << " ";
visited1[p->adjvex] = true;
q.push(p->adjvex);
}
p = p->next;
}
}
}
main.cpp
#include <iostream>
#include "MGraph.h"
#include "ALGraph.h"
using namespace std;
extern bool* visited, * visited1;
int main(int argc, char** argv)
{
//1.邻接矩阵
MGraph MG;
CreateMGrah(MG);
for (int i = 0; i < MG.numVertexes; i++) //对于连通图，只执行一次
{
if (!visited[i])
{
DFS(MG, i); //深度优先搜索遍历
//BFS(MG, 0); //广度优先搜索遍历
}
}
//////////////////////////////////////////////////
//2.邻接表
GraphAdjList ALG;
CreateALGraph(ALG);
for (int i = 0; i < ALG.numVertexes; i++) //对于连通图，只执行一次
{
if (!visited1[i])
{
DFS(ALG, i);
//BFS(ALG, 0);
}
}
return 0;
}
网友评论