[그래프]

그래프에서 꼭 알아야할 사항들

1. DFS-재귀

2. BFS-큐

3. 위상정렬

4. 다익스트라

5. 벨만포드

6. 최소신장트리

-----------------------------

1. DFS-재귀

DFS(u)

visited[u] = 1

//do something

for each v of adj[u]

if(visited[v]) continue

DFS(v)

code

void dfs(int u) {

         visited[u] = 1;

         

         for (int i = 0; i < g[u].size(); ++i) {

                  int v = g[u][i];

                  if (visited[v]) continue;

                  dfs(v);

         }

}

2. BFS-큐

BFS(s)

visited[s]=1

Q.push(s)

while(!Q.empty())

u = Q.pop()

//do something

for each v near u

if(visited[v]) continue

visited[v] = 1  

Q.push(v)

주의

- DFS와 달리 BFS는 '발견'과 '방문' 시점이 다름.

  즉, v에 대해 viisted[v]=1을 했고, queue에서 꺼낸 u에 대해서 '방문'에 대한 처리 수행

- DFS에서는 u에 대해서 '발견'과 '방문' 모두 처리

code

void bfs(int s) {

         visited[s] = 1;

 

         queue<int> q;

         q.push(s);

         visited[s] = 1;

         while (!q.empty()) {

                  int u = q.front(); q.pop();

                  path.push_back(u);

                 

                  for (int i = 0; i < g[u].size(); ++i) {

                           int v = g[u][i];

                           if (visited[v]) continue;

                           visited[v] = 1;

                           q.push(v);

                  }

         }

}

3. 위상정렬

핵심

-DAG(방향성이 있고, 사이클이 없는 경우만 가능)

- 재귀호출용 DFS를 응용해서 풀이 가능

   DFS콜이 끝나는 시점에서의 노드를 stack에 저장해뒀다가 출력하면 됨

code

void dfs(int u) {

         visited[u] = 1;

 

         for (int i = 0; i < g[u].size(); ++i) {

                  int v = g[u][i];

                  if (visited[v]) continue;

                  dfs(v);

         }

         st.push(u);

}

4. 다익스트라

핵심

- BFS에서 일반큐가아닌 priority_queue(이진힙)를 사용하면 됨

   #include <queue>

   #include <functional>

  

   priority_queue<pii, vector<pii>, greater<pii> > pq;

- 최소 dist인 노드만을 BFS로 돌면서, dist[i]를 Relax시키는게 메인 아이디어

- pq에서 꺼낸 u에 대해 if(dist[u] < u의 cost)이면 continue하는게 속도절감 핵심

슈도코드

dijkstra(s,tgt)

모든 dist[i]=INF

dist[s]=0

pq.push(make_pair(0,s))

while(!pq.empty())

u = pq.top().second, pq.pop()

if(u==tgt) 종료

cost=pq.top().first

//지금 큐에서 꺼낸경로보다, 이미 더 짧은경로가 발견된경우임

if(dist[u] < cost) continue //중요!!!

for each v near u

newDist = u's cost + v's distance

if(newDist < dist[v])

dist[v] = newDist

pq.push(make_pair(newDist,v)) 

소스

ll dijkstra(int s, int tgt) {

         vector<int> dist(N + 1, INF);

         dist[s] = 0;

 

         priority_queue<pli, vector<pli>, greater<pli> > q;

         q.push(make_pair(0, s));

         while (!q.empty()) {

                  pli tmp = q.top(); q.pop();

                  int u = tmp.second;

                  if (u == tgt) return dist[u];

 

                  ll z = tmp.first;

                  if (dist[u] < z) continue;

                  for (int i = 0; i < g[u].size(); ++i) {

                           int v = g[u][i].second;

                           ll newCost = z + g[u][i].first;

                           if (dist[v] > newCost) {

                                   dist[v] = newCost;

                                   q.push(make_pair(dist[v], v));

                           }

                  }

         }

 

         return -1;

         //return dist;

}

5. 벨만포드

6. 최소신장트리

핵심

- 모든 edge를 소팅하고, 사이클이 아닌 작은 에지부터 path에 넣으면 끝

- 사이클인지 아닌지는 상호배타집합에 의해 같은 조상노드를 가지고 있는지 확인으로 쉽게 구현됨 

트리를 이용한 상호배타집합 구현

- init, find, merge 세 단계

- init: parent[i]=i

- find(x) 

if(x == parent[x]) return x;

parent[x] = find(parent[x]);  //중요!!

return parent[x];

- merge: parent[pa] = pb

 

소스

#include <stdio.h>

#include <vector>

#include <algorithm>

 

#define MAX 50005

 

using namespace std;

 

struct Edge {

         int s, e, cost;

         Edge(int s, int e, int cost) : s(s), e(e), cost(cost) {}

         bool operator < (const Edge& x) const {

                  return (cost < x.cost);

         }

};

 

int N, M;

vector<Edge> g;

int parent[MAX];

 

int find(int x) {

         if (parent[x] == x) return x;

         parent[x] = find(parent[x]);

         return parent[x];

}

 

int mst(){

         sort(g.begin(), g.end());

         for (int i = 1; i <= N; ++i) parent[i] = i;

 

         int ans = 0;

         for (int i = 0; i < M; ++i) {

                  int pa = find(g[i].s);

                  int pb = find(g[i].e);

                  if (pa == pb) continue;

 

                  ans += g[i].cost;

                  parent[pa] = pb; //merge

         }

         return ans;      

}

 

int main() {

         freopen("고속도로건설.txt", "r", stdin);

 

         scanf("%d %d", &N, &M);

         int s, e, c;

         for (int i = 0; i < M; ++i) {

                  scanf("%d %d %d", &s, &e, &c);

                  g.push_back(Edge(s, e, c));

         }

 

         printf("%d\n", mst());

         return 0;

}

-끝-