자료구조 - 그래프(2)

[그래프의 추상 자료형(ADT)]

객체 : 정점의 집합과 간선의 집합
연산 : 
    create_graph() ::= 그래프 생성
    init(g) ::= 그래프 g 초기화
    insert_vertex(g, v) ::= 그래프 g에 정점 v삽입
    insert_edge(g, u, v) ::= 그래프 g에 간선 (u, v)삽입
    delete_vertex(g, v) ::= 그래프 g의 정점 v삭제
    delete_edge(g, u, v) ::= 그래프 g의 간선 (u, v)삭제
    adjacent(v) ::= 정점 v에 인접한 정점들의 리스트 반환
    destroy_graph(g) ::= 그래프 g제거

 

 

[그래프의 표현 방법 - 인접 행렬]

2차원 배열을 사용하여 그래프를 표현합니다.

그래프의 정점 수가 n이라면 n x n인 2차원 배열인 인접 행렬의 M의 각 원소를 다음의 규칙에 의해 할당함으로써 그래프를 메모리에 표현할 수 있습니다.

if(간선(i, j)가 그래프에 존재) M[i][j] = 1,
otherwise                     M[i][j] = 0

 

 

무방향 그래프(Undirected Graph)

무방향 그래프의 인접 행렬은 대칭 행렬이 됩니다.

따라서 무방향 그래프의 경우, 배열의 상위 삼각이나 하위 삼각만 저장하면 메모리를 절약할 수 있습니다.

 

 

 

 

무방향 그래프 코드

#include <iostream>
#include <vector>

class UndirectedGraph 
{
    public:
        // 생성자: 정점의 수를 받아 인접 행렬을 초기화
        UndirectedGraph(int vertices)
            : adjMatrix(vertices, std::vector<int>(vertices, 0)) {}    

        // 간선 추가 함수
        void addEdge(int u, int v) 
        {
            adjMatrix[u][v] = 1;
            adjMatrix[v][u] = 1;
        }

        // 그래프 출력 함수
        void printGraph()
        {
            for (const auto& row : adjMatrix)
            {
                for (int val : row)
                {
                    std::cout << val << " ";
                }
                std::cout << std::endl;
            }
        }

    private:
        // 인접 행렬: 2차원 벡터
        std::vector<std::vector<int>> adjMatrix;
};

int main() 
{
    // 정점 4개의 그래프 생성
    UndirectedGraph graph(4);

    // 간선 추가
    graph.addEdge(0, 1); // A-B
    graph.addEdge(0, 3); // A-D
    graph.addEdge(1, 2); // B-C
    graph.addEdge(2, 3); // C-D

    // 그래프 출력
    std::cout << "Undirected Graph Adjacency Matrix:" << std::endl;
    graph.printGraph();

    return 0;
}

 

 

 

방향 그래프(Directed Graph)

방향 그래프의 인접 행렬에서는 두 정점 사이에 간선이 존재할 때, 그 방향을 고려하여 행렬의 원소가 1(또는 간선의 가중치)로 설정됩니다. 방향 그래프의 인접 행렬은 대칭일 필요가 없습니다.

 

 

방향 그래프 코드

#include <iostream>
#include <vector>

class DirectedGraph 
{
    public:
        // 생성자: 정점의 수를 받아 인접 행렬을 초기화
        DirectedGraph(int vertices)
            : adjMatrix(vertices, std::vector<int>(vertices, 0)) {}

        // 간선 추가 함수: u에서 v로의 간선을 추가
        void addEdge(int u, int v) 
        {
            adjMatrix[u][v] = 1;
        }

        // 그래프 출력 함수: 인접 행렬을 출력
        void printGraph()
        {
            for (const auto& row : adjMatrix)
            {
                for (int val : row)
                {
                    std::cout << val << " ";
                }
                std::cout << std::endl;
            }
        }

    private:
        // 인접 행렬: 2차원 벡터
        std::vector<std::vector<int>> adjMatrix;
};

int main() 
{
    // 정점 4개의 그래프 생성
    DirectedGraph graph(4);

    // 간선 추가
    graph.addEdge(0, 1); // A->B
    graph.addEdge(1, 2); // B->C
    graph.addEdge(2, 3); // C->D
    graph.addEdge(3, 0); // D->A

    // 그래프 출력
    std::cout << "Directed Graph Adjacency Matrix:" << std::endl;
    graph.printGraph();

    return 0;
}

 

 

 

 

[인접 행렬의 장단점]

 

장점

• 간선의 존재 여부를 O(1) 시간에 빠르게 확인할 수 있습니다.
• 정점의 차수를 계산하는 데 용이합니다.

단점

• 점의 수가 많고 간선이 적은 희소 그래프(Sparse Graph)에서는 메모리 낭비가 큽니다.
• 간선의 수가 적은 경우 공간 효율성이 낮습니다.

 

 

 

 

 

[그래프의 표현 방법 - 인접 리스트]

각 정점에 대해 그 정점과 인접한 정점들을 리스트로 저장합니다.

인접 리스트는 메모리 사용 면에서 인접 행렬보다 효율적입니다.

특히 간선의 수가 적은 희소 그래프(Sparse Graph)에서 유리합니다.

 

 

 

표현 방법

• 각 정점에 대한 리스트를 유지하는 방법입니다.
• 무방향 그래프의 경우, 각 간선 (u, v)에 대해 u의 리스트에 v를, v의 리스트에 u를 추가합니다.
• 방향 그래프의 경우, 각 간선 (u, v)에 대해 u의 리스트에만 v를 추가합니다.

 

 

 

인접 리스트로 그래프 표현 코드

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

class UndirectedGraph 
{
    public:
        // 생성자: 정점의 수를 받아 인접 리스트를 초기화
        UndirectedGraph(int vertices)
            : adjList(vertices) {}

        // 간선 추가 함수: u와 v를 연결하는 간선을 추가
        void addEdge(int u, int v)
        {
            adjList[u].push_back(v);
            adjList[v].push_back(u); // 무방향 그래프이므로 대칭적으로 추가
        }

        // 그래프 출력 함수: 인접 리스트를 출력
        void printGraph() 
        {
            for (int i = 0; i < adjList.size(); ++i) 
            {
                std::cout << "Vertex " << i << ":";
                for (int v : adjList[i])
                {
                    std::cout << " -> " << v;
                }
                std::cout << std::endl;
            }
        }

    private:
        // 인접 리스트: 각 정점에 대해 연결된 정점들을 리스트로 저장
        std::vector<std::list<int>> adjList;
};

int main() 
{
    // 정점 4개의 그래프 생성
    UndirectedGraph graph(4);

    // 간선 추가
    graph.addEdge(0, 1); // A-B
    graph.addEdge(0, 3); // A-D
    graph.addEdge(1, 2); // B-C
    graph.addEdge(2, 3); // C-D

    // 그래프 출력
    std::cout << "Undirected Graph Adjacency List:" << std::endl;
    graph.printGraph();

    return 0;
}