基于邻接矩阵的图的深度和广度遍历_给出一个图的邻接矩阵,输出以1点开始的深度遍历结果

描述

输入指定的边数m和顶点数n建立图（无向图），对每个顶点1-n编号并输出从1号顶点深度优先遍历和广度优先遍历的结果（数据保证图是连通的）。
1

输入

首先输入两个正整数n,m分别表示顶点数和边数(1<=n,m<=100)
接下来m行每行两个整数a b表示a到b连边。
1
2

输出

首先第一行输出DFS
第二行输出BFS
1
2

（如果存在多组解的话输出任意一组解即可，每个编号之间有一个空格，最后一个数后面没有空格）

---

样例输入

3 3
1 2
2 3
3 1

样例输出

1 2 3
1 2 3

---

AC 代码

#include<iostream>
using namespace std;
#define MaxVex 100
#define INFINITY 65536
typedef int VertexTpye;
typedef int EdgeType;
int visited[MaxVex];

typedef struct {
    VertexTpye vexs[MaxVex];
    EdgeType arc[MaxVex][MaxVex];
    int numVertexes, numEdges;
}MGraph;

//广度优先遍历所需要的循环队列
typedef struct {
    int data[MaxVex];
    int front, rear;
}Queue;

//初始化队列
void init_queue(Queue* Q)
{
    Q->front = Q->rear = 0;
}

//入队
void enqueue(Queue* Q, int e)
{
    if ((Q->rear + 1) % MaxVex == Q->front)
    {
        return;
    }
    Q->data[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MaxVex;
}

//判空
bool check_empty(Queue* Q)
{
    if (Q->front == Q->rear)
    {
        return true;
    }
    else {
        return false;
    }
}

//出队
void dequeue(Queue* Q, int* e)
{
    if (Q->front == Q->rear)
    {
        return;
    }
    *e = Q->data[Q->front];
    Q->front = (Q->front + 1) % MaxVex;
}

//建立图的邻接矩阵
void create_graph(MGraph* G)
{
    cin >> G->numVertexes >> G->numEdges;

    //预置节点值
    for (int i = 0; i < G->numVertexes; i++)
    {
        G->vexs[i] = i + 1;
    }

    //预置邻接矩阵
    for (int i = 0; i < G->numVertexes; i++)
    {
        for (int j = 0; j < G->numVertexes; j++)
        {
            G->arc[i][j] = INFINITY;
        }
    }
    //输入连通点坐标
    for (int i,j,k = 0; k < G->numEdges; k++)
    {
        cin >> i >> j;
        G->arc[i-1][j-1] = 1;
        G->arc[j-1][i-1] = G->arc[i-1][j-1];
    }
}

//输出,测试用
void display_graph(MGraph* G)
{
    for (int i = 0; i < G->numVertexes; i++)
    {
        for (int j = 0; j < G->numVertexes; j++)
        {
            cout << G->arc[i][j];
        }
        cout << endl;
    }
}

//图的深度优先遍历访问一条路
void DFS(MGraph* G, int i, Queue* temp1)
{
    visited[i] = true;
    //cout << G->vexs[i];
    enqueue(temp1, G->vexs[i]);

    for (int j = 0; j < G->numVertexes; j++)
    {
        if (G->arc[i][j] != INFINITY && !visited[j])
        {
            DFS(G, j, temp1);
        }
    }
}

//深度优先搜索访问所有节点
void DFS_traversal(MGraph* G)
{
    Queue temp1;//用于存储访问记录的队列
    init_queue(&temp1);

    for (int i = 0; i < G->numVertexes; i++)
    {
        visited[i] = false;
    }

    for (int i = 0; i < G->numVertexes; i++)
    {
        if (!visited[i])
        {
            DFS(G, i, &temp1);
        }
    }

    for (int i = 0; i < G->numVertexes-1; i++)//用于规范输出格式
    {
        int output;
        dequeue(&temp1, &output);
        cout << output << " ";
    }
    int output;
    dequeue(&temp1, &output);
    cout << output << endl;
}

//图的广度优先遍历
void BFS_traversal(MGraph* G)
{
    Queue Q;
    init_queue(&Q);
    Queue temp2;//用于存储访问记录的队列
    init_queue(&temp2);

    for (int i = 0; i < G->numVertexes; i++)
    {
        visited[i] = false;
    }

    for (int i = 0; i < G->numVertexes; i++)
    {
        if (!visited[i])
        {
            visited[i] = true;
            //cout << G->vexs[i];//输出当前结点，并将其入队
            enqueue(&temp2, G->vexs[i]);
            enqueue(&Q, i);

            while (!check_empty(&Q))
            {
                dequeue(&Q, &i);
                for (int j = 0; j < G->numVertexes; j++)
                {
                    if (!visited[j] && G->arc[i][j] != INFINITY)
                    {
                        visited[j] = true;
                        //cout << G->vexs[j];
                        enqueue(&temp2, G->vexs[j]);
                        enqueue(&Q, j);
                    }
                }
            }
        }
    }

    for (int i = 0; i < G->numVertexes - 1; i++)//用于规范输出格式
    {
        int output;
        dequeue(&temp2, &output);
        cout << output << " ";
    }
    int output;
    dequeue(&temp2, &output);
    cout << output << endl;
}
int main()
{
    MGraph G;
    create_graph(&G);
    DFS_traversal(&G);
    BFS_traversal(&G);
    system("pause");
    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
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

github 原文链接

https://github.com/scaactk/OnlineJudgement/tree/master/LGOJ/%E5%9B%BE%E7%9A%84%E6%B7%B1%E5%BA%A6%E5%92%8C%E5%B9%BF%E5%BA%A6%E9%81%8D%E5%8E%86