Chapter 13. 그래프(Graph)

Def) 그래프(Graph)

  - 개체 간의 연결 관계를 표현할 수 있는 비선형 자료구조

  - ex. 도시들 간의 연결, 지하철 노선도, SNS 친구 관계도 등

 

Note) 그래프의 구성 요소

  - 그래프 G = (V, E)

  - 정점 V(Vertex, Node)

    그래프를 구성하는 기본 단위. 노드.

    데이터를 저장하거나 상태를 표현

  - 엣지 E(Edge, Link)

    정점과 정점을 잇는 선. 간선.

    방향을 가질 수도 있음.

    가중치(Weight)를 가질 수도 있음.

 

Note) 그래프 관련 용어

가중치(Weight)	엣지에 부여된 수치. 비용(Cost)
인접 정점(Adjacent Vertex)	엣지로 연결되어 있는 정점
차수(Degree)	정점에 연결된 다른 정점의 개수
경로(Path)	- 특정 정점에서 다른 정점으로 이동하는 방법을    인접 정점의 나열로 표현한 것. - 경로 상에 특정 정점이 중복되지 않는 경로를   단순 경로(Simple Path)라 함.
사이클(Cycle)	시작 정점과 마지막 정점이 같은 단순 경로. 즉, 트리는 사이클이 없는 그래프라 할 수 있음.
방향 그래프(Directed Graph)	- 엣지에 방향이 있는 그래프.   == 유향 그래프, 네트워크(Network) - 방향 그래프에서 엣지(u, v)는   정점 u에서 정점 v로 이동하는 엣지를 나타냄.   단, (u, v) != (v, u)
가중치 그래프(Weighted Graph)	엣지에 가중치가 부여되어 있는 그래프
서브 그래프(Sub-Graph)	주어진 그래프에서 정점과 간선 일부를 제외하여 만든 그래프. 부분 그래프.

 

Def) 인접 행렬

  - 정점 갯수가 N인 경우, N by N 크기의 2차원 행렬로

    정점의 인접 관계를 표현하는 방법

  - adj[u][v]: 노드 u에서 노드 v로 가는 간선이 있다면 1, 없다면 0

  - 그래프 정점 개수가 적고, 엣지가 많을 때 유리.

    정점 개수가 많을 수록, 엣지가 적을수록 공간이 낭비되게 됨.

    공간 복잡도는 O(N^2)

 

Ex) 무방향 그래프의 인접 행렬

  무방향 그래프의 경우, 대각원소를 기준으로 

  서로 대칭인 형태의 인접 행렬이 만들어짐.

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

enum {
    FALSE = 0,
    TRUE = 1,
    INVALIED_INDEX = -1,
    MAX_COUNT = 101	
};

int g_nAdjMatrix[MAX_COUNT][MAX_COUNT] = { 0, };
int g_nVisitMatrix[MAX_COUNT] = { 0, };
size_t g_uVertexCount, g_uEdgeCount, g_uStartVertex = 1;

int main(void)
{
    size_t i, j, uVertex1, uVertex2;
    scanf("%zu %zu", &g_uVertexCount, &g_uEdgeCount);

    for (i = 1; i <= g_uEdgeCount; ++i)
    {
        scanf("%zu %zu", &uVertex1, &uVertex2);
        g_nAdjMatrix[uVertex1][uVertex2] = TRUE;
        g_nAdjMatrix[uVertex2][uVertex1] = TRUE;
    }

    for (i = 1; i <= g_uVertexCount; ++i)
    {
        for (j = 1; j <= g_uVertexCount; ++j)
        {
            printf("%d ", g_nAdjMatrix[i][j]);
        }
        printf("\n");
    }

    return 0;
}

 

Ex) 방향 그래프의 인접 행렬

  방향 그래프의 경우, 특정 정점에서 다른 정점으로

  이동이 가능한 경우에만 1로 표시함.

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

enum {
    FALSE = 0,
    TRUE = 1,
    INVALIED_INDEX = -1,
    MAX_COUNT = 101
};

int g_nAdjMatrix[MAX_COUNT][MAX_COUNT] = { 0, };
int g_nVisitMatrix[MAX_COUNT] = {0,};
size_t g_uVertexCount, g_uEdgeCount, g_uStartVertex = 1;

int main(void)
{
    size_t i, j, uVertex1, uVertex2;

    scanf("%zu %zu", &g_uVertexCount, &g_uEdgeCount);
    for (i = 1; i <= g_uEdgeCount; ++i)
    {
        scanf("%zu %zu", &uVertex1, &uVertex2);
        g_nAdjMatrix[uVertex1][uVertex2] = TRUE;
    }

    for (i = 1; i <= g_uVertexCount; ++i)
    {
        for (j = 1; j <= g_uVertexCount; ++j)
        {
            printf("%d ", g_nAdjMatrix[i][j]);
        }
        printf("\n");
    }

    return 0;
}

Ex) 가중치 무방향 그래프의 인접 행렬

  가중치 무방향 그래프의 경우, 이동이 가능한 경우에는

  가중치를 저장하고, 불가능한 경우에는 극한값을 저장함.

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <limits.h>

enum {
    ...
};

int main(void)
{
    int adjMatrix[MAX_COUNT][MAX_COUNT] = {0,};
    size_t i, j, uVertexCount, uEdgeCount, uVertex1, uVertex2, uWeight;

    scanf("%zu %zu", &uVertexCount, &uEdgeCount);
    for (i = 1; i <= uVertexCount; ++i)
    {
        for (j = 1; j <= uVertexCount; ++j)
        {
            adjMatrix[i][j] = INT_MAX;
        }
    }

    for (i = 1; i <= uEdgeCount; ++i)
    {
        scanf("%zu %zu %zu", &uVertex1, &uVertex2, &uWeight);
        adjMatrix[uVertex1][uVertex2] = uWeight;
        adjMatrix[uVertex2][uVertex1] = uWeight;
    }

    for (i = 1; i <= uVertexCount; ++i)
    {
        for (j = 1; j <= uVertexCount; ++j)
        {
            if (INT_MAX == adjMatrix[i][j])
            {
                printf("INT_MAX ");
            }
            else
            {
                printf("%7d ", adjMatrix[i][j]);
            }
            
        }
        printf("\n");
    }	

    return 0;
}

   

Def) 인접 리스트

  - 각 정점에 인접한 정점들을 연결 리스트로 구현하는 방법

  - 보통 정점 개수에 해당하는 배열의 각 원소에

    연결 리스트가 속해 있는 형태로 구현

  - 정점 갯수가 N이고, 엣지 갯수가 M일 때,

    공간 복잡도는 O(N + M). 

 

Note) 무방향 그래프와 방향 그래프의 인접 리스트

  - 무방향 그래프의 경우, 공간 복잡도는 O(2M)

  - 방향 그래프의 경우, 공간 복잡도는 O(M)

 

Def) 엣지 리스트

  - 모든 엣지 (u, v)를 연결 리스트 또는 배열로 구현하는 방법

  - 엣지의 개수가 M일 때, 공간 복잡도는 O(M)