[자료구조] 12-3. 그래프의 기본 연산

위와 같은 그래프는 오른쪽과 같이 엣지 리스트의 형태로 표현된다. 해석하자면 4개의 버텍스와 6개의 엣지를 가지고 있다는 것이다. 4개이므로 0에서 3 또는 1부터 4로 표현된다. 그리고 그 아래에 엣지들의 관계가 나온다. 이러한 형태는 많은 코딩 문제에서 출제된다.

그래프는 n*n의 행렬로 표현할 수 있다. 그리고 버텍스 간의 연결이 존재하면 1을 쓰고 아니라면 0을 쓴다.

0 1이 연결되어 있다면 0 1 뿐만 아니라 1 0에도 같이 1을 써줘야 한다. 그럼 이러한 결과가 나온다.

표를 살펴보면 a[i][j] = a[j][i]이므로 대칭 행렬이다. 따라서 무방향 그래프의 인접 행렬은 대칭 행렬이라고 할 수 있다.

방향 그래프는 어떨까? 역시 i에서 j로 가는 엣지가 존재할 때는 1이고 아니면 0이다.

서로 방향이 다르므로 그래프의 형태가 다르게 나온다. 대칭성이 깨진다.

행렬 말고도 리스트로 표현하는 방법도 있다. 모든 버텍스에 대한 리스트 구조를 생성하고 리스트에서 버텍스를 연결한다.

이런 식으로 표현하는 방법이다.

리스트의 경우에도 방향 그래프는 다르게 나온다.

이러한 형태로 표현된다.

STL 라이브러리를 사용해 코드로 표현해보자. 버텍스의 수 4, 엣지의 수 5가 입력되었다. 버텍스를 1부터 4까지라고 치면 엣지는 1 2, 1 3, 1 4, 2 4, 3 4로 들어온다.

이전과 같은 입력을 받으면 위와 같은 코드가 작동한다.

1 .엣지를 저장할 벡터 타입의 리스트를 만든다. 그리고 scanf로 맨 처음의 4와 5를 n(버텍스의 수)과 m(엣지의 수)으로 읽어들인다.

2. 그 후, 엣지의 수만큼 반복하면서 엣지가 연결된 목록을 한 줄씩 읽어들인다. 1과 2를 읽어들였다면 edge값 1에는 2, 2에는 1이 들어간다. 서로 연결되어 있기 때문이다. 이런 식으로 나머지 엣지들도 저장된다.

3. 정리하면 1: 2 3 4 / 2: 1 4 / 3: 1 4 / 4: 1 2 3 이렇게 저장된다.

4. 3번의 값은 정렬되어 있지만, 만약 이 목록이 정렬되지 않은 상태로 들어왔다면 3 1 2 이렇게 정렬이 깨질 수 있다. 나중에 그래프를 스캔하거나 할 때 문제가 발생할 수 있으므로 이 모든 리스트를 정렬시켜준다.

5. 최종적으로 깔끔한 인접 리스트가 만들어진다.

그래프의 성능을 보자. 모든 버텍스에 인접한 모든 버텍스를 출력해야 한다면 이중 for문이 작동될 것이다. 

하지만 시간을 구하려고 보니 시간, 또는 연산이라는 개념이 일관되지 않는다. 

예를 들어, 완전 또는 밀집 그래프는 엣지의 수가 O(n^2)개이고 희소 그래프는 O(n)개이다. 이런 경우에 따라 성능이 달라진다. 또, 인접 행렬인지 인접 리스트인지에 따라 성능이 달라진다. 인접 리스트에 희소 그래프라면 O(n)이 걸린다. 따라서 가능하면 인접 리스트를 선택해야 한다. 운좋게 그래프가 희소 그래프라면 O(n)이 걸릴 수 있기 때문이다.

그래프의 연산은 기본적으로 깊이 우선 탐색 DFS냐, 넓이 우선 탐색 BFS냐로 나뉜다. 뱡항이건 무방향 그래프이건 상관없다.

- 깊이 우선 탐색: 연결 성분 / 신장 트리 / 이중 연결 성분 / 강한 연결 성분

- 넓이 우선 탐색: 최단 거리를 찾는 방법을 구현한다.

깊이 우선 탐색은 아래로 쭉 내려갔다가 찾는 그래프다.

넓이 우선 탐색은 옆으로 퍼지면서 찾는 알고리즘이다.

연결 성분 찾기 연산은 위와 같이 두 개의 연결 성분이 존재하는 그래프라면, 같은 연결 성분에 속하는 버텍스에 대해서는 같은 인덱스를 붙여준다.

신장 트리 찾기 연산은 왼쪽 그래프에 대해서 오른쪽 그래프 같은 경로로 찾아준다. 이때 버텍스의 수는 원래 주어진 버텍스와 같고, 엣지의 수는 버텍스 수 n의 -1과 같다. 사이클은 존재하지 않는다.

이중 연결 성분 연산은 연결 성분을 찾는데, 이중으로 연결되어 있는 것이다. 어떤 버텍스가 사라지더라도 남은 버텍스들 사이의 연결 성분이 유지된다.

파랑과 주황은 이중 연결 성분이 아니다. 2번 버텍스가 제거되면 그래프가 두개로 나눠지기 때문이다.

강한 연결 성분 연산은, 연결 성분을 찾기는 하는데 방향 그래프에서 말하는 강한 연결 성분을 찾는 연산이다. 예를 들어, B E 같은 강한 연결 성분을 찾는 것이다. 만약 서로 경로가 존재하지 않는다면 자기 자신도 하나의 강한 연결 성분이다.

최단 거리 연산은 특정 버텍스에서 다른 버텍스로 가는 최단 경로를 찾는 것이다.