用C语言编程编写一个可运行的代码实现图的遍历算法1、采用邻接表存储结构创建一个图;2、编程实现图的深度优先搜索或广度优先搜索遍历算法3、输出遍历结果;4、给定具体数据调试程序。
下面是使用C语言编写的一个图的深度优先搜索遍历算法的示例代码:
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
// 邻接表中的边结点
typedef struct EdgeNode {
int adjvex; // 邻接点的下标
struct EdgeNode *next; // 指向下一个邻接点的指针
} EdgeNode;
// 邻接表中的顶点结点
typedef struct VertexNode {
int data; // 顶点的数据
EdgeNode *firstEdge; // 指向第一个邻接点的指针
} VertexNode;
// 图的邻接表结构
typedef struct {
VertexNode adjList[MAX_VERTEX_NUM]; // 邻接表
int numVertexes; // 顶点数
int numEdges; // 边数
} Graph;
// 初始化图
void initGraph(Graph *G) {
printf("请输入图的顶点数和边数:");
scanf("%d %d", &(G->numVertexes), &(G->numEdges));
getchar(); // 读取换行符
// 初始化邻接表
for (int i = 0; i < G->numVertexes; i++) {
printf("请输入第 %d 个顶点的数据:", i + 1);
scanf("%d", &(G->adjList[i].data));
G->adjList[i].firstEdge = NULL;
}
// 建立边表
int v1, v2;
for (int k = 0; k < G->numEdges; k++) {
printf("请输入第 %d 条边的两个顶点的序号(从1开始):", k + 1);
scanf("%d %d", &v1, &v2);
// 创建边结点
EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex = v2 - 1;
e->next = G->adjList[v1 - 1].firstEdge;
G->adjList[v1 - 1].firstEdge = e;
// 如果是无向图,还需要创建反向的边结点
e = (EdgeNode *)malloc(sizeof(EdgeNode));
e->adjvex = v1 - 1;
e->next = G->adjList[v2 - 1].firstEdge;
G->adjList[v2 - 1].firstEdge = e;
}
}
// 深度优先搜索遍历算法
void DFS(Graph G, int v, int visited[]) {
visited[v] = 1; // 标记该顶点已访问
printf("%d ", G.adjList[v].data);
EdgeNode *p = G.adjList[v].firstEdge;
while (p) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex, visited);
}
p = p->next;
}
}
// 深度优先搜索遍历图
void DFSTraverse(Graph G) {
int visited[MAX_VERTEX_NUM] = {0}; // 访问标记数组
printf("深度优先搜索遍历结果:");
for (int i = 0; i < G.numVertexes; i++) {
if (!visited[i]) {
DFS(G, i, visited);
}
}
printf("\n");
}
int main() {
Graph G;
initGraph(&G);
DFSTraverse(G);
return 0;
}
使用该代码可以创建一个图,并进行深度优先搜索遍历。你可以根据具体的需求修改代码中的数据输入部分,然后编译和运行代码,即可得到图的深度优先搜索遍历结果
原文地址: https://www.cveoy.top/t/topic/hzP3 著作权归作者所有。请勿转载和采集!