인접 행렬로 구현한 그래프

인접 행렬 (adjacency matrix)

2차원 배열인 인접 행렬(M)에서 행(row)과 열(col)은 각 노드의 번호를 뜻하고 간선이 존재할 때 다음과 같이 나타낸다.

M[row][col] = 1

그래프는 자체 간선을 허용하지 않으므로 인접 행렬의 대각선 성분은 항상 0이다.

방향 그래프의 인접 행렬은 일반적으로 대칭이 아니다.

효율 분석

공간적

n개의 정점을 가지는 그래프를 인접행렬로 표현하기 위해서는 간선의 수와 무관하게 n²개의 메모리 공간이 필요하다.

간선의 수가 많이 존재하는 밀집 그래프(dense graph)를 표현하는 경우에는 적합하나 적은 숫자의 간선을 가지는 희소 그래프(sparse graph)의 경우에는 메모리 낭비가 크므로 적합하지 않다.

시간적

간선의 존재 여부는 M[row][col] 의 값을 조사하여 O(1) 시간 안에 즉시 알아낼 수 있다.

정점의 차수는 인접행렬의 행이나 열을 조사하면 알 수 있으므로 O(n)의 연산으로 알 수 있다.

그래프에 존재하는 모든 간선의 수를 알아내려면 인접 행렬 전체를 조사해야 하므로 O(n²)의 시간이 요구된다.

구현

소스코드

class matrixGraph():
    def __init__(self, max_vertices):
        self.n = 0 # vertex count
        self.max_vertices = max_vertices
        self.adj_mat = [[0 for _ in range(0, max_vertices)] for _ in range(0, max_vertices)]

    def insert_vertex(self, v):
        if self.n+1 > self.max_vertices:
            print("graph is full")
        else:
            self.n += 1

    def insert_edge(self, start, end):
        # vertex count - 1 = index
        if start > self.n-1 or end > self.n-1:
            print("out of area")
        else:
            self.adj_mat[start][end] = 1
            self.adj_mat[end][start] = 1

if __name__ == "__main__":
    g = matrixGraph(5)
    g.insert_vertex(0)
    g.insert_vertex(1)
    g.insert_vertex(2)
    g.insert_vertex(3)
    g.insert_vertex(4)
    g.insert_edge(0, 1)
    g.insert_edge(0, 2)
    g.insert_edge(0, 3)
    g.insert_edge(1, 2)
    g.insert_edge(1, 4)
    g.insert_edge(2, 3)
    g.insert_edge(3, 4)
    for i in g.adj_mat:
        print(i)

출력

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

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