[그래프]- 인접 행렬, 인접 그래프

• 그래프는 G(V, E)로 정의하고, V(Vertext : 정점)과 E(Edge : 간선) 의 집합을 의미한다.

• 연결되어 있는 원소들간의 관계를 표현하는 자료구조이다.

 

인접행렬

2차원 배열을 이용해 그래프를 표현하는 방법

1) 무방향 그래프

입력 형식 : edge = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 4]]

graph = [[0] * (n+1) for _ in range(n+1)] 
for [a, b] in edge:
	graph[a][b] = 1 
    graph[b][a] = 1

 

 

2) 방향 그래프

 

입력 형식 : edge = [[1, 2], [1, 3], [2, 5], [3, 4], [4, 2]]

graph = [[0] * (n+1) for _ in range(n+1)] 
for [a, b] in edge:
	graph[a][b] = 1

 

3) 가중치 그래프 

 

입력형식 : edge = [[1, 2, 2], [1, 3, 4], [2, 5, 5], [3, 4, 5], [4, 2, 2]]

 

graph = [[0] * (n+1) for _ in range(n+1)] 
for [a, b, c] in edge:
	graph[a][b] = c

 

 

 

 

 

인접 리스트

1) 무방향 그래프

 

 

입력형식 : edge = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 4]]

graph = [[] for _ in range(n+1)] 
for [a, b] in edge:
	graph[a].append(b) graph[b].append(a)

 

2) 방향 그래프

 

 

입력형식 : edge = [[1, 2], [1, 3], [2, 5], [3, 4], [4, 2]]

 

graph = [[] for _ in range(n+1)] 
for [a, b] in edge:
	graph[a].append(b)

 

 

3)가중치 그래프

 

 

입력형식 : edge = [[1, 2, 2], [1, 3, 4], [2, 5, 5], [3, 4, 5], [4, 2, 2]]

 

graph = [[] for _ in range(n+1)] 
for [a, b, c] in edge:
	graph[a].append([b, c])