[자료구조] 8주차 - 그래프 (Graph)

Graph

node(vertex), edge(link), graph

쾨니히스베르크(Konigsberg) 다리 문제

• 홀수 개의 edge에 연결된 vertex의 수가 4개 이상이면 한 붓 그리기가 불가능

그래프의 개념

정의

• 개체들 사이의 일대일 관계를 시각적으로 표현한 수학적 모델
• 그래프는 vertex(꼭짓점, 정점)와 edge(간선)의 집합
• G = (V, E)

그래프의 표현

1. 그래프의 수학적 표현

   • V = {0,1,2,3}
   • E = {(0,2), (0,3), (1,2), (1,3)}

2. 그래프의 시각적 표현

3. Edge리스트를 이용한 표현

   • 4, 4 : V의 수, E의 수 (Vertex : 0~3)

     0, 2 : Edge

     0, 3 : Edge

     1, 2 : Edge

     1, 3 : Edge

그래프의 종류

• 무방향 그래프, 방향 그래프
• 가중치 그래프(Weighted Graph), 방향 가중치 그래프
• 특별한 그래프
  • self edge를 가진 그래프
  • multi edge를 가진 그래프
• 복잡도에 따른 그래프
  • 희소 그래프 (sparse graph) : O(n)
    • 각 vertex들이 상수 개의 vertex와 연결된 그래프
    • 한 vertex에서 연결된 vertex의 수 : O(1)
    • Edge의 수 : O(n)
  • 밀집 그래프 (dense graph) : O(n^2)
    • n개의 vertex들 대부분이 서로 연결된 그래프
  • 완전 그래프 (complete graph) : O(n^2)
    • n개의 vertex들이 서로 연결된 그래프
    • 하나의 vertex가 n-1개의 vertex와 연결됨
    • edge의 수 : n(n-1)/2, n(n-1) [방향그래프의 경우]

그래프의 용어

vertex & edge

Adjacent(인접) & Incident

• vertex u와 v가 edge로 연결되어 있다면
  • (u, v) ∈E
  • u와 v는인접해 있다(adjacent)
• 두 edge가 같은 vertex를 공유하고 있다면
  • 두 edge는 incident하다

부분 그래프(Subgraph)

• G = (V, E)이고G’ = (V’, E’)일때, V’ ⊆ V and E’ ⊆ E

• G’은 G의 부분 그래프(subgraph)임

경로(Path)

• Path(1, 7) : (1,0,2,4,6,7)

• Path(1, 7) : ( (1,0), (0,2), (2,6), (6,7) )

• 여러개의 경로가 존재할 수 있음

• 경로의 길이 : 경로에 있는 vertex 또는 edge의 수

  • Path(1, 7)의 길이 : 5(vertex) 또는 4(edge)
  • 가중치 그래프의 경우 가중치(weight)의 합

• 최단 경로 :길이가 최소인 경로

• 단순 경로 : 시작 vertex와 끝vertex를 제외한 모든 vertex가 서로 다른 경로 (중복X)

순환(Cycle)

• 첫번째 vertex와 마지막 vertex가 일치하는 단순 경로
• 비순환 그래프 : 순환이 존재하지 않는 그래프

연결(Connected)

• vertex 수준 : u와 v 사이에 경로가 존재할 때 두 vertex는 열결 되었다고 함

• graph 수준 : 모든 쌍의 vertx들이 연결되어 있을 때, 이 그래프는 연결 되어 있다고 함

• 연결 성분 : 연결된 그래프의 최대치

• 트리(Tree)는 연결된 비순환 그래프

• 방향 그래프에선 강한 연결과 강한연결성분이 있음.

  • 연결이라는 말은 쓰지 않음 (무방향에서만 사용)
  • 두 vertex가 두 방향 모두에서 연결 되어 있어야 강한 열결임

Vertex의 차수 (Degree of a vertex)

• Vertex에 연결된 Edge의 수

신장 트리 (Spanning tree)

• 그래프 G = (V, E)의 부분그래프 T = (V’, E’)가 다음의 조건을 만족시킬때
  • V’ = V and E’ ⊆ E and |E’| = |V| -1
  • E’ 은순환이없음
• 여러 개의 신장 트리가 존재함

그래프의 기본 연산

그래프의 구현

1. Edge 리스트

2. 인접 행렬

3. 인접 리스트

STL을 이용한 그래프의 구현 (인접리스트)

nptredge[10001];
void main ( ) {
    scanf("%d %d”, &n, &m);
          for (i = 0; i < m; i++){
              scanf("%d %d", &u, &v);
              edge[u].add(v);
              edge[v].add(u);
          } 
}

인접 행렬과 인접 리스트 성능 비교

• 예) 모든 vertex에서 인접한 vertex 출력
• 완전/밀집 그래프 : 둘 다 O(n^2)
• 희소 그래프 : 인접행렬 O(n^2), 인접 리스트O(n)

그래프의 연산

1. DFS
2. BFS
3. 연결 성분(connected component)
4. 신장 트리(spanning tree)
5. 이중 연결 성분(Biconnected component)
6. 강한 연결 성분(Strongly connected component)
7. 최단 거리 (shortest path)