[Algorithm] 그래프

그래프

• 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료구조
• 정점의 개수 v개, 간선의 개수 e개 일 때 최대 간선의 개수 : v(v-1)/2
• 선형 자료구조 / 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기에 용이

 

그래프 유형

• 무향/유향 그래프 : 방향의 유무
• 가중치 그래프
• 사이클 없는 방향 그래프
• 완전 그래프 : 정점들에 대해 가능한 모든 간선들을 가진 그래프
• 부분 그래프 : 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프

 

그래프 표현

# 노드, 간선의 개수
V, E = 7, 8
# 간선의 연결 (무방향)
temp = [1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7]

위와 같은 입력이 들어왔을 때 그래프를 표현하는 방식

 

• 인접 행렬 (Adjacent matrix) : V*V 크기의 2차원 배열을 이용해서 간선 정보 저장

G  = [[0 for _ in range(V+1)] for _ in range(V+1)]

for i in range(0, len(temp), 2):
	# 무방향이므로 반대의 경우에도 표시
    G[temp[i]][temp[i+1]] = 1
    G[temp[i+1]][temp[i]] = 1

• 인접 리스트 (Adjacent List) : 각 정점마다 해당 정점으로 나가는 간선의 정보를 저장

L  = [[] for _ in range(V+1)]

for i in range(0, len(temp), 2):
	# 무방향이므로 반대의 경우에도 표시
    L[i].append(i+1)
    L[i+1].append(i)

 

그래프 순회

• 깊이 우선 탐색 (Depth First Search, DFS)
• 너비 우선 탐색 (Breadth First Search, BFS)

2021.10.03 - [ALGORITHM/개념 정리] - [Algorithm] DFS, BFS

[Algorithm] DFS, BFS