그래프의 표현과 정의

트리 : 선형으로 표현하기 힘든 계층 구조를 표현하기 위해 고안

 

그래프는 계층적인 구조보다 좀더 일반적이고 강력한 자료구조이다.

현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현

ex) 여려 도시를 연결하는 도로망, 사람들 간의 지인 관계, 웹사이트 간의 링크 관계 등의 연결 구조

 

트리와의 차이 => 트리는 부모-자식 관계에 대한 제약이 존재하나 그래프는 부모-자식 관계와 같은 제약이 없음

 

그래프의 정의

어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료 구조

정점과 간선으로 정의되며 정점의 위치, 간선의 순서 등은 그래프에 정의에 포함되지 않음. 

 

그래프의 종류

표현하고자 하는 대상에 따라 여러 가지 변형된 형태가 존재

 

간선이 가진 속성에 따른 분류

• 방향 그래프(directed graph) 
  
  • 각 각선은 방향 속성을 가짐. 정점 u에서 v로의 간선과 v에서 u로의 간선은 서로 다름
  • 예) 짝사랑 관계, 도로망에서 일방 통행 등
• 무향 그래프(undirected grah) : 방향 그래프와 반대로 간선에 방향 속성이 없음
• 가중치 그래프(weighted graph) 
  • 각 간선에 가중치(weight)라는 실수 속성을 부여
  • 가중치 적용 예 : 두 도시 사이의 거리, 두 물건 사이의 교환 비율, 두 사람 사이의 호감도 등
  • 관련 문제 : 최소 스패닝 트리, 최단 경로 문제

그래프의 형태에 따른 분류

• 다중 그래프(multigraph)
  • 두 정점 사이에 두 개 이상의 간선이 존재 가능
  • 예) 도로망의 경우 두 지점을 잇는 2개 이상의 도로가 있을 수 있으므로 다중 그래프 적용 가능
• 단순 그래프(simple graph)
  • 두 정점 사이에 최대 한 개의 간선만 존재

루트 없는 트리(unrooted tree) : 부모 자식 관계는 없지만 연결 관계는 트리와 같은 무향 그래프

여기서 간선들의 연결 관계가 트리와 같다는 말은 간선을 통해 두 정점을 잇는 방법이 하나밖에 없다는 의미

 

• 이분 그래프(bipartite graph)
  • 정점들을 겹치지 않는 두 개의 그룹으로 나눠서 서로 다른 그룹에 속한 정점들 간에만 간선이 존재할 수 있는 그래프
  • ex) 멘토-멘티를 그래프로 표현 :  두 사람이 멘토-멘티로써 함께 활동 하면 두 정점 사이에 간선이 있도록 함
  • 이 그래프를 멘토와 멘티로 나누면 간선은 항상 두 그룹 사이에만 존재
• 사이클 없는 방향 그래프(DAG, directed acyclic graph)
  • 방향 그래프의 일종
  • 사이클이 없음 => 한 점에서 출발해 자기 자신으로 돌아오는 경로(사이클)가 존재하지 않음
  • 여러 작업들 간의 상호 의존 관계 등을 그래프로 표현 시 적용 가능

그래프의 경로

경로 : 끝과 끝이 서로 연결된 간선들을 순서대로 나열한 것

방향 그래프의 경우 앞 간선의 끝점이 뒷 간선의 시작점과 만나야 함

단순 경로(simple path) : 경로 중 한 정점을 최대 한 번만 지나는 경로

 

그래프의 사용 예

• 철도망의 안정성 분석

어떤 철도망에서 한 역이 폐쇄되어 열차가 지나지 못할 경우 철도망 전체가 두 개 이상으로 쪼개질 가능성이 있는지, 만약 있다면 어느 역이 그런 위험성을 갖는지 분석

 

정점 : 철도의 각 역

간선 : 두 역 사이를 연결하는 철로들

문제 해결 : 그래프 + 절단점 찾기 알고리즘

 

• 소셜 네트워크 분석

사람들 간의 지인/친밀도 관계 분석

정점 : 사이트의 회원들

간선 : 두 회원이 서로 친구 사이인 경우 연결

문제 해결 : 그래프 너비 우선 탐색 => 한 다리 건너 알고 있는 사람 수, 몇 다리 건너야 특정 사람을 알게 되는 지 등의 문제 해결

 

• 인터넷 전송 속도 계산

수많은 컴퓨터와 라우터들이 네트워크로 연결되어 있는 인터넷

정점 : 라우터와 컴퓨터

간선 : 두 기계를 연결하는 케이블

 

문제 상황 : 두 컴퓨터 간 전송용량 구하기, 경로의 시간당 전송 용량 = 경로가 지나는 케이블 중 가장 작은 전송 용량을 갖는 케이블에 좌우

문제 해결 : 최소 스패닝 트리 알고리즘 응용

 

• 한 붓 그리기

종이에서 연필을 떼지 않고 주어진 도형을 그리되, 모든 선을 한 번씩만 지나는게 가능한지

정점 : 선들이 만나는 점들

간선 : 점들을 연결하는 선들

=> 그래프의 모든 간선을 한 번씩만 지나는 경로를 찾기

문제 해결 : 오일러 경로(Eulerian path), 깊이 우선 탐색 응용

 

• 외환 거래

외환 거래 시장은 달러, 유로, 엔, 프랑 등의 통화와 이들 간의 교환 비율로 구성된다.

1달러를 유로로 바꾸고, 유로를 엔으로, 다시 엔화를 달러로 환전하였을 때 1달러보다 많은 돈을 가지게 되는 것을 아비트러지라한다.

환율 목록이 주어질 때 목록에 아비트러지 존재 여부 구하기

정점 : 각 통화

간선 : 서로 교환 가능한 통화들 사이(방향 그래프)

u에서 v로 가는 간선의 가중치 : 두 통화 간의 교환 비율

ex) 1달러가 1000원이라면 달러에서 원으로 가는 가중치는 1000

 

아비트러지가 존재하는 경우 : 어떤 사이클에 포함된 간선의 가중치를 전부 곱했을 때 1을 초과하는 값이 되어야함

양변에 로그를 씌우고 -1을 곱하는 식의 변형을 통해 간선 가중치의 합이 음수인 사이클이 존재하면  아비트러지가 존재 함을 알 수 있음

문제 해결 : 최단 거리 알고리즘(가중치의 합이 음수인 사이클 찾기)

 

암시적 그래프 구조들

그래프 같은 형태를 갖는 구조가 아니라도 그래프를 통해서 표현하면 쉽게 해결할 수 있는 경우들이 있다.

• 할 일 목록 정리

외출을 하려면 외출복을 입어야 하고, 외출복을 입으려면 외출복을 빨아야 하고, 외출복을 빨려면 세제가 있어야 하고, 세제를 사려면 외출을 해야하는 서로 의존 관계에 있는 일들이 존재하는 경우. 

한 번에 하나씩 해 나갈 방법이 있는지, 어느 순서대로 하면 되는지를 계산 => 위상 정렬(topological sorting)

문제 해결 : 깊이 우선 탐색 응용

• 15-퍼즐

4x4 크기의 게임판에 1부터 15까지의 숫자가 적힌 열다섯 개의 타일이 끼워져 있고, 이 타일들을 최소로 움직여 원래 있던 순서대로 정렬

정점 : 게임판에서 현재 타일의 배치

간선 : 한 배치에서 타일을 한 번 움직여 다른 배치를 얻을 수 있을 때의 두 정점을 연결

그래프 상에서 두 점 사이를 잇는 가장 짧은 경로를 구하기 

 

• 게임판 덮기 

NxN 게임판을 1x2 크기의 블록으로 덮기(단, 게임판의 일부는 막혀 있어 모든 칸에 블록을 놓을 수 있는 것은 아님)

정점 : 막히지 않은 각 칸 

간선 : 상하좌우로 인접한 칸들 사이

문제 해결 : 이분 그래프 => 이분 매칭 알고리즘

 

• 회의실 배정

N개의 팀이 각각 회의를 하고 싶고, 회의실은 하나 뿐인 경우를 가정

각 팀은 회의실 사용 희망 시간을 2개씩 적어서 제출

회의실은 한번에 한팀만 사용가능, 회의는 시작부터 끝까지 중단없이 진행

문제 : 각 팀마다 제출한 2개의 희망 시간 중 하나씩을 배정하여 모든 팀이 문제없이 회의 진행 가능 여부

만족성 문제(satisfiabillity problem) 중 모든 사람이 두 선택지 중 하나를 선택해야하는 문제로 2-SAT이라 불리는 문제 유형

문제 해결 : 그래프에서 강 결합성 문제로 변환하여 해결

 

그래프의 표현 방법

각 정점에 0부터 시작하는 번호를 붙히고, 배열에 각 정점의 정보를 저장

각 간선은 반대쪽 정점의 번호를 저장

 

간선의 정보를 저장하는 방식 (인접 리스트, 인접 행렬)

 

인접 리스트(adjacency list) 표현

각 정점마다 해당 정점에서 나가는 간선의 목록을 저장해서 그래프로 표현

따라서 각 정점마다 하나의 연결 리스트를 갖는 방식으로 구현

ArrayList<ArrayList<Integer>> adjacent;

 

adjacent.get(i)는 정점 i 와 간선을 통해 연결된 정점들의 번호를 저장한 ArrayList<Integer>를 가져오는 것.

만약 가중치 그래프 등 간선이 추가적 속성을 갖는 그래프를 표현해야 한다면?

가중치가 있는 그래프를 표현하기 위해서는 단순히 ArrayList<Integer>로는 충분하지 않다. 각 간선이 가중치와 같은 추가적인 속성을 포함해야 하므로, 인접 리스트의 각 요소를 ArrayList<Edge> 형태로 정의할 수 있다. 여기서 Edge 클래스는 연결된 노드와 가중치 정보를 담게 된다.

class Edge {
    int destination;  // 연결된 노드
    int weight;       // 간선 가중치

    public Edge(int destination, int weight) {
        this.destination = destination;
        this.weight = weight;
    }
}

 

인접 리스트 그래프 표현 방식의 단점 : 두 정점이 주어질 때 이 정점이 연결되어 있는지 알기 위해서는 연결 리스트를 일일히 순회해야함.

=> 이러한 부분에서 더 좋은 성능을 가진 그래프 표현 방식이 인접 행렬 표현 방식임

 

 

인접 행렬(adjacency matrix) 표현

V x V 크기의 행렬, 즉 2차원 배열을 이용해 그래프의 간선 정보를 저장한다.

가장 간단한 형태의 인접 행렬 표현은 단순히 2차원 배열 boolean 값 배열이다.

boolean[][] adjacent = new boolean[n][n];

 

이때 adjacent[i][j]는 정점 i에서 정점 j로 가는 간선이 있는지 나타내는 boolean 값 변수다. 가중치 그래프를 인접 행렬로 표현할 때는, 각 간선의 정보를 boolean 대신 int나 double 값을 사용하여 저장한다. 간선이 없는 경우에는 -1 혹은 Integer.MAX_VALUE 같은 값으로 표기하여 구별한다.

 

 

인접 행렬 표현과 인접 리스트 표현의 비교

위 두가지 방식은 완전히 정반대의 특성을 가지기 때문에, 단점과 장점이 서로 정반대이다. 구현하려는 알고리즘의 종류나 그래프의 종류에 따라 적절히 표현 방식을 선택해 사용해야 한다.

 

인접 행렬 표현  (간선 존재 확인 시간 O(1), 공간 복잡도 비교적 높음)

• 장점 
  • 정점의 번호 u, v 가 주어졌을 때 두 정점을 잇는 간선이 있는지를 한 번의 배열 접근만으로 확인
• 단점 
  • V x V 크기의 2차원 배열을 사용하기 때문에, 실제 간선의 개수와 관계없이 항상 O(V^2) 크기의 공간을 사용
  • 간선의 개수가 V^2에 근접한다면 두 표현 방식은 비슷한 메모리를 사용하지만 간선의 수가 적은 경우 공간적 낭비가 비교적 심함

 

인접 리스트 표현 (간선 존재 유무 확인 비교적 느림, 공간 복잡도 간선이 적은 경우 유리)

• 장점
  • V 개의 연결 리스트에 실제 간선 수만큼의 원소가 들어 있으므로, 전체 O(V + E)의 공간만을 사용
• 단점 
  • 간선 (u, v)가 존재하는지 확인하기 위해서 연결 리스트를 처음부터 읽어가면서 각 원소 일일이 확인

 

희소 그래프(sparse graph)의 경우 인접 리스트, 밀집 그래프(dense graph)에 대해서는 인접 행렬 표현을 사용하는 것이 유리

 

 

 

참고 자료 :

프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 - 구종만 저자