C语言完成: 假设图G采用邻接表存储,利用深度优先搜索方法求出无向图中通过给定点v的简单回路。
时间: 2024-02-24 08:59:31 浏览: 73
以下是 C 语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 图中最大顶点数
// 边表节点结构体
typedef struct EdgeNode {
int adjvex; // 邻接点序号
struct EdgeNode *next; // 指向下一个邻接点
} EdgeNode;
// 顶点表结构体
typedef struct {
char data; // 顶点信息
EdgeNode *first; // 指向第一个邻接点
} VertexNode;
// 邻接表存储的图结构体
typedef struct {
VertexNode vertexList[MAX_VERTEX_NUM]; // 顶点表
int vertexNum; // 顶点数
int edgeNum; // 边数
} Graph;
// 初始化图
void initGraph(Graph *graph) {
graph->vertexNum = 0;
graph->edgeNum = 0;
for (int i = 0; i < MAX_VERTEX_NUM; i++) {
graph->vertexList[i].data = 0;
graph->vertexList[i].first = NULL;
}
}
// 向图中添加顶点
void addVertex(Graph *graph, char data) {
graph->vertexList[graph->vertexNum].data = data;
graph->vertexNum++;
}
// 向图中添加边
void addEdge(Graph *graph, int start, int end) {
EdgeNode *node = (EdgeNode *)malloc(sizeof(EdgeNode));
node->adjvex = end;
node->next = graph->vertexList[start].first;
graph->vertexList[start].first = node;
graph->edgeNum++;
}
// 判断顶点是否已在路径上
int isInPath(int path[], int v, int len) {
for (int i = 0; i < len; i++) {
if (path[i] == v) {
return 1;
}
}
return 0;
}
// 深度优先搜索函数
void DFS(Graph *graph, int v, int path[], int pathLen, int start, int *hasCycle) {
path[pathLen] = v;
pathLen++;
if (pathLen > 2 && v == start) { // 找到一个简单回路
printf("Simple cycle:");
for (int i = 0; i < pathLen; i++) {
printf(" %c", graph->vertexList[path[i]].data);
}
printf("\n");
*hasCycle = 1;
return;
}
EdgeNode *node = graph->vertexList[v].first;
while (node != NULL) {
if (!isInPath(path, node->adjvex, pathLen)) { // 邻接点不在路径上
DFS(graph, node->adjvex, path, pathLen, start, hasCycle);
}
node = node->next;
}
}
// 查找简单回路
void findSimpleCycle(Graph *graph, int v) {
int path[MAX_VERTEX_NUM];
int hasCycle = 0;
DFS(graph, v, path, 0, v, &hasCycle);
if (!hasCycle) {
printf("No simple cycle found.\n");
}
}
int main() {
Graph graph;
initGraph(&graph);
// 添加顶点
addVertex(&graph, 'A');
addVertex(&graph, 'B');
addVertex(&graph, 'C');
addVertex(&graph, 'D');
addVertex(&graph, 'E');
// 添加边
addEdge(&graph, 0, 1);
addEdge(&graph, 1, 2);
addEdge(&graph, 2, 3);
addEdge(&graph, 3, 4);
addEdge(&graph, 4, 0);
addEdge(&graph, 0, 2);
addEdge(&graph, 1, 3);
// 查找简单回路
findSimpleCycle(&graph, 0);
return 0;
}
```
这段代码实现了一个深度优先搜索来查找无向图中通过给定点 v 的简单回路。程序中使用邻接表存储图,通过添加顶点和边来构建图,然后从给定点 v 开始进行深度优先搜索,查找简单回路。
阅读全文