图的遍历算法代码c语言
图是一种重要的数据结构，其应用十分广泛，包括社交网络、交通网络、电力系统、通讯网络等。图的遍历在解决各类问题时也非常常见，例如查找两个节点之间的最短路径、寻找图中的环以及图的连通性问题等等。本文将介绍图的遍历算法代码，重点介绍常见的两种算法：深度优先搜索(DFS)和广度优先搜索(BFS)。
1. DFS算法
深度优先搜索(DFS)是一种递归算法，以极大的深度优先搜索图中的各个节点。该算法依次访问图中的每个节点，直到所有节点都被访问为止。具体来说：
- 访问起始节点，并将其标记为已访问。
- 从该节点出发，访问与之相邻的节点，并将其标记为已访问。
- 对于标记为已访问的节点，从该节点出发再次访问其相邻的未访问节点。
- 重复此过程，直到所有节点都被访问。
下面是图的深度优先搜索的代码实现：
```
void DFS(int v, int visited[], int** graph, int size)
{
visited[v] = 1; // 标记该节点已访问
for(int i = 0; i < size; i++)
{
if(graph[v][i] == 1 && visited[i] == 0) // 如果该节点与当前节点相邻并且未被访问
{
DFS(i, visited, graph, size); // 递归访问该节点
}
}
}
```
其中，v表示当前正在访问的节点，visited数组用于记录各节点的访问状态，graph表示整张图，size表示图的大小。
2. BFS算法
广度优先搜索(BFS)算法一般使用队列来实现，依次访问起始节点的所有相邻节点，再访问所有这些相邻节点的相邻节点，直到所有节点都被访问为止。具体来说：
- 将起始节点加入队列。
- 访问队列中首节点的相邻节点，并将这些相邻节点加入队列。
- 重复此过程，直到队列为空。
下面是图的广度优先搜索的代码实现：
```
void BFS(int v, int visited[], int** graph, int size)
{
queue
visited[v] = 1; // 标记当前节点已访问
q.push(v); // 将当前节点加入队列
while(!q.empty())
{
int temp = q.front(); // 取出队列头部元素
q.pop();
for(int i = 0; i < size; i++)
{
if(graph[temp][i] == 1 && visited[i] == 0) // 如果该节点与当前节点相邻并且未被访问
{
visited[i] = 1; // 标记该节点已访问
q.push(i); // 将该节点加入队列
}
}
}
}
```
其中，v表示起始节点，visited数组用于记录各节点的访问状态，graph表示整张图，size表示图的大小。
3. 总结
本文介绍了图的遍历算法代码，包括深度优先搜索和广度优先搜索。深度优先搜索使用递归实现，广度优先搜索使用队列实现。这两种算法在解决图的各种问题时经常用到，如查找两个节点之间的最短路径、判断图是否连通等等。在实际使用时，需要根据具体问题进行选择。
