深度优先遍历图的实现

"本文主要介绍了图的遍历，特别是深度优先搜索（DFS）算法的实现。文中给出了一个基于邻接表的数据结构，并提供了创建图和进行DFS遍历的函数。" 在计算机科学中，图是一种数据结构，用于表示对象之间的关系。在C语言中，可以使用结构体来表示图中的节点，每个节点包含一个整数值（vertex）以及指向下一个节点的指针（nextnode）。这里的代码定义了一个名为`struct node`的结构体，用于表示图的顶点。`struct node`中包含一个整型变量`vertex`，用来存储顶点的值，以及一个指向`struct node`类型的指针`nextnode`，用于链接相邻的顶点。 ```c struct node { int vertex; // 顶点的值 struct node* nextnode; // 指向下一个顶点的指针 }; ``` 为了操作这个图，我们还需要一个数组`head[9]`，它是一个指向`struct node`的指针数组，代表图的邻接表。`visited[9]`数组用于记录每个顶点是否已被访问过，初始值都为0，表示未访问。 接下来的`creategraph`函数用于根据给定的边列表创建图。它接受一个整型数组`node`和一个整型变量`num`，其中`node`数组的每个偶数索引表示一个顶点，奇数索引表示与之相邻的另一个顶点。函数通过遍历`node`数组，为每个边创建一个新的节点并将其插入到相应的顶点链表中。 ```c void creategraph(int* node, int num) { // ... 创建新节点、插入到链表等操作 ... } ``` 深度优先搜索（DFS）是一种遍历图的方法，从一个起始顶点开始，尽可能深地搜索图的分支，直到到达叶子节点，然后回溯。在给定的代码中，`dfs`函数实现了DFS遍历。它接收一个整数`current`作为当前访问的顶点，首先将该顶点标记为已访问，然后打印其值。接着，遍历当前顶点的所有邻居，如果邻居未被访问过，则递归调用`dfs`进行进一步的遍历。 ```c void dfs(int current) { // ... 访问当前顶点、打印顶点值、遍历并递归处理邻居节点 ... } ``` 这段代码提供了一个简单的图表示法，包括节点结构、邻接表以及创建图和进行深度优先搜索的功能。这种实现方法适用于处理有向图，可以通过修改和扩展以适应无向图或其他图遍历算法。