인접 리스트로 구현한 그래프

인접 리스트 (adjacency list)

각각의 정점에 인접한 정점들을 연결리스트로 표시한 것으로, 각 연결 리스트의 노드들은 인접 정점을 저장한다.

연결 리스트에 정점이 입력되는 순서에 따라 연결 리스트 내에서 정점의 순서가 달라질 수 있지만 표현의 일관성을 위해 오름 차순으로 연결된다고 가정하고 표현하였다.

효율 분석

공간적

정점의 수가 n개이고 간선의 수가 e개인 무방향 그래프를 표시가 위해서는 n개의 연결 리스트가 필요하고, n개의 헤드 포인터와 2e개의 노드가 필요하다. 따라서 인접 리스트 표현은 간선의 개수가 적은 희소 그래프(sparse graph)의 표현에 적합하다.

간선의 수가 최대치인 완전 그래프(complete graph)일 경우라 하더라도 인접 행렬을 사용한 그래프보다 많은 메모리 공간을 차지하는것은 아니다.

시간적

정점의 간선 존재 여부나 차수를 알기 위해서는 인접 리스트에서 해당 정점의 연결 리스트를 탐색해야 하므로 연결 리스트에 있는 노드의 수 만큼, 즉 정점의 차수만큼 시간이 필요하다.

n개 정점과 e개의 간선을 가진 그래프에서 전체 간선의 수를 알아내려면 헤더 노드를 포함하여 모든 인접 리스트를 조사해야하므로 O(n+e)의 연산이 요구된다.

구현

소스코드

class Node():
    def __init__(self, v):
        self.vertex = v
        self.link = None

class listGraph():
    def __init__(self):
        self.n = 0 # vertex count
        self.adj_list = []

    # adj_list 의 인덱스를 정점의 번호로 설정
    def insert_vertex(self):
        self.adj_list.append(None)
        self.n += 1

    # v값을 u의 인접 리스트에 삽입
    def insert_edge(self, u, v): 
        new = Node(v)
        if u > self.n-1 or v > self.n-1:
            print("out of area")    
        else:
            new = Node(v)
            new.vertex = v
            new.link = self.adj_list[u]
            self.adj_list[u] = new

if __name__ == "__main__":
    g = listGraph()

    for _ in range(0, 5):
        g.insert_vertex()

    g.insert_edge(0, 1)
    g.insert_edge(0, 2)
    g.insert_edge(0, 3)
    g.insert_edge(1, 0)
    g.insert_edge(1, 2)
    g.insert_edge(1, 4)
    g.insert_edge(2, 0)
    g.insert_edge(2, 1)
    g.insert_edge(2, 3)
    g.insert_edge(3, 0)
    g.insert_edge(3, 2)
    g.insert_edge(3, 4)
    g.insert_edge(4, 1)
    g.insert_edge(4, 3)

    c = 0

    for i in g.adj_list:
        print(c, "->", end=' ')
        while i != None:
            print(i.vertex, end=' ')
            i = i.link
        print('')
        c += 1

출력

0 -> 3 2 1
1 -> 4 2 0
2 -> 3 1 0
3 -> 4 2 0
4 -> 3 1

처음 첨부한 사진의 왼쪽, 무방향 그래프의 정점, 간선 삽입 연산을 구현하였고 삭제 연산은 생략하였다.

insert_edge 메소드에서 헤드 포인터에 노드를 연결하는 모습은 마치 스택과 유사하다. 먼저 들어간 값이 제일 마지막에 위치한다.

헤드 포인터가 모여있는 adj_list 리스트는 None 을 가리키도록 초기화된다. (None 값은 &0)