기초적인 그래프 연산들

📌 기초적인 그래프 연산들

💡깊이 우선 탐색(Depth First Search)

1. DFS 알고리즘
   • 출발 정점, v의 인접리스트부터 방문한다.
   • v에 인접하면서 아직 방문하지 않은 정점 w를 선택한다.
   • w를 시작점으로 하여 다시 DFS를 시작한다.
   • 순환 알고리즘을 이용하여 구현한다.(재귀)

💡너비 우선 탐색(Breath First Search)

1. BFS 알고리즘
   • 출발 정점, v의 인접 리스트부터 방문한다.
   • v에 인접한 모든 vertex부터 방문한다.
   • 그 다음, v에 인접한 첫번째 vertex에 인접한 vertex 중에서
     아직 방문하지 않은 vertex 들을 차례대로 다시 방문한다.
     -> Queue 자료구조를 사용하여 구현

💡연결요소(Connected Component)

1. 무방향성 그래프가 연결되어 있는지 검사한다.
   • DFS, BFS를 호출하여 방문하지 않은 정점이 있는지 검사한다.

💡신장트리(Spanning Tree)

1. 신장트리 : 그래프 G에 포함된 예시들로 구성되며, G의 모든 정점을 포함한 트리이다.
   * 싸이클 제외, 정점 N개 -> 엣지 (N - 1)개

 

2. DFS or BFS로 신장트리를 구성한다.
   • DFST(깊이 우선 신장 트리)
   • BFST(너비 우선 신장 트리)

💡단절점(Articulation Points)

1. 그래프 G의 정점 V에 연결된 Edge들을 모두 삭제할 경우,
   G가 두 개 이상의 연결요소로 분할되는 V

2. 이중 연결 그래프(Biconnected Graph)
   • 단절점이 없는 Connectd Graph

3. 이중 연결 요소(Biconnected component)
   • 연결 그래프 G에서 Maximal Biconnected Subgraph, H
   • Maxiaml : 이중연결 되었으면서, H를 완전히 포함하는 부분 그래프가
     G에 존재하지 않는다.

어떤 노드를 연결했을 때, 단절점이 생길 수 있다.