0722-dfs.md

2020.07.22 Wed

📚공부한 거 List📚

• 종만북 - 28. 그래프의 깊이 우선 탐색

---

[종만북] 그래프의 깊이 우선 탐색

DFS_Depth First Search

⌨️그래프의 깊이 우선 탐색

vector<vector<int>> adj;
vector<bool> visited;

void dfs(int here) {
  visited[here] = true;
  for(int i=0; i<adj[here].size(); ++i) {
    int there = adj[here][i];
    if(!visited[there]) dfs(there);
  }
}

void dfsAll() {
  visited = vector<int>(adj.size(), false);
  for(int i=0; i<adj.size(); ++i) {
    if(!visited[i]) dfs(i);
  }
}

Time/Space Complexity

인접 리스트를 사용하는 경우 : O(|V|+|E|)

인접 행렬을 사용하는 경우 : O(|V|^2)

희소행렬(spare matrix)인 경우에는 인접리스트를, 밀집행렬(dense matrix)인 경우에는 인접 행렬을 사용하는 것이 공간의 낭비를 줄일 수 있는 방법이다.

위상정렬

의존성 그래프(Dependency Graph) : 각 작업을 정점으로 표현하고 작업 간의 의존 관계를 간선으로 표현한 방향 그래프

DAG : 사이클 없는 방향 그래프.

DAG의 정점을 배열하는 문제를 위상정렬(Topological Sort)라고 한다.

dfs()가 종료될 때마다 정점의 번호를 저장해두고, dfsAll()이 종료한 뒤 기록된 정점들의 순서를 뒤집으면 위상정렬의 결과가 된다.

📝예제::고대어 사전(ID: DICTIONARY)

문제 : 단어들의 목록이 순서대로 주어질 때 이 언어에서 알파벳의 순서를 계산.

⚡️keypoint⚡️

1. 각 알파벳을 정점으로 표현하고, 순서는 방향그래프로 표현한다.
2. 사이클이 있다면 위상정렬이 아니다. 사이클의 유무를 확인하는 방법은 오른쪽에서 왼쪽으로 간선이 있는지 확인하면된다.

🔑**해답(코드)**🔑

/*
 * 고대어 사전 문제의 그래프 생성
 */
vector<vector<int>> adj;
void makeGraph(const vector<string>& words) {
  adj = vector<vector<int>>(26,vector<int>(26,0));
  for(int i=1; i<words.size(); ++i) {
    int j=i-1, len = min(words[i].size(), words[j].size());
    for(int k=0; k<len; ++k) {
      if(words[i][k] != words[j][k]){
        int a = words[i][k] - 'a';
        int b = words[j][k] - 'a';
        adj[a][b] = 1;
        break;
      }
    }
  }
}

//깊이 우선 탐색을 이용한 위상정렬
vector<int> visited, order;
void dfs(int here) {
  visited[here] = 1;
  for(int there = 0; there<adj.size(); ++there) { //전체 노드의 개수만큼
    //만약 here->there 간선이 있고, 아직 there을 방문하지 않았다면, there 방문
    if(adj[here][there] && !visited[there]) dfs(there);
  }
  order.push_back(here); //order에 here 추가
}

vector<int> topologicalSort() {
  visited = vector<int>(adj.size(), false); //초기화
  order.clear(); //순서 배열 초기화
  for(int i=0; i<adj.size(); ++i) { //전체노드의 수만큼
    if(!visited[i]) dfs(i); //i-노드 방문안했다면, 방문하기
  }
  //#include <algorithm>
  reverse(order.begin(), order.end()); //order 순서 거꾸로 정렬
  //역방향 간선이 있는지 확인하고, 있다면 빈 벡터를 반환
  for(int i=0; i<adj.size(); ++i) { 
    for(int j=i+1; j<adj.size(); ++j) { 
      if(adj[order[j]][order[i]]) return vector<int>();
    }
  } 
  return order;
}

오일러 서킷(Euler Circuit)

그래프의 모든 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 찾는 문제

• 그래프의 모든 정점들이 짝수점이어야만 오일러 서킷이 존재할 수 있다.
• findRandomCircuit(u) : 정점 u에서 시작해 아직 따라가지 않은 간선 중 하나를 따라가며 임의의 경로를 만드는 함수/더이상 남은 간선이 없을때까지.

⌨️깊이 우선 탐색을 이용한 오일러 서킷 찾기 💦

vector<vector<int>> adj;
void getEulerCircuit(int here, vector<int>& circuit) {
  for(int there=0; there<adj[here].size(); ++there) {
    while(adj[here][there]>0){
      adj[here][there]--;
      adj[there][here]--;
      getEulerCircuit(there, circuit);
    }
  }
  circuit.push_back(here);
}