그래프

노드
무방향(=양뱡향) vs 방향
순환그래프 vs 비순환그래프
방향성 비순환 그래프 DAG (Diredcted Acyclic Graph)
-> ex) VCS(버전관리 시스템) like git/github

코드로 그래프를 나타내는 방법

인접행렬

행렬에 갈수있으면 1 갈수없으면 0
시간 복잡도 O(V2) -> 정점 갯수의 제곱

인접리스트

한 노드로부터 갈 수 있는 노드들을 연결리스트로
시간 복잡도 O(V+E) -> 정점 갯수+간선 갯수

비교

공간과 시간은 trade off 관계임
인접행렬은 공간을 많이 쓰는 대신에 접근이 빠르고
인접리스트는 공간을 적게 쓰는 대신에 접근이 느리다

DFS

깊이 우선 탐색
기본적으로 완전탐색 -> 깊이를 우선해서 전부 탐색함

• 스택 or 재귀를 사용해 구현함

  
  탐색순서
  0-> 1-> 2-> 3-> 4-> 5-> 6-> 7-> 8-> 9-> 10-> 11-> 12

adj = [ [0] * 13 for _ in range(13)] //2차배열 선언
adj[0][1]=adj[0][7]=1 // 이런식으로 어디에서 어디로 갈 수 있다면 1로 채워줌

def dfs(now):   //dfs함수작성 now에는 아마 0인자가 들어갈것임
    for nxt in range(13):  //13까지 돌면서
        if adj[now][nxt]:  //adj[now][nxt]가 1이면
           dfs(nxt)       //nxt로 넘어감
           
dfs(0)  //사용은 이런식으로

BFS

너비 우선 탐색
마찬가지로 완전탐색, 즉 모든 노드를 탐색하는것은 똑같은데 너비를 우선으로 탐색함

• 큐를 사용해서 구현함 ( pop하면서 갈 수 있는 노드들을 넣음)

  
  탐색순서
  0-> 1-> 2-> 3-> 4-> 5-> 6-> 7-> 8-> 9-> 10-> 11-> 12

from collection import deque
adj = [ [0] * 13 for _ in range(13)] //2차배열 선언
adj[0][1]=adj[0][7]=1 // 이런식으로 어디에서 어디로 갈 수 있다면 1로 채워줌

def bfs:
    dq = deque()
    dq.append(0)
    while dq:   //덱이 빌 때까지 반복
       now = dq.popleft()   
       for nxt in range(13):
           if adj[now][nxt]:  //옆에있는 (같은level)노드가 있다면
              dq.append(nxt)  //넣어줌
              
 def()  //실행