그래프를 나타내는 방법은 여러 가지가 있습니다. 각각 장점과 단점을 가지고 있습니다. 그래프를 입력으로 하여 어떤 상황이나 알고리즘을 실행하고자 할 때는 상황에 따라 그래프를 다르게 나타냅니다. 그래프를 나타내는 3가지 방법을 알아봅시다.
3가지 기준에 대해 알아볼 것입니다. 하나는 각각의 표현에서 얼마나 많은 메모리나 공간이 필요하는가 하는 것입니다. 이를 위해서는 점근적 표기법을 사용합니다. 네, 실행 시간을 나타내기 위한 목적이 아니더라도 점근적 표기법을 사용할 수 있답니다! 실제로 점근적 표기법은 함수의 특성을 묘사하는 방법입니다. 함수는 실행 시간, 필요한 공간 크기, 기타 자원에 대해 나타낼 수 있죠. 우리가 사용할 다른 두 기준은 시간과 연관된 것입니다. 하나는 주어진 변이 그래프에 있는지 여부를 결정하는데 얼마나 걸리느냐 하는 것입니다. 또 하나는 주어진 정점의 이웃을 알아내는데 얼마나 걸리느냐 하는 것입니다.
정점은 ("오드리" "보스톤" 또는 "스웨터" 등과 같은) 이름이 아닌 숫자로 특정하는 것이 일반적입니다. 즉 vertical bar, V, vertical bar 정점들에 0부터 vertical bar, V, vertical bar, minus, 1까지의 숫자를 붙이는 것입니다. 아래는 이름이 아닌 숫자로 식별되는 10개의 정점을 가진 소셜 네트워크입니다.

연결선 리스트(Edge lists)

그래프를 표현하는 간단한 방법 중 하나는 변 vertical bar, E, vertical bar 개로 이루어진 리스트나 배열로 나타내는 것으로 이를 연결선 리스트라고 합니다. 변을 나타내기 위해서는 두 정점 숫자의 배열이나 변으로 연결된 정점의 정점 숫자가 포함된 객체의 배열를 만듭니다. 변에 가중치가 있다면 3번째 요소를 배열에 추가하거나 더 많은 정보를 객체에 추가하여 변에 가중치를 더합니다. 각각의 변은 두개나 세개의 숫자만을 포함하기 때문에 연결선 리스트에 필요한 총 공간은 Θ(E) \Theta(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] ]
연결선 리스트는 간단하지만 그래프에 특정 변이 있는지 알고자 할 경우 연결선 리스트를 모두 검색해야 합니다. 연결선 리스트에 변이 아무런 순서 없이 들어가 있다면 변 vertical bar, E, vertical bar개 중에 특정 변을 찾는 것은 선형 검색이 됩니다. 특정한 변을 찾는데 O(lgE) O(\lg E) 시간 내에 찾으려면 연결선 리스트를 어떻게 구성해야 할까요? 해답은 약간 복잡합니다.

인접 행렬

vertical bar, V, vertical bar 정점이 있는 그래프에서 인접 행렬은 0과 1의 vertical bar, V, vertical bar, times, vertical bar, V, vertical bar 행렬입니다. 여기서 변 left parenthesis, i, comma, j, right parenthesis가 그래프에 있을 경우에만 i행과 j열의 값이 1이 됩니다. 변 가중치를 지정하고자 한다면 i행, j열 항목에 가중치를 주고 변이 없을 경우를 나타내기 위한 특수값(보통 null값) 을 예약해 둡니다. 다음은 소셜 네트워크 그래프를 나타내는 인접 행렬입니다.
자바스크립트에서는 이 행렬을 다음과 같이 나타냅니다.
[ [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로 한다면 변 left parenthesis, i, comma, j, right parenthesis가 그래프에 있는지 여부는 graph[i][j]를 찾아봄으로써 알 수 있습니다. 그렇다면 인접 행렬의 단점은 무엇일까요? 두 가지가 있습니다. 먼저 그래프가 희소 그래프일 경우에도 공간을 Θ(V2) \Theta(V^2) 만큼 차지한다는 것입니다. 즉 희소 그래프에서 인접 행렬은 대부분 0으로 이루어지는데 겨우 몇 개의 변을 나타내기 위해 너무 많은 공간을 사용하게 되는 것입니다. 둘째로 어떤 정점이 주어진 정점 i와 인접해 있는지 알기 위해서 i 정점과 인접한 정점들의 수가 적을 때조차도 i 행의 모든 vertical bar, V, vertical bar 항목을 찾아봐야 한다는 것입니다.
비방향 그래프에서 인접 행렬은 대칭입니다. 즉 i행, j열의 항목은 j행, i열이 1일 경우에만 1입니다. 방향 그래프에서 인접 행렬은 꼭 대칭일 필요는 없습니다.

인접 리스트

인접 리스트로 그래프를 나타내려면 인접 행렬과 연결선 리스트를 결합합니다. 각 정점 i에 대해 그 정점과 인접한 정점들의 배열을저장합니다. 일반적으로 인접 리스트 vertical bar, V, vertical bar개의 배열를 가집니다. 한 정점 당 하나의 인접 리스트가 있습니다. 다음은 소셜 네트워크를 나타낸 인접 리스트입니다.
자바스크립트에서는 이 인접 리스트를 다음과 같이 표현합니다.
[ [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] ]
인접 리스트에 있는 정점 숫자는 특정 순서에 따라 나열될 필요는 없습니다. 이 예제처럼 오름 차순으로 나타내는 것이 편리할 때가 많긴 합니다.
각 정점의 인접 리스트는 배열을 찾아보기만 하면 되기 때문에 일정 시간 내에 얻을 수 있습니다. 변 left parenthesis, i, comma, j, right parenthesis가 그래프에 있는지 여부를 알아보려면 일정 시간 내에 i의 인접 리스트로 가서 i의 인접 리스트에서 j를 찾아보면 됩니다. 최악의 경우에는 얼마나 걸릴까요? 답은 Θ(d) \Theta(d) 입니다. 여기서 d는 정점 i의 차수입니다. 왜냐하면 이것이 i의 인접 리스트가 얼마나 긴지 알려주기 때문입니다. 정점 i의 차수는 vertical bar, V, vertical bar, minus, 1만큼 커지거나(i 이 다른 모든 vertical bar, V, vertical bar, minus, 1 정점들과 인접한 경우) 0으로 작아질 수( i가 인접한 변 없이 고립된 경우) 있습니다 비방향 그래프에서 정점 jij의 인접 리스트에 있을 경우에만 정점 i의 인접 리스트에 있습니다. 그래프에 가중치가 있다면 각 인접 리스트 내 각 항목은 정점 번호와 변 가중치의 두 항목으로 된 배열이거나 객체이어야 합니다.
인접 리스트 내 정점들을 모두 돌기 위해 for 반복문을 이용할 수 있습니다. 예를 들어 변수 graph로 그래프를 인접 리스트로 표현했다고 가정합시다. 여기서 graph[i]는 정점 i의 이웃들을 포함하는 배열입니다. 그런 후 정점 i와 인접한 각 정점에 대해 doStuff 함수를 호출하기 위해 다음과 같은 자바스크립트 코드를 사용할 수 있습니다.
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]);
}
인접 리스트가 차지하는 공간은 얼마나 될까요? vertical bar, V, vertical bar 리스트가 있고 각 리스트는 vertical bar, V, vertical bar, minus, 1개만큼 정점을 가질 수 있지만 비방향 그래프를 위한 인접 리스트는 통틀어 2, vertical bar, E, vertical bar개의 항목이 있습니다. 왜 2, vertical bar, E, vertical bar일까요? 각 변 left parenthesis, i, comma, j, right parenthesisi의 리스트에서 한 번, 그리고 j의 리스트에서 한 번으로 정확히 두 번 나타나며 리스트에는 vertical bar, E, vertical bar개의 변이 있기 때문입니다. 방향 그래프에서 인접 리스트는 방향성 있는 변 하나 당 한 항목씩 총 vertical bar, E, vertical bar개의 항목을 포함합니다.

위 자료는 다트머스 대학교 컴퓨터공학과토마스 콜먼 교수와 데빈 발컴 교수, 그리고 칸아카데미 컴퓨팅 과정 팀이 공동으로 저술했으며, 본 내용물의 저작권은 CC-BY-NC-SA 라이선스를 적용합니다.