图的遍历算法代码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 q; // 定义队列

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. 总结

本文介绍了图的遍历算法代码，包括深度优先搜索和广度优先搜索。深度优先搜索使用递归实现，广度优先搜索使用队列实现。这两种算法在解决图的各种问题时经常用到，如查找两个节点之间的最短路径、判断图是否连通等等。在实际使用时，需要根据具体问题进行选择。