22.3. 프로그램언어 C++에서의 그래프 알고리즘

by

프로그램언어 C++의 깊이 우선 탐색 (DFS)

깊이 우선 탐색(DFS)은 그래프나 트리 구조에서 한 노드로부터 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 알고리즘입니다. 이 알고리즘은 스택 또는 재귀 함수를 사용하여 구현할 수 있습니다.

아래는 C++로 구현된 깊이 우선 탐색(DFS)의 간단한 예제 코드입니다.


#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> graph;
vector<bool> visited;

void dfs(int node) {
    visited[node] = true;
    cout << node << " ";

    for (int i = 0; i < graph[node].size(); ++i) {
        int nextNode = graph[node][i];
        if (!visited[nextNode]) {
            dfs(nextNode);
        }
    }
}

int main() {
    int n = 6; // 노드의 개수
    graph.resize(n);
    visited.resize(n, false);

    // 그래프 정보 입력
    graph[0].push_back(1);
    graph[0].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(4);
    graph[2].push_back(5);

    cout << "DFS 순서: ";
    dfs(0);

    return 0;
}

프로그램언어 C++의 너비 우선 탐색 (BFS)

C++의 너비 우선 탐색 (BFS)에 대한 설명

BFS(너비 우선 탐색)는 그래프나 트리 구조에서 가까운 노드부터 순차적으로 탐색하는 알고리즘입니다. BFS는 큐(Queue) 자료구조를 사용하여 구현됩니다. 먼저 시작 노드를 큐에 넣고, 해당 노드와 인접한 노드들을 모두 방문한 후에는 그 인접한 노드들을 큐에 순서대로 넣어가며 탐색을 진행합니다. 이러한 방식으로 레벨 단위로 탐색을 수행하며, 최단 경로 문제나 최단 거리를 구하는 데 유용하게 활용됩니다.

예제 코드


#include 
#include 
#include 

using namespace std;

void bfs(vector>& graph, int start) {
    vector visited(graph.size(), false);
    queue q;

    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        cout << current << " ";

        for (int neighbor : graph[current]) {
            if (!visited[neighbor]) {
                q.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

int main() {
    vector> graph = {{1, 2}, {0, 3, 4}, {0, 5}, {1}, {1}, {2}};
    bfs(graph, 0);

    return 0;
}

프로그램언어 C++의 최소 신장 트리 (MST)

프로그램언어 C++의 최소 신장 트리 (Minimum Spanning Tree, MST)는 그래프 이론에서 중요한 개념입니다. MST는 주어진 가중치가 있는 연결된 무방향 그래프에서 모든 정점을 포함하면서 그 가중치의 합이 최소가 되는 트리를 의미합니다.

최소 신장 트리를 찾는 대표적인 알고리즘으로는 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘이 있습니다. 크루스칼 알고리즘은 간선을 가중치의 오름차순으로 정렬한 뒤, 사이클을 형성하지 않는 간선을 선택하여 트리를 구성하는 방식입니다. 반면 프림 알고리즘은 하나의 정점을 시작으로 해당 정점과 연결된 간선 중 최소 가중치를 선택하여 트리를 확장해가는 방식입니다.

아래는 C++로 구현된 크루스칼 알고리즘을 통해 최소 신장 트리를 찾는 예제 코드입니다.


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int src, dest, weight;
};

struct Graph {
    int V, E;
    vector<Edge> edges;
};

struct Subset {
    int parent, rank;
};

int find(vector<Subset> subsets, int i) {
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
}

void Union(vector<Subset> &subsets, int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);

    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
    else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}

void KruskalMST(Graph graph) {
    int V = graph.V;
    vector<Edge> result;
    vector<Subset> subsets(V);

    for (int v = 0; v < V; v++) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }

    sort(graph.edges.begin(), graph.edges.end(), [](Edge a, Edge b) {
        return a.weight < b.weight;
    });

    int e = 0, i = 0;
    while (e < V - 1) {
        Edge next_edge = graph.edges[i++];

        int x = find(subsets, next_edge.src);
        int y = find(subsets, next_edge.dest);

        if (x != y) {
            result.push_back(next_edge);
            Union(subsets, x, y);
            e++;
        }
    }

    for (Edge edge : result) {
        cout << edge.src << " - " << edge.dest << " : " << edge.weight << endl;
    }
}

int main() {
    Graph graph = {4, 5, {{0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}}};
    KruskalMST(graph);

    return 0;
}

프로그램언어 C++의 다익스트라 (Dijkstra)

다익스트라 알고리즘은 그래프에서 한 출발점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 가중치가 있는 그래프에서 사용되며, 음수 가중치를 포함하고 있지 않을 때 최적의 해를 찾을 수 있습니다.

다익스트라 알고리즘의 동작 과정:

  1. 출발 노드를 선택하고 해당 노드까지의 거리를 0으로 설정하고, 다른 노드까지의 거리를 무한대로 초기화합니다.
  2. 아직 처리하지 않은 노드 중에서 출발 노드까지의 거리가 가장 짧은 노드를 선택합니다.
  3. 선택한 노드를 경유지로 하여 다른 노드까지의 거리를 갱신합니다. (더 짧은 거리로 업데이트)
  4. 모든 historians. is of Real

    of of of of of of of of of 202 of of

    프로그램언어 C++의 벨만-포드 (Bellman-Ford)

    벨만-포드 (Bellman-Ford) 알고리즘은 그래프 내의 음수 가중치를 가지는 간선이 존재할 때도 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 다익스트라 알고리즘과 달리 음수 가중치를 처리할 수 있으나, 시간 복잡도가 더 높습니다.

    아래는 C++로 구현된 벨만-포드 알고리즘의 간단한 예제 코드입니다. 이 코드는 음수 사이클이 없는 경우에만 정상적으로 동작합니다. 

    
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

struct Edge {
    int source, destination, weight;
};

void bellmanFord(vector<Edge> edges, int V, int E, int start) {
    vector<int> distance(V, INT_MAX);
    distance[start] = 0;

    for (int i = 0; i < V - 1; ++i) {
        for (int j = 0; j < E; ++j) {
            int u = edges[j].source;
            int v = edges[j].destination;
            int weight = edges[j].weight;
            if (distance[u] != INT_MAX && distance[u] + weight < distance[v]) {
                distance[v] = distance[u] + weight;
            }
        }
    }

    for (int i = 0; i < E; ++i) {
        int u = edges[i].source;
        int v = edges[i].destination;
        int weight = edges[i].weight;
        if (distance[u] != INT_MAX && distance[u] + weight < distance[v]) {
            cout << "Graph contains negative weight cycle" << endl;
            return;
        }
    }

    cout << "Vertex Distance from Source" << endl;
    for (int i = 0; i < V; ++i) {
        cout << i << " " << distance[i] << endl;
    }
}

int main() {
    int V = 5; // 정점의 수
    int E = 8; // 간선의 수
    vector<Edge> edges = {
        {0, 1, -1},
        {0, 2, 4},
        {1, 2, 3},
        {1, 3, 2},
        {1, 4, 2},
        {3, 2, 5},
        {3, 1, 1},
        {4, 3, -3}
    };

    bellmanFord(edges, V, E, 0);

    return 0;
}

Leave a Comment