[C++로 배우는 알고리즘과 자료구조] Day 12: 그래프 표현 방법 (인접 리스트, 인접 행렬)

그래프 표현 방법

그래프는 다양한 방식으로 표현할 수 있습니다. 주요한 두 가지 방법은 인접 리스트와 인접 행렬입니다. 각 표현 방법은 공간 복잡도와 특정 연산에 대한 시간 복잡도에서 장단점이 있습니다.

인접 리스트 (Adjacency List)

인접 리스트는 그래프의 각 노드가 연결된 노드의 리스트를 가지는 방식으로 그래프를 표현합니다. 이 방법은 연결 리스트나 벡터를 사용하여 구현할 수 있습니다.

인접 리스트의 특징:

1. 공간 복잡도: (O(V + E)), 여기서 (V)는 노드의 수, (E)는 간선의 수입니다.
2. 장점: 희소 그래프(Sparse Graph)에 적합하며, 메모리 사용이 효율적입니다.
3. 단점: 두 노드 간의 연결 여부를 확인하는 데 O(V)의 시간이 소요될 수 있습니다.

인접 리스트 구현

AdjacencyListGraph.h

#ifndef ADJACENCYLISTGRAPH_H
#define ADJACENCYLISTGRAPH_H

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

class AdjacencyListGraph {
public:
    AdjacencyListGraph(int vertices);

    void addEdge(int src, int dest); // 간선 추가
    void display() const; // 그래프 출력

private:
    std::vector<std::list<int>> adjList; // 인접 리스트
    int vertices; // 정점의 개수
};

// 생성자 정의
AdjacencyListGraph::AdjacencyListGraph(int vertices)
    : vertices(vertices), adjList(vertices) {}

// 간선 추가 함수 정의
void AdjacencyListGraph::addEdge(int src, int dest) {
    adjList[src].push_back(dest);
}

// 그래프 출력 함수 정의
void AdjacencyListGraph::display() const {
    for (int i = 0; i < vertices; ++i) {
        std::cout << i << ": ";
        for (int dest : adjList[i]) {
            std::cout << dest << " ";
        }
        std::cout << std::endl;
    }
}

#endif // ADJACENCYLISTGRAPH_H

 

인접 리스트 그래프 예제

#include <iostream>
#include "AdjacencyListGraph.h"

int main() {
    AdjacencyListGraph 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);

    std::cout << "인접 리스트 그래프:" << std::endl;
    graph.display(); // 그래프 출력

    return 0;
}

 

인접 행렬 (Adjacency Matrix)

인접 행렬은 2차원 배열을 사용하여 그래프를 표현합니다. 행렬의 각 요소는 노드 간의 연결을 나타내며, 연결이 있으면 1, 없으면 0을 사용합니다. 가중치 그래프의 경우, 연결이 있으면 가중치를, 없으면 무한대 값을 사용합니다.

인접 행렬의 특징:

1. 공간 복잡도: (O(V^2)), 여기서 (V)는 노드의 수입니다.
2. 장점: 두 노드 간의 연결 여부를 O(1) 시간에 확인할 수 있습니다.
3. 단점: 공간을 많이 차지하며, 밀집 그래프(Dense Graph)에 적합합니다.

인접 행렬 구현

AdjacencyMatrixGraph.h

#ifndef ADJACENCYMATRIXGRAPH_H
#define ADJACENCYMATRIXGRAPH_H

#include <iostream>
#include <vector>

class AdjacencyMatrixGraph {
public:
    AdjacencyMatrixGraph(int vertices);

    void addEdge(int src, int dest, int weight = 1); // 간선 추가
    void display() const; // 그래프 출력

private:
    std::vector<std::vector<int>> adjMatrix; // 인접 행렬
    int vertices; // 정점의 개수
};

// 생성자 정의
AdjacencyMatrixGraph::AdjacencyMatrixGraph(int vertices)
    : vertices(vertices), adjMatrix(vertices, std::vector<int>(vertices, 0)) {}

// 간선 추가 함수 정의
void AdjacencyMatrixGraph::addEdge(int src, int dest, int weight) {
    adjMatrix[src][dest] = weight;
}

// 그래프 출력 함수 정의
void AdjacencyMatrixGraph::display() const {
    for (int i = 0; i < vertices; ++i) {
        for (int j = 0; j < vertices; ++j) {
            std::cout << adjMatrix[i][j] << " ";
        }
        std::cout << std::endl;
    }
}

#endif // ADJACENCYMATRIXGRAPH_H

 

인접 행렬 그래프 예제

#include <iostream>
#include "AdjacencyMatrixGraph.h"

int main() {
    AdjacencyMatrixGraph 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);

    std::cout << "인접 행렬 그래프:" << std::endl;
    graph.display(); // 그래프 출력

    return 0;
}

 

설명

1. 인접 리스트 (Adjacency List):
   • 인접 리스트는 그래프의 각 노드가 연결된 노드의 리스트를 가지는 방식입니다.
   • 공간 복잡도는 (O(V + E))이며, 희소 그래프(Sparse Graph)에 적합합니다.
   • 두 노드 간의 연결 여부를 확인하는 데 O(V)의 시간이 소요될 수 있습니다.
2. 인접 행렬 (Adjacency Matrix):
   • 인접 행렬은 2차원 배열을 사용하여 그래프를 표현합니다.
   • 공간 복잡도는 (O(V^2))이며, 밀집 그래프(Dense Graph)에 적합합니다.
   • 두 노드 간의 연결 여부를 O(1) 시간에 확인할 수 있습니다.

이제 그래프의 두 가지 주요 표현 방법인 인접 리스트와 인접 행렬을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 자료구조와 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 13: 이진 힙과 힙 정렬"에 대해 학습하겠습니다.