用C语言编写.给定一个无向连通图G,采用深度优先搜索方式访问图中节点,并输出。
时间: 2024-06-13 20:08:51 浏览: 258
以下是用C语言编写的深度优先搜索无向连通图并输出的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
typedef struct ArcNode {
int adjvex;
struct ArcNode *nextarc;
} ArcNode;
typedef struct VNode {
int data;
ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices;
int vexnum, arcnum;
} ALGraph;
void DFS(ALGraph *G, int v, int *visited) {
visited[v] = 1;
printf("%d ", G->vertices[v].data);
ArcNode *p = G->vertices[v].firstarc;
while (p) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex, visited);
}
p = p->nextarc;
}
}
void DFSTraverse(ALGraph *G) {
int visited[MAX_VERTEX_NUM] = {0};
for (int i = 0; i < G->vexnum; i++) {
if (!visited[i]) {
DFS(G, i, visited);
}
}
}
ALGraph* InitGraph(ALGraph* g, int number) {
g = (ALGraph*)malloc(sizeof(ALGraph));
g->vexnum = number;
g->arcnum = 0;
for (int i = 0; i < number; i++) {
g->vertices[i].data = i;
g->vertices[i].firstarc = NULL;
}
return g;
}
void AddEdge(ALGraph* g, int u, int v) {
ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = v;
p->nextarc = g->vertices[u].firstarc;
g->vertices[u].firstarc = p;
}
int main() {
int n = 5;
int edges[3][2] = {{0, 1}, {1, 2}, {3, 4}};
ALGraph *G = InitGraph(G, n);
for (int i = 0; i < 3; i++) {
AddEdge(G, edges[i][0], edges[i][1]);
AddEdge(G, edges[i][1], edges[i][0]);
}
DFSTraverse(G);
return 0;
}
```
阅读全文