数据结构——图的深度（DFS）和广度优先所搜遍历（BFS)

使用邻接矩阵和邻接表结构存储图。输入或存储一个无向图，根据一个初始顶点，输出图的深度和广度优先搜索遍历路径。 代码片.

//-------邻接矩阵（数组）存储表示------- void DFSTraverse_Matrix(MatrixGraph G, int v) {//深度优先搜索遍历-递归 printf("%c", G.vexs[v]); visited[v] = true; for (int i = 0; i < G.vexnum; i++) { if (G.arcs[v][i].adj != 0 && !visited[i]) {//adj!=0说明v i之间有连接，并且若第i点没被访问过 //继续进行递归 printf("-->"); DFSTraverse_Matrix(G, i); } } } void DFS_Matrix(MatrixGraph G, char V0) {//深度优先搜索遍历函数入口 int v = LocateMatrixVex(G, V0); for (int i = 0; i < MAX_VERTEX_NUM; i++) {//visited数组初始化，初始状态都未访问； visited[i] = false; } DFSTraverse_Matrix(G, v); printf("\n"); //以下循环为查找为确保与V0不连通的点也能被访问 for (int i = 0; i < G.vexnum; i++) { if (visited[i] == false) { DFSTraverse_Matrix(G, i); printf("\n"); } } printf("\n"); } /* 邻接矩阵的广度优先搜索遍历 */ void BFS_Matrix(MatrixGraph & G, char V0) { int v = LocateMatrixVex(G, V0); for (int i = 0; i < G.vexnum; i++) //visited[MAX_VERTEX_NUM]初始化 { visited[i] = false; } for (int i = 0; i < G.vexnum; i++) { char u, w, V0; if (i == 0) { V0 = G.vexs[v]; v = LocateMatrixVex(G, V0); } else if (visited[i]) { continue; } else { V0 = G.vexs[i]; v = LocateMatrixVex(G, V0); } queue<char> q; printf("%c", V0); visited[v] = true; q.push(V0); while (!q.empty()) { u = q.front(); v = LocateMatrixVex(G, u); q.pop(); for (int i = 0; i < G.vexnum; i++) { w = G.vexs[i]; if (G.arcs[v][i].adj != 0 && !visited[i]) { printf("-->%c", w); q.push(w); visited[i] = true; } } } printf("\n"); } printf("\n"); }

代码片

//-------邻接表存储表示------- //（算法与邻接矩阵存储一致） void DFSTraverse_List(ListGraph G, int v) {//深度优先搜索遍历-递归 int w; printf("%c", G.vertices[v].data); visited[v] = true; ArcNode * p = new ArcNode; p = G.vertices[v].firstarc; while (p) { w = p->adjvex; if (!visited[w]) { printf("-->"); DFSTraverse_List(G, w); } p = p->nextarc; } } void DFS_List(ListGraph G, char V0) {//邻接表深度优先搜索遍历函数入口 int v = LocateListVex(G, V0); for (int i = 0; i < G.vexnum; i++) { if (i == 0) { DFSTraverse_List(G, v); printf("\n"); } else if (i != 0 && !visited[i]) { DFSTraverse_List(G, i); printf("\n"); } } } //邻接表的广度优先搜索遍历 int BFS_List(ListGraph G, char V0) { int v = LocateListVex(G, V0); for (int i = 0; i < MAX_VERTEX_NUM; i++) { visited[i] = false; } for (int i = 0; i < G.vexnum; i++) { if (i != 0 && !visited[i]) v = i; else if (visited[i]) { continue; } int u, w; char V0 = G.vertices[v].data; queue<char> q; printf("%c", V0);//打印顶点v0 v = LocateListVex(G, V0); //找到v0对应的下标 visited[v] = true;//顶点v0已被访问 q.push(V0);//将顶点v0入队 ArcNode * p = new ArcNode; while (!q.empty()) { u = q.front();//将顶点元素u出队，开始访问u的所有邻接点 v = LocateListVex(G, u);//得到顶点u的对应下标 q.pop();//将顶点u出队 for (p = G.vertices[v].firstarc; p; p = p->nextarc)//遍历顶点u的邻接点 { w = p->adjvex; if (!visited[w])//顶点p未被访问 { printf("-->%c", G.vertices[w].data); //打印顶点p visited[w] = 1; //顶点p已被访问 q.push(G.vertices[w].data);//将顶点p入队 } } } printf("\n"); } return 0; }

完整代码

代码片

文件Graph.h #pragma once #ifndef _GRAPH_H_ #define _GRAPH_H_ #define MAX_VERTEX_NUM 20 //最大顶点个数 #define MAX_ARC_NUM 190 //最大边数 #define MAX_NUM (~(0x1<<31))//最大值 #define ERROR -1 #define OK 0 #include <stdio.h> #include <queue> using namespace std; //bool visited[MAX_VERTEX_NUM]; typedef int VRType; typedef int InfoType; typedef char VertexType; typedef enum { DG, DN, UDG, UDN } GraphKind; using namespace std; typedef struct ArcCell {//弧的定义 VRType adj; //对无权图，用1和0表示相邻否；对带权图，则为全职类型 InfoType* info; //该弧相关信息的指针 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; //顶点向量 AdjMatrix arcs; //邻接矩阵 int vexnum, arcnum; //顶点数和弧数 GraphKind kind; //图的类型 }MatrixGraph; typedef struct ArcNode {//邻接表顶点 int adjvex; ArcNode * nextarc; InfoType * info; }ArcNode; typedef struct VexNode {//邻接表顶点列表 VertexType data; ArcNode *firstarc; }VexNode, AdjList[MAX_VERTEX_NUM]; typedef struct {//图的邻接表形式 int vexnum, arcnum; GraphKind kind; AdjList vertices; }ListGraph; typedef struct {//Prim——记录数组 VertexType adjvex; VRType lowcost; }CLOSEDGE[MAX_VERTEX_NUM]; typedef struct {//带权图边集 VertexType v1, v2; VRType info; }Edge, Edges[MAX_ARC_NUM]; /* 邻接矩阵相关函数 */ int LocateMatrixVex(MatrixGraph G, VertexType V);//定位点V在G中的位置 int CreatMatrixUDG(MatrixGraph & G);//创建无向图 int CreatMatrixUDN(MatrixGraph & G);//创建无向网 void DFSTraverse_Matrix(MatrixGraph G, int v);//深度优先遍历（递归） void DFS_Matrix(MatrixGraph G, char V0);//深度优先遍历入口 void BFS_Matrix(MatrixGraph & G, char V0);//广度优先遍历 //MatrixGraph CreatTestMatrixUDN(MatrixGraph & G); //供测试使用的无向网（已删除） //MatrixGraph CreatTestMatrixUDG(MatrixGraph & G); //供测试使用的无向图 /* 邻接表相关函数 */ int LocateListVex(ListGraph G, VertexType V); //定位点V在G中位置 int CreatListUDG(ListGraph & G); //创建无向图 int CreatListUDN(ListGraph & G, Edges & edge); //创建无向网 //int CreatTestListUDG(ListGraph & G); //创建供测试的无向图（已删除） void DFSTraverse_List(ListGraph G, int v); //深度优先遍历（递归） void DFS_List(ListGraph G, char V0); //深度优先遍历函数入口 int BFS_List(ListGraph G, char V0); //广度优先遍历 #endif // !_GRAPH_H_

代码片

#include "stdafx.h" #include "Graph.h" bool visited[MAX_VERTEX_NUM] = { false }; //定位点在图中的位置 int LocateMatrixVex(MatrixGraph G, VertexType V) { for (int i = 0; i < G.vexnum; i++) { if (V == G.vexs[i]) return i; } return ERROR; } //创建无向图 int CreatMatrixUDG(MatrixGraph & G) { char c; VertexType V1, V2; G.kind = UDN; printf("请输入无向图的顶点数和弧数：（例： 2 3）\n"); scanf("%d %d", &G.vexnum, &G.arcnum); while ((c = getchar()) != '\n'&&c != EOF); for (int i = 0; i < G.vexnum; i++) { printf("请输入第%d个顶点的符号：\n", i + 1); scanf("%c", &G.vexs[i]); while ((c = getchar()) != '\n'&&c != EOF); //清楚输入缓存 } //矩阵的初始化 for (int i = 0; i < G.vexnum; i++) { for (int j = 0; j < G.vexnum; j++) { G.arcs[i][j].adj = 0; G.arcs[i][j].info = NULL; } } printf("请输入有连接的点：（例如：A B）\n"); for (int i = 0, j, k; i < G.arcnum; i++) { printf("第%d对连接点：", i + 1); scanf("%c %c", &V1, &V2); while ((c = getchar()) != '\n'&&c != EOF); j = LocateMatrixVex(G, V1); //获取矩阵下标 k = LocateMatrixVex(G, V2); G.arcs[j][k].adj = 1; //修改矩阵值 G.arcs[k][j].adj = G.arcs[j][k].adj; //无向图矩阵为对称矩阵 } return OK; } //创建无向有权图 int CreatMatrixUDN(MatrixGraph & G) { char c; VertexType V1, V2; G.kind = UDN; printf("请输入无向图的顶点数和弧数：（例： 2 3）\n"); scanf("%d %d", &G.vexnum, &G.arcnum); while ((c = getchar()) != '\n'&&c != EOF); for (int i = 0; i < G.vexnum; i++) { printf("请输入第%d个顶点的符号：\n", i + 1); scanf("%c", &G.vexs[i]); while ((c = getchar()) != '\n'&&c != EOF); //清楚输入缓存 } //矩阵的初始化 for (int i = 0; i < G.vexnum; i++) { for (int j = 0; j < G.vexnum; j++) { G.arcs[i][j].adj = 0; G.arcs[i][j].info = NULL; } } printf("请输入有连接的点以及两点之间的权值：（例如：A B 5）\n"); for (int i = 0, j, k; i < G.arcnum; i++) { int adj = 0; printf("第%d对连接点：", i + 1); scanf("%c %c %d", &V1, &V2, &adj); while ((c = getchar()) != '\n'&&c != EOF); j = LocateMatrixVex(G, V1); //获取矩阵下标 k = LocateMatrixVex(G, V2); G.arcs[j][k].adj = adj; //修改矩阵值 G.arcs[k][j].adj = G.arcs[j][k].adj; //无向图矩阵为对称矩阵 } return OK; } //深度优先搜索遍历 //对结点是否被访问进行记录，初始状态都未访问； void DFSTraverse_Matrix(MatrixGraph G, int v) { printf("%c", G.vexs[v]); visited[v] = true; for (int i = 0; i < G.vexnum; i++) { if (G.arcs[v][i].adj != 0 && visited[i] == false) { printf("-->"); DFSTraverse_Matrix(G, i); } } } void DFS_Matrix(MatrixGraph G, char V0) { int v = LocateMatrixVex(G, V0); for (int i = 0; i < MAX_VERTEX_NUM; i++) {//visited数组初始化，初始状态都未访问； visited[i] = false; } DFSTraverse_Matrix(G, v); printf("\n"); for (int i = 0; i < G.vexnum; i++) { if (visited[i] == false) { DFSTraverse_Matrix(G, i); printf("\n"); } } printf("\n"); } /* 邻接矩阵的广度优先搜索遍历 */ void BFS_Matrix(MatrixGraph & G, char V0) { int v = LocateMatrixVex(G, V0); for (int i = 0; i < G.vexnum; i++) //visited[MAX_VERTEX_NUM]初始化 { visited[i] = false; } for (int i = 0; i < G.vexnum; i++) { char u, w, V0; if (i == 0) { V0 = G.vexs[v]; v = LocateMatrixVex(G, V0); } else if (visited[i]) { continue; } else { V0 = G.vexs[i]; v = LocateMatrixVex(G, V0); } queue<char> q; printf("%c", V0); visited[v] = true; q.push(V0); while (!q.empty()) { u = q.front(); v = LocateMatrixVex(G, u); q.pop(); for (int i = 0; i < G.vexnum; i++) { w = G.vexs[i]; if (G.arcs[v][i].adj != 0 && !visited[i]) { printf("-->%c", w); q.push(w); visited[i] = true; } } } printf("\n"); } printf("\n"); } //查找V点图中的位置 int LocateListVex(ListGraph G, VertexType V) { for (int i = 0; i < G.vexnum; i++) { if (G.vertices[i].data == V) return i; } return ERROR; } //创建邻接表 int CreatListUDG(ListGraph & G) { int c, j, k; VertexType V1, V2; G.kind = UDG; printf("请输入图的顶点数和边数：（例如：3 2）\n"); scanf("%d %d", &G.vexnum, &G.arcnum); while ((c = getchar()) != '\n'&&c != EOF); for (int i = 0; i < G.vexnum; i++) { printf("请输入第%d个顶点\n", i + 1); scanf("%c", &G.vertices[i].data); while ((c = getchar()) != '\n'&&c != EOF); G.vertices[i].firstarc = NULL; } for (int i = 0; i < G.arcnum; i++) { printf("请输入第%d条弧的两端顶点：（例如：A B)\n", i + 1); scanf("%c %c", &V1, &V2); while ((c = getchar()) != '\n'&&c != EOF); k = LocateListVex(G, V1); //找到顶点i的下标 j = LocateListVex(G, V2); //找到顶点j的下标 ArcNode *p1 = new ArcNode; //创建一个边结点*p1 p1->adjvex = j; //其邻接点域为j p1->nextarc = G.vertices[k].firstarc; G.vertices[k].firstarc = p1; // 将新结点*p插入到顶点v1的边表头部 ArcNode *p2 = new ArcNode;//另一对 p2->adjvex = k; p2->nextarc = G.vertices[j].firstarc; G.vertices[j].firstarc = p2; } return 0; } int CreatListUDN(ListGraph & G, Edges & edge) { int c, j, k; VRType n; VertexType V1, V2; G.kind = UDN; printf("请输入图的顶点数和边数：（例如：3 2）\n"); scanf("%d %d", &G.vexnum, &G.arcnum); while ((c = getchar()) != '\n'&&c != EOF); for (int i = 0; i < G.vexnum; i++) { printf("请输入第%d个顶点\n", i + 1); scanf("%c", &G.vertices[i].data); while ((c = getchar()) != '\n'&&c != EOF); G.vertices[i].firstarc = NULL; } for (int i = 0; i < G.arcnum; i++) { printf("请输入第%d条边的两端顶点以及边的权值：（例如：A B 5)\n", i + 1); scanf("%c %c %d", &V1, &V2, &n); while ((c = getchar()) != '\n'&&c != EOF); edge[i]= { V1, V2, n }; k = LocateListVex(G, V1); //找到顶点i的下标 j = LocateListVex(G, V2); //找到顶点j的下标 ArcNode *p1 = new ArcNode; //创建一个边结点*p1 p1->adjvex = j; //其邻接点域为j p1->nextarc = G.vertices[k].firstarc; p1->info = &n; //权值 G.vertices[k].firstarc = p1; // 将新结点*p插入到顶点v1的边表头部 ArcNode *p2 = new ArcNode;//另一对 p2->adjvex = k; p2->nextarc = G.vertices[j].firstarc; p2->info = &n; G.vertices[j].firstarc = p2; } return OK; } //邻接表的深度优先搜索 void DFSTraverse_List(ListGraph G, int v) { int w; printf("%c", G.vertices[v].data); visited[v] = true; ArcNode * p = new ArcNode; p = G.vertices[v].firstarc; while (p) { w = p->adjvex; if (!visited[w]) { printf("-->"); DFSTraverse_List(G, w); } p = p->nextarc; } } void DFS_List(ListGraph G, char V0) { int v = LocateListVex(G, V0); for (int i = 0; i < G.vexnum; i++) { if (i == 0) { DFSTraverse_List(G, v); printf("\n"); } else if (i != 0 && !visited[i]) { DFSTraverse_List(G, i); printf("\n"); } } } //邻接表的广度优先搜索遍历 int BFS_List(ListGraph G, char V0) { int v = LocateListVex(G, V0); for (int i = 0; i < MAX_VERTEX_NUM; i++) { visited[i] = false; } for (int i = 0; i < G.vexnum; i++) { if (i != 0 && !visited[i]) v = i; else if (visited[i]) { continue; } int u, w; char V0 = G.vertices[v].data; queue<char> q; printf("%c", V0);//打印顶点v0 v = LocateListVex(G, V0); //找到v0对应的下标 visited[v] = true;//顶点v0已被访问 q.push(V0);//将顶点v0入队 ArcNode * p = new ArcNode; while (!q.empty()) { u = q.front();//将顶点元素u出队，开始访问u的所有邻接点 v = LocateListVex(G, u);//得到顶点u的对应下标 q.pop();//将顶点u出队 for (p = G.vertices[v].firstarc; p; p = p->nextarc)//遍历顶点u的邻接点 { w = p->adjvex; if (!visited[w])//顶点p未被访问 { printf("-->%c", G.vertices[w].data); //打印顶点p visited[w] = 1; //顶点p已被访问 q.push(G.vertices[w].data);//将顶点p入队 } } } printf("\n"); } return 0; }

代码片

文件：main.cpp // main.cpp: 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <stdlib.h> #include "Graph.h" #include "MinCostSpanTree.h" int main() { int switch_on, c; printf("********输出图的深度搜索遍历和广度搜索遍历********\n"); printf("1、使用邻接矩阵（数组）存储图；\n"); printf("2、使用邻接表存储图；\n"); printf("3、图的最小生成树——Prim算法；\n"); printf("4、图的最小生成树——Kruscal算法；\n"); printf("请输入选项："); scanf("%d", &switch_on); while ((c = getchar()) != '\n'&&c != EOF); switch (switch_on) { case 1: { MatrixGraph G; char i; CreatMatrixUDG(G); //G = CreatTestUDNraph(G); printf("请输入初始点：\n"); scanf("%c", &i); while ((c = getchar()) != '\n'&&c != EOF); printf("深度优先搜素遍历结果：\n"); DFS_Matrix(G, i); printf("广度优先搜索遍历结果：\n"); BFS_Matrix(G, i); break; } case 2: { char i; ListGraph G; CreatListUDG(G); printf("请输入初始点：\n"); scanf("%c", &i); while ((c = getchar()) != '\n'&&c != EOF); printf("深度优先搜索遍历结果：\n"); DFS_List(G, i); printf("\n广度优先搜索遍历结果：\n"); BFS_List(G, i); break; } default: break; } system("pause"); return 0; } //测试数据如下图输入