그래프 종류
•
방향 그래프
◦
간선의 방향이 한 방향으로 정해져 있는 그래프
•
양방향 그래프
◦
간선의 방향이 양방향인 그래프
•
가중 그래프
◦
간선에 가중치가 존재하는 그래프
그래프를 코드로 표현하는 방법 3가지
1.
인접 리스트 (Adjacency List)
•
각 노드를 기준으로 연결된 노드를 저장하는 방식
더 보기
2.
인접 행렬 (Adjacency Matrix)
•
(노드의 개수) x (노드의 개수) 형태의 행렬을 만든 후에 간선을 표현하는 방식
더 보기
3.
간선 리스트 (Edge List)
•
간선의 정보만을 간단히 표현하는 방식으로, 간선 1개당 노드 2개로 표현하는 방식
더 보기
내용 정리
•
인접 리스트
◦
그래프를 코드로 표현할 때 이 방법을 기본(default)로 생각하면 된다.
▪
어떤 노드와 연결된 노드들을 쉽게 접근할 수 있다.
▪
따라서, 그래프 순회(탐색)에 사용하기에 적합한 형식이다.
◦
최단 경로 알고리즘의 다익스트라 알고리즘을 구현할 때에 쓰인다.
•
인접 행렬
◦
어떤 노드 A에서 B로 가는 간선을 확인해야 하는 작업이 많은 경우에 사용하면 된다.
▪
adj_matrix[A][B] 를 접근하면 되기 때문에 에 확인할 수 있다.
◦
최단 경로 알고리즘의 플로이드 워셜 알고리즘을 구현할 때에 쓰인다.
•
간선 리스트
◦
간선들을 기준으로 무언가를 처리해야할 때 사용하면 된다.
◦
최단 경로 알고리즘의 벨만-포드를 구현할 때에 쓰인다.
인접 행렬과 간선 리스트는 플로이드-워셜 알고리즘, 벨만-포드 알고리즘을 사용하는 것이 아니면 거의 쓸 일이 없다.