알고리즘을 풀기 위한 그래프 지식

그래프 기본

그래프 종류 및 개념

  1. 무향 그래프 - 방향 없는 그래프

  2. 유향 그래프

  3. 가중치 그래프

  4. 사이클 없는 방향 그래프

  5. 완전그래프 - 정점들에 대해 가능한 모든 간선들을 가진 그래프

  6. 부분 그래프 - 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프

    인접(Adjacency)

    • 두 개의 정점에 간선이 존재하면 서로 인접해있다고 한다.
    • 완전 그래프에 속한 임의의 두 정점들은 모두 인접해 있다.

그래프 경로

  • 경로란 간선들을 순서대로 나열한 것
    • 간선들 : (0,2), (2, 4)
    • 정점들: 0, 2, 4
  • 경로중 한 정점을 최대한 한번만 지나는 경로를 단순경로라 한다.
  • 시작한 정점에서 끝나는 경로를 사이클 이라고 한다.

그래프 표현

  • 간선의 정보를 저장하는 방식, 메모리나 성능을 고려해서 결정

  • 인접행렬

    • |V| x |V| 크기의 2차원 배열을 이용해서 간선 정보를 저장

    • 배열의 배열

    • 무향 그래프

      • i번째 행의 합 = i번째 열의 합 = Vi의 차수
    • 유향 그래프
      - 행 i의 합 = Vi의 진출 차수
      - 열 i의 합 = Vi의 진입 차수

      인접행렬 코드(python)

      
      V, E = map(int, input().split())
      edge = list(map(int, input().split())
      adj = [[0]*(V+1) for _ in range(V+1)]
      for i in range(E):
          n1 = edge[i*2]
          n2 = edge[i*2+1]
          adj[n1][n2] = 1
          adj[n2][n1] = 1 # 무향 그래프인 경우 대칭
  • 인접 리스트

    • 각 정점마다 해당 정점으로 나가는 간선의 정보를 저장

    • 각 정점에 대한 인접 정점들을 순차적으로 표현

    • 하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결 리스트로 저장

      인접리스트 코드(python)

      
      V, E = map(int, input().split())
      edge = list(map(int, input().split())
      adj_list = [[]*(V+1) for _ in range(V+1)]
      for i in range(E):
          n1 = edge[i*2]
          n2 = edge[i*2+1]
          adj[n1].append(n2)
          adj[n2].append(n1) # 무향 그래프인 경우 대칭
  • 간선의 배열

    • 간선(시작 정점, 끝 정점)을 배열에 연속적으로 저장

그래프 순회(탐색)

DFS(깊이 우선 탐색)

시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 탐색해 가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회 방법

  • 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택 사용
    stack사용한 코드

    STACK s
    visited[]
    DFS(v)
        push( s, v )
        WHILE NOT isEmpty( s )
            v <- poop(s)
            IF NOT visited[v]
                visited ( v )
                FOR each w in adjacency( v )
                    IF NOT visited[w]
                        push(s, w)

    재귀를 사용한 코드

    DFS_Recursive(G, v)
        visited[ v ] <- TRUE // v 방문 설정
        FOR each all w in adjacency( G, V )
            IF visited[w] is not TRUE
                DFS_Recursive(G, w)

BFS(너비 우선 탐색)

탐색 시작점의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식

  • 인접한 정점들에 대해 탐색한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용함.
BFS(G, v)
    큐 생성
    시작점에 v를 큐에 삽입
    점 v를 방문한 것으로 표시
    WHILE 큐가 비어있지 않은 경우
    	 t <- 큐의 첫번째 원소 반환
         FOR t와 연결된 모든 선에 대해 
         	u <- t의 이웃점
            u가 방문되지 않은 곳이면, 
            u를 큐에 넣고, 방문한 것으로 표시

좋은 웹페이지 즐겨찾기