图的遍历
介绍
是从图的某一顶点出发，按照某种搜索方式对图中所有顶点访问一次且仅一次。图的遍历可以解决很多搜索问题，在实际中应用非常广泛。图的遍历根据搜索方式的不同，分为广度优先搜索和深度优先搜索。
一.深度优先遍历
1.1介绍
深度优先搜索（Depth First Search, DFS）是最常见的图搜索方法之一。深度优先搜索沿着一条路径一直走下去，无法行进时，回退到刚刚访问的节点，似“不撞南墙不回头，不到黄河不死心”。深度优先遍历是按照深度优先搜索的方式对图进行遍历。
深度优先遍历秘籍：后被访问的顶点，其邻接点先被访问。
根据深度优先遍历秘籍，后来先服务，可以借助于栈实现。递归本身就是使用栈实现的，因此使用递归方法更方便。
举例
代码实现1—深度优先遍历邻接矩阵
//深度优先遍历 邻接矩阵 #include <iostream> using namespace std; #define MaxVnum 100 //顶点数最大值 bool visited[MaxVnum]; //访问标志数组，其初值为"false" typedef char VexType; //顶点的数据类型，根据需要定义 typedef int EdgeType; //边上权值的数据类型，若不带权值的图，则为0或1 typedef struct { VexType Vex[MaxVnum]; EdgeType Edge[MaxVnum][MaxVnum]; int vexnum, edgenum; //顶点数，边数 }AMGragh; int locatevex(AMGragh G, VexType x) { for (int i = 0; i < G.vexnum; i++)//查找顶点信息的下标 if (x == G.Vex[i]) return i; return -1;//没找到 } void CreateAMGraph(AMGragh& G)//创建无向图的邻接矩阵 { int i, j; VexType u, v; cout << "请输入顶点数：" << endl; cin >> G.vexnum; cout << "请输入边数:" << endl; cin >> G.edgenum; cout << "请输入顶点信息:" << endl; for (int i = 0; i < G.vexnum; i++)//输入顶点信息，存入顶点信息数组 cin >> G.Vex[i]; for (int i = 0; i < G.vexnum; i++)//初始化邻接矩阵所有值为0，如果是网，则初始化邻接矩阵为无穷大 for (int j = 0; j < G.vexnum; j++) G.Edge[i][j] = 0; cout << "请输入每条边依附的两个顶点：" << endl; while (G.edgenum--) { cin >> u >> v; i = locatevex(G, u);//查找顶点u的存储下标 j = locatevex(G, v);//查找顶点v的存储下标 if (i != -1 && j != -1) G.Edge[i][j] = G.Edge[j][i] = 1; //邻接矩阵储置1，若有向图G.Edge[i][j]=1 else { cout << "输入顶点信息错！请重新输入！" << endl; G.edgenum++;//本次输入不算 } } } void print(AMGragh G)//输出邻接矩阵 { cout << "图的邻接矩阵为：" << endl; for (int i = 0; i < G.vexnum; i++) { for (int j = 0; j < G.vexnum; j++) cout << G.Edge[i][j] << "\t"; cout << endl; } } void DFS_AM(AMGragh G, int v)//基于邻接矩阵的深度优先遍历 { int w; cout << G.Vex[v] << "\t"; visited[v] = true; for (w = 0; w < G.vexnum; w++)//依次检查v的所有邻接点 { if (G.Edge[v][w] && !visited[w])//v,w邻接且w未被访问 { DFS_AM(G, w);//从w顶点开始递归深度优先遍历 } } } //如果不是一个连通图,还需要进行验证. void DFS_AM(AMGragh G) { for (int i = 0; i < G.vexnum; i++)//检查未被访问的顶点 { if (!visited[i]) { DFS_AM(G, i); } } } int main() { int v; VexType c; AMGragh G; CreateAMGraph(G); print(G); cout << "请输入遍历连通图的起始点: "; cin >> c; v = locatevex(G, c);//查找顶点u的存储下标 if (v != -1) { cout << "深度优先搜索遍历连通图结果: " << endl; DFS_AM(G); } else { cout << "输入顶点信息错误!请重新输入!" << endl; } return 0; }
运行结果1
如图:
代码实现2—深度优先遍历 邻接表
//深度优先遍历 邻接表 #include <iostream> using namespace std; const int MaxVnum = 100;//顶点数最大值 bool visited[MaxVnum]; //访问标志数组，其初值为"false" typedef char VexType;//顶点的数据类型为字符型 typedef struct AdjNode { //定义邻接点类型 int v; //邻接点下标 struct AdjNode* next; //指向下一个邻接点 }AdjNode; typedef struct VexNode { //定义顶点类型 VexType data; // VexType为顶点的数据类型，根据需要定义 AdjNode* first; //指向第一个邻接点 }VexNode; typedef struct {//定义邻接表类型 VexNode Vex[MaxVnum]; int vexnum, edgenum; //顶点数，边数 }ALGragh; int locatevex(ALGragh G, VexType x) { for (int i = 0; i < G.vexnum; i++)//查找顶点信息的下标 if (x == G.Vex[i].data) return i; return -1;//没找到 } void insertedge(ALGragh& G, int i, int j)//插入一条边 { AdjNode* s; s = new AdjNode; s->v = j; s->next = G.Vex[i].first; G.Vex[i].first = s; } void printg(ALGragh G)//输出邻接表 { cout << "----------邻接表如下：----------" << endl; for (int i = 0; i < G.vexnum; i++) { AdjNode* t = G.Vex[i].first; cout << G.Vex[i].data << ": "; while (t != NULL) { cout << "---->"; cout << "[" << G.Vex[t->v].data << "]"; t = t->next; } cout << endl; } } void CreateALGraph(ALGragh& G)//创建无向图邻接表 { int i, j; VexType u, v; cout << "请输入顶点数和边数:" << endl; cin >> G.vexnum >> G.edgenum; cout << "请输入顶点信息:" << endl; for (i = 0; i < G.vexnum; i++)//输入顶点信息，存入顶点信息数组 cin >> G.Vex[i].data; for (i = 0; i < G.vexnum; i++) G.Vex[i].first = NULL; cout << "请依次输入每条边的两个顶点u,v" << endl; while (G.edgenum--) { cin >> u >> v; i = locatevex(G, u);//查找顶点u的存储下标 j = locatevex(G, v);//查找顶点v的存储下标 if (i != -1 && j != -1) { insertedge(G, i, j); //insertedge(G, j, i);//无向图多插入一条边 } else { cout << "输入顶点信息错！请重新输入！" << endl; G.edgenum++;//本次输入不算 } } } void DFS_AL(ALGragh G, int v)//基于邻接表的深度优先遍历 { int w; AdjNode* p;//辅助指针 cout << G.Vex[v].data << "\t"; visited[v] = true; p = G.Vex[v].first;//获取该顶点的第一个邻接点 while (p)//依次检查v的所有邻接点 { w = p->v;//w为v的邻接点. if (!visited[w])//w未被访问,则从w出发,递归深度优先遍历 { DFS_AL(G, w); } p = p->next; } } void DFS_AL(ALGragh G) //非连通图,基于邻接表的深度优先遍历 { for(int i = 0; i < G.vexnum; i++)//检查未被访问的点. if (!visited[i]) { DFS_AL(G, i); } } int main() { ALGragh G; int v; VexType c; CreateALGraph(G);//创建有向图邻接表 printg(G);//输出 cout << "请输入遍历连通图的起始点: "; cin >> c; v = locatevex(G, c); if (v != -1) { cout << "深度优先搜索遍历连通图结果: " << endl; DFS_AL(G, v); DFS_AL(G); } else { cout << "输入顶点信息错误!请重新输入!" << endl; } return 0; }
运行结果2
如图:
算法分析
基于邻接矩阵的DFS算法
查找每个顶点的邻接点需要O(n)时间，一共n个顶点，总的时间复杂度为O(n^2)，使用了一个递归工作栈，空间复杂度为O(n)。
基于邻接表的DFS算法
查找顶点vi的邻接点需要O(d(vi))时间，d(vi)为vi的出度（无向图为度），对有向图而言，所有顶点的出度之和等于边数e，对无向图而言，所有顶点的度之和等于2e，因此查找邻接点的时间复杂度为O(e)，加上初始化时间O(n)，总的时间复杂度为O(n+e)，(由于n和e大小未知,所以时间复杂度两者都涉及)使用了一个递归工作栈，空间复杂度为O(n)。
二.广度优先遍历
2.1介绍
广度优先搜索（Breadth First Search, BFS），又称宽度优先搜索，是最常见的图搜索方法之一。广度优先搜索是从某个顶点（源点）出发，一次性访问所有未被访问的邻接点，再依次从这些访问过的邻接点出发……似水中涟漪，一层层地传播开来.
举例
广度优先遍历秘籍：先被访问的顶点，其邻接点先被访问。
根据广度优先遍历秘籍，先来先服务，可以借助于队列实现。每个节点访问一次且只访问一次，因此可以设置一个辅助数组visited[i]=false，表示第i个顶点未访问；visited[i]=true，表示第i个顶点已访问。
代码实现1—广度优先遍历邻接矩阵
#include <iostream> #include <queue>//引入队列头文件 using namespace std; #define MaxVnum 100 //顶点数最大值 bool visited[MaxVnum]; //访问标志数组，其初值为"false" typedef char VexType; //顶点的数据类型，根据需要定义 typedef int EdgeType; //边上权值的数据类型，若不带权值的图，则为0或1 typedef struct { VexType Vex[MaxVnum]; EdgeType Edge[MaxVnum][MaxVnum]; int vexnum, edgenum; //顶点数，边数 }AMGragh; int locatevex(AMGragh G, VexType x) { for (int i = 0; i < G.vexnum; i++)//查找顶点信息的下标 if (x == G.Vex[i]) return i; return -1;//没找到 } void CreateAMGraph(AMGragh& G)//创建有向图的邻接矩阵 { int i, j; VexType u, v; cout << "请输入顶点数：" << endl; cin >> G.vexnum; cout << "请输入边数:" << endl; cin >> G.edgenum; cout << "请输入顶点信息:" << endl; for (int i = 0; i < G.vexnum; i++)//输入顶点信息，存入顶点信息数组 cin >> G.Vex[i]; for (int i = 0; i < G.vexnum; i++)//初始化邻接矩阵所有值为0，如果是网，则初始化邻接矩阵为无穷大 for (int j = 0; j < G.vexnum; j++) G.Edge[i][j] = 0; cout << "请输入每条边依附的两个顶点：" << endl; while (G.edgenum--) { cin >> u >> v; i = locatevex(G, u);//查找顶点u的存储下标 j = locatevex(G, v);//查找顶点v的存储下标 if (i != -1 && j != -1) G.Edge[i][j] = G.Edge[j][i] = 1; //邻接矩阵储置1，若无向图G.Edge[i][j]=G.Edge[j][i]=1 else { cout << "输入顶点信息错！请重新输入！" << endl; G.edgenum++;//本次输入不算 } } } void print(AMGragh G)//输出邻接矩阵 { cout << "图的邻接矩阵为：" << endl; for (int i = 0; i < G.vexnum; i++) { for (int j = 0; j < G.vexnum; j++) cout << G.Edge[i][j] << "\t"; cout << endl; } } void BFS_AM(AMGragh G, int v) { int u, w; queue<int> Q;//创建一个队列,里面存放节点的下标 cout << G.Vex[v] << "\t"; visited[v] = true; Q.push(v);//源点v入队 while (!Q.empty()) { u = Q.front();//取对头 Q.pop(); for (w = 0; w < G.vexnum; w++)//一次检查u的所有邻接点 { if (G.Edge[u][w] && !visited[w])//是邻接点但没有访问则进行访问 { cout << G.Vex[w] << "\t"; visited[w] = true; Q.push(w); } } } } void BFS_AM(AMGragh G){ for(int i = 0; i < G.vexnum; i++){ if(!visited[i]){ BFS_AM(G,i); } } } int main() { int v; VexType c; AMGragh G; CreateAMGraph(G); print(G); cout << "请输入遍历连通图的起始点: "; cin >> c; v = locatevex(G, c);//查找顶点u的存储下标 if (v != -1) { cout << "广度优先搜索遍历连通图结果: " << endl; BFS_AM(G, v); BFS_AM(G); } else { cout << "输入顶点信息错! 请重新输入!" << endl; } return 0; }
运行结果1
如图:
代码实现2—广度优先遍历邻接表
#include <iostream> #include <queue>//引入队列头文件 using namespace std; const int MaxVnum = 100;//顶点数最大值 bool visited[MaxVnum]; //访问标志数组，其初值为"false" typedef char VexType;//顶点的数据类型为字符型 typedef struct AdjNode { //定义邻接点类型 int v; //邻接点下标 struct AdjNode* next; //指向下一个邻接点 }AdjNode; typedef struct VexNode { //定义顶点类型 VexType data; // VexType为顶点的数据类型，根据需要定义 AdjNode* first; //指向第一个邻接点 }VexNode; typedef struct {//定义邻接表类型 VexNode Vex[MaxVnum]; int vexnum, edgenum; //顶点数，边数 }ALGragh; int locatevex(ALGragh G, VexType x) { for (int i = 0; i < G.vexnum; i++)//查找顶点信息的下标 if (x == G.Vex[i].data) return i; return -1;//没找到 } void insertedge(ALGragh& G, int i, int j)//插入一条边 { AdjNode* s; s = new AdjNode; s->v = j; s->next = G.Vex[i].first; G.Vex[i].first = s; } void printg(ALGragh G)//输出邻接表 { cout << "----------邻接表如下：----------" << endl; for (int i = 0; i < G.vexnum; i++) { AdjNode* t = G.Vex[i].first; cout << G.Vex[i].data << ": "; while (t != NULL) { cout << "---->"; cout << "[" << G.Vex[t->v].data << "]"; t = t->next; } cout << endl; } } void CreateALGraph(ALGragh& G)//创建有向图邻接表 { int i, j; VexType u, v; cout << "请输入顶点数和边数:" << endl; cin >> G.vexnum >> G.edgenum; cout << "请输入顶点信息:" << endl; for (i = 0; i < G.vexnum; i++)//输入顶点信息，存入顶点信息数组 cin >> G.Vex[i].data; for (i = 0; i < G.vexnum; i++) G.Vex[i].first = NULL; cout << "请依次输入每条边的两个顶点u,v" << endl; while (G.edgenum--) { cin >> u >> v; i = locatevex(G, u);//查找顶点u的存储下标 j = locatevex(G, v);//查找顶点v的存储下标 if (i != -1 && j != -1) insertedge(G, i, j); else { cout << "输入顶点信息错！请重新输入！" << endl; G.edgenum++;//本次输入不算 } } } void BFS_AL(ALGragh G, int v)//基于邻接表的广度优先遍历 { int u, w; AdjNode* p; queue<int> Q; cout << G.Vex[v].data << "\t"; visited[v] = true; Q.push(v); while (!Q.empty()) { u = Q.front();//取对头元素 Q.pop(); p = G.Vex[u].first; while (p) { w = p->v; if (!visited[w])//w未被访问 { cout << G.Vex[w].data << "\t"; visited[w] = true; Q.push(w); } p = p->next; } } } void BFS_AL(ALGragh G)//非连通图,基于邻接表的广度优先遍历 { for (int i = 0; i < G.vexnum; i++)//查漏点. { if (!visited[i])//未被访问则进行访问 { BFS_AL(G, i); } } } int main() { ALGragh G; int v; VexType c; CreateALGraph(G);//创建有向邻接表 printg(G);//输出 cout << "请输入遍历连通图的起始点: "; cin >> c; v = locatevex(G, c);//查找顶点u的存储下标 if (v != -1) { cout << "广度优先搜索遍历连通图结构: " << endl; BFS_AL(G, v); BFS_AL(G); } else { cout << "输入顶点错!请重新输入!" << endl; } return 0; }
运行结果2
如图:
算法分析
基于邻接矩阵的BFS算法
查找每个顶点的邻接点需要O(n)时间，一共n个顶点，总的时间复杂度为O(n^2)，使用了一个辅助队列，最坏的情况下每个顶点入队一次(访问完就入队)，空间复杂度为O(n)。
基于邻接表的BFS算法
查找顶点vi的邻接点需要O(d(vi))时间，d(vi)为vi的出度（无向图为度），对有向图而言，所有顶点的出度之和等于边数e，对无向图而言，所有顶点的度之和等于2e，因此查找邻接点的时间复杂度为O(e)，加上初始化时间O(n)，总的时间复杂度为O(n+e)，使用了一个辅助队列，最坏的情况下每个顶点入队一次，空间复杂度为O(n)。
总结
容易发现,广度优先和深度优先的算法效率基本相同,在实际应用中要根据需要合理选择.
需要注意的是，一个图的邻接矩阵是唯一的，因此基于邻接矩阵的BFS或DFS遍历序列也是唯一的。而图的邻接表不是唯一的，边的输入顺序不同，正序或逆序建表都会影响邻接表的邻接点顺序，因此基于邻接表的BFS或DFS遍历序列不是唯一的。
