그래프

• 그래프는 아이템들과 이들 사이의 연결관계를 표현함
• 그래프는 정점들의 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료 구조

• 선형 자료구조나 트리 자료구조로 표현하기 어려운 N : N관계를 가지는 원소들을 표현하기에 용이함

• 인접(Adjacency)

  • 두 개의 정점에 간선이 존재하면 (연결되어 있으면) 서로 인접해 있다고 함
    

• 경로

  • 간선들을 순서대로 나열한 것
  • 간선 : (0,2), (2,4), (4,6)
    -> 0 - 2 - 4 - 6
  • 단순 경로
    • 처음 정점과 끝 정점을 제외하고 중복된 정점이 없는 경로

• 사이클 (Cycle)

  • 시작한 정점에서 끝나는 경로를 사이클이라고 함
    

  • 1 - 3 - 5 - 1

유형

• Undirected Graph
  

  • 방향 없는거

• Directed Graph
  

  • 방향 있는거

• Weighted Graph
  

  • 비용, 가중치 있는거

• Complete Graph
  

  • 정점들에 대해 가능한 모든 간선들을 가진 그래프

• Subgraph

  • 원해 그래프에서 일부의 정점이나 간선을 제외한 그래프

• DAG, Directed Acyclic Graph
  https://steemit.com/dag/@cryptodreamers/dag-dag-directed-acyclic-graph

  • 사이클 없는 방향 그래프

표현

• 간선의 정보를 저장하는 방식, 메모리나 성능을 고려해서 결정하면 됨
• 인접행렬
  • 2차원 배열 이용해서 간선 정보
  • 배열의 배열
• 인접 리스트
  • 각 정점마다 해당 정점으로 나가는 간선의 정보를 저장
• 간선의 배열
  • 간선을 배열에 연속적으로 저장

인접 행렬

• 두 정점을 연결하는 간선의 유무를 행렬로 표현
  • V x V 정방행렬
  • 행 번호와 열 번호는 그래프의 정점에 대응
  • 두 정점이 인접되어 있으면 1, 그렇지 않으면 0으로 표현
    
  • 방향 표시가 있으면 표현이 달라짐

'''
7 8 
1 2 1 4 2 4 2 5 4 6 5 6 6 7 3 7
'''

V , E = map(int,input().split())
arr = list(map(int,input().split()))
adjM = [[]*(V+1) for _ in range(V+1)]
for i in range(E):
    n1, n2 = arr[i*2], arr[i*2 + 1]
    adjM[n1][n2] = 1
    adjM[n2][n1] = 1 #방향이 없는 경우   
  

인접 리스트

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

'''
7 8 
1 2 1 4 2 4 2 5 4 6 5 6 6 7 3 7
'''

V , E = map(int,input().split())
arr = list(map(int,input().split()))
adjL = [[] for _ in range(V+1)]
for i in range(E):
    n1, n2 = arr[i*2], arr[i*2 + 1]
    adjL[n1].append(n2)
    adjL[n2].append(n1) # 뱡향이 없는 경우