그래프 기본

그래프 종류 및 개념

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를 큐에 넣고, 방문한 것으로 표시