Algortihms/BFS.cpp at master · chetan767/Algortihms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include<bits/stdc++.h>
using namespace std;

template<typename t>
class graph
{
public :
    map<t,list<t> > adjlist;
    void addEdge(t u,t v,bool bidir=true)
    {
        adjlist[u].push_back(v);
        if(bidir)
        {
            adjlist[v].push_back(u);
        }
    }
    void print()
    {

        for(auto node : adjlist)
        {
            cout<<node.first<<" --> ";
            for(auto adj : node.second)
            {
                cout<<adj<<"  ";
            }
            cout<<"\n";
        }
    }

    void bfs(t src)
    {
        unordered_map<t,bool> visited;
        queue<t>q;
        q.push(src);
        visited[src]=true;
        while(!q.empty())
        {
            t node = q.front();
            q.pop();
            cout<<node<<"   ";
            for(auto adj : adjlist[node])
            {
                if(!visited[adj])
                {
                    visited[adj]=true;
                    q.push(adj);
                }
            }
        }
    }

    void dfs_helper(t src,unordered_map<t,bool> &visited)
    {
        visited[src]=true;
        cout<<src<<"   ";
        for(auto node : adjlist[src])
        {
            if(!visited[node])
            {
                dfs_helper(node,visited);
            }
        }

    }

    void dfs(t src)
    {
    unordered_map<t,bool> visited;
    dfs_helper(src,visited);
    }


};

int main()
{
    graph<int> g;
    g.addEdge(1,2);
    g.addEdge(0,1);
    g.addEdge(2,3);
    g.addEdge(3,4);
    g.addEdge(3,5);
    g.addEdge(0,4);
    g.print();
    cout<<"\nBFS : ";
    g.bfs(0);
    cout<<"\n\nDFS : ";
    g.dfs(0);
}