[자료구조] 11장 그래프

1. 그래프

  - 오일러 정리: 모든 정점에 연결된 간선의 수가 짝수이면 오일러 경로가존재함.

  - 동일한 그래프? 배열로 정점의 집합과 간선의 집합을 나타냈을 떄 두 배열이 다른 그래프의 배열과 동일할 때.

  - 방향그래프, 무방향 그래프, 가중치 그래프, 부분 그래프

 

2. 그래프 용어

• 인접 정점 - 자신과 간선으로 직접 연결된 정점
• 차수 - 자신과 연결된 정점의 수
• 그래프의 경로
• 경로의 길이 - 경로를 구성하는데 사용된 간선의 수
• 단순 경로 - 경로 중에 반복 간선이 없는 경로
• 사이클 - 시작 정점과 종료 정점이 동일한 경로
• 연결 그래프 - 모든 정점쌍에 대한 경로 존재
• 트리 - 그래프의특수한 형태. 사이클이 없음
• 완전 그래 - 모든 정점이 연결되어 있는 그래프

3. 그래프 표현 방법1: 인접행렬

 

4. 그래프 표현 방법2: 인접 리스트

 

5. 그래프 탐색 방법1: DFS -> 인접 행렬 사용

• 한 방향으로 갈 수 없을 때까지 쭉 갔다가 더 이상 갈 수 없게되면 가장 가까운 길로 돌아와 다시 탐색.
• 스택 필요.

 

6. 그래프 탐색 방법2: BFS -> 인접 리스트 사

• 시작 정점부터 가까운 정점 먼저 방문. 

 

7. 신장트리

• 모든 정점들이연결되어 있고,사이클이 포함되면 안 됨.
• 신장 트리는 n-1개 간선을가짐.

 

8. 가중치 그래프

• 표현 방법1: 가중치를 위한 추가적인 배열 사용
• 표현 방법2: 인접행렬을 가중치를 위해 사용 -> 선호
  • 간선이 없으면 매우 큰 값을 가지도록 함

9. 최소비용 신장 트리

MST: Minimum Spannig Tree: 네트워크에 있는 모든 정점들을 가장 작은 수의 간선과 비용으로 연결

<최소 비용 신장트리의 조건(3)>

• 간선의 가중치 합이최소
• 반드시 n-1개의 간선만 사용
• 사이클이 포함되면 안됨

<종류>

  (1) kruskal의 MST

       : 간선들 중 가중치가 가장 작은 간선을 선택함. 만약 사이클이 있으면 선택을 취소하고 앞 내용 반복.

         - 최소 가중치 선택 어떻게?

           -> minHeap 사

         - 사이클 검사는 어떻게?

           -> Union-find 알고리즘

              find: 원소가 어떤 집합에 속하는지 알아냄

              union: 두 집합들의 합집합을 만듦.

         - 퀵정렬로 정렬한다면 kruskal의 시간 복잡도는 O(e*(log(e))

윗부분은 가중치를저장하는코드, 아랫부분은 union-find부분. 각 정점이 속한 집합이 다르면 union

• parent[i] < 0: 노드 i가 속한 집합의 대표(루트) 노드이며, 해당 집합의 크기는 -parent[i]
• parent[i] >= 0: 노드 i의 부모 노드의 인덱스를 나타냄.

 

  (2) Prim의 MST

         - 시간 복잡도 = O(n^2)

         - 간선이 희박하면 kruskal이 유리

         - 간선이 밀집되어있으면 prim이 유리

 

10. 최단 경로 문제

최단 경로: 네트워크에서 정점 u와 v를 연결하는 경로 중 간선드의 가중치 합이 최소가 되는 경로

<종류>

  (1) Dijkstra 최단 경로 알고리즘

       : 새로운 정점이 S에 추가되면 distance 값 갱신.  

      - 시간 복잡도: o(n^2)

  (2) Floyd의 최단 경로 알고리즘

      - 시간 복잡도: o(n^3)