그래프 탐색

그래프

그래프는 G(V, E)와 같은 형태로 정의하며 V: Vertext: 정점과 E: Edge : 간선의 집합을 의미한다.

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

그래프에는 방향이 존재하는 방향그래프와 방향이 존재하지 않는 무방향 그래프가 있다.

무방향 그래프

위 그림과 같이 정점을 연결하고 있는 간선에 방향이 없는 경우, 무방향 그래프라고 한다.

이를 인접 행렬로 표현하면,

0 1 1 0 0
1 0 0 1 1
1 0 0 1 0
0 1 1 0 0
0 1 0 0 0

과 같이 나타낼 수 있다.

이를 코드로 나타내면 다음과 같다.

graph = [[0] * (n+1) for _ in range(n+1)

for [a, b] in edge:
	graph[a][b] = 1
    graph[b][a] = 1

인접 리스트를 활용한 코드는 다음과 같다.

graph = [[] for _ in range(n+1)]

for [a,b] in edge:
	graph[a].append(b)
    graph[b].append(a)

---

방향그래프

방향 그래프는 말 그대로 아래와 같이 정점을 연결하는 간선에 방향이 있다.

이를 인접 행렬로 표현하면 다음과 같다.

0 1 1 0 0
0 0 0 0 1
0 0 0 1 0
0 1 0 0 0
0 0 0 0 0

코드로 나타내면 다음과 같다.

graph = [[0] * (n+1) for _ in range(n+1)

for [a, b] in edge:
	graph[a][b] = 1

인접리스트를 활용한 코드는 다음과 같다.

graph = [[] for _ in range(n+1)]

for [a,b] in edge:
	graph[a].append(b)