You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: src/graph/search-for-connected-components.md
+38-35Lines changed: 38 additions & 35 deletions
Original file line number
Diff line number
Diff line change
@@ -20,40 +20,53 @@ Given an undirected graph $G$ with $n$ nodes and $m$ edges. We are required to f
20
20
21
21
```cpp
22
22
int n;
23
-
vector<int> g[MAXN] ;
24
-
bool used[MAXN] ;
25
-
vector<int> comp;
23
+
vector<vector<int>> adj;
24
+
vector<bool> used;
25
+
vector<int> comp;
26
26
27
27
voiddfs(int v) {
28
28
used[v] = true ;
29
29
comp.push_back(v);
30
-
for (size_t i = 0; i < (int) g[v].size(); ++i) {
31
-
int to = g[v][i];
32
-
if (!used[to])
33
-
dfs(to);
30
+
for (int u : adj[v]) {
31
+
if (!used[u])
32
+
dfs(u);
34
33
}
35
34
}
36
35
37
36
void find_comps() {
38
-
for (int i = 0; i < n ; ++i)
39
-
used [i] = false;
40
-
for (int i = 0; i < n ; ++i)
37
+
fill(used.begin(), used.end(), 0);
38
+
for (int v = 0; v < n; ++v) {
41
39
if (!used[i]) {
42
40
comp.clear();
43
41
dfs(i);
44
-
cout << "Component:" ;
45
-
for (size_t j = 0; j < comp.size(); ++j)
46
-
cout << ' ' << comp[j];
42
+
cout << "Component:" ;
43
+
for (int u : comp)
44
+
cout << ' ' << u;
47
45
cout << endl ;
48
46
}
47
+
}
49
48
}
50
49
```
51
50
51
+
* The most important function that is used is `find_comps()` which finds and displays connected components of the graph.
52
+
53
+
* The graph is stored in adjacency list representation, i.e `adj[v]` contains a list of vertices that have edges from the vertex `v`.
54
+
55
+
* Vector `comp` contains a list of nodes in the current connected component.
56
+
52
57
## Iterative implementation of the code
53
-
``` cpp
58
+
59
+
Deeply recursive functions are in general bad.
60
+
Ever single recursive call will require a little bit of memory in the stack, and per default programs only have a limited amount of stack space.
61
+
So when you do a recursive DFS over a connected graph with millions of nodes, you might run into stack overflows.
62
+
63
+
It is always possible to translate a recursive program into an iterative program, by manually maintaining a stack data structure.
64
+
Since this data structure is allocated on the heap, no stack overflow will occur.
65
+
66
+
```cpp
54
67
int n;
55
-
vector<int> g[MAXN];
56
-
bool used[MAXN];
68
+
vector<vector<int>> adj;
69
+
vector<bool> used;
57
70
vector<int> comp;
58
71
59
72
void dfs(int v) {
@@ -66,38 +79,28 @@ void dfs(int v) {
66
79
if (!used[curr]) {
67
80
used[curr] = true;
68
81
comp.push_back(curr);
69
-
for (int i = g[curr].size() - 1; i >= 0; i--) {
70
-
int to = g[curr][i];
71
-
st.push(to);
82
+
for (int i = adj[curr].size() - 1; i >= 0; i--) {
83
+
st.push(adj[curr][i]);
72
84
}
73
85
}
74
86
}
75
87
}
76
88
77
89
void find_comps() {
78
-
for (int i = 0; i < n ; ++i)
79
-
used [i] = false;
80
-
for (int i = 0; i < n ; ++i)
81
-
if (!used[i]) {
90
+
fill(used.begin(), used.end(), 0);
91
+
for (int v = 0; v < n ; ++v) {
92
+
if (!used[v]) {
82
93
comp.clear();
83
-
dfs(i);
94
+
dfs(v);
84
95
cout << "Component:" ;
85
-
for (size_t j = 0; j < comp.size(); ++j)
86
-
cout << ' ' << comp[j];
96
+
for (int u : comp)
97
+
cout << ' ' << u;
87
98
cout << endl ;
88
99
}
100
+
}
89
101
}
90
-
91
102
```
92
103
93
-
94
-
95
-
* The most important function that is used is `find_comps()` which finds and displays connected components of the graph.
96
-
97
-
* The graph is stored in adjacency list representation, i.e `g[i]` contains a list of vertices that have edges from the vertex `i`. The constant `MAXN` should be set equal to the maximum possible number of vertices in the graph.
98
-
99
-
* Vector `comp` contains a list of nodes in the current connected component.
0 commit comments