邻接矩阵的深度优先算法
时间: 2023-10-12 19:17:37 浏览: 46
邻接矩阵的深度优先算法(Depth-First Search, DFS)是一种常用的图遍历算法,主要用于查找和遍历图中的节点。
算法步骤:
1. 从任意一个未访问的节点开始遍历,标记该节点为已访问。
2. 对于当前节点的所有未访问的邻居节点,递归调用 DFS 算法。
3. 返回到上一级节点时,继续查找该节点的其他未访问邻居节点,直到所有节点都被访问。
具体实现:
假设邻接矩阵的表示方式为 $adjMatrix$,$visited$ 数组用于记录每个节点是否已经被访问。
```
void DFS(int v, int n, int adjMatrix[][n], int visited[]) {
visited[v] = 1; // 标记当前节点已访问
printf("%d ", v); // 输出当前节点
for(int i = 0; i < n; i++) {
if(adjMatrix[v][i] == 1 && visited[i] == 0) { // 如果当前节点与邻居节点有连线且邻居节点未访问
DFS(i, n, adjMatrix, visited); // 递归访问邻居节点
}
}
}
```
其中,$v$ 表示当前节点的编号,$n$ 表示节点总数,$adjMatrix$ 表示图的邻接矩阵,$visited$ 用于记录每个节点是否已经被访问。算法入口为 $DFS(v, n, adjMatrix, visited)$。
示例:
假设有以下邻接矩阵表示的无向图:
```
0 1 1 0
1 0 1 0
1 1 0 1
0 0 1 0
```
从节点 0 开始遍历,输出结果为:0 1 2 3
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.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)