[c++] 인접 행렬과 인접 리스트 구현

08 Dec 2023

그래프를 표현하는 방법에는 여러 가지가 있지만, 가장 일반적인 방법으로는 인접 행렬과 인접 리스트가 있습니다. 이 글에서는 C++을 사용하여 그래프를 인접 행렬과 인접 리스트로 구현하는 방법에 대해 알아보겠습니다.

인접 행렬 (Adjacency Matrix)

인접 행렬은 2차원 배열을 사용하여 그래프를 나타내는 방법입니다. 배열의 각 요소는 두 개의 노드 사이에 간선이 존재하는지를 나타내며, 간선이 존재하면 1로 표시하고, 존재하지 않으면 0으로 표시합니다.

#include <iostream>
#include <vector>

using namespace std;

class AdjacencyMatrix {
private:
    vector<vector<int>> graph;

public:
    AdjacencyMatrix(int n) {
        graph = vector<vector<int>>(n, vector<int>(n, 0));
    }

    void addEdge(int u, int v) {
        graph[u][v] = 1;  // 간선 추가
        graph[v][u] = 1;  // 무방향 그래프인 경우
    }

    void printGraph() {
        for (auto row : graph) {
            for (auto cell : row) {
                cout << cell << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    AdjacencyMatrix graph(5);
    graph.addEdge(0, 1);
    graph.addEdge(0, 4);
    graph.addEdge(1, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    graph.printGraph();
    return 0;
}

위와 같이 인접 행렬을 이용하면 간단하게 그래프를 표현하고, 두 노드 사이의 연결성을 빠르게 확인할 수 있습니다.

인접 리스트 (Adjacency List)

인접 리스트는 배열 대신 연결 리스트를 사용하여 그래프를 나타내는 방법입니다. 각 노드마다 인접한 노드들을 연결 리스트로 표현하는 방식입니다.

#include <iostream>
#include <list>
#include <vector>

using namespace std;

class AdjacencyList {
private:
    vector<list<int>> graph;

public:
    AdjacencyList(int n) {
        graph = vector<list<int>>(n);
    }

    void addEdge(int u, int v) {
        graph[u].push_back(v);  // 간선 추가
        graph[v].push_back(u);  // 무방향 그래프인 경우
    }

    void printGraph() {
        for (int i = 0; i < graph.size(); i++) {
            cout << "정점 " << i << "의 인접 리스트: ";
            for (auto v : graph[i]) {
                cout << v << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    AdjacencyList graph(5);
    graph.addEdge(0, 1);
    graph.addEdge(0, 4);
    graph.addEdge(1, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    graph.printGraph();
    return 0;
}

인접 리스트를 사용하면 각 노드의 인접한 노드를 탐색하는데 유용하며, 연결된 간선의 개수가 적을 때 메모리를 적게 사용하는 장점이 있습니다.

결론

인접 행렬과 인접 리스트는 각각의 장단점이 있으며, 그래프의 크기나 사용하는 알고리즘에 따라 적합한 방법을 선택해야 합니다. 이러한 그래프 표현 방법은 프로그래밍에서 널리 사용되며, 실제 응용 프로그램에서도 종종 활용됩니다.

이상으로 C++을 사용하여 인접 행렬과 인접 리스트를 구현하는 방법에 대해 알아보았습니다. 감사합니다.

참고: GeeksforGeeks - Graph and its representations