用c++写一段代码，试实现邻接矩阵存储图的深度优先遍历。 输入 第一行n为顶点数，第二行至第n+2行为其邻接矩阵表示形式，最后一行为遍历的起始点。 输入：7 0 0 1 1 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 2 输出样例 DFS from 2: 2 0 3 1 4 5 6

以下是实现邻接矩阵存储图的深度优先遍历的 C++ 代码：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 100;

int n;
int G[MAXN][MAXN];
bool vis[MAXN];

void dfs(int u) {
    vis[u] = true;
    cout << u << " ";
    for (int v = 0; v < n; v++) {
        if (G[u][v] && !vis[v]) {
            dfs(v);
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> G[i][j];
        }
    }
    int start;
    cin >> start;
    cout << "DFS from " << start << ": ";
    dfs(start);
    cout << endl;
    return 0;
}

输入格式中，每一行输入之间有多余的空格，需要注意处理。

时间复杂度为 $O(n^2)$，空间复杂度为 $O(n)$。

相关问题

题目描述 一个有n个节点的连通图，这些节点以编号：1、2、……n进行编号，现给出节点间的连接关系。请以节点1为起点，按dfs的顺序遍历并输出该图。n<100 输入格式 第一行为两整数，n和e，表示n个顶点，e条边 以下e行每行两个数，表示两个节点是联通的 输出格式 只有一行，为节点的dfs顺序 用c++编代码

DFS（深度优先搜索）是一种图形搜索算法，它沿着边的方向遍历图中的所有节点，直到找到目标节点或所有节点都已被遍历。

以下是用C语言实现DFS遍历图的代码示例：

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100

int n, e; // n为顶点数，e为边数
int adj[MAX_N][MAX_N]; // 邻接矩阵存储图
int visited[MAX_N]; // 记录每个节点是否被访问过

// dfs函数，v为当前节点编号
void dfs(int v) {
  printf("%d ", v); // 输出当前节点编号
  visited[v] = 1; // 标记为已访问
  for (int i = 1; i <= n; i++) {
    // 如果i和v相连且i未被访问过，则继续dfs
    if (adj[v][i] && !visited[i]) {
      dfs(i);
    }
  }
}

int main() {
  scanf("%d%d", &n, &e); // 读入n和e
  for (int i = 0; i < e; i++) {
    int u, v;
    scanf("%d%d", &u, &v); // 读入边的两个端点
    adj[u][v] = adj[v][u] = 1; // 在邻接矩阵中标记两个端点相连
  }
  dfs(1); // 从节点1开始遍历
  return 0;
}

在这段代码中，我们使用邻接矩阵来存储图的信息。邻接矩阵是一种常用的存储图的方式，它用一个二维