[C] 그래프 알고리즘 (Graph Algorithm)

정의 :

   - 정점과 간선으로 구성하는 자료 구조ㅠㄷ

 

용어 :

   - 정점, 노드(Vertex, Node)  : 여러 특성을 가질 수 있는 객체

   - 간선(Edge, link)  : 각 노드를 연결하는 선. 화살표나 직선 등 형태는 다양하다.

   - self-loops  : 노드에서 자기 자신으로 돌아오는 간선. 

   - Adjacency  : 방향 그래프(Directed Graph) 에서 간선으로 연결된 이동가능한 인접 노드. 방향그래프의 간선은 편도이므로 역방향의 노드는 Adjacency 가 아니다.

   - Degree  :

      1) 각 노드에 연결된 간선의 수.

      2) in-degree 는 해당 노드로 들어오는 간선. out-degree 는 해당 노드를 나가는 간선. 

      3) Degree = in-degree + out-degree

   - Path  : 한 노드에서 다른 노드로 이동 가능한 경로. 이동 가능한 경로가 있다면 reachable 이라고도 표현한다.

   - Simple Path  : 경로 상의 모든 노드가 중복되지 않는 경우. 거쳐간 노드를 지나선 안된다.

   - Cycle(폐로)  :

      1) 그래프가 path를 따라 동일한 노드로 돌아올 수 있는 경우.

      2) Simple Cycle  : 돌아오는 경로에서 중복 노드가 시작점(끝점) 외에 발생하지 않는 경우.

   - Connected Component  : 방향이 없는 그래프의 노드 하위 집합을 최대로 연결한 것.

   - Tree  : 사이클(Cycle) 이 없는 '연결' 그래프. 

   - Forest  : 사이클(Cycle) 이 없는 '비연결' 그래프.

 

그래프 종류 :

   - 가중치 그래프(Weighted Graph)  : 간선 위에 비용(cost)나 가중치(weight)가 들어간 그래프. 그래프에 가중치가 없다면 모두 동일한 가중치를 가진다.

   - 방향 그래프 (Directed Graph)  : 간선 방향에 따라 편도 이동만 가능하다. 역주행이 불가능하다. (A to B ≠ B to A)

   - 무방향 그래프 (Undirected Graph)  : 간선에 방향이 없어 어디로든 이동이 가능. 역주행 가능. (A to B = B to A)

   - 부분 그래프 (Sub Graph)  : 노드 집합 & 간선 집합으로 이루어진 그래프

   - Acyclic Graph  : 사이클(Cycle) 이 없는 그래프

   

 

그래프 탐색 기법 :

   - Breadth-first search (BFS)  :

   - Depth-first search (DFS)  :