컴퓨터과학/자료구조

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

윤호 2021. 2. 3. 00:01

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)