BFS

bfs.cpp

#include <iostream>
#include <vector>
#include <algorithm>

class Graph {
public:
  int N;  // 정점의 개수
  std::vector<std::vector<int>> adj;  // 인접 리스트 방식
  std::vector<bool> visited;  // 방문 여부
  
  Graph(): N(0) {}
  Graph(int n): N(n) {
    adj.resize(N);
    visited.resize(N);
  }
  
  void addEdge(int u, int v) {
    // 인접 리스트 방식
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  
  void sortList() {
    for (int i = 0; i < N; ++i)
      std::sort(adj[i].begin(), adj[i].end());
  }
  
  void dfs() {
    std::fill(visited.begin(), visited.end(), false);
    dfs(0);
  }
  
private:
  void dfs(int curr) {
    visited[curr] = true;
    std::cout << "node " << curr << " visited" << endl;
    for (int next: adj[curr])
      if (!visited[next])
        dfs(next);
  }
};

DFS-iterative.py

'''pseudo
DFS-iterative(G, v)
    let s be a stack
    S.push(v)
    while S is not empty do
        v = S.pop()
        if v is not labeled as discovered then
            label v as discovered
            for all edges from v to w in G.adjacentEdges(v) do
                S.push(w)
'''

def iterative_dfs(start_v):
    discovered = []; stack = [start_v]
    while stack:
        v = stack.pop()
        if v not in discovered:
            discovered.append(v)
            for w in graph[v]:
                stack.append(w)
    
    return discovered

DFS.py

'''pseudo
DFS(G, v)
  label v as discoverd
  for all directed edges from v to w that are in G.adjacentEdges(v) do
    if vertex w is not labeled as discovered then
      recursively call DFS(G, w)
 '''

def recursive_dfs(v, discovered=[]):
  discovered.append(v)
  for w in graph[v]:
    if w not in discovered:
      discovered = recursive_dfs(w, discovered)
    
    return discovered
 

dfsall.cpp

int dfsAll() {
  int components = 0;
  fill(visited.begin(), visited.end(), false);
  
  for (int i = 0; i < N; ++i) {
    if (!visited[i]){
      cout << "--- new DFS begins ---" << endl;
      dfs(i);
      components++;
    }
  }
  return components;
}