[자료구조] Chap12 그래프, 그래프 탐색

Chap12 그래프, 그래프 탐색

1. 그래프의 개념

• 그래프 G1의 노드 V(G1) = {0,1,2,3,4}
• 그래프 G1의 간선 E(G1) = {(0,1) ..} ()는 무방향. {<0,1>..} <>는 방향이 있는 간선. G1은 방향그래프.
• 분리된 그래프 : 모든 루트가 연결되어있지 않고 분리되어있지만 하나의 그래프임. <-> 연결된 그래프
• 용어 정리  
  1. 완전 그래프 : 간선 수가 최대. 모든 각 노드에 모든 노드로의 간선이 존재. 완전그래프인 방향그래프에 n개의 노드가 있으면 간선의 수는 n(n-1), 무방향이면 n(n-1)/2
  2. 인접 : 두 노드를 직접 연결하는 간선이 존재하면 두 노드는 인접하다고 함
  3. 부속 : 두 노드를 직접 연결하는 간선이 존재하면 그 간선에 양쪽 노드가 부속된다고 함.
  4. 부분 그래프 : 그래프의 간선들과 노드들의 일부(부분집합)로 구성된 그래프. 
  5. 경로 : 
  6. 경로의 길이 : 경로 상의 간선 수
  7. 단순 경로 : 경로 상의 노드가 중복되지 않는 경로
  8. 사이클 : 단순 경로 중 경로가 다시 원점에 도달하는 경우
  9. 연결됨 : 경로가 있음
  10. 연결된 부분 : 부분 그래프 중 최대로 연결되어있는 부분그래프들
  11. 트리 : 사이클이 없는 연결된 그래프이며 루트노드가 1개임.
  12. 강연결, 강연결 요소 : 그래프의 각 노드들에서 다른 노드로 가는 경로(여러 노드나 간선을 거쳐도 갈 수만 있으면 됨)가 모두 존재할 때 강연결돼있다고 함. 강연결된 최대의 부분 그래프를 강연결 요소라 함. (완전그래프이면 강연결임. 강연결되어있지만 완전그래프는 아닐 수 있음)
  13. 차수 : 노드에 부속된 간선의 수

 

2. 그래프의 표현방법 (노드 수 n개)

1. 인접 행렬
   • 이차원 행렬 형식으로 그래프를 표현.
   • 행열번호는 각 노드로부터 다른 노드로 연결됨을 나타내고 행렬의 값은 각 노드를 잇는 간선의 존재 여부이다.존재(인접)하면 1, 없으면 0.
   • 무방향 그래프이면 인접행렬이 대각선 대칭임. 공간복잡도는 n^2
2. 인접 리스트
   • n개의 연결리스트로 그래프 표현.
   • 각 연결리스트에는 각 노드에 연결된 간선들이 줄줄이 연결되어있음

 

3. 그래프의 탐색

1. DFS(Depth First Search) 깊이 우선 탐색
   • 스택 활용. (그래프는 인접리스트 등으로 표현되어있는 상황. 탐색에는 큐를 쓴다는 말)
   • 노드를 방문해 원하는 작업을 하고 현재 노드를 스택에 저장한 뒤 간선으로 연결된(자식) 노드로 넘어간다. 더 이상 연결된 노드가 없으면 스택에서 노드를 하나 꺼내 다른 연결된(자식) 노드로 이어간다.
   • 시간복잡도 O(간선 수)
2. BFS(Breath First Search) 너비 우선 탐색
   • 큐 활용.
   • 노드 방문해 원하는 작업을 하고 연결된(자식) 노드들을 모두 큐에 넣는다. 큐에서 (가장 예전에 넣은)하나를 꺼내어 자식 노드로 이동해 작업한다. 그 노드에서도 그 노드의 자식노드들을 모두 큐에 넣는다. 큐에서 (가장 예전에 넣은)하나를 꺼내어 탐색하면 먼저 넣었던 형제노드를 모두 방문한 후 그 다음 레벨로 넘어가게 된다.

그래프 표현과 탐색 코드들 . . . .