[이산수학]인접행렬, 인접리스트로 그래프 표현하기

 

그래프의 표현: 인접행렬, 인접리스트

 

■ 인접행렬(Adjacency Matrix)

인접행렬은 그래프를 행렬 형태로 표현하는 방법입니다. 그래프를 구성하는 꼭짓점을 행렬의 각 원소로, 꼭짓점에 근접하는 변을 1 또는 0으로 표기하여 그래프로 표현합니다. 

 

그래프 G = (V, E) 에서 |V| = n일 때, n ×  n 행렬로 나타내는 방법입니다. 그래서 그래프 G = (V, E) 에서 |V| = 3일 때, 그래프 G를 인접행렬로 표현하면 3 × 3 행렬이 됩니다. 그리고 꼭짓점에 근접하는 변이 두 꼭짓점 사이에 존재하면 행렬에 해당하는 원소의 값이 1, 꼭짓점 간에 변이 존재하지 않는다면 행렬에 해당하는 원소의 값이 0이 됩니다. 

 

위 그래프를 인접행렬로 표현해보겠습니다. 

G = (V, E)

V = {a, b, c, d}

E = {(a, c),(c, b),(b, d),(d, d)}

 

인접행렬로 표현하면  4 × 4 행렬이 만들어집니다. 또한 변을 표현하기 위해 행렬의 원소 중  꼭짓점이 만나는 원소를 1로 두고, 나머지 원소는 0으로 둡니다. 

 

 

이 때 주의할 점은  꼭짓점 a, c에 근접하는 변이 있을 때, (a, c), (c, a)는 모두  꼭짓점 a와 c에 근접하는 변을 표현하는 것이기 때문에 모두 1로 표현해야 합니다. 그래서 인접행렬에는 대칭행렬의 특징이 있습니다. 

 

하지만 하나의 변에 대해 두 가지 순서쌍 표현을 모두 행렬의 원소에 표현하기 때문에 다중 그래프를 인접행렬로 표현하는 데에는 한계가 있습니다. 

 

 

 

■ 인접리스트(Adjacency List)

그래프 G = (V, E)를 구성하는 각 꼭짓점에 인접하는 꼭짓점들을 연결리스트(Licked List)로 표현한 것입니다. 

 

인접리스트이 시작 노드는 각 꼭짓점을 가리킵니다. 시작 노드 뒤로 연결되는 노드들은 시작 노드가 갖는 꼭짓점과 인접한 꼭짓점들을 나열한 것입니다. 

 

 

각 꼭짓점마다 인접해 있는 꼭짓점들을 찾아보면, a는 c와 인접하고, b는 c와 d, c는 a와 b, d는 b와 d와 인접합니다. 각 꼭짓점에 대한 연결리스트를 그리면 다음과 같습니다. 

 

 

인접행렬과 마찬가지로 인접리스트도 두 꼭짓점과 근접하는 변에 대한 표기를 모두 해야합니다. 즉,  (a, c), (c, a)는 같은 변을 가리키지만 인접리스트에 모두 표현해야 합니다. 그래서 꼭짓점 a에 대한 노드에 c가 있고, 꼭짓점 c에 대한 노드에 a가 있습니다. 

 

 

수학으로 이해하는 디지털 논리 이산수학 328p 참고

 

-----------------------------------

이산수학 총정리

목록 보러가기 

-----------------------------------