Graph - Graph Traversal

Graph Traversal

• 로컬에서 대부분의 일처리
• 글로벌한 관점에서의 정보

• 어떤 순서에 따라 노드들을 방문
  같은 노드를 여러번 방문할 수도 있다.
• 순회의 결과로는 보통 Tree가 생긴다.

---

Any-Order Traversal

1. 시작 노드를 Box에 넣는다.
2. Box가 비워질때까지 계속 아래를 반복한다.
   • Box에서 노드를 하나 꺼낸다.
     만약 노드가 마킹 되어있지 않다면
     1. 노드를 마킹한다.
     2. 뭔가 필요하다면 계산을 한다.
     3. 노드에 인접한 모든 노드들을 Box에 넣는다.

---

Reachability

• s노드에서 t노드까지 갈 수 있을까?

1. 다익스트라를 했더니
   t 노드의 값이 무한대(시작 값)가 아니라면 갈 수 있는길이 있다는 뜻.
2. Any-order Traversal 을 했더니
   t노드에 마킹이 되어있다면 갈 수 있다는 뜻.

증명)
인접한 노드를 무조건 Box에 넣고 Box가 전부 비워질 때까지 반복하므로
s노드에서 t노드로 가는 길이 있을 때
t노드가 마킹 안되어 있다는 것은 인접한 노드에 마킹을 하지 않았다는 의미.
따라서 모순이다.

---

Connected Component

• 가능한 제일 큰 연결된 덩어리 찾기
• Connected Component는 maximal(극대)이다.
  즉, 글로벌(maximum)이 아닌 로컬에서 가장 크다.

1. 아무데서나 시작해서 Any-order traversal을 한다.
   ⇒ Connected component를 하나 찾았다. (마킹된 노드들)
2. 마킹 안된곳에서 다시 Any-order traversal을 한다.
   ⇒ Connected component를 하나 더 찾았다.
3. 마킹 안된곳이 없을 때까지 반복

---

Time Complexity

1. 시작 노드를 Box에 넣는다.
2. Box가 비워질때까지 계속 아래를 반복한다.
   • Box에서 노드를 하나 꺼낸다. ⇒ 알고리즘에 따라 다름. O(?)
     만약 노드가 마킹 되어있지 않다면
     1. 노드를 마킹한다. ⇒ 노드마다 1번씩만 하므로 O(n)
     2. 뭔가 필요하다면 계산을 한다. ⇒ 위와 마찬가지
     3. 노드에 인접한 모든 노드들을 Box에 넣는다.
        ⇒ 한 노드의 인접노드를 넣어야 하는데 그만큼 다른 노드에서는 이부분이 빠지므로
        노드 하나 기준으로 다른 노드와의 상호 순회 만큼만 보면 된다.
        ⇒ O(2m)

---

Event Queue

• Box로 사용되는 자료구조
• 순서가 필요없다면 그냥 큐
  순서가 필요하다면 PQ

---

Infection Spreads

m*n크기의 2차원 배열

상하좌우 4개중에 2개 이상이 감염되면 나도 감염.

⇒ O(mn * x) 만큼의 시간이 걸린다. x는 끝날때까지 걸린 시간, 매번 m*n크기 전부 확인.

1. 처음 바로 감염될 애들을 event queue에 넣는다.
2. Queue에서 꺼내고 인접한 애들중 감염될 애들을 다시 queue에 넣는다.
3. 반복한다.

⇒ 최초에 m*n 크기 확인하고 넣기 + queue에는 m*n개(모든 노드의 개수) 까지 들어갈 수 있다.
따라서 O(mn + mn) = O(2mn)

---

What Kind of Box

• Box 의 종류
• 나간다는 것 = 확정된다는 뜻.

1. Stack → DFS
   가장 먼저 들어온게 가장 나중에 나가므로 깊이 우선. (=가장 먼것이 가장 먼저 나간다.)
2. Queue → BFS
   가장 먼저 들어온게 가장 먼저 나가므로 너비 우선. (=가장 가까운 너비 부터 나간다.)
   엣지 웨이트가 전부 1이라면 Shortest Path (=다익스트라)
3. Priority Queue
   • 엣지 웨이트가 있다면 → Prim
   • s로 부터의 거리를 구한다면 → Dijkstra
   • 평가 함수가 있다면 → A*
     평가 함수를 통해서 가장 좋은 것을 queue에서 꺼낸다.