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$ 数组记录每个顶点的访问状态。

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

相关问题

图的存储和遍历c语言,图的邻接矩阵存储 深度优先遍历 广度优先遍历 C语言实现...

好的，我可以回答您的问题。

首先，图是一种非线性数据结构，它由一组节点（顶点）和一组边组成。图可以用多种方式存储，其中邻接矩阵是一种常见的存储方式。邻接矩阵是一个二维数组，数组中的元素表示图中两个节点之间是否有边相连。如果节点i和节点j之间有边相连，则邻接矩阵中第i行第j列的元素为1，否则为0。

下面是用C语言实现图的邻接矩阵存储：

#define MAX_VERTEX_NUM 100 //最大顶点数
typedef struct {
    int vexs[MAX_VERTEX_NUM]; //顶点数组
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵
    int vexnum, arcnum; //图的顶点数和边数
} MGraph;

其中，vexs数组用来存储图的顶点，arcs数组用来存储邻接矩阵，vexnum表示图的顶点数，arcnum表示图的边数。

接下来是图的遍历。图的遍历是指按照某种顺序访问图中的每个节点。常用的两种遍历方式是深度优先遍历和广度优先遍历。

深度优先遍历（Depth-First-Search，DFS）是一种先访问深度较深的节点的遍历方式。具体实现可以用递归或栈来实现。

下面是用C语言实现图的深度优先遍历：

void DFS(MGraph G, int v, int* visited) {
    visited[v] = 1; //标记节点v已经被访问
    printf("%d ", G.vexs[v]); //输出节点v的值
    for (int i = 0; i < G.vexnum; i++) {
        if (G.arcs[v][i] == 1 && visited[i] == 0) { //如果节点v和节点i之间有边相连且节点i未被访问过
            DFS(G, i, visited); //递归访问节点i
        }
    }
}

void DFSTraverse(MGraph G) {
    int visited[MAX_VERTEX_NUM] = {0}; //标记数组，用来记录每个节点是否被访问过
    for (int i = 0; i < G.vexnum; i++) {
        if (visited[i] == 0) { //如果节点i未被访问过
            DFS(G, i, visited); //从节点i开始进行深度优先遍历
        }
    }
}

其中，DFS函数是递归实现的深度优先遍历，DFSTraverse函数是遍历整个图的入口函数。

广度优先遍历（Breadth-First-Search，BFS）是一种先访问深度较浅的节点的遍历方式。具体实现可以用队列来实现。

下面是用C语言实现图的广度优先遍历：

void BFSTraverse(MGraph G) {
    int visited[MAX_VERTEX_NUM] = {0}; //标记数组，用来记录每个节点是否被访问过
    int queue[MAX_VERTEX_NUM]; //队列
    int front = -1, rear = -1; //队列的头和尾
    for (int i = 0; i < G.vexnum; i++) {
        if (visited[i] == 0) { //如果节点i未被访问过
            visited[i] = 1; //标记节点i已经被访问
            printf("%d ", G.vexs[i]); //输出节点i的值
            queue[++rear] = i; //将节点i入队
            while (front != rear) { //当队列不为空时
                int j = queue[++front]; //将队列头部元素出队
                for (int k = 0; k < G.vexnum; k++) {
                    if (G.arcs[j][k] == 1 && visited[k] == 0) { //如果节点j和节点k之间有边相连且节点k未被访问过
                        visited[k] = 1; //标记节点k已经被访问
                        printf("%d ", G.vexs[k]); //输出节点k的值
                        queue[++rear] = k; //将节点k入队
                    }
                }
            }
        }
    }
}

其中，BFSTraverse函数是遍历整个图的入口函数，使用了队列来实现广度优先遍历。

希望我的回答能够解决您的问题。

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