7-6 列出连通集

预备知识

  • 图 多对多的关系
    • 无向边(u v)
    • 有向边
  • 线性表 一对一
  • 树 一对多
  • 抽象数据类型定义的三要
    • 类型名称
    • 数据对象集
    • 操作集
  • 网络 带权重的图
  • 图的表示方法取决于你要解决的具体问题
  • DFS 深度优先搜索 出栈
  • DFS 时间复杂度取决于图的表示方法
    • 领接表 O(N+E)
    • 邻接矩阵 O(N^2)
  • BFS 广度优先
  • DFS BFS 复杂度相同

广优的话,占内存多,能找到最优解,必须遍历所有分枝. 广优的一个应用就是迪科斯彻单元最短路径算法.

深优的话,占内存少,能找到最优解(一定条件下),但能很快找到接近解(优点),可能不必遍历所有分枝(也就是速度快), 深优的一个应用就是连连看游戏.

  • 连通分量 一次DFS 遍历了一个连通分量

题目描述

分别用深度优先搜索和广度优先搜索遍历一幅图的所有节点。

思路

首先就是考虑这个图该用领接表还是邻接矩阵来表示,后来在码代码的过程中发现确实是邻接矩阵方便的多,不用findmin函数。但我没用过邻接表,这次练习一下。

难点

基本没有难点

体会与感想

  • 大工程绝对不要企图用一个.cpp文件就想写完,太天真了。
  • 果然写的太长了是因为我太菜了嘛
  • 半天200行的效率
  • 反复传图指针很难受
  • 还没来得及看视频

源代码

这次的代码比较长,放一个文件里也比较乱

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
#include <iostream>

using namespace std;

struct node {
int element;
node * next;
};

struct Queue {
int * queue;
int head;
int tail;
int size;
};

node * createGraph(int n);
void readGraph(node * G, int e);
void DFSlistComponents(node * G, int n);
void deleteGraph(node * G, int n);
void BFSlistComponents(node * G, int n);

int main(int argc, char const *argv[]) {
freopen("D:\\SJTU\\Freshman Summer\\DS\\test.txt", "r", stdin);
int n, e;cin >> n >> e;
node * G = createGraph(n);
readGraph(G,e);
DFSlistComponents(G,n);
BFSlistComponents(G,n);
deleteGraph(G,n);
return 0;
}

int findMin(node * ptr, bool * visited) {
int min;
while (ptr->next && visited[ptr->next->element])
{
ptr = ptr->next;
}
if (ptr->next==NULL) return -1;
else min = ptr->next->element;
ptr = ptr->next->next;
while (ptr) {
if (ptr->element<min && !visited[ptr->element]) {
min = ptr->element;
}
ptr = ptr->next;
}
return min;
}

bool remains(node * ptr, bool * visited) {
while (ptr->next) {
if (!visited[ptr->next->element]) {
return true;
}
ptr = ptr->next;
}
return false;
}

Queue * creatQueue(int n) {
Queue * q = new Queue;
q->size = n;
q->queue = new int [n];
q->head = 0;
q->tail = -1;
return q;
}

void deleteQueue(Queue * q) {
delete [] q->queue;
delete q;
}

void enQueue(Queue * q, int element) {
q->queue[++q->tail] = element;
}

int deQueue(Queue * q) {
return q->queue[q->head++];
}

void push(Queue * q, node * ptr, bool * visited) {
while (remains(ptr,visited)) {
int min = findMin(ptr,visited);
if (min==-1) return;
enQueue(q,min);
visited[min] = true;
}
}

void BFSlistComponents(node * G, int n) {
Queue * q = creatQueue(n);
bool * visited = new bool [n];
for (int i = 0; i < n; i++) {
visited[i] = false;
}
for (int i = 0; i < n; i++) {
if (!visited[i]) {
cout << "{ ";
enQueue(q,i);
visited[i] = true;
while (q->head!=q->tail+1) {
int popelement = deQueue(q);
cout << popelement <<" ";
push(q,&G[popelement],visited);
}
cout << '}' << endl;
}
}
delete [] visited;
deleteQueue(q);
}

void DFS(node * G, int i, bool * visited) {
while (remains(&G[i],visited)) {
int min = findMin(&G[i],visited);
if (min==-1) return;
cout << min <<" ";
visited[min] = true;
DFS(G,min,visited);
}
}

void DFSlistComponents(node * G, int n) {
bool * visited = new bool [n];
for (int i = 0; i < n; i++) {
visited[i] = false;
}
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
cout << "{ ";
if (!visited[i]) {
cout << i <<" ";
visited[i] = true;
DFS(G,i,visited);
}
cout << "}" << endl;
}
delete [] visited;
}

void deleteGraph(node * G, int n) {
for (int i = 0; i < n; i++) {
node * ptr = G[i].next;
while (ptr) {
node * temp = ptr->next;
delete ptr;
ptr = temp;
}
}
delete [] G;
}

void insertEdge(node * G, int i, int j) {
node * ptr = &G[i];
while (ptr->next) {
ptr = ptr->next;
}
ptr->next = new node;
ptr = ptr->next;
ptr->element = j;
ptr->next = NULL;

ptr = &G[j];
while (ptr->next) {
ptr = ptr->next;
}
ptr->next = new node;
ptr = ptr->next;
ptr->element = i;
ptr->next = NULL;
}

void readGraph(node * G, int e) {
int vi, vj;
for (int i = 0; i < e; i++) {
cin >> vi >> vj;
insertEdge(G, vi, vj);
}
}

node * createGraph(int n) {
node * G = new node [n];
for (int i = 0; i < n; i++) {
G[i].element = i;
G[i].next = NULL;
}
return G;
}