BFS & DFS

DFS() and BFS() are two basic searching methods in graph. They are the foundation of many algorithms.

What is DFS?

We will use tree to understand DFS better, and it’s same as other graph actually.

Obviously, the DFS is a method that will proceed along a single way until the end of way, and it will go back to the last fork. Repeat this process until the all the roads are traveled.

c++ code:

vector<vector<int>> adj;// adjacency list
void init(void)
{
    adj = vector<vector<int>>(1000);
}
void dfs(int u)
{
    vector<bool> visit(1000, false);
    visit[u] = true;
    for(int i : adj[i])
    {
        if(!visit[i]) dfs(i);
    }
}

What is BFS?

We will also use tree to understand DFS better, and it’s same as other graph actually.

Obviously, the BFS is a method that will traverse all the out-edges of the current node until all the nodes in current level are traversed and then enter the next level to repeat this process.

c++ code:

vector<int> head;
int cnt;
struct Edge{
    int to, next;
}edge[1000];

int init(void)
{
    cnt = 0;
    head = vector<int>(1000, -1);
}

void addEdge(int u, int v)
{
    edge[cnt].to = v;
    edge[cnt].next = head[u];
    head[u] = cnt++;
}

void bfs(int u)
{
    queue<int> q;
    vector<bool> visit(1000, false);
    q.push(u);
    visit[u] = true;
    while(!q.empty())
    {
        int tmp = q.front();
        q.pop();
        for(int i = head[tmp]; i != -1; i = edge[i].next)
        {
            int v = edge[i].to;
            if(!visit[v])
            {
                visit[v] = true;
                q.push(v);
            }
        }
    }
}