주요 내용

코스: 컴퓨터과학 > 단원 1

단원 10: 그래프 표현

그래프 나타내기

그래프는 여러 가지 방법으로 나타낼 수 있는데, 방법마다 장단점이 있습니다. 그래프를 입력값으로 어떤 상황이나 알고리즘을 실행하고자 할 때는 상황에 따라 그래프를 다르게 나타냅니다. 그래프를 나타내는 3가지 방법을 알아봅시다.

3가지 기준에 대해 알아볼 것입니다. 첫 번째 기준은 그래프를 나타낼 때 차지하는 메모리나 공간입니다. 이를 위해 점근적 표기법을 사용합니다. 금방 눈치챘겠지만, 실행 시간을 나타내기 위한 목적이 아니더라도 점근적 표기법을 사용할 수 있습니다! 실제로 점근적 표기법은 함수 의 특성을 묘사하는 방법입니다. 함수는 실행 시간, 필요한 공간 크기, 기타 자원에 대해 나타낼 수 있죠. 다른 두 기준은 시간과 관련이 있습니다. 하나는 주어진 변이 그래프 안에 있는지 결정하는데 걸리는 시간입니다. 나머지 하나는 주어진 정점의 이웃을 알아내는데 걸리는 시간입니다.

정점은 "오드리" "보스톤" 또는 "스웨터" 처럼 이름으로 나타내지 않고 숫자로 표시하는 것이 일반적입니다. 즉

| V |

정점에 0부터

| V | - 1

까지 숫자를 붙이는 것입니다. 아래는 이름이 아닌 숫자로 나타낸 10개의 정점이 있는 소셜 네트워크입니다.

연결선 리스트(Edge lists)

그래프를 표현하는 간단한 방법 중 하나는 변

| E |

개로 이루어진 리스트나 배열로 나타내는 것입니다. 이를 연결선 리스트라고 합니다. 변을 나타내기 위해서는 두 정점 번호의 배열이나 변으로 연결된 정점의 정점 숫자가 포함된 객체의 배열을 만듭니다. 변에 가중치가 있다면 3번째 요소를 배열에 추가하거나 더 많은 정보를 객체에 추가하여 변에 가중치를 더합니다. 각각의 변은 두 개나 세 개의 숫자만을 포함하기 때문에 연결선 리스트에 필요한 총 공간은

Θ (E)

입니다. 예를 들어 다음은 소셜 네트워크 그래프를 나타내기 위해 JavaScript로 연결선 리스트를 나타낸 것입니다.

[ [0,1], [0,6], [0,8], [1,4], [1,6], [1,9], [2,4], [2,6], [3,4], [3,5],  
[3,8], [4,5], [4,9], [7,8], [7,9] ]

연결선 리스트는 간단하지만, 그래프에 특정 변이 있는지 알고 싶으면 연결선 리스트를 모두 검색해야 합니다. 연결선 리스트에 변이 아무런 순서 없이 무작위로 들어가 있다면 변

| E |

개 중에 특정 변을 찾으려면 선형 검색을 해야 됩니다. 특정한 변을 찾는데

O (\lg E)

시간 내에 찾으려면 연결선 리스트를 어떻게 구성해야 할까요? 해답은 약간 복잡합니다.

인접 행렬

| V |

정점이 있는 그래프에서 인접 행렬은 0과 1로 이루어진

| V | \times | V |

행렬입니다. 여기서 변

(i, j)

가 그래프에 있을 경우에만

i

행과

j

열의 값이 1이 됩니다. 변 가중치를 지정하고자 한다면

i

행,

j

열 항목에 가중치를 주고 변이 없을 경우를 나타내기 위한 특수값(보통 null값) 을 지정해 놓습니다. 다음은 소셜 네트워크 그래프의 인접 행렬입니다.

javaScript에서는 이 행렬을 다음과 같이 나타냅니다.

[ [0, 1, 0, 0, 0, 0, 1, 0, 1, 0],
  [1, 0, 0, 0, 1, 0, 1, 0, 0, 1],
  [0, 0, 0, 0, 1, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 1, 1, 0, 0, 1, 0],
  [0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
  [0, 0, 0, 1, 1, 0, 0, 0, 0, 0],
  [1, 1, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
  [1, 0, 0, 1, 0, 0, 0, 1, 0, 0],
  [0, 1, 0, 0, 1, 0, 0, 1, 0, 0] ]

인접 행렬에서는 어떤 변의 존재 여부를 일정 시간 내에 파악할 수 있습니다. 행렬에서 해당 항목을 찾아보기만 하면 됩니다. 예를 들어 인접 행렬 이름이 graph고 변

(i, j)

가 그래프에 있는지 알아보려면 graph[i][j]를 탐색해보면 됩니다. 그렇다면 인접 행렬의 단점은 무엇일까요? 두 가지가 있습니다. 먼저 그래프가 변이 몇 개 없는 희소 그래프일 경우라도 공간을

Θ (V^{2})

만큼 차지한다는 것입니다. 즉, 희소 그래프에서 인접 행렬은 대부분 0으로 이루어지는데 겨우 변 몇 개를 나타내는데 지나치게 많은 공간을 사용하게 되는 것입니다. 둘째로 어떤 정점이 주어진 정점

i

와 인접해 있는지 알기 위해서

i

정점과 인접한 정점들의 수가 적을 때도

i

행의 모든

| V |

항목을 찾아봐야 한다는 것입니다.

비방향 그래프에서 인접 행렬은 대칭입니다.

i

행,

j

열의 항목은

j

행,

i

열이 1일 경우에만 1입니다. 방향 그래프에서 인접 행렬은 꼭 대칭일 필요는 없습니다.

인접 리스트

인접 리스트로 그래프를 나타내려면 인접 행렬과 연결선 리스트를 결합해야 합니다. 각 정점

i

에 대해 그 정점과 인접한 정점의 배열을 저장합니다. 일반적으로 한 정점 당 하나의 인접 리스트가 존재하여 총

| V |

개의 배열을 가집니다. 다음은 소셜 네트워크를 나타낸 인접 리스트입니다.

JavaScript에서는 이 인접 리스트를 다음과 같이 표현합니다.

[ [1, 6, 8],
  [0, 4, 6, 9],
  [4, 6],
  [4, 5, 8],
  [1, 2, 3, 5, 9],
  [3, 4],
  [0, 1, 2],
  [8, 9],
  [0, 3, 7],
  [1, 4, 7] ]

인접 리스트에 있는 정점 숫자는 특정 순서를 따라서 나열할 필요는 없습니다. 그러나 예제처럼 오름차순으로 나타내는 것이 편리할 때가 많긴 합니다.

각 정점의 인접 리스트는 배열을 찾아보기만 하면 되기 때문에 일정 시간 내에 얻을 수 있습니다. 변

(i, j)

가 그래프에 있는지 알아보려면 일정 시간 내에

i

의 인접 리스트로 가서

i

의 인접 리스트에서

j

를 찾아보면 됩니다. 최악의 경우에는 얼마나 걸릴까요? 정답은

Θ (d)

입니다. 여기서

d

는 정점

i

의 차수입니다. 왜냐하면 바로 이 수치가

i

의 인접 리스트의 길이를 알려주기 때문입니다. 정점

i

의 차수는

| V | - 1

만큼 커지거나(

i

이 다른 모든

| V | - 1

정점들과 인접한 경우) 0으로 작아질 수(

i

가 인접한 변 없이 고립된 경우) 있습니다. 비방향 그래프에서 정점

j

는

i

가

j

의 인접 리스트에 있을 경우에만 정점

i

의 인접 리스트에 있습니다. 그래프에 가중치가 있다면 각 인접 리스트 내 각 항목은 정점 번호와 변 가중치의 두 항목으로 이루어진 배열이나 객체이어야 합니다.

인접 리스트 내 정점 사이를 반복해서 순환할 때 for 반복문을 이용할 수 있습니다. 예를 들어 변수 graph를 사용하여 그래프를 인접 리스트로 나타냈다고 가정해 봅시다. 여기서 graph[i]는 정점

i

의 이웃을 포함하는 배열입니다. 그다음 정점

i

와 인접한 각 정점에 대해 doStuff 함수를 호출하기 위해 다음과 같은 JavaScript 코드를 사용할 수 있습니다.

for (var j = 0; j < graph[i].length; j++) {
    doStuff(graph[i][j]);
}

2중 첨자 표기가 헷갈린다면 다음과 같이 생각해 보세요.

var vertex = graph[i];
for (var j = 0; j < vertex.length; j++) {
    doStuff(vertex[j]);
}

인접 리스트가 차지하는 공간은 얼마나 될까요? 리스트가

| V |

개만큼 있고 각 리스트는

| V | - 1

개만큼 정점을 가질 수 있지만 비방향 그래프의 인접 리스트에는

2 | E |

개의 항목이 있습니다. 왜

2 | E |

일까요? 각 변

(i, j)

는

i

의 리스트에서 한 번, 그리고

j

의 리스트에서 한 번, 모두 합쳐서 두 번 나타나며 리스트에는

| E |

개의 변이 있기 때문입니다. 방향 그래프에서 인접 리스트는 방향성 있는 변 하나 당 한 요소씩 총

| E |

개의 요소를 가지고 있습니다.

대화에 참여하고 싶으신가요?

로그인

정렬 기준:

포스트가 아직 없습니다.

영어를 잘 하시나요? 그렇다면, 이곳을 클릭하여 미국 칸아카데미에서 어떠한 토론이 진행되고 있는지 둘러 보세요.