Graph - 그래프

 

 

Graph

G = (V, E)
V : node/vertices의 집합
E : edge/link의 집합

• undirected graph - 방향이 없음 (E를 집합으로 나타냄 {A, B} )
  • N(v) - v의 주변 노드의 집합
  • deg(v) = |N(v)| 주변 노드의 수
• directed graph - 방향이 있음 (E를 순서쌍으로 나타냄 (A, B) 랑 (B, A)는 다름 )
  • u->v , u<-v 하는 모든 u가 v의 주변 집합
  • $N^{-}(v)$ v로 들어오는 노드
  • $N^{+}(v)$ v로 나가는 노드
  • $deg^{-}(v)$ 들어오는 노드의 수 in-degree
  • $deg^{+}(v)$ 나가는 노드의 수 out-degree

Various Graphs

• simple graph
• multigraph - 두 노드를 잇는 edge가 여러 개
• pseudograph - multigraph 인데 loop 허용
• hypergraph - edge가 여러개의 vertice를 지날 수 있음

Adjacency Matrix - node와 node 사이가 연결되어 있는 지 나타냄

• 대각 성분이 0이면 loop가 없는 것
• 대칭 행렬이면 undirected
• 0과 1로만 이루어져 있으면 unweigted simple graph

Incidence Matrix - 한 edge가 어떤 vertex와 vertex를 잇는 지 알 수 있는 행렬
 

Topological Sort = Topological Ordering

DAG(directed Acyclic Graph)일 때 방향을 고려하여 모든 정점을 연결하는 방법을 찾는 것!
순서가 있을 때 자주 씀
 

Kahn's algorithm (In- degree)

1. Queue를 만들어 indegree(자기로 들어오는 edge의 수) 가 0인 모든 노드를 enqueue한다
2. Queue가 빌때까지 while 문 반복 - 모든 edge에 대해서 해준다고 생각!
   1. dequeue를 한 후에
   2. 그 노드가 향하는 모든 노드의 indegree를 -1 해준다. 
   3. 만약 그 주변 노드 중 indegree가 0이 된다면 queueq에 넣어준다.

시간 복잡도는 처음 1. 과정에서 O(V) + 2. 과정에서 O(E) 여서 O(V+E)이다. 

---

BFS - level order

1. start노드에서 부터 시작해 방문한 노드인지 확인하며 방문하지 않았을 경우 그 노드 주변 노드를 큐에 넣어준다.
2. 큐에서 하나씩 빼면서 다시 1을 반복한다. 

DFS - pre-, in-, post- order

제일 아래쪽 노드까지 다녀오는 건데 나는 저 pre-order, in-order, post-order가 계속 헷갈렸다. 
근데 멍청인가? 너무 간단한 이유였다 뭐지 주입식 교육의 폐해인가...라고 변명해 본다. 
root를 언제 방문하느냐에 따라 pre,in,post라는 이름이 붙은 거다.
📍print위치 잘 보기
 

pre-order

는 order 전에 root 를 방문하는 것으로 코드로 보면

def preorder(root):
    if root: 
        return
    print(root.val)
    preorder(root.left)
    preorder(root.right)

root -> left -> right 다
 

in-order

는 order 안에 root를 방문하는 거라 

def inorder(root):
    if root:
        return
    inorder(root.left)
    print(root.val)
    inorder(root.right)

left -> root -> right
 

post-order

는 이제 감이 오겠죠?

def postorder(root):
    if root: 
        return
    postorder(root.left)
    postorder(root.right)
    print(root.val)

left ->  right -> root
 
모두 DFS의 종류이다!

---

Weighted Graph

edge에 가중치 값이 있는 graph를 다뤄보자
Minimum Spanning Tree 랑 Shortest Path problem을 다룰 건데
둘의 차이는 MST는 모든 점을 최소 요금으로 연결하는 거라고 생각하면 좋다. Graph를 Tree로 만들기! 도시 도로 공사한다고 생각하자.
SPP는 한 노드에서부터 나모지 노드까지 최소 시간을 다 찾는 거다. 집까지 어딘가로 갈때 가장 빠른 루트 찾기라고 생각하자.

Minimum Spanning Tree

2개의 노드 사이의 거리가 최소가 아닐 수 있음! 전체를 보는 것임!

Prim's Algorithm - 우선순위 큐, 방문한 노드 표시

1. 📍우선순위 큐를 만들어 start를 제외한 모든 노드의 weight를 NIL로 넣고 시작한다. (weight가 적은 것을 골라야 해서 우선순위 큐 사용)
2. 큐에서 하나 빼서 방문했다고 표시해준다.
   1. 노드의 주변 노드들을 보면서 원래 갖고 있던 값보다 새로 업데이트 하는 값이 더 작을 경우 값을 업데이트 해준다. 우선 순위 큐를 업데이트 해준다. 
   2. 큐에 아무것도 없을 때까지 반복한다. 

 Kruskal's Algorithm - disjoint

1. 모든 edge를 오름차순으로 정렬하고, vertex도 각각 set을 하나씩 만든다.
2. edge를 하나씩 빼내서 만약 그 edge의 2개 노드가 서로 disjoint 이어준다.

kruskal 을 실행할 때 disjoint set을 구축하기 위해 tree를 사용한다. 

Tree의 정의는 connected acyclic graph이다. 

한 tree에 있는 경우 같은 set에 있다는 것을 의미한다. 

 

Union 하는 경우 depth가 더 얕은 tree를 더 깊은 tree에 연결해 주어 효율성 문제가 생기지 않도록 한다.

그렇다면 depth를 어떻게 추적할까, array에

root가 아닌 경우에는 parent node index를 넣어주고

root 노드이면 -(depth)를 넣어주는 것으로 해결해 볼 수 있다.

Shortest Path Problem

하나의 Vertex로부터 나머지 모든 vertex까지 최소 거리 찾기

Dijkstra's Algorithm

프림 알고리즘과 굉장히 유사한데, 업데이트 할때 누적값으로 업데이트 해준다. 
누적값를 통해 시작점으로부터 최소거리임을 확인할 수 있는 것이다. 그래서 방문했는지 안했는지 체크해줄 필요가 없다. 
처음부터 가장 최소 거리로 보장하면서 알고리즘이 진행되기 때문에 방문을 했는데 더 짧은 거리가 존재할 수 없다. 
프림은 방문했는지 안했는지와 더 작은 값을 찾았는 지 유무로 거리값을 업데이트 할지 결정했다면
다익스트라는 더 빠른 길을 찾았냐 안찾았냐로 거리값을 업데이트 할지 말지를 결정한다. 

Bellman-Ford

이것은 음수 값일 때도 적용 가능한 알고리즘이다.
사실 음수 값일 때도 다익스트라로 찾을 수 있는 경우도 있는 데 음수 간선 순환이 있을 경우에도 할 수 있다고 한다.
다익스트라는 우선순위 큐에서 계속 노드를 빼내면서 진행했다면
벨만포드는 모든 edge를 for문으로 돌면서 관찰해 시간은 더 오래 걸린다.