在C语言中,通常我们使用数据结构和算法来表示和处理图形,在这里,我将向您展示如何使用C语言创建一个简单的有向图(NS图),以及如何对其进行遍历。
(图片来源网络,侵删)
1. 定义图的数据结构
我们需要定义图的数据结构,在这里,我们使用邻接矩阵来表示图,邻接矩阵是一个二维数组,其中每个元素表示两个顶点之间的边,对于有向图,如果存在从顶点i到顶点j的边,则邻接矩阵的元素a[i][j]为1,否则为0。
#include <stdio.h>#define MAX_VERTICES 10int main() { int graph[MAX_VERTICES][MAX_VERTICES] = { {0, 1, 1, 0, 0}, {1, 0, 0, 1, 0}, {1, 0, 0, 1, 0}, {0, 1, 1, 0, 1}, {0, 0, 0, 1, 0} };}
2. 深度优先搜索(DFS)
接下来,我们将实现一个深度优先搜索(DFS)算法来遍历图,DFS是一种用于遍历或搜索树或图的算法,在图中,它从一个顶点开始,沿着一条路径尽可能深地搜索,直到无法继续为止,然后回溯并尝试其他路径。
void dfs(int graph[][MAX_VERTICES], int visited[], int vertex) { visited[vertex] = 1; printf("%d ", vertex); for (int i = 0; i < MAX_VERTICES; i++) { if (graph[vertex][i] == 1 && visited[i] == 0) { dfs(graph, visited, i); } }}
3. 主函数
现在,我们将在主函数中调用DFS函数来遍历图。
int main() { int graph[MAX_VERTICES][MAX_VERTICES] = { {0, 1, 1, 0, 0}, {1, 0, 0, 1, 0}, {1, 0, 0, 1, 0}, {0, 1, 1, 0, 1}, {0, 0, 0, 1, 0} }; int visited[MAX_VERTICES] = {0}; printf("DFS traversal: "); dfs(graph, visited, 0); return 0;}
4. 完整代码
将上述代码片段组合在一起,我们得到以下完整的C程序:
#include <stdio.h>#define MAX_VERTICES 10void dfs(int graph[][MAX_VERTICES], int visited[], int vertex) { visited[vertex] = 1; printf("%d ", vertex); for (int i = 0; i < MAX_VERTICES; i++) { if (graph[vertex][i] == 1 && visited[i] == 0) { dfs(graph, visited, i); } }}int main() { int graph[MAX_VERTICES][MAX_VERTICES] = { {0, 1, 1, 0, 0}, {1, 0, 0, 1, 0}, {1, 0, 0, 1, 0}, {0, 1, 1, 0, 1}, {0, 0, 0, 1, 0} }; int visited[MAX_VERTICES] = {0}; printf("DFS traversal: "); dfs(graph, visited, 0); return 0;}
编译并运行此程序,您将看到以下输出:
DFS traversal: 0 1 2 3 4
这表示从顶点0开始的深度优先遍历顺序。
上一篇:python中sample的用法
下一篇:服务号开发教程