그래프

그래프

• 자료구조의 일종
• 정점 (Node, Vertex)와 간선 (Edge)로 이루어져 있다.
• G = (V, E) 로 나타낸다. (그래프 G는 정점 V와 간선 E의 집합)

경로 (Path)

• 정점 A 에서 B 로 가는 모든 경로

사이클 (Cycle)

• 정점 A 에서 다시 A로 돌아오는 모든 경로

단순 경로와 단순 사이클

• 같은 정점을 두 번 이상 방문하지 않는 경로 / 사이클
• 일반적으로 사용하는 경로와 사이클은 단순 경로와 단순 사이클이다.

그래프의 표현

• 간선에 방향이 없으므로 양방향 그래프이다.
• 정점 : {1,2,3,4,5,6}
• 간선 : {(1,2), (1,5), (2,5), (2,3), (3,4), (2,4), (4,5), (4,6)}

그래프의 저장

• 인접 행렬

  • 정점의 개수를 V라고 하면 V * V 크기의 이차원 배열을 이용한다.
  • A[i][j] = 1 (i에서 j까지의 간선이 있을 때) A[i][j] = 0 (간선이 없을 때)
  • 존재하지 않는 간선까지 저장하기 떄문에 많이 사용빈도가 높은 편은 아님

  # 양방향 그래프 인접행렬로 구현
  import sys
  input = sys.stdin.readline
  
  n,e = map(int, input().split())
  arr = [[0 for i in range(n)] for j in range(n)]
  
  for i in range(e):
      start, end = map(int, input().split())
      arr[start][end] = 1
      arr[end][start] = 1

• 인접 리스트

  • 각 노드에 연결된 노드를 원소로 갖는 리스트들의 배열
  • A[i]은 i와 연결된 정점을 링크드 리스트로 포함하고 있음
    • A[1] 2 5
    • A[2] 1 3 4 5
    • A[3] 2 4
    • A[4] 3 5 2 6
    • A[5] 1 2 4
    • A[6] 4
  • 간선의 개수만큼 저장할 수 있음

  # 양방향 그래프 인접리스트로 구현
  import sys
  input = sys.stdin.readline
  
  n,e = map(int, input().split())
  arr = [[] for i in range(n)]
  
  for i in range(e):
      start, end = map(int, input().split())
      arr[start].append(end)
      arr[end].append(start)