读入一个无向图的邻接矩阵,建立无向图并按照深度优先遍历算法遍历所有顶点,输出遍历顶点顺序。输入第一行包含一个正整数n,表示图中有n个顶点;后面n行中每行有n个用空格隔开的整数0或1,对于第i行的第j个0或1,1表示第i个顶点和第j个顶点有直接连接,0表示没有直接连接,当i和j相等的时候,保证对应的整数为0。输出只有一行,包含n个整数,表示按照深度优先遍历算法遍历所有顶点的顺序。样例输入: 4 0 1 0 1 1 0 1 0 0 0 0 1 1 0 1 0 输出: 0 1 3 2
时间: 2024-02-12 18:06:22 浏览: 24
可以使用递归实现深度优先遍历,首先从一个顶点开始,访问与之相邻的顶点,并标记已访问过的顶点,然后继续从这些相邻的顶点开始递归访问它们的相邻顶点。具体实现如下:
```python
n = int(input())
adj_matrix = [list(map(int, input().split())) for _ in range(n)]
visited = [False] * n
order = []
def dfs(v):
visited[v] = True
order.append(v)
for i in range(n):
if adj_matrix[v][i] == 1 and not visited[i]:
dfs(i)
for i in range(n):
if not visited[i]:
dfs(i)
print(' '.join(map(str, order)))
```
输入样例:
```
4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
```
输出样例:
```
0 1 2 3
```
相关问题
无向图邻接矩阵深度优先遍历
好的,我可以为您解答这个问题。
无向图的邻接矩阵表示法可以用一个二维数组来表示,其中矩阵的行列数都等于图的顶点数,矩阵中的元素表示两个顶点之间是否有边相连,通常用 0 或 1 来表示。
深度优先遍历(Depth First Search,DFS)是一种常用的图遍历算法,主要思想是从某个顶点开始,沿着一条路径遍历直到不能继续为止,然后返回到前一级顶点,继续沿着另一条路径遍历,直到所有的顶点都被访问过。
无向图邻接矩阵深度优先遍历的步骤如下:
1. 访问起始顶点,并将其标记为已访问;
2. 从起始顶点出发,依次遍历它的邻接点;
3. 对于每个邻接点,如果它未被访问,则递归访问它,并将其标记为已访问;
4. 重复步骤 2 和步骤 3,直到所有顶点都被访问过。
具体实现可以参考以下代码:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100;
int n; // 顶点数
int G[MAXN][MAXN]; // 邻接矩阵
bool visited[MAXN]; // 标记数组
void dfs(int v) {
visited[v] = true; // 标记当前顶点已访问
cout << v << " "; // 输出当前顶点
for (int i = 0; i < n; i++) {
if (G[v][i] && !visited[i]) { // 如果有边相连且未访问过
dfs(i); // 递归访问邻接点
}
}
}
int main() {
memset(G, 0, sizeof(G)); // 初始化邻接矩阵
memset(visited, false, sizeof(visited)); // 初始化标记数组
// 读入无向图的顶点数和边数
int m;
cin >> n >> m;
// 读入边的信息,建立邻接矩阵
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
G[u][v] = G[v][u] = 1; // 无向图的边是双向的
}
// 从顶点 0 开始深度优先遍历
dfs(0);
return 0;
}
```
以上代码实现了无向图邻接矩阵深度优先遍历,并输出了遍历结果。
编写基于邻接矩阵存储的无向图的深度优先遍历的一个程序
好的,以下是基于邻接矩阵存储的无向图的深度优先遍历的一个程序:
```c++
#include <iostream>
#include <stack>
using namespace std;
const int MAX = 100; // 最大顶点数
int visited[MAX] = {0}; // 记录顶点是否已访问,初始为0
void DFS(int graph[][MAX], int vertex, int size)
{
visited[vertex] = 1; // 标记该顶点已被访问
cout << vertex << " "; // 输出该顶点
for (int i = 0; i < size; i++) {
if (graph[vertex][i] == 1 && visited[i] == 0) { // 未被访问过的相邻顶点
DFS(graph, i, size); // 递归访问相邻顶点
}
}
}
int main()
{
int size; // 顶点数
int graph[MAX][MAX]; // 邻接矩阵存储图
cout << "请输入顶点数:";
cin >> size;
cout << "请输入邻接矩阵:\n";
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
cin >> graph[i][j];
}
}
cout << "深度优先遍历结果为:\n";
for (int i = 0; i < size; i++) {
if (visited[i] == 0) { // 未被访问过的顶点
DFS(graph, i, size); // 从该顶点开始深度优先遍历
}
}
cout << endl;
return 0;
}
```
该程序中,DFS函数实现了深度优先遍历,visited数组记录了每个顶点是否已被访问过。在主函数中,先读入邻接矩阵表示的无向图,然后对每个未被访问过的顶点进行深度优先遍历。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)