12_graph_basic.cpp

Download
cpp 392 lines 10.3 KB 
  1/*
  2 * κ·Έλž˜ν”„ 기초 (Graph Basics)
  3 * Graph Representation, DFS, BFS, Connected Components
  4 *
  5 * κ·Έλž˜ν”„μ˜ κΈ°λ³Έ ν‘œν˜„κ³Ό 탐색 μ•Œκ³ λ¦¬μ¦˜μž…λ‹ˆλ‹€.
  6 */
  7
  8#include <iostream>
  9#include <vector>
 10#include <queue>
 11#include <stack>
 12#include <unordered_set>
 13#include <algorithm>
 14
 15using namespace std;
 16
 17// =============================================================================
 18// 1. κ·Έλž˜ν”„ ν‘œν˜„
 19// =============================================================================
 20
 21// 인접 리슀트
 22class AdjacencyList {
 23public:
 24    int V;
 25    vector<vector<int>> adj;
 26    bool directed;
 27
 28    AdjacencyList(int v, bool dir = false) : V(v), adj(v), directed(dir) {}
 29
 30    void addEdge(int u, int v) {
 31        adj[u].push_back(v);
 32        if (!directed) {
 33            adj[v].push_back(u);
 34        }
 35    }
 36
 37    void print() {
 38        for (int i = 0; i < V; i++) {
 39            cout << i << ": ";
 40            for (int neighbor : adj[i]) {
 41                cout << neighbor << " ";
 42            }
 43            cout << endl;
 44        }
 45    }
 46};
 47
 48// 인접 ν–‰λ ¬
 49class AdjacencyMatrix {
 50public:
 51    int V;
 52    vector<vector<int>> matrix;
 53
 54    AdjacencyMatrix(int v) : V(v), matrix(v, vector<int>(v, 0)) {}
 55
 56    void addEdge(int u, int v, int weight = 1) {
 57        matrix[u][v] = weight;
 58        matrix[v][u] = weight;  // 무방ν–₯
 59    }
 60
 61    void print() {
 62        for (int i = 0; i < V; i++) {
 63            for (int j = 0; j < V; j++) {
 64                cout << matrix[i][j] << " ";
 65            }
 66            cout << endl;
 67        }
 68    }
 69};
 70
 71// =============================================================================
 72// 2. DFS (깊이 μš°μ„  탐색)
 73// =============================================================================
 74
 75void dfsRecursive(const vector<vector<int>>& adj, int node, vector<bool>& visited, vector<int>& result) {
 76    visited[node] = true;
 77    result.push_back(node);
 78
 79    for (int neighbor : adj[node]) {
 80        if (!visited[neighbor]) {
 81            dfsRecursive(adj, neighbor, visited, result);
 82        }
 83    }
 84}
 85
 86vector<int> dfs(const vector<vector<int>>& adj, int start) {
 87    int n = adj.size();
 88    vector<bool> visited(n, false);
 89    vector<int> result;
 90    dfsRecursive(adj, start, visited, result);
 91    return result;
 92}
 93
 94// 반볡적 DFS
 95vector<int> dfsIterative(const vector<vector<int>>& adj, int start) {
 96    int n = adj.size();
 97    vector<bool> visited(n, false);
 98    vector<int> result;
 99    stack<int> st;
100
101    st.push(start);
102
103    while (!st.empty()) {
104        int node = st.top();
105        st.pop();
106
107        if (visited[node]) continue;
108        visited[node] = true;
109        result.push_back(node);
110
111        for (auto it = adj[node].rbegin(); it != adj[node].rend(); ++it) {
112            if (!visited[*it]) {
113                st.push(*it);
114            }
115        }
116    }
117
118    return result;
119}
120
121// =============================================================================
122// 3. BFS (λ„ˆλΉ„ μš°μ„  탐색)
123// =============================================================================
124
125vector<int> bfs(const vector<vector<int>>& adj, int start) {
126    int n = adj.size();
127    vector<bool> visited(n, false);
128    vector<int> result;
129    queue<int> q;
130
131    q.push(start);
132    visited[start] = true;
133
134    while (!q.empty()) {
135        int node = q.front();
136        q.pop();
137        result.push_back(node);
138
139        for (int neighbor : adj[node]) {
140            if (!visited[neighbor]) {
141                visited[neighbor] = true;
142                q.push(neighbor);
143            }
144        }
145    }
146
147    return result;
148}
149
150// BFS μ΅œλ‹¨ 거리
151vector<int> bfsDistance(const vector<vector<int>>& adj, int start) {
152    int n = adj.size();
153    vector<int> dist(n, -1);
154    queue<int> q;
155
156    q.push(start);
157    dist[start] = 0;
158
159    while (!q.empty()) {
160        int node = q.front();
161        q.pop();
162
163        for (int neighbor : adj[node]) {
164            if (dist[neighbor] == -1) {
165                dist[neighbor] = dist[node] + 1;
166                q.push(neighbor);
167            }
168        }
169    }
170
171    return dist;
172}
173
174// =============================================================================
175// 4. μ—°κ²° μš”μ†Œ
176// =============================================================================
177
178int countConnectedComponents(int n, const vector<vector<int>>& adj) {
179    vector<bool> visited(n, false);
180    int count = 0;
181
182    for (int i = 0; i < n; i++) {
183        if (!visited[i]) {
184            count++;
185            queue<int> q;
186            q.push(i);
187            visited[i] = true;
188
189            while (!q.empty()) {
190                int node = q.front();
191                q.pop();
192                for (int neighbor : adj[node]) {
193                    if (!visited[neighbor]) {
194                        visited[neighbor] = true;
195                        q.push(neighbor);
196                    }
197                }
198            }
199        }
200    }
201
202    return count;
203}
204
205// =============================================================================
206// 5. 사이클 탐지
207// =============================================================================
208
209// 무방ν–₯ κ·Έλž˜ν”„ 사이클 탐지 (DFS)
210bool hasCycleUndirected(const vector<vector<int>>& adj, int node, int parent, vector<bool>& visited) {
211    visited[node] = true;
212
213    for (int neighbor : adj[node]) {
214        if (!visited[neighbor]) {
215            if (hasCycleUndirected(adj, neighbor, node, visited)) {
216                return true;
217            }
218        } else if (neighbor != parent) {
219            return true;
220        }
221    }
222
223    return false;
224}
225
226bool detectCycleUndirected(int n, const vector<vector<int>>& adj) {
227    vector<bool> visited(n, false);
228
229    for (int i = 0; i < n; i++) {
230        if (!visited[i]) {
231            if (hasCycleUndirected(adj, i, -1, visited)) {
232                return true;
233            }
234        }
235    }
236
237    return false;
238}
239
240// λ°©ν–₯ κ·Έλž˜ν”„ 사이클 탐지 (DFS)
241bool hasCycleDirected(const vector<vector<int>>& adj, int node, vector<int>& color) {
242    color[node] = 1;  // λ°©λ¬Έ 쀑 (νšŒμƒ‰)
243
244    for (int neighbor : adj[node]) {
245        if (color[neighbor] == 1) {  // ν˜„μž¬ DFS κ²½λ‘œμ—μ„œ 발견
246            return true;
247        }
248        if (color[neighbor] == 0 && hasCycleDirected(adj, neighbor, color)) {
249            return true;
250        }
251    }
252
253    color[node] = 2;  // μ™„λ£Œ (검은색)
254    return false;
255}
256
257bool detectCycleDirected(int n, const vector<vector<int>>& adj) {
258    vector<int> color(n, 0);  // 0: λ―Έλ°©λ¬Έ, 1: λ°©λ¬Έ 쀑, 2: μ™„λ£Œ
259
260    for (int i = 0; i < n; i++) {
261        if (color[i] == 0 && hasCycleDirected(adj, i, color)) {
262            return true;
263        }
264    }
265
266    return false;
267}
268
269// =============================================================================
270// 6. 이뢄 κ·Έλž˜ν”„ 검사
271// =============================================================================
272
273bool isBipartite(const vector<vector<int>>& adj) {
274    int n = adj.size();
275    vector<int> color(n, -1);
276
277    for (int start = 0; start < n; start++) {
278        if (color[start] != -1) continue;
279
280        queue<int> q;
281        q.push(start);
282        color[start] = 0;
283
284        while (!q.empty()) {
285            int node = q.front();
286            q.pop();
287
288            for (int neighbor : adj[node]) {
289                if (color[neighbor] == -1) {
290                    color[neighbor] = 1 - color[node];
291                    q.push(neighbor);
292                } else if (color[neighbor] == color[node]) {
293                    return false;
294                }
295            }
296        }
297    }
298
299    return true;
300}
301
302// =============================================================================
303// ν…ŒμŠ€νŠΈ
304// =============================================================================
305
306void printVector(const vector<int>& v) {
307    cout << "[";
308    for (size_t i = 0; i < v.size(); i++) {
309        cout << v[i];
310        if (i < v.size() - 1) cout << ", ";
311    }
312    cout << "]";
313}
314
315int main() {
316    cout << "============================================================" << endl;
317    cout << "κ·Έλž˜ν”„ 기초 예제" << endl;
318    cout << "============================================================" << endl;
319
320    // ν…ŒμŠ€νŠΈ κ·Έλž˜ν”„ 생성
321    //   0 --- 1
322    //   |     |
323    //   2 --- 3
324    //         |
325    //         4
326    int n = 5;
327    vector<vector<int>> adj(n);
328    adj[0] = {1, 2};
329    adj[1] = {0, 3};
330    adj[2] = {0, 3};
331    adj[3] = {1, 2, 4};
332    adj[4] = {3};
333
334    // 1. DFS
335    cout << "\n[1] DFS (깊이 μš°μ„  탐색)" << endl;
336    auto dfsResult = dfs(adj, 0);
337    cout << "    0μ—μ„œ μ‹œμž‘: ";
338    printVector(dfsResult);
339    cout << endl;
340
341    // 2. BFS
342    cout << "\n[2] BFS (λ„ˆλΉ„ μš°μ„  탐색)" << endl;
343    auto bfsResult = bfs(adj, 0);
344    cout << "    0μ—μ„œ μ‹œμž‘: ";
345    printVector(bfsResult);
346    cout << endl;
347
348    auto distances = bfsDistance(adj, 0);
349    cout << "    0μ—μ„œ 각 λ…Έλ“œκΉŒμ§€ 거리: ";
350    printVector(distances);
351    cout << endl;
352
353    // 3. μ—°κ²° μš”μ†Œ
354    cout << "\n[3] μ—°κ²° μš”μ†Œ" << endl;
355    vector<vector<int>> disconnected(6);
356    disconnected[0] = {1};
357    disconnected[1] = {0};
358    disconnected[2] = {3};
359    disconnected[3] = {2};
360    disconnected[4] = {5};
361    disconnected[5] = {4};
362    cout << "    μ—°κ²° μš”μ†Œ 개수: " << countConnectedComponents(6, disconnected) << endl;
363
364    // 4. 사이클 탐지
365    cout << "\n[4] 사이클 탐지" << endl;
366    cout << "    무방ν–₯ κ·Έλž˜ν”„ 사이클: " << (detectCycleUndirected(n, adj) ? "있음" : "μ—†μŒ") << endl;
367
368    vector<vector<int>> directedAdj(4);
369    directedAdj[0] = {1};
370    directedAdj[1] = {2};
371    directedAdj[2] = {3};
372    directedAdj[3] = {1};  // 사이클
373    cout << "    λ°©ν–₯ κ·Έλž˜ν”„ 사이클: " << (detectCycleDirected(4, directedAdj) ? "있음" : "μ—†μŒ") << endl;
374
375    // 5. 이뢄 κ·Έλž˜ν”„
376    cout << "\n[5] 이뢄 κ·Έλž˜ν”„" << endl;
377    cout << "    ν˜„μž¬ κ·Έλž˜ν”„: " << (isBipartite(adj) ? "이뢄 κ·Έλž˜ν”„" : "이뢄 κ·Έλž˜ν”„ μ•„λ‹˜") << endl;
378
379    // 6. λ³΅μž‘λ„ μš”μ•½
380    cout << "\n[6] λ³΅μž‘λ„ μš”μ•½" << endl;
381    cout << "    | μ•Œκ³ λ¦¬μ¦˜        | μ‹œκ°„λ³΅μž‘λ„ | κ³΅κ°„λ³΅μž‘λ„ |" << endl;
382    cout << "    |-----------------|------------|------------|" << endl;
383    cout << "    | DFS             | O(V + E)   | O(V)       |" << endl;
384    cout << "    | BFS             | O(V + E)   | O(V)       |" << endl;
385    cout << "    | μ—°κ²° μš”μ†Œ       | O(V + E)   | O(V)       |" << endl;
386    cout << "    | 사이클 탐지     | O(V + E)   | O(V)       |" << endl;
387
388    cout << "\n============================================================" << endl;
389
390    return 0;
391}