[C++로 배우는 알고리즘과 자료구조] Day 11: 그래프의 기본 개념

그래프 (Graph)

그래프는 노드(정점, Vertex)와 간선(Edge)으로 구성된 자료구조로, 여러 노드가 간선으로 연결된 형태를 가집니다. 그래프는 다양한 문제를 모델링하고 해결하는 데 사용됩니다.

그래프의 구성 요소:

1. 노드 (Vertex): 그래프의 개별 요소입니다.
2. 간선 (Edge): 노드 간의 연결을 나타냅니다.

그래프의 종류:

1. 방향 그래프 (Directed Graph): 간선이 방향을 가지는 그래프입니다.
2. 무방향 그래프 (Undirected Graph): 간선이 방향을 가지지 않는 그래프입니다.
3. 가중치 그래프 (Weighted Graph): 간선에 가중치가 있는 그래프입니다.
4. 비가중치 그래프 (Unweighted Graph): 간선에 가중치가 없는 그래프입니다.

그래프의 표현 방법

그래프는 다음과 같은 방법으로 표현할 수 있습니다:

1. 인접 행렬 (Adjacency Matrix): 2차원 배열을 사용하여 그래프를 표현합니다.
2. 인접 리스트 (Adjacency List): 배열이나 리스트의 리스트를 사용하여 그래프를 표현합니다.

그래프의 표현 예제

인접 행렬 (Adjacency Matrix)

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

 

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

 

인접 리스트 (Adjacency List)

인접 리스트는 배열이나 리스트의 리스트를 사용하여 그래프를 표현합니다. 각 노드는 연결된 노드의 리스트를 가집니다.

 

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 "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;
}

 

인접 리스트 그래프 예제

#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;
}

 

설명

1. 그래프 (Graph):
   • 그래프는 노드(정점, Vertex)와 간선(Edge)으로 구성된 자료구조입니다.
   • 방향 그래프, 무방향 그래프, 가중치 그래프, 비가중치 그래프 등 다양한 종류가 있습니다.
2. 그래프의 표현 방법:
   • 인접 행렬 (Adjacency Matrix): 2차원 배열을 사용하여 그래프를 표현합니다. 노드 간의 연결 여부를 행렬의 요소로 나타냅니다.
   • 인접 리스트 (Adjacency List): 배열이나 리스트의 리스트를 사용하여 그래프를 표현합니다. 각 노드는 연결된 노드의 리스트를 가집니다.

이제 그래프의 기본 개념과 표현 방법을 이해했습니다. 다음 단계로 넘어가며, 더 복잡한 자료구조와 알고리즘을 학습해보겠습니다.

질문이나 피드백이 있으면 언제든지 댓글로 남겨 주세요. 내일은 "Day 12: 그래프 표현 방법 (인접 리스트, 인접 행렬)"에 대해 학습하겠습니다.