문제해결 전략 - 27. 그래프 표현과 정의

---

그래프 

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

• 여러 도시들을 연결하는 도로망
• 사람들 간의 지인 관계
• 웹사이트 간의 링크 관계

트리에 있던 부모 자식 관계에 관한 제약이 없기 떄문에 트리보다 훨씬 다양한 구조를 표현할 수 있다.

---

 

그래프의 정의

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

---

그래프의 종류

• 방향 그래프(directed graph) : 각 간선이 방향이라는 새로운 속성을 가짐
• 무향 그래프(undirected graph)
• 가중치 그래프(weighted graph) : 각 간선에 가중치(weight)라고 불리는 실수 속성을 부여함
• 다중 그래프(multigraph) : 두 정점 사이에 두 개 이상의 간선이 있을 수 있는 그래프
• 단순 그래프(simple graph) : 두 정점 사이에 최대 한개의 간선만 있는 그래프
• 이분 그래프(bipartite graph) : 정점들을 겹치지 않는 두 개의 그룹으로 나눠서 서로 다른 그룹에 속한 정점들 간에만 간선이 존재하도록 만든 그래프

* 한 그래프가 두가지 이상의 속성을 함께 가지는 경우도 있다.

• 가중치 그래프 + 이분 가중치 그래프
• 사이클 없는 방향 그래프 : 한점에서 출발해 자기 자신으로 돌아오는 경로(사이클)가 존재하지 않는 경우

---

그래프의 경로

• 단순 경로(simple path) : 경로 중 한 정점을 최대 한 번만 지나는 경로
• 사이클(cycle) : 시작한 점에서 끝나는 경로

---

그래프의 사용의 예

• 철도망의 안정성 분석
  : 철도망에서 한 역이 폐쇠되어 열차가 지나지 못할 경우 철도망 전체가 두 개 이상으로 쪼개지는지
• 소셜 네이퉈크 분석
  : 사람들 간의 지인/친밀도 관계
• 인터넷 전송 속도 계산
  : 인터넷에 연결된 라우터와 컴퓨터들을 정점으로 하고 두 기계를 연결하는 케이블을 간선으로 표현하는 그래프를 만든다.
• 한 붓 그리기
  : 선들이 만나는 점들을 정점으로 하고 이 점들을 연결하는 선들을 간선으로 삼은 그래프를 만든다. 그리고 모든 간선을 한 번씩만 지나는 경로를 찾는 문제를 푼다,
• 외환 거래
  : 각 통화를 정점으로 하고 서로 교환가능한 통화들 사이에 간선을 두는 방향 그래프를 만들고 간선의 가중치에 두 통화 간의 교환 비율을 나타낸다.

---

암시적 그래프 구조들

현실 세계에서 그래프 같은 형태를 갖는 구조가 아니더라고 그래프를 통해서 표현하면 쉽게 해결할 수 있는 문제

• 할 일 목록 정리
   : 어느 순서대로 하면 되는지 계산하는 문제를 위상 정렬 문제라고 한다. 깊이 우선 탐색을 응용하여 푼다.
• 15-퍼즐
   : 4x4크기의 게임판에 1부터 15까지의 숫자가 적힌 15개의 타일을 하나씩 움직여 정렬하는 문제. 타일의 배치를 하나의 정점으로 하고, 한 배치에서 타일을 한 번 움직여 다른 배치를 얻을 수 있을 때 두 정점을 간선으로 연결하는 그래프. --> 그래프 상에서 두 점 사이를 잇는 가장 짧은 경로 문제
• 게임판 덮기
   : 가로 N, 세로 N칸으로 나뉜 정사각형의 게임판을 1x2크기의 블록으로 덮는 문제. 게임판 일부는 막혀 있을 때 모든 칸에 블록을 놓을 수 있는 방법. --> 게임판의 막히지 않은 각 칸을 정점으로 하고, 상하 좌우로 인접한 칸들 사이에 간선을 연결하는 그래프르 만든다. --> 이분 그래프 --> 이분 매칭 알고리즘
• 회의실 배정
   : N팀이 회의하는데 회의실은 하나이다. 각 팀은 회의실을 사용하고 싶은 시간을 각각 두개씩 적어 낸다. 회의실은 한 번에 한 팀만 사용할 수 있다. 모든 팀이 회의할수 있도록 할 수 있냐는 문제 --> 만족성 문제 --> 모든 두사람이 두 선택지 중 하나를 선택해야 하는 문제 --> 그래프에서 강 결합성 문제로 변환해서 푼다.

---

그래프의 표현 방법

• 그래프의 경우 드리에 비해 훨씬 정적인 용도로 사용된다.
  --> 새로운 정점이나 간선을 추가하고 삭제하는 일이 자주 일어나지 않는다.
  --->그래서 대부분의 그래프는 구조의 변경이 어렵더라도 좀 더 간단하고 메모리를 적게 차지하는 방법으로 구현
• 그래프 정점들의 객체를 인스턴스로 표현하는 대신 각 정점에 0부터 시작하는 번호를 붙이고, 배열에 각 정점의 정보를 저장하는 것.
• 각 간선은 반대쪽 끝 정점 객체의 포인터 대신 반대쪽 정점의 번호를 저장함
• 간선의 정보를 어떤 식으로 저장하느냐에 따라 크게 두가지로 나뉨

1. 인접 리스트 표현(adjacency list)

• 그래프의 각 정점마다 해당 정점에서 나가는 간선의 목록을 저장해서 그래프를 표현
• 그래프는 각 정점마다 하나의 연결 리스트를 갖는 방식으로 구현됨
• vector<list<int>> adjacent; (C++)
• adjacent[i] 는 정점 i 와 간선을 통해 연결된 정점들의 번호를 저장하는 연결 리스트
• 가중치 같은 추가적인 속성을 가지려면 간선의 정보를 구조체로 표현

struct Edge{
	int vertex; //간선의 반대쪽 끝 점의 번호
    int weight; //간선의 가중치
};

• 단점) 두 정점이 주어질때 이 정점이 연결되어 있는지를 알기 위해선 연결 리스트를 일일히 다 검색해야 한다.

2. 인접 행렬 표현(adjacency matrix)

• |V|x|V|크기의 2차원 배열, 행렬을 이용해 그래프 간선의 정보를 저장한다.
• 가장 간단한 형태의 인접 행렬 표현은 단순히 2차원 boolean 값 배열이다.
• vector<vector<bool>> adjacent; (C++)
• adjacent[i, j]는 정점 i에 정점 j로 가는 간선이 있는지 나타내는 불린 값 변수이다.
• 가중치 그래프를 인접 행렬로 표현하려면 간선의 정보를 boolean 대신 정수나 실수로 둔다.
• 이떄 두 정점 사이에 간선이 없는 경우 이 값을 -1로 하거나 아주 큰 값이나 존재할 수 없는 값으로 지정한다.

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

• 한 방식의 단점이 바로 다른 방식의 장점이기 떄문에 구현 하려는 알고리즘의 종류나 그래프의 종류에 따라 적절히 선택한다.
• 인접 행렬 표현
  
  • 정점의 번호 u, v가 주어졌을 떄 두 정점을 잇는 간선이 있는지를 한번의 배열 접근만으로 확인할 수 있다.
  • 실제 간선의 개수와 관계없이 항상 O(|V|^2)의 공간을 사용한다.
• 인접 리스트 표현
  • 정점의 번호 u, v가 주어졌을 때 두 정점을 잇는 간선이 있는지 확인 하려면 연결 리스트 adjacent[u]를 처음부터 읽어가며 각 원소를 일일히 확인해야 한다.
  • 존재하는 간선의 수만큼 원소가 들어있으므로 전체 O(|V|+|E|)만큼의 공간을 사용한다.
• 희소 그래프 : 간선의 수가 |V|^2 보다 훨씬 적은 그래프 --> 인접 리스트 사용
• 밀집 그래프 : 간선의 수가 |V|^2에 비례하는 그래프 --> 인접 행렬 사용

암시적 그래프 표현

• 항상 직접 메모리에 그래프를 표현할 필요는 없다.
• 그래프 구조를 직접 사용하지 않고도 문제를 해결할 수 있는 경우가 있다.
• 예를들어
  정점으로 표현 하는 대신 빈칸의 위치(y,x)로 표현한다.
  그래프의 크기가 아주 큰데 실제로는 그 중 일부만 사용 할때(15-퍼즐)
• 단점 : 그래프를 사용하는 알고리즘과 변환 과정이 합쳐지게 되고 이 과정에서 코드가 좀 더 복잡해 진다.
• 그래프에 대한 복잡한 연산이나 알고리즘을 수행해야 한다면 입력을 미리 그래프 표현으로 바꿔 두는게 좋다.