Graph 표현 방법

우리는 보통 두 가지의 방법으로 그래프를 표현한다.

1. 인접 배열
2. 인접 리스트

우리는 위의 두 가지의 방법을 아주 간단하게 정리하고 코드로 구현을 해볼 것이다.

인접 배열

> ‘모든 노드를 **출발점(**열)으로 설정하고 다른 노드에 **연결**(행)이 되어있는지’의 대한 여부를 **(0, 1)** 로 표현하는 것이다. 이 때 가중치가 있을 경우에는 1을 사용하지 않고 가중치를 넣는다. >

v = 5

edges = [(0,1,1),(0,4,1),(1,2,1),(1,3,1),(2,3,1),(3,4,1)]

# n * n의 0 배열 생성
def zeroMatrix(v):
    return [[0] * v for _ in range(v)]

def initMatrix(graph,edges):
    for s,e,val in edges:
        graph[s][e] = val
        graph[e][s] = val

def printMatrix(graph):
    for row in graph:
        print(" ".join(map(str,row)))

graph = zeroMatrix(v)

initMatrix(graph,edges)
printMatrix(graph)

• 장점

  • 2차원 배열에 모든 노드들의 간선 정보가 있기 때문에, 두 노드를 연결하는 간선을 조회할 때 O(1)의 시간 복잡도를 가지며 매우 빠르게 찾을 수 있다.

• 단점

  • 간선의 수와 무관하게 노드수^2의 2차원 배열이 필요하기 때문에 메모리 공간의 낭비가 발생 할 수 있다. 또한 그래프의 모든 간선을 알려고 할 때는 O(n^2)의 시간 복잡도가 발생한다.

인접 리스트

한개의 노드를 기준으로 해당 노드와 연결된 노드를 리스트로 표현한 것이다. 즉, 각 정점이 ‘연결 리스트’를 가지고 인접한 정점들을 연결 리스트로 표현한 것

• 각 정점에 대한 인접 정점들을 순차적으로 연결 리스트로 표현하는 방법

• 하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결 리스트로 저장하며 인접 행렬과는 다르게 존재하지 않는 간선은 표현상 나타나지 않음

• 가중치가 있는 그래프일 경우

  • 리스트에 가중치도 보관한다.

v = 5

# 가중치 그래프
edges = [(0,1,1),(0,4,1),(1,2,1),(1,3,1),(2,3,1),(3,4,1)]

# dictionary 구조를 사용한다.
def zeroList(v):
    return {i : [] for i in range(v)} 

def initList(graph,edges):
    for s,e,val in edges:
        graph[s].append((e,val))
        graph[e].append((s,val))
        
def printlist(graph):
    for v in graph:# v는 key 값
        print(f"{v} : {graph[v]}")

graph = zeroList(v)

initList(graph,edges)

printlist(graph)

• 장점
  • 연결된 정점들만 저장하여 표현하므로 인접 행렬에 비해 메모리의 낭비를 줄 일 수 있음
  • 정점에 연결된 노드의 수를 이용하여 정점의 차수를 쉽게 구할 수 있음
• 단점
  • 하나의 연결을 표시하기 위해 정점에 대한 정보만 아니라 연결 정보까지 필요하므로 ‘간선의 수’가 상대적으로 많은 경우에 인접 행렬보다 메모리 낭비가 심하다.