C语言实现图的存储表示和深度优先搜索并输出
时间: 2024-02-13 13:01:26 浏览: 20
好的,我可以回答你的问题。
首先,图的存储表示有多种方法,最常用的是邻接矩阵和邻接表。这里我选择邻接表来存储图。
邻接表是一种链式存储结构,它由一个数组和若干个链表组成。数组的每个元素表示一个顶点,链表则表示以该顶点为起点的边。具体实现可以参考以下代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 图中最大顶点数
// 定义邻接表中的边结构体
typedef struct ArcNode {
int adjvex; // 该边指向的顶点的位置
struct ArcNode* next; // 指向下一条边的指针
} ArcNode;
// 定义邻接表中的顶点结构体
typedef struct VNode {
int data; // 顶点的数据
ArcNode* first; // 指向第一条依附该顶点的边的指针
} VNode, AdjList[MAX_VERTEX_NUM];
// 定义图结构体
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 顶点数和边数
} Graph;
// 初始化图
void InitGraph(Graph* G, int vexnum) {
G->vexnum = vexnum;
G->arcnum = 0;
for (int i = 0; i < G->vexnum; i++) {
G->vertices[i].data = i;
G->vertices[i].first = NULL;
}
}
// 添加边
void AddArc(Graph* G, int i, int j) {
ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->next = G->vertices[i].first;
G->vertices[i].first = p;
G->arcnum++;
}
// 深度优先搜索
void DFS(Graph* G, int v, int visited[]) {
visited[v] = 1; // 标记该顶点已经被访问
printf("%d ", v);
ArcNode* p = G->vertices[v].first;
while (p != NULL) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex, visited);
}
p = p->next;
}
}
// 输出图
void PrintGraph(Graph* G) {
for (int i = 0; i < G->vexnum; i++) {
printf("%d: ", G->vertices[i].data);
ArcNode* p = G->vertices[i].first;
while (p != NULL) {
printf("%d ", p->adjvex);
p = p->next;
}
printf("\n");
}
}
int main() {
Graph G;
int n, m, u, v;
scanf("%d%d", &n, &m);
InitGraph(&G, n);
for (int i = 0; i < m; i++) {
scanf("%d%d", &u, &v);
AddArc(&G, u, v);
}
PrintGraph(&G);
int visited[MAX_VERTEX_NUM] = {0};
for (int i = 0; i < G.vexnum; i++) {
if (!visited[i]) {
DFS(&G, i, visited);
}
}
return 0;
}
```
在上面的代码中,`Graph` 结构体表示图,包含邻接表 `vertices`、顶点数 `vexnum` 和边数 `arcnum`。`InitGraph` 函数用于初始化图,`AddArc` 函数用于添加边,`PrintGraph` 函数用于输出图,`DFS` 函数用于深度优先搜索。
你可以输入图的顶点数和边数以及每条边所连接的两个顶点,程序会输出邻接表和深度优先搜索的结果。
希望这个回答能够帮助到你!