DFS Tutorial | Competitive Programming

Depth First Search (DFS) for a Graph

Basics:

(1)   http://www.shafaetsplanet.com/?p=973.

(2)   https://www.youtube.com/watch?v=oL5J5il9pFg.

(3)   https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/tutorial/

Problems:

(1)   Unreachable Nodes (Hackerearth).- see bottom of the page

(2)   280 - Vertex (UVa).

(3)   11518 - Dominos 2 (UVa).

(4)   10452 – Marcus (UVa).

(5)   Vjudge: 1.

(6)   DFS variation: Lightoj. A2OJ.

// DFS.cpp

/// (Data Structure: graph, visit)

vector<int> v[30001];

int vis[30001], c=0;

void dfs(int s)

{

    if(vis[s])

        return ;

    vis[s]=1;

    c++;

    for(int i=0;i<v[s].size();i++)

    {

        if(!vis[v[s][i]])

        {

            dfs(v[s][i]);

        }

    }

}

BFS Tutorial | Competitive Programming

Breadth First Search (BFS) for a Graph:

ü     1D Breadth First Search (BFS):

Basics:

(1)   http://www.shafaetsplanet.com/planetcoding/?p=604.

(2)   https://www.youtube.com/watch?time_continue=71&v=FyMkQ6prLHk.

(3)   http://zakilive.com/2017/05/26/algorithm-bfsbreadth-first-search/.

(4)   https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/tutorial/.

(5)   https://www.youtube.com/watch?v=GVSxGBCtQCE.

Problems:

(1)   BFS of graph (geeksforgeeks).

(2)   Level Nodes (Hackerearth) : see bottom of the page.

(3)   Bishu and his Girlfriend (Hackerearth).

(4)   336 - A Node Too Far (UVa).

(5)   567 - Risk(UVa).

(6)   762 - We Ship Cheap(UVa).

(7)   Vjudge: 1, 2.

(8)   BFS variation: Lightoj, A2OJ

//BFS.cpp

//(Data Structure: graph, level, visit, parent, queue)

vector<int>g[1000];

void print_dist(int lev[], int n, int s)

{

    for(int i=1; i<=n; i++)

        cout<<s<<" to "<<i<<" "<<lev[i]<<endl;

}

void bfs_traverse(vector<int> path) /// bfs traversal

{

    for(int i=0; i<path.size(); i++)

    {

        if(i) cout<<" ";

        cout<<path[i];

    }

    cout<<endl;

}

void bfs_path(int par[], int s, int d) /// (parent, source, destination) shortest path

{

    vector<int>path;

    path.push_back(d);

    while(par[d]!=-1)

    {

        path.push_back(par[d]);

        d=par[d];

    }

    reverse(path.begin(),path.end());

    bfs_traverse(path);

}

void bfs(int s,int n) /// s = source, d = destination, n = number of node

{

    queue<int>q;

    vector<int> path;

    bool vis[1000]= {0};

    int lev[1000],par[1000];

    q.push(s);

    vis[s]=true;

    lev[s]=0;

    par[s]=-1;

    while(!q.empty())

    {

        int u=q.front();

        path.push_back(u);

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

        {

            //cout<<"---------"<<endl;

            int v=g[u][i];

            if(!vis[v])

            {

                lev[v]=lev[u]+1;

                par[v]=u;

                vis[v]=true;

                q.push(v);

            }

        }

        q.pop();

    }

    print_dist(lev, n, s);

    bfs_traverse(path);

    bfs_path(par, s, n);

}

ü  2D Breadth First Search (BFS):

Basics:

(1)   http://www.shafaetsplanet.com/planetcoding/?p=604.

(2)   https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/tutorial/.

Problems:

(1)   10653 - Bomb! No they are mines (UVa).

(2)   439- Knight Moves(UVa).

(3)   Vjudge: 1, 2.

(4)   BFS variation: Lightoj.

//BFS-2D-grid.cpp

//(Data Structure: matrix, distance, visit, queue)

#define  mx 1001

using namespace std;

int mat[mx][mx]; /// -1 means obstacle

int vis[mx][mx],dis[mx][mx];

int m,n;

int X[4] = {-1,0,0,1}; // up, down, left, right

int Y[4] = {0,-1,1,0};

void bfs(int x,int y)

{

    int ux,uy,vx,vy,k;

    queue<int>Q;

    Q.push(x);

    Q.push(y);

    vis[x][y] = true;

    dis[x][y]=0;

    while(!Q.empty())

    {

        ux = Q.front();

        Q.pop();

        uy = Q.front();

        Q.pop();

        for(k=0; k<4; k++)

        {

            vx = ux+X[k];

            vy = uy+Y[k];

            if((vx>=0&&vx<m) and (vy>=0&&vy<n) and mat[vx][vy]!=-1 and vis[vx][vy]==false)

            {

                vis[vx][vy]=true;

                Q.push(vx);

                Q.push(vy);

                dis[vx][vy]=dis[ux][uy]+1;

            }

        }

    }

}