Graph (Adjacency Matrix, Adjacency List)

Graph (Adjacency Matrix, Adjacency List)

Graph

Directed Graph (방향이 존재하는 그래프)

Un-Directed Graph (방향이 없는 그래프)

Weighted Graph (가중치가 존재하는 그래프)

Adjacency Matrix(인접 행렬)

2차원 배열로 그래프의 노드간 연결관계를 표현

연결되지 않은 노드는 INF로, 연결된 노드는 거리로 나타내기 (노드간 거리가 존재하는 경우)

연결된 노드끼리는 1(True), 연결되지 않은 경우 0 (False)

방향이 없는 그래프인 경우 graph[i][j] = graph[j][i]

방향이 있는 그래프인 경우 graph[from][to]

Adjacency List(인접 리스트)

각 노드에 대해서 연결된 노드 정보를 저장

Python

# Adjacency Matrix 로 표현 graph = [ [0]*5 for _ in range(5) ] graph[1][2]=1 graph[2][3]=1 graph[3][1]=1 graph[1][3]=1 graph[3][4]=1 # Adjacency List 로 표현 graph = [[] for i in range(5)] graph[1].append(2) graph[1].append(3) graph[2].append(3) graph[3].append(1) graph[3].append(4)

from http://akatapata.tistory.com/66 by ccl(A) rewrite - 2021-12-27 19:01:09