A. 邻接矩阵存储图的深度优先遍历 时间限制 1s 内存限制 128MB 题目描述 试实现邻接矩阵存储图的深度优先遍历。 输入 第一行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

题目描述

试实现邻接矩阵存储图的深度优先遍历。

输入

第一行 $n$ 为顶点数，第二行至第 $n+1$ 行为其邻接矩阵表示形式，最后一行为遍历的起始点。

输出

一行，为深度优先遍历的顶点序列，以空格分隔。格式见样例。

样例输入

7
0 0 1 1 1 0 0
0 0 0 0 0 1 0
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 0 1 0 0 0 0
0 0 0 0 0 0 1
0 0 0 0 0 0 0
2

样例输出

DFS from 2: 2 0 3 4 5 1 6

算法

(深度优先搜索)

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

C++ 代码

注：下面代码中的 $MAXN$ 需要定义为 $\ge n$ 的数，例如 $100$。

注意在进行 DFS 时要先判断当前顶点是否已经被访问过，否则会出现死循环。

因此需要一个 $vis$ 数组记录每个顶点的访问状态。

另外，题目给出的输入格式中，每一行输入之间有多余的空格，需要注意处理。

相关问题

试实现邻接矩阵存储图的深度优先遍历。

好的，对于您的问题，我可以给出以下代码实现邻接矩阵存储图的深度优先遍历：

#include<iostream>
using namespace std;
const int MAXN=100;//图的最大节点数
int G[MAXN][MAXN];//邻接矩阵
bool visited[MAXN];//标记节点是否被访问过

//深度优先遍历函数
void DFS(int u,int n){
    visited[u]=true;//标记当前节点为已访问
    cout<<u<<" ";//输出当前节点的编号
    for(int v=0;v<n;v++){
        if(G[u][v]==1&&!visited[v]){//如果当前节点与v节点有边相连且v节点未被访问过
            DFS(v,n);//递归遍历v节点
        }
    }
}

int main(){
    int n,m;//n表示节点数，m表示边数
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int u,v;//表示一条边的两个端点
        cin>>u>>v;
        G[u][v]=G[v][u]=1;//在邻接矩阵中标记这条边
    }
    for(int i=0;i<n;i++){
        visited[i]=false;//初始化所有节点为未访问状态
    }
    for(int i=0;i<n;i++){
        if(!visited[i]){//如果节点i未被访问过
            DFS(i,n);//从节点i开始进行深度优先遍历
        }
    }
    return 0;
}

在该代码中，我们首先输入图的节点数n和边数m，然后输入每一条边的两个端点，并在邻接矩阵中标记这条边。接着，我们初始化所有节点为未访问状态，然后从未被访问的节点开始进行深度优先遍历，遍历过程中使用visited数组标记节点是否被访问过，并输出访问的节点编号。

c语言实现邻接矩阵非递归深度优先遍历

邻接矩阵是表示图的一种方式，非递归深度优先遍历是指不使用递归算法来实现深度优先遍历。下面是C语言实现邻接矩阵非递归深度优先遍历的步骤：

1. 定义一个栈结构，用于存储待遍历的节点。
2. 定义一个visited数组，用于记录每个节点是否已经被遍历。
3. 从某个起始节点开始，将其压入栈中，并将visited数组中对应位置标记为已访问。
4. 循环执行以下步骤直到栈为空：
a. 取出栈顶元素，并输出该节点。
b. 遍历该节点的所有邻居节点，若该邻居节点未被访问，则将其压入栈中并标记为已访问。

下面是邻接矩阵非递归深度优先遍历的C语言实现代码：

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

#define MAX_VERTEX_NUM 100

typedef int VertexType;
typedef int EdgeType;

typedef struct {
    VertexType vertex[MAX_VERTEX_NUM];
    EdgeType edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int vertex_num, edge_num;
} MGraph;

typedef struct {
    VertexType data[MAX_VERTEX_NUM];
    int top;
} Stack;

void InitStack(Stack *S) {
    S->top = -1;
}

void Push(Stack *S, VertexType x) {
    S->data[++S->top] = x;
}

VertexType Pop(Stack *S) {
    return S->data[S->top--];
}

int IsEmpty(Stack *S) {
    return S->top == -1;
}

void CreateGraph(MGraph *G) {
    int i, j;
    printf("请输入图的顶点数和边数：\n");
    scanf("%d %d", &G->vertex_num, &G->edge_num);
    printf("请输入各个顶点：\n");
    for (i = 0; i < G->vertex_num; i++) {
        scanf("%d", &G->vertex[i]);
    }
    for (i = 0; i < G->vertex_num; i++) {
        for (j = 0; j < G->vertex_num; j++) {
            G->edge[i][j] = 0;
        }
    }
    printf("请输入各条边的起点和终点：\n");
    for (i = 0; i < G->edge_num; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        G->edge[u][v] = G->edge[v][u] = 1;
    }
}

void DFS(MGraph *G, int v, int visited[]) {
    Stack S;
    InitStack(&S);
    Push(&S, v);
    visited[v] = 1;
    while (!IsEmpty(&S)) {
        int i, w = Pop(&S);
        printf("%d ", G->vertex[w]);
        for (i = 0; i < G->vertex_num; i++) {
            if (G->edge[w][i] && !visited[i]) {
                Push(&S, i);
                visited[i] = 1;
            }
        }
    }
}

void DFSTraverse(MGraph *G) {
    int visited[MAX_VERTEX_NUM] = {0};
    int i;
    for (i = 0; i < G->vertex_num; i++) {
        if (!visited[i]) {
            DFS(G, i, visited);
        }
    }
}

int main() {
    MGraph G;
    CreateGraph(&G);
    DFSTraverse(&G);
    return 0;
}