6-1 邻接矩阵存储图的深度优先遍历

6-1 邻接矩阵存储图的深度优先遍历

分数 20
作者 DS课程组
单位 浙江大学

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

函数接口定义：

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

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

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

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

裁判测试程序样例：

#include 


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;

}


/* 你的代码将被嵌在这里 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

输入样例：

给定图下

5
1

输出样例：

DFS from 5: 5 1 3 0 2 4 6
1

代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
C (gcc)

思路：

深度优先遍历类似于树的先根遍历，是树先根遍历的推广，遍历过程如下：

（1）将图中所有顶点做未访问的标记

（2）任选图中一个未访问过的顶点v作为遍历起点

（3）访问v结点，然后深度优先访问v的第一个未被访问的邻接点w1

（4）再从w1出发深度优先访问w1的第一个未被访问的邻接点w2，…如此下去，直到到达一个所有邻接点都被访问过的顶点为止

（5）然后一次退回，查找前一节点Wi-1是否还有未被访问的邻接点，如果存在则访问此邻接点，并从该节点出发按深度优先的规则访问。如果结点Wi-1不存在尚未被访问的结点，则再退后一步，直到找到所有未被访问的邻接点的顶点

（6）重复上述过程，直到图中所有与v有路径此相连的顶点都被访问过
c
（7）若此时图中仍有未被访问的顶点，则返回到（2）；否则遍历结束

递归思路：

1.访问结点V
2.找到v的第一个邻接点w
3.如果邻接点w存在且未被访问，则从w出发深度优先遍历图；否则，结束
4.找顶点v关于w的下一个邻接点，返回（3）

AC代码:

void DFS( MGraph Graph, Vertex V, void (*Visit)(Vertex) )
{
    Visited[V]=true;//先标记顶点被访问
    Visit(V);//访问顶点的邻接点
    for(int i=0;i<Graph->Nv;i++)
    {
        //遍历顶点的邻接点
        if(Graph->G[V][i]==1&&!(Visited[i]))
            DFS(Graph,i,Visit);//如果邻接点可达并且没有被访问过，那么以邻接点为顶点再次进行深度优先遍历
    }
    return;
}
1
2
3
4
5
6
7
8
9
10
11
12