[자료구조]그래프

그래프

정점과 간선으로 이루어져 있다
방향성이 없는 그래프를 가리켜 무방향 그래프
방향정보가 포함된 그래프를 가리켜 방향 그래프, 다이그래프
그 중에서 각각의 정점에서 다른 모든 정점을 연결한 그래프 완전 그래프
간선에 가중치 정보(두 정점 사이의 거리, 두 정점 사이의 걸리는 시간...)를 둔 가중치 그래프

그래프의 표현

그래프 G의 정점 집합 V(G)
그래프 G의 간선 집합 E(G) 으로 표시할때
정점 A 에서 정점 B 간의 간선 하나있는 무방향 그래프는
V(G) = {A, B}
E(G) = {<A, B>} 로 나타낼 수 있다

방향 그래프에서 <A, B>와 <B, A> 는 다른 간선 이다

그래프의 구현

인접 리스트

배열 또는 해시테이블로 구현하여 각 인덱스마다 존재하는 또 다른 리스트는
연결리스트, 배열 어떤 것으로 구현해도 상관없다

ex)
0: 1, 2
1: 0
2: 0

인접 행렬

N x N 행렬 matrix[i][j] 가 true 면 i에서 j로 가는 간선이 있다는 뜻
무방향 그래프는 대칭 행렬이 된다

 

인접 리스트 기반으로 구현하면 인접 행렬 기반의 구현도 차이가 없기 때문에 문제 되지 않는다

인접 리스트 로 구현 하기 위해서 연결 리스트가 필요하다

무방향 그래프로 구현하면 방향그래프는 쉽게 구현할 수 있다

무방향은 리스트 연결하는 과정을 두번하면 되기 때문이다

 

python