【实验目的】

使学生深入了解图结构的特点，掌握创建图的各种存储结构的方法；同时深刻理解图的DFS和BFS遍历过程。

【实验内容】

  1. 问题描述：很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序，演示在连通的无向图上访问全部结点的操作。
  2. 基本要求：以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。分别输出每种遍历下的结点访问序列和相应生成树的边集。
  3. 实现提示：设图的结点不超过30个，每个结点用一个编号表示（如果一个图有n个结点，则它们的编号分别为1,2,…,n）。通过输入图的全部边输入一个图，每个边为一个数对，可以对边的输入顺序作出某种限制，注意，生成树的边是有向边，端点顺序不能颠倒。

【实验代码】

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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
#include <iostream>
using namespace std;

/*
 * 9 15
A B C D E F G H I
A B
A F
B G
G F
B C
B I
G D
G H
F E
C I
C D
I D
D H
D E
H E
*/


template <class T>
struct Queue // 队列
{
    T value;
    Queue<T> * next;
    Queue<T> * front, * rear;
};

struct EdgeNode
{
    int adjvex; // 邻接点下标
    EdgeNode * next;
};

struct VertexNode
{
    char data;
    EdgeNode * firstEdge;
};

struct Graph
{
    VertexNode * adjList;
    int numVertexs, numEdges; // 顶点数，边数
};

template <class T>
void InitQueue(Queue<T> &s); // 初始化队列

template <class T>
void enQueue(Queue<T> &s, T e); // 入列

template <class T>
bool deQueue(Queue<T> &s, T &e); // 出列

template <class T>
bool QEmpty(Queue<T> s); // 判断队列是否为空

void CreateALGraph(Graph * G); // 创建图
int find(Graph * G, char ch); // 寻找字符所在顶点的下标

void DFS(Graph * G, int i); // 深度优先搜索遍历递归处
void DFSTraverse(Graph * G); // 深度优先搜索
void BFSTraverse(Graph *G); // 广度优先搜索

int main() {
    Graph * G = new Graph;
    CreateALGraph(G);
    DFSTraverse(G);
    BFSTraverse(G);

    return 0;
}

void CreateALGraph(Graph * G) // 创建图
{
    int numVexs, numEdges; // 顶点数，边数
    cout << "请输入顶点数和边数：" << endl;
    cin >> numVexs >> numEdges;

    G->adjList = new VertexNode[numVexs];
    G->numVertexs = numVexs;
    G->numEdges = numEdges;

    cout << "请输入你的图的顶点的数据：" << endl;
    for(int i = 0; i < G->numVertexs; i++)
    {
        cin >> G->adjList[i].data;
        G->adjList[i].firstEdge = NULL;
    }

    cout << "请输入你的图中的边，输入格式只需输入这条边所连接的两个顶点，比如边(a,b)，只需输入：a b，即可。" << endl;
    for(int i = 0; i < G->numEdges; i++)
    {
        char vex1, vex2; // 边的两个端点
        cin >> vex1 >> vex2;
        int index1, index2;
        index1 = find(G,vex1); //顶点1的下标
        index2 = find(G,vex2); //顶点2的下标

        EdgeNode * e = new EdgeNode;
        e->adjvex = index1;
        e->next = G->adjList[index2].firstEdge;
        G->adjList[index2].firstEdge = e;

        e = new EdgeNode;
        e->adjvex = index2;
        e->next = G->adjList[index1].firstEdge;
        G->adjList[index1].firstEdge = e;

    }
}

int find(Graph * G, char ch) // 寻找字符所在顶点的下标
{
    for(int i = 0; i < G->numVertexs; i++)
    {
        if(ch == G->adjList[i].data)
        {
            return i;
        }
    }
    cout << "未在图中找到所要寻找的顶点！" << endl;
    return -1;
}

bool * visitedDFS; // 深度优先搜索遍历数组标志
string DFSSpanningTree;
void DFS(Graph * G, int i) // 深度优先搜索遍历递归处
{
    EdgeNode * p =G->adjList[i].firstEdge;
    visitedDFS[i] = true;
    cout << G->adjList[i].data << " ";

    while(p)
    {
        if(!visitedDFS[p->adjvex])
        {
            DFSSpanningTree = DFSSpanningTree + "(" + G->adjList[i].data + "," + G->adjList[p->adjvex].data + ") ";
            DFS(G,p->adjvex);
        }
        p = p->next;
    }
}

void DFSTraverse(Graph * G) // 深度优先搜索
{
    cout << "深度优先搜索：" << endl;
    visitedDFS = new bool[G->numVertexs];
    for(int i = 0; i < G->numVertexs; i++)
    {
        visitedDFS[i] = false;
    }

    for(int i = 0; i < G->numVertexs; i++)
    {
        if(!visitedDFS[i])
        {
            DFS(G,i);
        }
    }
    cout << endl << "边集：" << DFSSpanningTree << endl;
}

bool * visitedBFS; // 广度优先搜索遍历数组标志
string BFSSpanningTree;
void BFSTraverse(Graph *G) // 广度优先搜索
{
    cout << "广度优先搜索：" << endl;
    Queue<int> queue;
    InitQueue(queue);

    visitedBFS = new bool[G->numVertexs];
    for(int i = 0; i < G->numVertexs; i++)
    {
        visitedBFS[i] = false;
    }

    for(int i = 0; i < G->numVertexs; i++)
    {
        if(!visitedBFS[i])
        {
            visitedBFS[i] = true;
            cout << G->adjList[i].data << " ";
            enQueue(queue,i);
            while(!QEmpty(queue))
            {
                deQueue(queue,i);
                EdgeNode * p = G->adjList[i].firstEdge;
                while(p)
                {
                    if(!visitedBFS[p->adjvex])
                    {
                        visitedBFS[p->adjvex] = true;
                        cout << G->adjList[p->adjvex].data << " ";
                        BFSSpanningTree = BFSSpanningTree + "(" + G->adjList[i].data + "," + G->adjList[p->adjvex].data + ") ";
                        enQueue(queue,p->adjvex);
                    }
                    p = p->next;
                }

            }
        }
    }
    cout << endl << "边集：" << BFSSpanningTree << endl;
}

template <class T>
void InitQueue(Queue<T> &s) // 初始化队列
{
    s.front = new Queue<T>;
    s.rear = s.front;
    s.front->next = NULL;
}

template <class T>
void enQueue(Queue<T> &s, T e) // 入列
{
    Queue<T> * p = new Queue<T>;
    p->value = e;
    p->next = NULL;
    s.rear->next = p;
    s.rear = p;
}

template <class T>
bool deQueue(Queue<T> &s, T &e) // 出列
{
    if (QEmpty(s))
    {
        cout << "队列为空！" << endl;
        return false;
    }
    e = s.front->next->value;//获取数据并传递给e,头节点不存放数据
    Queue<T> * p;
    p = s.front->next;
    s.front->next = s.front->next->next;//指向下一块地址
    if (s.front->next == NULL)//如果链队空了，则队尾指针指向队头指针
    {
        s.rear = s.front;
    }
    delete p;
    return true;
}

template <class T>
bool QEmpty(Queue<T> s) // 判断队列是否为空
{
    return s.front->next==NULL;
}