邻接矩阵存储的图的深度优先搜索void dfs （MGraph*g,int v){ int i；visit（g，v）；visited[v]=1;

}在这个深度优先搜索算法中，visited[v]数组的作用是什么？

visited[v]数组是用来标记顶点v是否被访问过的。在搜索过程中，对于每个顶点v，只有在visited[v]为0的情况下才会对其进行访问并继续搜索。当搜索到的路径不能继续往下搜索时，算法会回溯到之前的结点并继续搜索其他路径，回溯过程中visited数组也会被更新。这样，visited数组的作用就是在搜索过程中记录哪些顶点已经被访问了，以避免重复访问和死循环。

相关问题

邻接矩阵存储图的深度优先遍历 分数 20 作者 DS课程组 单位 浙江大学 试实现邻接矩阵存储图的深度优先遍历。 函数接口定义： void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) ); 其中MGraph是邻接矩阵存储的图，定义如下： typedef struct GNode *PtrToGNode; struct GNode{ int Nv; /* 顶点数 */ int Ne; /* 边数 */ WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */ }; typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */ 函数DFS应从第V个顶点出发递归地深度优先遍历图Graph，遍历时用裁判定义的函数Visit访问每个顶点。当访问邻接点时，要求按序号递增的顺序。题目保证V是图中的合法顶点。 裁判测试程序样例： #include <stdio.h> typedef enum {false, true} bool; #define MaxVertexNum 10 /* 最大顶点数设为10 */ #define INFINITY 65535 /* ∞设为双字节无符号整数的最大值65535*/ typedef int Vertex; /* 用顶点下标表示顶点,为整型 */ typedef int WeightType; /* 边的权值设为整型 */ typedef struct GNode *PtrToGNode; struct GNode{ int Nv; /* 顶点数 */ int Ne; /* 边数 */ WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */ }; typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */ bool Visited[MaxVertexNum]; /* 顶点的访问标记 */ MGraph CreateGraph(); /* 创建图并且将Visited初始化为false；裁判实现，细节不表 */ void Visit( Vertex V ) { printf(" %d", V); } void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) ); int main() { MGraph G; Vertex V; G = CreateGraph(); scanf("%d", &V); printf("DFS from %d:", V); DFS(G, V, Visit); return 0; } /* 你的代码将被嵌在这里 */ 输入样例：给定图如下 5 输出样例： DFS from 5: 5 1 3 0 2 4 6

题目描述

本题要求实现邻接矩阵存储图的深度优先遍历。

函数接口定义：

void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) );

其中MGraph是邻接矩阵存储的图，定义如下：

typedef struct GNode *PtrToGNode;
struct GNode{
int Nv; /* 顶点数 */
int Ne; /* 边数 */
WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
};
typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */

函数DFS应从第V个顶点出发递归地深度优先遍历图Graph，遍历时用裁判定义的函数Visit访问每个顶点。当访问邻接点时，要求按序号递增的顺序。

裁判测试程序样例：

#include <stdio.h>

typedef enum {false, true} bool;
#define MaxVertexNum 10 /* 最大顶点数设为10 */
#define INFINITY 65535 /* ∞设为双字节无符号整数的最大值65535*/
typedef int Vertex; /* 用顶点下标表示顶点,为整型 */
typedef int WeightType; /* 边的权值设为整型 */

typedef struct GNode *PtrToGNode;
struct GNode{
int Nv; /* 顶点数 */
int Ne; /* 边数 */
WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
};
typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */

bool Visited[MaxVertexNum]; /* 顶点的访问标记 */

MGraph CreateGraph(); /* 创建图并且将Visited初始化为false；裁判实现，细节不表 */

void Visit( Vertex V ) {
printf(" %d", V);
}

void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) );

int main() {
MGraph G;
Vertex V;

G = CreateGraph();
scanf("%d", &V);
printf("DFS from %d:", V);
DFS(G, V, Visit);

return 0;
}

输入样例：

给定图如下

5

输出样例：

DFS from 5: 5 1 3 0 2 4 6

算法1

深度优先遍历

我们可以使用递归的方式实现深度优先遍历。首先标记当前节点已经被访问，然后依次访问当前节点的邻居节点，对于每个邻居节点，如果该节点没有被访问过，则递归遍历该节点。具体实现时，我们可以使用一个Visited数组来记录每个节点是否被访问过。

C++ 代码

void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) )
{
Visit(V);
Visited[V] = true;
for (Vertex W = 0; W < Graph->Nv; W++) {
if (Graph->G[V][W] != 0 && !Visited[W]) {
DFS(Graph, W, Visit);
}
}
}

时间复杂度

深度优先遍历的时间复杂度是O(V + E)，其中V是顶点数，E是边数。

参考文献

算法基础课程第二版

C++ 代码

#include <stdio.h> typedef enum {false, true} bool; #define MaxVertexNum 10 #define INFINITY 65535 typedef int Vertex; typedef int WeightType; typedef struct GNode *PtrToGNode; struct GNode{ int Nv; int Ne; WeightType G[MaxVertexNum][MaxVertexNum]; }; typedef PtrToGNode MGraph; bool Visited[MaxVertexNum]; MGraph CreateGraph(); void Visit( Vertex V ) { printf(" %d", V); } void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) ); int main() { MGraph G; Vertex V; G = CreateGraph(); scanf("%d", &V); printf("DFS from %d:", V); DFS(G, V, Visit); return 0; } void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) ) { int i; Visit(V); Visited[V]=true; for(i=0;i<MaxVertexNum;i++) { if(Graph->G[V][i]!=0 && Visited[i]!=true) { DFS(Graph,i,Visit); } } }这段代码有什么问题

这段代码存在以下问题：

1. 在定义枚举类型时，应该把 true 定义为 1，false 定义为 0，否则在使用该枚举类型时可能会出现问题。

2. 在定义结构体时，应该将结构体名称放在结构体内部，而不是外部。

3. 在遍历图时，应该遍历所有的顶点，而不是仅仅遍历 MaxVertexNum 个顶点。可以通过 Graph->Nv 获取顶点个数。

下面是修改后的代码：

#include <stdio.h>

typedef enum {false = 0, true = 1} bool;
#define MaxVertexNum 10
#define INFINITY 65535
typedef int Vertex;
typedef int WeightType;

typedef struct GNode{
    int Nv;
    int Ne;
    WeightType G[MaxVertexNum][MaxVertexNum];
} *PtrToGNode;

typedef PtrToGNode MGraph;

bool Visited[MaxVertexNum];

MGraph CreateGraph();

void Visit(Vertex V) {
    printf(" %d", V);
}

void DFS(MGraph Graph, Vertex V, void (*Visit)(Vertex));

int main() {
    MGraph G;
    Vertex V;
    G = CreateGraph();
    scanf("%d", &V);
    printf("DFS from %d:", V);
    DFS(G, V, Visit);
    return 0;
}

void DFS(MGraph Graph, Vertex V, void (*Visit)(Vertex)) {
    int i;
    Visit(V);
    Visited[V] = true;
    for (i = 0; i < Graph->Nv; i++) {
        if (Graph->G[V][i] != 0 && Visited[i] != true) {
            DFS(Graph, i, Visit);
        }
    }
}

MGraph CreateGraph() {
    int N, M;
    Vertex V, W;
    WeightType Weight;
    MGraph Graph;
    Graph = (MGraph)malloc(sizeof(struct GNode));
    scanf("%d", &(Graph->Nv));
    scanf("%d", &(Graph->Ne));
    for (V = 0; V < Graph->Nv; V++) {
        for (W = 0; W < Graph->Nv; W++) {
            Graph->G[V][W] = 0;
        }
    }
    for (M = 0; M < Graph->Ne; M++) {
        scanf("%d %d %d", &V, &W, &Weight);
        Graph->G[V][W] = Weight;
        Graph->G[W][V] = Weight;
    }
    return Graph;
}