그래프

그래프

• 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합과, 이들을 연결하는 간선(edge)들의 집합으로 구성된 자료구조
• 그래프가 트리보다 넓은 개념. (트리는 계층적 구조)

그래프 종류

• 방향 그래프 vs 무향 그래프
  방향 그래프(방향이 존재)
  무향 그래프(방향 미존재)
• 다중 그래프 vs 단순 그래프
  다중 그래프(두 점을 연결하는 간선이 여러 개가 될 수 있음)
  단순 그래프(두 점을 연결하는 간선이 한 개)
• 가중치 그래프 -> 다익스트라
  한 점을 기준으로 간선들의 가중치가 존재

그래프 활용

• 도시들을 연결하는 도로망
• 지하철 연결 노선도
• 컴퓨터 네트워크
• 소셜 네트워크 분석

그래프 표현 방법

인접 행렬

graph = [
	[0, 0, 1, 0, 1],
	[0, 0, 0, 1, 1], 
	[1, 0, 0, 0, 1], 
	[0, 1, 0, 0, 1], 
	[1, 1, 1, 1, 0], 
]

인접 리스트

graph = {
	1 : [3, 5],
	2 : [4, 5], 
	3 : [1, 5], 
	4 : [2, 5], 
	5 : [1, 2, 3, 4] 
}

암시적 그래프

• x,y좌표로 된 맵을 행렬에 옮긴 것

graph = [
	[1, 1, 1, 1, 1],
	[0, 0, 0, 1, 1], 
	[1, 1, 0, 1, 1], 
	[1, 0, 0, 0, 0], 
	[1, 1, 1, 1, 1], 
]

참고자료

https://www.inflearn.com/course/%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EC%9E%85%EB%AC%B8-%ED%8C%8C%EC%9D%B4%EC%8D%AC