您的位置:首页 > 文旅 > 美景 > 《数据结构(C语言版)第二版》第六章-图(6.5 图的遍历)

《数据结构(C语言版)第二版》第六章-图(6.5 图的遍历)

2024/12/23 11:01:38 来源:https://blog.csdn.net/qq_44883214/article/details/141201530  浏览:    关键词:《数据结构(C语言版)第二版》第六章-图(6.5 图的遍历)

6.5.1 深度优先搜索(递归)

算法6.3 采用邻接多重表 深度优先搜索遍历连通图(一定是无向的)

//算法6.3 深度优先搜索遍历连通图#include <stdio.h>
#include <stdlib.h>#define MAX_VERTEX_NUM  20bool visited[MAX_VERTEX_NUM];
//标记某个顶点是否被访问过。数组中初值均为 "false",如果被访问过,则置其相应的分量为 "true"typedef enum { Eunvisited, Evisited } EVisitIf;  //标记某条边edge是否被搜索过
typedef int InfoType;   //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
typedef char VerTexType;  //假设顶点的数据类型为字符型typedef struct EBox
{EVisitIf mark;   //mark为标志域,可用以标记该条边是否被搜索过int ivex;int jvex;struct EBox* ilink;struct EBox* jlink;InfoType* info;
}EBox;typedef struct VexBox
{VerTexType data;EBox* firstedge;
}VexBox;typedef struct
{VexBox adjmulist[MAX_VERTEX_NUM];  //表头向量int vexnum;  //顶点总数int edgenum;  //总边数
}AMLGraph;  //图的信息void CreateAMLGraph(AMLGraph& G);
int LocateVex(AMLGraph& G, VerTexType v);
void printAMLGraph(AMLGraph& G);
void DFS(AMLGraph G, int i);
int FirstAdjVex(AMLGraph G, int i);
int NextAdjVex(AMLGraph G, int i, int w);int main()
{AMLGraph G = { {'\0',NULL,NULL}, 0,0 };CreateAMLGraph(G);printAMLGraph(G);printf("\n从第一个顶点开始,图的深度优先搜索遍历序列为:");DFS(G, 1);return 0;
}//采用邻接多重表表示法创建无向图
void CreateAMLGraph(AMLGraph& G)
{int i = 0;int j = 0;int k = 0;VerTexType v1 = 0;VerTexType v2 = 0;EBox* p1 = NULL;printf("请输入无向图的总顶点数:");scanf_s(" %d", &G.vexnum);printf("请输入无向图的总边数:");scanf_s(" %d", &G.edgenum);for (i = 0; i < G.vexnum; ++i){printf("请输入第%d个顶点的值:", i + 1);scanf_s(" %c", &(G.adjmulist[i].data));G.adjmulist[i].firstedge = NULL;}for (k = 0; k < G.edgenum; k++){printf("请输入第%d条弧依附的两个顶点(用空格间隔,输入结束后按回车): ", k + 1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));i = LocateVex(G, v1);j = LocateVex(G, v2);p1 = (EBox*)malloc(sizeof(EBox));p1->ivex = i;p1->jvex = j;p1->ilink = G.adjmulist[i].firstedge;G.adjmulist[i].firstedge = p1;p1->jlink = G.adjmulist[j].firstedge;G.adjmulist[j].firstedge = p1;}
}//在G的顶点表adjmulist中获取字符v的下标(数组G.xlist的下标从0开始)
int LocateVex(AMLGraph& G, VerTexType v)
{int i = 0;for (i = 0; i < G.vexnum && (G.adjmulist[i].data != v); ++i){;}return i;
}//打印邻接多重表
void printAMLGraph(AMLGraph& G)
{int i = 0;EBox* pMove = NULL;for (i = 0; i < G.vexnum; i++){printf("\n第%d个顶点为:%c", i + 1, G.adjmulist[i].data);pMove = G.adjmulist[i].firstedge;if (pMove){printf("\n与第%d个顶点相邻接的每个顶点在图中的位置数为:", i + 1);while (pMove){if (pMove->ivex == i){printf("%d ", pMove->jvex+1);pMove = pMove->ilink;}else if (pMove->jvex == i){printf("%d ", pMove->ivex+1);pMove = pMove->jlink;}}}else{printf("\n没有与第%d个顶点相邻接的顶点。", i + 1);}}
}//从第i个顶点出发,递归地深度优先遍历连通图G
void DFS(AMLGraph G, int i)
{printf("%c ", G.adjmulist[i - 1].data);visited[i - 1] = true;int w = 0;for (w = FirstAdjVex(G, i); w >= 0; w = NextAdjVex(G, i, w+1)){if (!visited[w]){DFS(G, w + 1);}}
}//查找第i个顶点的第一个邻接点下标
int FirstAdjVex(AMLGraph G, int i)
{EBox* p = G.adjmulist[i-1].firstedge;if (p){if (i-1 == p->ivex){return p->jvex;}else if(i-1 == p->jvex){return p->ivex;}else{return -1;}}else{return -1;}
}//查找第i个顶点相对于 第w个顶点 邻接点的下一个邻接点的下标
int NextAdjVex(AMLGraph G, int i, int w)
{EBox* p = G.adjmulist[i - 1].firstedge;// 寻找当前边while (p){if ((i - 1 == p->ivex && w - 1 == p->jvex) || (i - 1 == p->jvex && w - 1 == p->ivex))break;p = (i - 1 == p->ivex) ? p->ilink : p->jlink;//注意 if 及 p向后移动 的命令顺序}if (!p)return -1; // 如果没有找到当前边则返回 -1// 移动到下一个边p = (i - 1 == p->ivex) ? p->ilink : p->jlink;// 查找下一个邻接顶点if (p){if (i - 1 == p->ivex)return p->jvex;else if (i - 1 == p->jvex)return p->ivex;}return -1; // 如果没有找到下一个邻接顶点则返回 -1
}

在这里插入图片描述
在这里插入图片描述

不改变图中每个顶点的命名方式,也不改变图的边(每条边的起终点),仅改变边的输入次序时:
因为图中的顶点没变,边也没变,每个顶点及其边表中的内容不会发生变化。
但图的邻接多重表中每个顶点后面边结点排序方式会发生变化,从而会导致 图的深度优先搜索遍历 序列 发生改变。
但是 顶点总数量 不会变。

在这里插入图片描述

在这里插入图片描述

//从第i个顶点出发,递归地深度优先遍历连通图G
void DFS(AMLGraph G, int i)
{printf("\n\n%c \n", G.adjmulist[i - 1].data);visited[i - 1] = true;printf("\nvisited[%d] = true ", i);int w = 0;printf("\nFirstAdjVex(G, i) : FirstAdjVex(G, %d) = %d: ", i, FirstAdjVex(G, i)+1);for (w = FirstAdjVex(G, i); w >= 0; w = NextAdjVex(G, i, w + 1)){printf("\ni = %d", i);printf("\nw = %d", w+1);  printf("\nvisited[%d] = %d ", w + 1, visited[w]);printf("\nNextAdjVex(G, i, w): NextAdjVex(G, %d, %d) = %d", i, w + 1, NextAdjVex(G, i, w + 1)+1);if (!visited[w]){printf("\nif语句中:visited[%d] = false ", w+1);printf("\nif语句中:DFS(G, w) : DFS(G, %d) ", w + 1);DFS(G, w + 1);printf("\nif语句中:i = %d", i);printf("\nif语句中:w = %d", w);}}
}

算法6.4 采用邻接多重表 深度优先搜索遍历非连通图(一定是无向的)

//算法6.4 深度优先搜索遍历非连通图#include <stdio.h>
#include <stdlib.h>#define MAX_VERTEX_NUM  20bool visited[MAX_VERTEX_NUM];
//标记某个顶点是否被访问过。数组中初值均为 "false",如果被访问过,则置其相应的分量为 "true"typedef enum { Eunvisited, Evisited } EVisitIf;  //标记某条边edge是否被搜索过
typedef int InfoType;   //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
typedef char VerTexType;  //假设顶点的数据类型为字符型typedef struct EBox
{EVisitIf mark;   //mark为标志域,可用以标记该条边是否被搜索过int ivex;int jvex;struct EBox* ilink;struct EBox* jlink;InfoType* info;
}EBox;typedef struct VexBox
{VerTexType data;EBox* firstedge;
}VexBox;typedef struct
{VexBox adjmulist[MAX_VERTEX_NUM];  //表头向量int vexnum;  //顶点总数int edgenum;  //总边数
}AMLGraph;  //图的信息void CreateAMLGraph(AMLGraph& G);
int LocateVex(AMLGraph& G, VerTexType v);
void printAMLGraph(AMLGraph& G);
void DFS(AMLGraph G, int i);
int FirstAdjVex(AMLGraph G, int i);
int NextAdjVex(AMLGraph G, int i, int w);
void DFSTraverse(AMLGraph G);int main()
{AMLGraph G = { {'\0',NULL,NULL}, 0,0 };int i = 0;int j = 0;CreateAMLGraph(G);printAMLGraph(G);printf("\n");for (i = 0; i < G.vexnum; i++){printf("\n从第%d个顶点开始,采用邻接多重表表示的", i + 1);DFSTraverse(G);//将visited数组初始化(重置visited数组)for (j = 0; j < G.vexnum; j++){visited[j] = false;}}return 0;
}//采用邻接多重表表示法创建无向图
void CreateAMLGraph(AMLGraph& G)
{int i = 0;int j = 0;int k = 0;VerTexType v1 = 0;VerTexType v2 = 0;EBox* p1 = NULL;printf("请输入无向图的总顶点数:");scanf_s(" %d", &G.vexnum);printf("请输入无向图的总边数:");scanf_s(" %d", &G.edgenum);for (i = 0; i < G.vexnum; ++i){printf("请输入第%d个顶点的值:", i + 1);scanf_s(" %c", &(G.adjmulist[i].data));G.adjmulist[i].firstedge = NULL;}for (k = 0; k < G.edgenum; k++){printf("请输入第%d条边依附的两个顶点(用空格间隔,输入结束后按回车): ", k + 1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));i = LocateVex(G, v1);j = LocateVex(G, v2);p1 = (EBox*)malloc(sizeof(EBox));p1->ivex = i;p1->jvex = j;p1->ilink = G.adjmulist[i].firstedge;G.adjmulist[i].firstedge = p1;p1->jlink = G.adjmulist[j].firstedge;G.adjmulist[j].firstedge = p1;}
}//在G的顶点表adjmulist中获取字符v的下标(数组G.xlist的下标从0开始)
int LocateVex(AMLGraph& G, VerTexType v)
{int i = 0;for (i = 0; i < G.vexnum && (G.adjmulist[i].data != v); ++i){;}return i;
}//打印邻接多重表
void printAMLGraph(AMLGraph& G)
{int i = 0;EBox* pMove = NULL;for (i = 0; i < G.vexnum; i++){printf("\n第%d个顶点为:%c", i + 1, G.adjmulist[i].data);pMove = G.adjmulist[i].firstedge;if (pMove){printf("\n与第%d个顶点相邻接的每个顶点为:", i + 1);while (pMove){if (pMove->ivex == i){printf("%c ", G.adjmulist[pMove->jvex].data);pMove = pMove->ilink;}else if (pMove->jvex == i){printf("%c ", G.adjmulist[pMove->ivex].data);pMove = pMove->jlink;}}}else{printf("\n没有与第%d个顶点相邻接的顶点。", i + 1);}}
}//从第i个顶点出发,递归地深度优先遍历连通图G
void DFS(AMLGraph G, int i)
{printf("%c ", G.adjmulist[i - 1].data);visited[i - 1] = true;int w = 0;for (w = FirstAdjVex(G, i); w >= 0; w = NextAdjVex(G, i, w + 1)){if (!visited[w]){DFS(G, w + 1);}}
}//查找第i个顶点的第一个邻接点下标
int FirstAdjVex(AMLGraph G, int i)
{EBox* p = G.adjmulist[i - 1].firstedge;if (p){if (i - 1 == p->ivex){return p->jvex;}else if (i - 1 == p->jvex){return p->ivex;}else{return -1;}}else{return -1;}
}//查找第i个顶点相对于 第w个顶点 邻接点的下一个邻接点的下标
int NextAdjVex(AMLGraph G, int i, int w)
{EBox* p = G.adjmulist[i - 1].firstedge;// 寻找当前边while (p){if ((i - 1 == p->ivex && w - 1 == p->jvex) || (i - 1 == p->jvex && w - 1 == p->ivex))break;p = (i - 1 == p->ivex) ? p->ilink : p->jlink;//注意 if 及 p向后移动 的命令顺序}if (!p)return -1; // 如果没有找到当前边则返回 -1// 移动到下一个边p = (i - 1 == p->ivex) ? p->ilink : p->jlink;// 查找下一个邻接顶点if (p){if (i - 1 == p->ivex)return p->jvex;else if (i - 1 == p->jvex)return p->ivex;}return -1; // 如果没有找到下一个邻接顶点则返回 -1
}//算法6.4 深度优先搜索遍历非连通图
void DFSTraverse(AMLGraph G)
{int v = 0;for (v = 0; v < G.vexnum; ++v){visited[v] = false;}printf("非连通图G的深度优先搜索遍历序列为:");for (v = 0; v < G.vexnum; ++v){if (!visited[v]){DFS(G, v+1);}}
}

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

算法6.5 采用邻接矩阵表示图的深度优先搜索遍历(无向图、有向图均适用)

此处仅以无向图为例(连通图和非连通图也都适用)。
(若为有向图时,构造邻接矩阵的方式会发生变化)

//算法 6.5 采用邻接矩阵表示图的深度优先搜索遍历#include <stdio.h>
#include <stdlib.h>#define MaxInt 32767
#define MVNum 100bool visited[MVNum];
//标记某个顶点是否被访问过。数组中初值均为 "false",如果被访问过,则置其相应的分量为 "true"typedef char VerTexType;
typedef int ArcType;typedef struct
{VerTexType vexs[MVNum];ArcType arcs[MVNum][MVNum];int vexnum;int arcnum;
}AMGraph;void CreateUDG(AMGraph& G);
int LocateVex(AMGraph& G, VerTexType v);
void printfAMGraph(AMGraph& G);
void DFS_AM(AMGraph G, int v);int main()
{AMGraph G = { {'\0'}, {0}, 0, 0 };int i = 0;int j = 0;CreateUDG(G);printfAMGraph(G);printf("\n");for (i = 0; i < G.vexnum; i++){printf("\n从第%d个顶点开始,采用邻接矩阵表示图的深度优先搜索遍历序列为:",i+1);DFS_AM(G, i+1);//将visited数组初始化(重置visited数组)for (j = 0; j < G.vexnum; j++){visited[j] = false;}}return 0;
}//采用邻接矩阵表示法创建无向图
void CreateUDG(AMGraph& G)
{int i = 0;int j = 0;int k = 0;VerTexType v1 = '\0';VerTexType v2 = '\0';ArcType w = 0;printf("请输入无向图的总顶点数:");scanf_s(" %d", &G.vexnum);printf("请输入无向图的总边数:");scanf_s(" %d", &G.arcnum);for (i = 0; i < G.vexnum; ++i){printf("请输入第%d个顶点储存的元素:", i + 1);scanf_s(" %c", &G.vexs[i], sizeof(VerTexType));}//初始化邻接矩阵,将边的权值均置为0for (i = 0; i < G.vexnum; ++i){for (j = 0; j < G.vexnum; ++j){G.arcs[i][j] = 0;}}//构造邻接矩阵for (k = 0; k < G.arcnum; ++k){printf("请输入第%d条边依附的两个顶点(用空格间隔,输入结束后按回车) : ", k + 1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));i = LocateVex(G, v1);j = LocateVex(G, v2);G.arcs[i][j] = 1;  //存在的边权值均为1G.arcs[j][i] = G.arcs[i][j];}
}//在G的顶点表vexs中获取字符v的下标(数组G.vexs的下标从0开始)
int LocateVex(AMGraph& G, VerTexType v)
{int i = 0;for (i = 0; i < G.vexnum && (G.vexs[i] != v); ++i){;}return i;
}//打印邻接矩阵表示法中的顶点表vexs和邻接矩阵arcs
void printfAMGraph(AMGraph& G)
{int i = 0;int j = 0;printf("各顶点为:");for (i = 0; i < G.vexnum; i++){printf("%c ", G.vexs[i]);}printf("\n邻接矩阵为:\n");for (i = 0; i < G.vexnum; i++){for (j = 0; j < G.vexnum; j++){if (G.arcs[i][j] == 32767){printf("%d  ", G.arcs[i][j]);}else{printf("%d      ", G.arcs[i][j]);}}printf("\n");}
}//算法 6.5 采用邻接矩阵表示图的深度优先搜索遍历
void DFS_AM(AMGraph G, int v)
{printf("%c ", G.vexs[v-1]);visited[v - 1] = true;int w = 0;for (w = 0; w < G.vexnum; w++){if ((G.arcs[v - 1][w] != 0) && (!visited[w])){DFS_AM(G, w+1);}}
}

在这里插入图片描述
在这里插入图片描述

算法6.6 采用邻接表表示图的深度优先搜索遍历(无向图、有向图均适用)

此处仅以无向图为例(连通图和非连通图也都适用)。
(若为有向图时,构造邻接表的方式会发生变化)

//算法6.6 采用邻接表表示图的深度优先搜索遍历#include <stdio.h>
#include <stdlib.h>#define MVNum 100bool visited[MVNum];
//标记某个顶点是否被访问过。数组中初值均为 "false",如果被访问过,则置其相应的分量为 "true"typedef int OtherInfo;   //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
typedef char VerTexType;  //假设顶点的数据类型为字符型typedef struct ArcNode
{int adjvex;struct ArcNode* nextarc;OtherInfo info;
}ArcNode;  //边结点typedef struct VNode
{VerTexType data;ArcNode* firstarc;
}VNode, AdjList[MVNum];  //表头结点typedef struct
{AdjList vertices;  //存储所有顶点int vexnum;  //顶点总数int arcnum;  //总边数
}ALGraph;  //图的信息void CreateUDG(ALGraph& G);
int LocateVex(ALGraph& G, VerTexType v);
void printALGraph(ALGraph& G);
void DFS_AL(ALGraph G, int v);int main()
{ALGraph G = { {'\0',NULL}, 0,0 };int i = 0;int j = 0;CreateUDG(G);printALGraph(G);printf("\n");for (i = 0; i < G.vexnum; i++){printf("\n从第%d个顶点开始,采用邻接矩阵表示图的深度优先搜索遍历序列为:", i + 1);DFS_AL(G, i + 1);//将visited数组初始化(重置visited数组)for (j = 0; j < G.vexnum; j++){visited[j] = false;}}return 0;
}void CreateUDG(ALGraph& G)
{int i = 0;int k = 0;VerTexType v1 = 0;VerTexType v2 = 0;int j = 0;ArcNode* p1 = NULL;ArcNode* p2 = NULL;printf("请输入无向图的总顶点数:");scanf_s(" %d", &G.vexnum);printf("请输入无向图的总边数:");scanf_s(" %d", &G.arcnum);for (i = 0; i < G.vexnum; ++i){printf("请输入第%d个顶点的值:", i + 1);scanf_s(" %c", &(G.vertices[i].data));G.vertices[i].firstarc = NULL;   //初始化}for (k = 0; k < G.arcnum; k++){printf("请输入第%d条边依附的两个顶点(用空格间隔,输入结束后按回车): ", k + 1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));i = LocateVex(G, v1);j = LocateVex(G, v2);p1 = (ArcNode*)malloc(sizeof(ArcNode));p1->adjvex = j;p1->nextarc = G.vertices[i].firstarc;G.vertices[i].firstarc = p1;  //将新结点*p1插入顶点Vi的边表头部p2 = (ArcNode*)malloc(sizeof(ArcNode));p2->adjvex = i;p2->nextarc = G.vertices[j].firstarc;G.vertices[j].firstarc = p2;  //将与*p1对称的新的边结点*p2插入顶点Vj的边表头部}
}//在G的顶点表vexs中获取字符v的下标(数组G.vexs的下标从0开始)
int LocateVex(ALGraph& G, VerTexType v)
{int i = 0;for (i = 0; i < G.vexnum && (G.vertices[i].data != v); ++i){;}return i;
}//打印邻接表
void printALGraph(ALGraph& G)
{int i = 0;ArcNode* pMove = NULL;for (i = 0; i < G.vexnum; i++){printf("\n第%d个顶点为:%c", i + 1, G.vertices[i].data);pMove = G.vertices[i].firstarc;if (pMove){printf("\n与第%d个顶点相邻接的每个顶点在图中的位置(下标值)为:", i + 1);while (pMove){printf("%d ", pMove->adjvex);pMove = pMove->nextarc;}}else{printf("\n没有与第%d个顶点相邻接的顶点。", i + 1);}}
}//算法6.6 采用邻接表表示图的深度优先搜索遍历
void DFS_AL(ALGraph G, int v)
{printf("%c ", G.vertices[v - 1].data);visited[v-1] = true;ArcNode *p = G.vertices[v - 1].firstarc;int w = 0;while (p != NULL){w = p->adjvex;if (!visited[w]){DFS_AL(G, w + 1);}p = p->nextarc;}
}
//算法6.6 第二种写法//算法6.6 采用邻接表表示图的深度优先搜索遍历
void DFS_AL(ALGraph G, int v)
{printf("%c ", G.vertices[v - 1].data);visited[v - 1] = true;ArcNode* w = NULL;int m = 0;for (w = G.vertices[v - 1].firstarc; w != NULL; w = w->nextarc){m = w->adjvex;if (!(visited[m])){DFS_AL(G, m + 1);}}
}

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

6.5.2 广度优先搜索(非递归,队列)

算法6.7 采用邻接多重表 广度优先搜索遍历连通图(一定是无向的)

//算法6.7 广度优先搜索遍历连通图#include <stdio.h>
#include <stdlib.h>#define MAX_VERTEX_NUM  20bool visited[MAX_VERTEX_NUM];
//标记某个顶点是否被访问过。数组中初值均为 "false",如果被访问过,则置其相应的分量为 "true"typedef enum { Eunvisited, Evisited } EVisitIf;  //标记某条边edge是否被搜索过
typedef int InfoType;   //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
typedef char VerTexType;  //假设顶点的数据类型为字符型typedef struct EBox
{EVisitIf mark;   //mark为标志域,可用以标记该条边是否被搜索过int ivex;int jvex;struct EBox* ilink;struct EBox* jlink;InfoType* info;
}EBox;typedef struct VexBox
{VerTexType data;EBox* firstedge;
}VexBox;typedef struct
{VexBox adjmulist[MAX_VERTEX_NUM];  //表头向量int vexnum;  //顶点总数int edgenum;  //总边数
}AMLGraph;  //图的信息typedef struct QNode
{int data; //因为每个顶点后面还跟着边的链表,因此队列中只保存顶点的位置数struct QNode* next;
}QNode, * QNodeptr;typedef struct
{QNodeptr front;QNodeptr rear;
}LinkQueue;  //链队void CreateAMLGraph(AMLGraph& G);
int LocateVex(AMLGraph& G, VerTexType v);
void printAMLGraph(AMLGraph& G);
void InitQueue(LinkQueue& Q);
void EnQueue(LinkQueue& Q, int e);
int DeQueue(LinkQueue& Q);
int EmptyQueue(LinkQueue& Q);
void BFS(AMLGraph G, int i);
int FirstAdjVex(AMLGraph G, int i);
int NextAdjVex(AMLGraph G, int i, int w);int main()
{AMLGraph G = { {'\0',NULL,NULL}, 0,0 };int i = 0;int j = 0;CreateAMLGraph(G);printAMLGraph(G);for (i = 0; i < G.vexnum; i++){printf("\n从第%d个顶点开始,采用邻接多重表表示图的广度优先搜索遍历序列为:", i + 1);BFS(G, i + 1);//将visited数组初始化(重置visited数组)for (j = 0; j < G.vexnum; j++){visited[j] = false;}}return 0;
}//采用邻接多重表表示法创建无向图
void CreateAMLGraph(AMLGraph& G)
{int i = 0;int j = 0;int k = 0;VerTexType v1 = 0;VerTexType v2 = 0;EBox* p1 = NULL;printf("请输入无向图的总顶点数:");scanf_s(" %d", &G.vexnum);printf("请输入无向图的总边数:");scanf_s(" %d", &G.edgenum);for (i = 0; i < G.vexnum; ++i){printf("请输入第%d个顶点的值:", i + 1);scanf_s(" %c", &(G.adjmulist[i].data));G.adjmulist[i].firstedge = NULL;}for (k = 0; k < G.edgenum; k++){printf("请输入第%d条边依附的两个顶点(用空格间隔,输入结束后按回车): ", k + 1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));i = LocateVex(G, v1);j = LocateVex(G, v2);p1 = (EBox*)malloc(sizeof(EBox));p1->ivex = i;p1->jvex = j;p1->ilink = G.adjmulist[i].firstedge;G.adjmulist[i].firstedge = p1;p1->jlink = G.adjmulist[j].firstedge;G.adjmulist[j].firstedge = p1;}
}//在G的顶点表adjmulist中获取字符v的下标(数组G.xlist的下标从0开始)
int LocateVex(AMLGraph& G, VerTexType v)
{int i = 0;for (i = 0; i < G.vexnum && (G.adjmulist[i].data != v); ++i){;}return i;
}//打印邻接多重表
void printAMLGraph(AMLGraph& G)
{int i = 0;EBox* pMove = NULL;for (i = 0; i < G.vexnum; i++){printf("\n第%d个顶点为:%c", i + 1, G.adjmulist[i].data);pMove = G.adjmulist[i].firstedge;if (pMove){printf("\n与第%d个顶点相邻接的每个顶点在图中的位置数为:", i + 1);while (pMove){if (pMove->ivex == i){printf("%d ", pMove->jvex + 1);pMove = pMove->ilink;}else if (pMove->jvex == i){printf("%d ", pMove->ivex + 1);pMove = pMove->jlink;}}}else{printf("\n没有与第%d个顶点相邻接的顶点。", i + 1);}}
}//初始化链队
void InitQueue(LinkQueue& Q)
{Q.front = (QNodeptr)malloc(sizeof(QNode));if (!Q.front){printf("初始化链队时,内存分配失败。\n");return;}Q.rear = Q.front;Q.front->next = NULL;
}//入队
void EnQueue(LinkQueue& Q, int e)
{QNodeptr p = (QNodeptr)malloc(sizeof(QNode));if (!p){printf("元素入队时,新结点内存分配失败。\n");return;}p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;
}//出队
int DeQueue(LinkQueue& Q)
{if (EmptyQueue(Q)){printf("元素出队时,链队为空。\n");return 0;}QNodeptr p = Q.front->next;int e = p->data;Q.front->next = p->next;if (p == Q.rear){Q.rear = Q.front;}free(p);p = NULL;return e;
}//判空
int EmptyQueue(LinkQueue& Q)
{if (Q.front == Q.rear){return 1;}else{return 0;}
}//从第i个顶点出发,非递归地广度优先遍历连通图G
void BFS(AMLGraph G, int i)
{VerTexType e = G.adjmulist[i - 1].data;printf("%c ", e);visited[i - 1] = true;LinkQueue Q = { NULL,NULL };int u = 0;int w = 0;InitQueue(Q);EnQueue(Q, i);while (!EmptyQueue(Q)){u = DeQueue(Q);  //第一次while循环中:u是队头,即efor (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w + 1)){if (!visited[w]){e = G.adjmulist[w].data;printf("%c ", e);visited[w] = true;EnQueue(Q, w+1);}}}
}//查找第i个顶点的第一个邻接点下标
int FirstAdjVex(AMLGraph G, int i)
{EBox* p = G.adjmulist[i - 1].firstedge;if (p){if (i - 1 == p->ivex){return p->jvex;}else if (i - 1 == p->jvex){return p->ivex;}else{return -1;}}else{return -1;}
}//查找第i个顶点相对于 第w个顶点 邻接点的下一个邻接点的下标
int NextAdjVex(AMLGraph G, int i, int w)
{EBox* p = G.adjmulist[i - 1].firstedge;// 寻找当前边while (p){if ((i - 1 == p->ivex && w - 1 == p->jvex) || (i - 1 == p->jvex && w - 1 == p->ivex))break;p = (i - 1 == p->ivex) ? p->ilink : p->jlink;//注意 if 及 p向后移动 的命令顺序}if (!p)return -1; // 如果没有找到当前边则返回 -1// 移动到下一个边p = (i - 1 == p->ivex) ? p->ilink : p->jlink;// 查找下一个邻接顶点if (p){if (i - 1 == p->ivex)return p->jvex;else if (i - 1 == p->jvex)return p->ivex;}return -1; // 如果没有找到下一个邻接顶点则返回 -1
}

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

//从第i个顶点出发,非递归地广度优先遍历连通图G
void BFS(AMLGraph G, int i)
{VerTexType e = G.adjmulist[i - 1].data;printf("\n\n%c \n", e);visited[i - 1] = true;printf("\nvisited[%d] = true ", i);LinkQueue Q = { NULL,NULL };int u = '\0';int w = 0;InitQueue(Q);EnQueue(Q, i);while (!EmptyQueue(Q)){u = DeQueue(Q);  //第一次while循环中:u是队头,即iprintf("\nu = %d ", u);printf("\nFirstAdjVex(G, u) : FirstAdjVex(G, %d) = %d: ", u, FirstAdjVex(G, u) + 1);for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w + 1)){printf("\nu = %d", u);printf("\nw = %d", w + 1);printf("\nvisited[%d] = %d ", w + 1, visited[w]);printf("\nNextAdjVex(G, u, w): NextAdjVex(G, %d, %d) = %d", u, w + 1, NextAdjVex(G, u, w + 1) + 1);if (!visited[w]){e = G.adjmulist[w].data;printf("\n\n%c \n", e);visited[w] = true;EnQueue(Q, w+1);}}}
}

采用邻接多重表 广度优先搜索遍历非连通图(一定是无向的)

//广度优先搜索遍历非连通图#include <stdio.h>
#include <stdlib.h>#define MAX_VERTEX_NUM  20bool visited[MAX_VERTEX_NUM];
//标记某个顶点是否被访问过。数组中初值均为 "false",如果被访问过,则置其相应的分量为 "true"typedef enum { Eunvisited, Evisited } EVisitIf;  //标记某条边edge是否被搜索过
typedef int InfoType;   //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
typedef char VerTexType;  //假设顶点的数据类型为字符型typedef struct EBox
{EVisitIf mark;   //mark为标志域,可用以标记该条边是否被搜索过int ivex;int jvex;struct EBox* ilink;struct EBox* jlink;InfoType* info;
}EBox;typedef struct VexBox
{VerTexType data;EBox* firstedge;
}VexBox;typedef struct
{VexBox adjmulist[MAX_VERTEX_NUM];  //表头向量int vexnum;  //顶点总数int edgenum;  //总边数
}AMLGraph;  //图的信息typedef struct QNode
{VerTexType data; //因为每个顶点后面还跟着边的链表,因此队列中只保存顶点存储的信息struct QNode* next;
}QNode, * QNodeptr;typedef struct
{QNodeptr front;QNodeptr rear;
}LinkQueue;  //链队void CreateAMLGraph(AMLGraph& G);
int LocateVex(AMLGraph& G, VerTexType v);
void printAMLGraph(AMLGraph& G);
void InitQueue(LinkQueue& Q);
void EnQueue(LinkQueue& Q, VerTexType e);
VerTexType DeQueue(LinkQueue& Q);
int EmptyQueue(LinkQueue& Q);
void BFS(AMLGraph G, int i);
int FirstAdjVex(AMLGraph G, int i);
int NextAdjVex(AMLGraph G, int i, int w);
void BFSTraverse(AMLGraph G);int main()
{AMLGraph G = { {'\0',NULL,NULL}, 0,0 };int i = 0;int j = 0;CreateAMLGraph(G);printAMLGraph(G);printf("\n");for (i = 0; i < G.vexnum; i++){printf("\n从第%d个顶点开始,采用邻接多重表表示的", i + 1);BFSTraverse(G);//将visited数组初始化(重置visited数组)for (j = 0; j < G.vexnum; j++){visited[j] = false;}}return 0;
}//采用邻接多重表表示法创建无向图
void CreateAMLGraph(AMLGraph& G)
{int i = 0;int j = 0;int k = 0;VerTexType v1 = 0;VerTexType v2 = 0;EBox* p1 = NULL;printf("请输入无向图的总顶点数:");scanf_s(" %d", &G.vexnum);printf("请输入无向图的总边数:");scanf_s(" %d", &G.edgenum);for (i = 0; i < G.vexnum; ++i){printf("请输入第%d个顶点的值:", i + 1);scanf_s(" %c", &(G.adjmulist[i].data));G.adjmulist[i].firstedge = NULL;}for (k = 0; k < G.edgenum; k++){printf("请输入第%d条边依附的两个顶点(用空格间隔,输入结束后按回车): ", k + 1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));i = LocateVex(G, v1);j = LocateVex(G, v2);p1 = (EBox*)malloc(sizeof(EBox));p1->ivex = i;p1->jvex = j;p1->ilink = G.adjmulist[i].firstedge;G.adjmulist[i].firstedge = p1;p1->jlink = G.adjmulist[j].firstedge;G.adjmulist[j].firstedge = p1;}
}//在G的顶点表adjmulist中获取字符v的下标(数组G.xlist的下标从0开始)
int LocateVex(AMLGraph& G, VerTexType v)
{int i = 0;for (i = 0; i < G.vexnum && (G.adjmulist[i].data != v); ++i){;}return i;
}//打印邻接多重表
void printAMLGraph(AMLGraph& G)
{int i = 0;EBox* pMove = NULL;for (i = 0; i < G.vexnum; i++){printf("\n第%d个顶点为:%c", i + 1, G.adjmulist[i].data);pMove = G.adjmulist[i].firstedge;if (pMove){printf("\n与第%d个顶点相邻接的每个顶点在图中的位置数为:", i + 1);while (pMove){if (pMove->ivex == i){printf("%c ", G.adjmulist[pMove->jvex].data);pMove = pMove->ilink;}else if (pMove->jvex == i){printf("%c ", G.adjmulist[pMove->ivex].data);pMove = pMove->jlink;}}}else{printf("\n没有与第%d个顶点相邻接的顶点。", i + 1);}}
}//初始化链队
void InitQueue(LinkQueue& Q)
{Q.front = (QNodeptr)malloc(sizeof(QNode));if (!Q.front){printf("初始化链队时,内存分配失败。\n");return;}Q.rear = Q.front;Q.front->next = NULL;
}//入队
void EnQueue(LinkQueue& Q, VerTexType e)
{QNodeptr p = (QNodeptr)malloc(sizeof(QNode));if (!p){printf("元素入队时,新结点内存分配失败。\n");return;}p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;
}//出队
VerTexType DeQueue(LinkQueue& Q)
{if (EmptyQueue(Q)){printf("元素出队时,链队为空。\n");return '\0';}QNodeptr p = Q.front->next;VerTexType e = p->data;Q.front->next = p->next;if (p == Q.rear){Q.rear = Q.front;}free(p);p = NULL;return e;
}//判空
int EmptyQueue(LinkQueue& Q)
{if (Q.front == Q.rear){return 1;}else{return 0;}
}//从第i个顶点出发,非递归地广度优先遍历连通图G
//可如连通图中,修改队列的存储元素类型为位置数,相应地本算法中的变量j即可去掉。
void BFS(AMLGraph G, int i)
{VerTexType e = G.adjmulist[i - 1].data;printf("%c ", e);visited[i - 1] = true;LinkQueue Q = { NULL,NULL };VerTexType u = '\0';int w = 0;int j = 0;InitQueue(Q);EnQueue(Q, e);while (!EmptyQueue(Q)){u = DeQueue(Q);  //第一次while循环中:u是队头,即ej = LocateVex(G, u);  //第一次while循环中:u即e,e的下标是i-1,即j就是i-1for (w = FirstAdjVex(G, j+1); w >= 0; w = NextAdjVex(G, j+1, w + 1)){if (!visited[w]){e = G.adjmulist[w].data;printf("%c ", e);visited[w] = true;EnQueue(Q, e);}}}
}//查找第i个顶点的第一个邻接点下标
int FirstAdjVex(AMLGraph G, int i)
{EBox* p = G.adjmulist[i - 1].firstedge;if (p){if (i - 1 == p->ivex){return p->jvex;}else if (i - 1 == p->jvex){return p->ivex;}else{return -1;}}else{return -1;}
}//查找第i个顶点相对于 第w个顶点 邻接点的下一个邻接点的下标
int NextAdjVex(AMLGraph G, int i, int w)
{EBox* p = G.adjmulist[i - 1].firstedge;// 寻找当前边while (p){if ((i - 1 == p->ivex && w - 1 == p->jvex) || (i - 1 == p->jvex && w - 1 == p->ivex))break;p = (i - 1 == p->ivex) ? p->ilink : p->jlink;//注意 if 及 p向后移动 的命令顺序}if (!p)return -1; // 如果没有找到当前边则返回 -1// 移动到下一个边p = (i - 1 == p->ivex) ? p->ilink : p->jlink;// 查找下一个邻接顶点if (p){if (i - 1 == p->ivex)return p->jvex;else if (i - 1 == p->jvex)return p->ivex;}return -1; // 如果没有找到下一个邻接顶点则返回 -1
}//广度优先搜索遍历非连通图
void BFSTraverse(AMLGraph G)
{int v = 0;for (v = 0; v < G.vexnum; ++v){visited[v] = false;}printf("非连通图G的广度优先搜索遍历序列为:");for (v = 0; v < G.vexnum; ++v){if (!visited[v]){BFS(G, v + 1);}}
}

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

采用邻接矩阵表示图的广度优先搜索遍历(无向图、有向图均适用)

此处仅以无向图为例(连通图和非连通图也都适用)。
(若为有向图时,构造邻接矩阵的方式会发生变化)

//采用邻接矩阵表示图的广度优先搜索遍历#include <stdio.h>
#include <stdlib.h>#define MaxInt 32767
#define MVNum 100bool visited[MVNum];
//标记某个顶点是否被访问过。数组中初值均为 "false",如果被访问过,则置其相应的分量为 "true"typedef char VerTexType;
typedef int ArcType;typedef struct
{VerTexType vexs[MVNum];ArcType arcs[MVNum][MVNum];int vexnum;int arcnum;
}AMGraph;typedef struct QNode
{VerTexType data; //因为每个顶点后面还跟着边的链表,因此队列中只保存顶点存储的信息struct QNode* next;
}QNode, * QNodeptr;typedef struct
{QNodeptr front;QNodeptr rear;
}LinkQueue;  //链队void CreateUDG(AMGraph& G);
int LocateVex(AMGraph& G, VerTexType v);
void printfAMGraph(AMGraph& G);
void InitQueue(LinkQueue& Q);
void EnQueue(LinkQueue& Q, VerTexType e);
VerTexType DeQueue(LinkQueue& Q);
int EmptyQueue(LinkQueue& Q);
void BFS_AM(AMGraph G, int v);int main()
{AMGraph G = { {'\0'}, {0}, 0, 0 };int i = 0;int j = 0;CreateUDG(G);printfAMGraph(G);printf("\n");for (i = 0; i < G.vexnum; i++){printf("\n从第%d个顶点开始,采用邻接矩阵表示图的广度优先搜索遍历序列为:", i + 1);BFS_AM(G, i + 1);//将visited数组初始化(重置visited数组)for (j = 0; j < G.vexnum; j++){visited[j] = false;}}return 0;
}//采用邻接矩阵表示法创建无向图
void CreateUDG(AMGraph& G)
{int i = 0;int j = 0;int k = 0;VerTexType v1 = '\0';VerTexType v2 = '\0';ArcType w = 0;printf("请输入无向图的总顶点数:");scanf_s(" %d", &G.vexnum);printf("请输入无向图的总边数:");scanf_s(" %d", &G.arcnum);for (i = 0; i < G.vexnum; ++i){printf("请输入第%d个顶点储存的元素:", i + 1);scanf_s(" %c", &G.vexs[i], sizeof(VerTexType));}//初始化邻接矩阵,将边的权值均置为0for (i = 0; i < G.vexnum; ++i){for (j = 0; j < G.vexnum; ++j){G.arcs[i][j] = 0;}}//构造邻接矩阵for (k = 0; k < G.arcnum; ++k){printf("请输入第%d条边依附的两个顶点(用空格间隔,输入结束后按回车) : ", k + 1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));i = LocateVex(G, v1);j = LocateVex(G, v2);G.arcs[i][j] = 1;  //存在的边权值均为1G.arcs[j][i] = G.arcs[i][j];}
}//在G的顶点表vexs中获取字符v的下标(数组G.vexs的下标从0开始)
int LocateVex(AMGraph& G, VerTexType v)
{int i = 0;for (i = 0; i < G.vexnum && (G.vexs[i] != v); ++i){;}return i;
}//打印邻接矩阵表示法中的顶点表vexs和邻接矩阵arcs
void printfAMGraph(AMGraph& G)
{int i = 0;int j = 0;printf("各顶点为:");for (i = 0; i < G.vexnum; i++){printf("%c ", G.vexs[i]);}printf("\n邻接矩阵为:\n");for (i = 0; i < G.vexnum; i++){for (j = 0; j < G.vexnum; j++){if (G.arcs[i][j] == 32767){printf("%d  ", G.arcs[i][j]);}else{printf("%d      ", G.arcs[i][j]);}}printf("\n");}
}//初始化链队
void InitQueue(LinkQueue& Q)
{Q.front = (QNodeptr)malloc(sizeof(QNode));if (!Q.front){printf("初始化链队时,内存分配失败。\n");return;}Q.rear = Q.front;Q.front->next = NULL;
}//入队
void EnQueue(LinkQueue& Q, VerTexType e)
{QNodeptr p = (QNodeptr)malloc(sizeof(QNode));if (!p){printf("元素入队时,新结点内存分配失败。\n");return;}p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;
}//出队
VerTexType DeQueue(LinkQueue& Q)
{if (EmptyQueue(Q)){printf("元素出队时,链队为空。\n");return '\0';}QNodeptr p = Q.front->next;VerTexType e = p->data;Q.front->next = p->next;if (p == Q.rear){Q.rear = Q.front;}free(p);p = NULL;return e;
}//判空
int EmptyQueue(LinkQueue& Q)
{if (Q.front == Q.rear){return 1;}else{return 0;}
}//从第i个顶点出发,非递归地广度优先遍历图G
//采用邻接矩阵表示图的广度优先搜索遍历
//可如连通图中,修改队列的存储元素类型为位置数,相应地本算法中的变量j即可去掉。
void BFS_AM(AMGraph G, int i)
{VerTexType e = G.vexs[i - 1];printf("%c ", e);visited[i - 1] = true;LinkQueue Q = { NULL,NULL };VerTexType u = '\0';int w = 0;int j = 0;InitQueue(Q);EnQueue(Q, e);while (!EmptyQueue(Q)){u = DeQueue(Q);  //第一次while循环中:u是队头,即ej = LocateVex(G, u);  //第一次while循环中:u即e,e的下标是i-1,即j就是i-1for (w = 0; w <G.vexnum; w++){if ((G.arcs[j][w] != 0) && (!visited[w])){e = G.vexs[w];printf("%c ", e);visited[w] = true;EnQueue(Q, e);}}}
}

在这里插入图片描述
在这里插入图片描述

采用邻接表表示图的广度优先搜索遍历(无向图、有向图均适用)

此处仅以无向图为例(连通图和非连通图也都适用)。
(若为有向图时,构造邻接表的方式会发生变化)

//采用邻接表表示图的广度优先搜索遍历#include <stdio.h>
#include <stdlib.h>#define MVNum 100bool visited[MVNum];
//标记某个顶点是否被访问过。数组中初值均为 "false",如果被访问过,则置其相应的分量为 "true"typedef int OtherInfo;   //假设在边结点中的数据域存储边的权值,且边的权值类型为整型
typedef char VerTexType;  //假设顶点的数据类型为字符型typedef struct ArcNode
{int adjvex;struct ArcNode* nextarc;OtherInfo info;
}ArcNode;  //边结点typedef struct VNode
{VerTexType data;ArcNode* firstarc;
}VNode, AdjList[MVNum];  //表头结点typedef struct
{AdjList vertices;  //存储所有顶点int vexnum;  //顶点总数int arcnum;  //总边数
}ALGraph;  //图的信息typedef struct QNode
{VerTexType data; //因为每个顶点后面还跟着边的链表,因此队列中只保存顶点存储的信息struct QNode* next;
}QNode, * QNodeptr;typedef struct
{QNodeptr front;QNodeptr rear;
}LinkQueue;  //链队void CreateUDG(ALGraph& G);
int LocateVex(ALGraph& G, VerTexType v);
void printALGraph(ALGraph& G);
void InitQueue(LinkQueue& Q);
void EnQueue(LinkQueue& Q, VerTexType e);
VerTexType DeQueue(LinkQueue& Q);
int EmptyQueue(LinkQueue& Q);
void BFS_AL(ALGraph G, int i);int main()
{ALGraph G = { {'\0',NULL}, 0,0 };int i = 0;int j = 0;CreateUDG(G);printALGraph(G);printf("\n");for (i = 0; i < G.vexnum; i++){printf("\n从第%d个顶点开始,采用邻接表表示图的广度优先搜索遍历序列为:", i + 1);BFS_AL(G, i + 1);//将visited数组初始化(重置visited数组)for (j = 0; j < G.vexnum; j++){visited[j] = false;}}return 0;
}void CreateUDG(ALGraph& G)
{int i = 0;int k = 0;VerTexType v1 = 0;VerTexType v2 = 0;int j = 0;ArcNode* p1 = NULL;ArcNode* p2 = NULL;printf("请输入无向图的总顶点数:");scanf_s(" %d", &G.vexnum);printf("请输入无向图的总边数:");scanf_s(" %d", &G.arcnum);for (i = 0; i < G.vexnum; ++i){printf("请输入第%d个顶点的值:", i + 1);scanf_s(" %c", &(G.vertices[i].data));G.vertices[i].firstarc = NULL;   //初始化}for (k = 0; k < G.arcnum; k++){printf("请输入第%d条边依附的两个顶点(用空格间隔,输入结束后按回车): ", k + 1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));i = LocateVex(G, v1);j = LocateVex(G, v2);p1 = (ArcNode*)malloc(sizeof(ArcNode));p1->adjvex = j;p1->nextarc = G.vertices[i].firstarc;G.vertices[i].firstarc = p1;  //将新结点*p1插入顶点Vi的边表头部p2 = (ArcNode*)malloc(sizeof(ArcNode));p2->adjvex = i;p2->nextarc = G.vertices[j].firstarc;G.vertices[j].firstarc = p2;  //将与*p1对称的新的边结点*p2插入顶点Vj的边表头部}
}//在G的顶点表vexs中获取字符v的下标(数组G.vexs的下标从0开始)
int LocateVex(ALGraph& G, VerTexType v)
{int i = 0;for (i = 0; i < G.vexnum && (G.vertices[i].data != v); ++i){;}return i;
}//打印邻接表
void printALGraph(ALGraph& G)
{int i = 0;ArcNode* pMove = NULL;for (i = 0; i < G.vexnum; i++){printf("\n第%d个顶点为:%c", i + 1, G.vertices[i].data);pMove = G.vertices[i].firstarc;if (pMove){printf("\n与第%d个顶点相邻接的每个顶点在图中的位置(下标值)为:", i + 1);while (pMove){printf("%d ", pMove->adjvex);pMove = pMove->nextarc;}}else{printf("\n没有与第%d个顶点相邻接的顶点。", i + 1);}}
}//初始化链队
void InitQueue(LinkQueue& Q)
{Q.front = (QNodeptr)malloc(sizeof(QNode));if (!Q.front){printf("初始化链队时,内存分配失败。\n");return;}Q.rear = Q.front;Q.front->next = NULL;
}//入队
void EnQueue(LinkQueue& Q, VerTexType e)
{QNodeptr p = (QNodeptr)malloc(sizeof(QNode));if (!p){printf("元素入队时,新结点内存分配失败。\n");return;}p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;
}//出队
VerTexType DeQueue(LinkQueue& Q)
{if (EmptyQueue(Q)){printf("元素出队时,链队为空。\n");return '\0';}QNodeptr p = Q.front->next;VerTexType e = p->data;Q.front->next = p->next;if (p == Q.rear){Q.rear = Q.front;}free(p);p = NULL;return e;
}//判空
int EmptyQueue(LinkQueue& Q)
{if (Q.front == Q.rear){return 1;}else{return 0;}
}//从第i个顶点出发,非递归地广度优先遍历图G
//采用邻接表表示图的广度优先搜索遍历
//可如连通图中,修改队列的存储元素类型为位置数,相应地本算法中的变量j即可去掉。
void BFS_AL(ALGraph G, int i)
{VerTexType e = G.vertices[i - 1].data;printf("%c ", e);visited[i - 1] = true;LinkQueue Q = { NULL,NULL };VerTexType u = '\0';ArcNode* w = NULL;int j = 0;int m = 0;InitQueue(Q);EnQueue(Q, e);while (!EmptyQueue(Q)){u = DeQueue(Q);  //第一次while循环中:u是队头,即ej = LocateVex(G, u);  //第一次while循环中:u即e,e的下标是i-1,即j就是i-1for (w = G.vertices[j].firstarc; w != NULL; w = w->nextarc){m = w->adjvex;if ((!visited[m])){e = G.vertices[m].data;printf("%c ", e);visited[m] = true;EnQueue(Q, e);}}}
}
//BFS_AL第二种写法//从第i个顶点出发,非递归地广度优先遍历图G
//采用邻接表表示图的广度优先搜索遍历
//可如连通图中,修改队列的存储元素类型为位置数,相应地本算法中的变量j即可去掉。
void BFS_AL(ALGraph G, int i)
{VerTexType e = G.vertices[i - 1].data;printf("%c ", e);visited[i - 1] = true;LinkQueue Q = { NULL,NULL };VerTexType u = '\0';ArcNode* p = NULL;int j = 0;int w = 0;InitQueue(Q);EnQueue(Q, e);while (!EmptyQueue(Q)){u = DeQueue(Q);  //第一次while循环中:u是队头,即ej = LocateVex(G, u);  //第一次while循环中:u即e,e的下标是i-1,即j就是i-1p = G.vertices[j].firstarc;while (p){w = p->adjvex;if ((!visited[w])){e = G.vertices[w].data;printf("%c ", e);visited[w] = true;EnQueue(Q, e);}p = p->nextarc;}}
}

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com