[Data Structures] Graph (그래프)

Graph

그래프란 노드와 간선으로 이루어진 자료구조이다.

노드 : 각 점을 나타낸다. 노드는 때로 정점이라고도 불린다.

간선 : 노드들 사이를 연결하는 선을 의미한다. 두 노드를 연결하는 관계를 나타낸다.

 

그래프는 크게 두 유형으로 나눌 수 있다.

1. 방향 그래프(Directed Graph) : 간선에 방향이 있는 그래프

2. 무방향 그래프(Undirected Graph) : 간산에 방향이 없는 그래프

 

Directed Graph

방향 그래프에서 간선 {u, v}가 있다고 하자.

노드 u는 v를 향하지만 v는 u를 향하지 않는다.

 

- in-degree : 노드로 들어오는 화살표의 개수

- out-degree : 노드에서 나가는 화살표의 개수

- 방향 그래프에서 in-degree의 합과 out-degree의 합은 같고 이는 간선의 개수를 나타낸다.

 

Undirected Graph

무방향 그래프에서 간선 {u, v}가 있다고 하자.

노드 u는 v를 향하고 v도 u를 향한다고 취급하고, 굳이 방향성을 취급하지 않는다.

 

Weighted Graph

간선 상에 가중치가 주어지는 그래프

Connectivity of Graphs

방향 그래프가 있을 때.

- Path : 두 노드를 포함하고 그 사이에 있는 노드들의 sequence이다.

- Length of path : 그 노드들은 연결하는 간선의 개수이다.

- Cycle : 시작한 노드에서 출발하여 한번 이상의 간선을 따라 다른 노드를 방문한 후 다시 처음 시작한 노드로 돌아오는 path를 의미한다.

- Simple path : 첫번째와 마지막 노드를 제외한 모든 모드가 서로 다른 Path <- Cycle은 Simple path이다.

- DAG(Directed Acyclic Graph) : 사이클이 존재하지 않는 방향 그래프

- Strongly Connected Graph : 모든 노드 중 두 노드 a, b에 대하여 a에서 b로의 path가 존재할 때, b에서 a로의 path가 존재하는 그래프

- Weakly Connected Graph : 모든 노드 중 두 노드 a, b에 대하여 a에서 b로의 path가 존재할 때, b에서 a로의 path는 존재하지 않는 경우가 적어도 하나라도 있는 그래프

 

Graph representation : Adjacency Matrices (인접 행렬)

A[u][v]는 u에서 v로의 간선의 존재 및 가중치를 의미한다.

이 방법은 V^2 만큼의 공간을 필요로 하기 때문에 간선이 V^2에 근접할 정도로 많을 때 사용하면 좋다.

 

Graph representation : Adjacency Lists (인접 리스트)

노드 u가 v로 향한다면 A[u]에 v를 추가하는 방식이다.

이 방법은 E + V의 공간을 필요로 하기 때문에 간선이 그리 많지 않을 때 사용하면 좋다.

 

Implementation of Adjacency Matrix Graph

#include <iostream>
using namespace std;

int V, E;
int A[101][101];

void input()
{
    cin >> V >> E;

    for (int i = 1; i <= E; i++)
    {
        int u, v;
        // int w;
        cin >> u >> v;
        // cin >> w;

        // Directed Graph
        A[u][v] = 1;

        // Diredted Weighted Graph
        // A[u][v] = w;

        // Undirected Graph
        // A[u][v] = 1;
        // A[v][u] = 1;

        // Undirected Weighted Graph
        // A[u][v] = w;
        // A[v][u] = w;
    }
}

void output()
{
    for (int i = 1; i <= V; i++)
    {
        for (int j = 1; j <= V; j++)
        {
            if (A[i][j] != 0)
            {
                // Unweighted Graph
                cout << i << " -> " << j << endl;

                // Weighted Graph
                // cout << i << " -> " << j << " (" << A[i][j] << ")" << endl;
            }
        }
    }
}

int main(void)
{
    input();
    output();
    return 0;
}

 

Implementation of Adjacency List Graph

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

int V, E;
vector<int> A[101];
vector<pair<int, int>> Aw[101];

void input()
{
    cin >> V >> E;

    for (int i = 1; i <= E; i++)
    {
        int u, v;
        // int w;
        cin >> u >> v;
        // cin >> w;

        // Directed Graph
        A[u].push_back(v);

        // Diredted Wighted Graph
        // Aw[u].push_back({v, w});

        // Undirected Graph
        // A[u].push_back(v);
        // A[v].push_back(u);

        // Undirected Weighted Graph
        // Aw[u].push_back({v, w});
        // Aw[v].push_back({u, w});
    }
}

void output()
{
    for (int i = 1; i <= V; i++)
    {
        // Unweighted Graph
        for (int j : A[i])
        {
            cout << i << " -> " << j << endl;
        }

        // Weighted Graph
        // for(pair<int, int> j : Aw[i])
        // {
        //     cout << i << " -> " << j.first << " (" << j.second << ")" << endl;
        // }
    }
}

int main(void)
{
    input();
    output();
    return 0;
}