C语言写关于图论的代码
时间: 2023-07-10 12:12:24 浏览: 74
图论是计算机科学中的一个重要分支,其研究对象是图,即由节点和边组成的数据结构。在C语言中,我们可以使用邻接矩阵或邻接表来表示图,并使用深度优先搜索或广度优先搜索等算法来遍历图。下面是一个使用邻接矩阵表示图,并使用深度优先搜索遍历图的C语言代码示例。
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
typedef struct {
int vertex[MAX_VERTEX_NUM];
int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vertex_num;
int edge_num;
} Graph;
void init_graph(Graph* g) {
g->vertex_num = 0;
g->edge_num = 0;
for (int i = 0; i < MAX_VERTEX_NUM; i++) {
g->vertex[i] = 0;
for (int j = 0; j < MAX_VERTEX_NUM; j++) {
g->edge[i][j] = 0;
}
}
}
void add_vertex(Graph* g, int v) {
g->vertex[g->vertex_num++] = v;
}
void add_edge(Graph* g, int v1, int v2) {
g->edge[v1][v2] = 1;
g->edge[v2][v1] = 1;
g->edge_num++;
}
void dfs(Graph* g, int v, int visited[]) {
visited[v] = 1;
printf("%d ", g->vertex[v]);
for (int i = 0; i < g->vertex_num; i++) {
if (g->edge[v][i] && !visited[i]) {
dfs(g, i, visited);
}
}
}
int main() {
Graph g;
init_graph(&g);
add_vertex(&g, 0);
add_vertex(&g, 1);
add_vertex(&g, 2);
add_vertex(&g, 3);
add_vertex(&g, 4);
add_edge(&g, 0, 1);
add_edge(&g, 0, 2);
add_edge(&g, 1, 2);
add_edge(&g, 2, 3);
add_edge(&g, 3, 4);
int visited[MAX_VERTEX_NUM] = {0};
dfs(&g, 0, visited);
return 0;
}
```
上述代码中,我们定义了一个Graph结构体,包含了图的节点、边信息,以及节点数和边数。我们使用init_graph函数初始化图,使用add_vertex函数添加节点,使用add_edge函数添加边。在dfs函数中,我们使用递归的方式遍历图,并使用visited数组记录节点是否被访问过。在主函数中,我们构建了一个简单的图,并使用dfs函数遍历该图。
这只是一个简单的图论例子,实际上图论的应用非常广泛,例如最短路径算法、最小生成树算法等等。希望这个例子能够帮助您更好地理解图论的基本原理和C语言的实现。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)