그래프 (Graph)

 

노드와 그 노드를 연결하는 간선을 하나로 모아 놓은 것.

 

간선의 방향이 있는 그래프 -> 방향 그래프

간선의 방향이 없는 그래프 -> 무방향 그래프

모든 정점이 간에 경로가 존재하는 그래프 -> 연결 그래프

사이클이 있는 그래프 -> 순환 그래프

사이클이 없는 그래프 -> 비순환 그래프

간선에 가중치가 할당된 그래프 -> 가중치 그래프, 네트워크

사이클이 없는 방향 그래프 (자기 자신으로 돌아오는 경로가 없는 그래프) -> DAG (directed acyclic graph)

정점들이 겹치지 않는 두 개의 그룹으로 나눌 때 서로 다른 그룹의 정점들 간에만 간선이 있는 그래프 -> 이분 그래프 

 

코드에서 그래프를 표현하는 방법

1. 인접 리스트

   ->한 정점에서 갈 수 있는 다른 정점들을 리스트로 저장 

   ->무방향 그래프에서 (a, b) 간선은 두 번 저장된다. a 기준에서 b, b 기준에서 a

2. 인접 배열

   ->m[i][j]가 1이라면 i에서 j로 갈 수 있는 간선이 존재함을 의미

   ->무방향 그래프의 인접 행렬은 대칭행렬이다.

 

그래프 탐색

1. 깊이 우선 탐색 (depth-first search, dfs)

   ->임의의 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법\

   ->모든 노드를 방문하고자 할 때 더 선호됨

2. 너비 우선 탐색 (breadth-first search, bfs)

   ->임의의 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법

   ->두 노드 사이의 최단 경로 혹은 임의의 경로를 찾을 때 더 선호됨

3. 양방향 탐색

   ->출발지와 도착지 두 노드에서 동시에 너비 우선 탐색을 수행한 뒤, 두 탐색 지점이 충돌할 때의 경로를 찾는 방식