读入一个无向图的邻接矩阵，建立无向图并按照深度优先遍历算法遍历所有顶点，输出遍历顶点顺序。输入第一行包含一个正整数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

可以使用递归实现深度优先遍历，首先从一个顶点开始，访问与之相邻的顶点，并标记已访问过的顶点，然后继续从这些相邻的顶点开始递归访问它们的相邻顶点。具体实现如下：

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

相关问题

在本题中，读入一个无向图的邻接矩阵（即数组表示），建立无向图并按照以上描述中的算法遍历所有顶点，输出遍历顶点的顺序。 Input 输入的第一行包含一个正整数n，表示图中共有n个顶点。其中n不超过50。 以后的n行中每行有n个用空格隔开的整数0或1，对于第i行的第j个0或1，1表示第i个顶点和第j个顶点有直接连接，0表示没有直接连接。当i和j相等的时候，保证对应的整数为0。 输入保证邻接矩阵为对称矩阵，即输入的图一定是无向图。 Output 只有一行，包含n个整数，表示按照题目描述中的深度优先遍历算法遍历整个图的访问顶点顺序。每个整数后输出一个空格，并请注意行尾输出换行。 Sample Input 4 0 1 0 1 1 0 0 0 0 0 0 1 1 0 1 0Sample Output 0 1 3 2 上述问题用C语言和数据结构如何写代码

以下是深度优先遍历的伪代码：

void dfs(int v) {
visited[v] = true; // 标记当前顶点已访问
printf("%d ", v); // 输出当前顶点
for (int i = 0; i < n; i++) {
if (adjMatrix[v][i] && !visited[i]) { // 如果当前顶点与 i 相邻且 i 未被访问过
dfs(i); // 递归访问 i
}
}
}

其中，visited 数组记录顶点是否被访问过，adjMatrix 是邻接矩阵，n 是顶点个数。

完整的C语言代码如下：

无向图邻接矩阵深度优先遍历

好的，我可以为您解答这个问题。

无向图的邻接矩阵表示法可以用一个二维数组来表示，其中矩阵的行列数都等于图的顶点数，矩阵中的元素表示两个顶点之间是否有边相连，通常用 0 或 1 来表示。

深度优先遍历（Depth First Search，DFS）是一种常用的图遍历算法，主要思想是从某个顶点开始，沿着一条路径遍历直到不能继续为止，然后返回到前一级顶点，继续沿着另一条路径遍历，直到所有的顶点都被访问过。

无向图邻接矩阵深度优先遍历的步骤如下：

1. 访问起始顶点，并将其标记为已访问；
2. 从起始顶点出发，依次遍历它的邻接点；
3. 对于每个邻接点，如果它未被访问，则递归访问它，并将其标记为已访问；
4. 重复步骤 2 和步骤 3，直到所有顶点都被访问过。

具体实现可以参考以下代码：

#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;
}

以上代码实现了无向图邻接矩阵深度优先遍历，并输出了遍历结果。