数据结构PTA 案例6-1.4 地下迷宫探索_输入第一行给出三个正整数,分别表示地下迷宫的节点数n(1

题目

假设有一个地下通道迷宫，它的通道都是直的，而通道所有交叉点（包括通道的端点）上都有一盏灯和一个开关。请问你如何从某个起点开始在迷宫中点亮所有的灯并回到起点？

输入格式:
输入第一行给出三个正整数，分别表示地下迷宫的节点数N（1<N≤1000，表示通道所有交叉点和端点）、边数M（≤3000，表示通道数）和探索起始节点编号S（节点从1到N编号）。随后的M行对应M条边（通道），每行给出一对正整数，分别是该条边直接连通的两个节点的编号。

输出格式:
若可以点亮所有节点的灯，则输出从S开始并以S结束的包含所有节点的序列，序列中相邻的节点一定有边（通道）；否则虽然不能点亮所有节点的灯，但还是输出点亮部分灯的节点序列，最后输出0，此时表示迷宫不是连通图。

由于深度优先遍历的节点序列是不唯一的，为了使得输出具有唯一的结果，我们约定以节点小编号优先的次序访问（点灯）。在点亮所有可以点亮的灯后，以原路返回的方式回到起点。

输入样例1:

6 8 1
1 2
2 3
3 4
4 5
5 6
6 4
3 6
1 5

输出样例1:

1 2 3 4 5 6 5 4 3 2 1

输入样例2:

6 6 6
1 2
1 3
2 3
5 4
6 5
6 4

输出样例2:

6 4 5 4 6 0

解法

思路
这个题目本质上还是一个深度优先遍历的问题。只是有以下两点不同：

1. 这个不仅要在进入顶点时用Visit函数输出，以代表进入了此顶点，而且还要在完成DFS遍历后，进行一次Visit函数的输出。
2. 因为在最后输出起始点的时候，末尾不能有空格，所以起始点SP需要单独处理，因此，如果图不连通的话，输出的0需要按照printf(" %d", 0);输出，即前面要加一个空格

实现

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

#define INFINITY 100000
#define MAXN 1000

typedef int Vertex;
typedef int WeightType;
typedef int DataType;

typedef struct GNode *PtrToGNode;
typedef PtrToGNode MGraph;
struct GNode
{
    int Nv;
    int Ne;
    WeightType **G;
};

typedef struct ENode *PtrToENode;
typedef PtrToENode Edge;
struct ENode
{
    Vertex V1, V2;
    WeightType W;
};

MGraph CreateGraph(int VertexNum)
{
    int i,j;
    MGraph Graph = (MGraph)malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->G = (WeightType **)malloc(Graph->Nv*sizeof(WeightType *));
    for(i=0; i<Graph->Nv; i++)
    {
        Graph->G[i] = (WeightType*)malloc(Graph->Nv*sizeof(WeightType));
    }

    for(i=0; i<Graph->Nv; i++)
    {
        for(j=0; j<Graph->Nv; j++)
            Graph->G[i][j] = INFINITY;
    }

    return Graph;
}

void InsertEdge(MGraph Graph, Edge E)
{
    Graph->G[E->V1][E->V2] = E->W;
    Graph->G[E->V2][E->V1] = E->W;
}

MGraph BuildGraph(int N, int M)
{
    int i;

    MGraph Graph = CreateGraph(N);
    Graph->Ne = M;

    if(Graph->Ne != 0)
    {
        Edge E = (Edge)malloc(sizeof(struct ENode));
        for(i=0; i<Graph->Ne; i++)
        {
            scanf("%d %d", &E->V1, &E->V2);
            E->V1--;
            E->V2--;
            E->W = 1;
            InsertEdge(Graph, E);
        }
    }

    return Graph;

}

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

int *Visited;
int SP; //start point. set the global variable to satisfy the output format

void DFS(MGraph Graph, Vertex V, void(*Visit)(Vertex))
{
    Visit(V);
    Visited[V] = 1;
    int i;
    for(i=0; i<Graph->Nv; i++)
    {
        if(Graph->G[V][i] == 1 && Visited[i] == 0)     //V is adjacent to i, and i is not visited
        {
            DFS(Graph, i, Visit);
            if(V==SP)
                printf("%d", SP+1);
            else
                Visit(V);
        }
    }
}

int main()
{

    int i,N,M;

    scanf("%d %d %d", &N, &M, &SP);
    SP = SP-1;

    MGraph Graph = BuildGraph(N, M);

    Visited = (int *)malloc(Graph->Nv*sizeof(int));
    for(i=0; i<Graph->Nv; i++)
        Visited[i] = 0;


    DFS(Graph, SP, Visit);
    int flag = 1;
    for(i=0; i<Graph->Nv; i++)
    {
        if(Visited[i] == 0)
        {
            flag = 0;
            break;
        }

    }
    if(flag == 0)
        printf(" %d", 0);

    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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136