Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
17 kB
1
Indexable
Never
 
 ​#​include​ ​<​iostream​> 
 ​#​include​ ​<​queue​> 
  
 ​using​ ​namespace​ ​std​; 
  
 ​class​ ​Node 
 ​{ 
 ​private: 
 ​    ​int​ vertexNumber; 
 ​    Node *next; 
  
 ​public: 
 ​    ​Node​() 
 ​    { 
 ​        vertexNumber = ​0​; 
 ​        next = ​nullptr​; 
 ​    } 
 ​    ​Node​(​int​ n) 
 ​    { 
 ​        vertexNumber = n; 
 ​        next = ​nullptr​; 
 ​    } 
 ​    ​friend​ ​class​ ​Graph​; 
 ​}; 
  
 ​class​ ​Graph 
 ​{ 
 ​private: 
 ​    Node **adjList; 
 ​    ​bool​ *visitedList; 
 ​    ​int​ totalV; 
 ​    ​int​ totalE; 
  
 ​    ​void​ ​addEdge​(​int​ source, ​int​ destination) 
 ​    { 
 ​        Node *newnode = ​new​ ​Node​(destination); 
 ​        newnode->​next​ = adjList[source]; 
 ​        adjList[source] = newnode; 
 ​    } 
  
 ​    ​void​ ​clear​() 
 ​    { 
 ​        ​for​ (​int​ i = ​0​; i < totalV; i++) 
 ​        { 
 ​            visitedList[i] = ​false​; 
 ​        } 
 ​    } 
  
 ​public: 
 ​    ​Graph​(​int​ vertices, ​int​ edges) 
 ​    { 
 ​        totalE = edges; 
 ​        totalV = vertices; 
 ​        adjList = ​new​ Node *[vertices]; 
 ​        visitedList = ​new​ ​bool​[vertices]; 
 ​        ​for​ (​int​ i = ​0​; i < vertices; i++) 
 ​        { 
 ​            adjList[i] = ​nullptr​; 
 ​            visitedList[i] = ​false​; 
 ​        } 
 ​    } 
  
 ​    ​void​ ​createGraph​() 
 ​    { 
 ​        ​int​ source, destination; 
 ​        ​for​ (​int​ i = ​0​; i < totalE; i++) 
 ​        { 
 ​            cout << ​"​Enter Source and Destination ​\n​"​; 
 ​            cout << ​"​Source: ​"​; 
 ​            cin >> source; 
 ​            cout << ​"​Destination: ​"​; 
 ​            cin >> destination; 
 ​            ​addEdge​(source, destination); 
 ​            ​addEdge​(destination, source); 
 ​        } 
 ​    } 
  
 ​    ​void​ ​display​() 
 ​    { 
 ​        cout << ​"​Graph is --> ​\n​"​; 
 ​        ​for​ (​int​ i = ​0​; i < totalV; i++) 
 ​        { 
 ​            ​if​ (adjList[i] == ​NULL​) 
 ​            { 
 ​                cout << ​"​No connections for node ​"​ << i << ​"​ ​\n​"​; 
 ​            } 
 ​            ​else 
 ​            { 
 ​                cout << ​"​Node connected to ​"​ << i << ​"​ --> ​"​; 
 ​                Node *temp = adjList[i]; 
 ​                ​while​ (temp != ​NULL​) 
 ​                { 
 ​                    cout << temp->​vertexNumber​ << ​"​ ​"​; 
 ​                    temp = temp->​next​; 
 ​                } 
 ​                cout << ​"​\n​"​; 
 ​            } 
 ​        } 
 ​    } 
  
 ​    ​void​ ​dfs​(​int​ vertexNo) 
 ​    { 
 ​        cout << ​"​At node ​"​ << vertexNo << ​"​\n​"​; 
 ​        visitedList[vertexNo] = ​true​; 
 ​        Node *temp = adjList[vertexNo]; 
 ​        ​while​ (temp) 
 ​        { 
 ​            ​if​ (!visitedList[temp->​vertexNumber​]) 
 ​            { 
 ​                ​dfs​(temp->​vertexNumber​); 
 ​            } 
 ​            temp = temp->​next​; 
 ​        } 
 ​        ​return​; 
 ​    } 
  
 ​    ​void​ ​bfs​(​int​ startnode) 
 ​    { 
 ​        ​clear​(); 
 ​        queue<​int​> que; 
 ​        cout << ​"​Bfs --> ​"​; 
 ​        que.​push​(startnode); 
 ​        visitedList[startnode] = ​true​; 
 ​        ​while​ (!que.​empty​()) 
 ​        { 
 ​            ​int​ temp = que.​front​(); 
 ​            cout << temp << ​"​ ​"​; 
 ​            que.​pop​(); 
 ​            Node *current = adjList[temp]; 
 ​            ​while​ (current != ​nullptr​) ​//​checking for nodes connected to current node 
 ​            { 
 ​                ​if​ (!visitedList[current->​vertexNumber​]) 
 ​                { 
 ​                    visitedList[current->​vertexNumber​] = ​true​; 
 ​                    que.​push​(current->​vertexNumber​); 
 ​                } 
 ​                current = current->​next​; 
 ​            } 
 ​        } 
 ​        cout << ​"​\n​"​; 
 ​        ​clear​(); 
 ​        ​return​; 
 ​    } 
 ​}; 
  
 ​int​ ​main​() 
 ​{ 
 ​    cout << ​"​Enter number of nodes: ​"​; 
 ​    ​int​ node = ​0​, edges = ​0​; 
 ​    cin >> node; 
 ​    cout << ​"​Enter number of edges: ​"​; 
 ​    cin >> edges; 
 ​    Graph ​G​(node, edges); 
 ​    G.​createGraph​(); 
  
 ​    ​int​ choice = ​0​, choice2 = ​0​; 
 ​    ​while​ (choice != ​3​) 
 ​    { 
 ​        cout << ​"​1.Display graph​\n​"​; 
 ​        cout << ​"​2.Traverse the graph​\n​"​; 
 ​        cout << ​"​3.Exit​\n​"​; 
 ​        cout << ​"​Enter Choice: ​"​; 
 ​        cin >> choice; 
 ​        ​switch​ (choice) 
 ​        { 
 ​        ​case​ ​1​: 
 ​            G.​display​(); 
 ​            ​break​; 
 ​        ​case​ ​2​: 
 ​            cout << ​"​1.DFS​\n​"​; 
 ​            cout << ​"​2.BFS​\n​"​; 
 ​            cin >> choice2; 
 ​            ​if​ (choice2 == ​1​) 
 ​            { 
 ​                cout << ​"​Dfs on graph ​\n​"​; 
 ​                cout << ​"​Enter the Start Node​\n​"​; 
 ​                ​int​ startNode; 
 ​                cin >> startNode; 
 ​                G.​dfs​(startNode); 
 ​                cout << ​"​\n​"​; 
 ​            } 
 ​            ​else 
 ​            { 
 ​                cout << ​"​Bfs on graph ​\n​"​; 
 ​                cout << ​"​Enter the Start Node​\n​"​; 
 ​                ​int​ startNode; 
 ​                cin >> startNode; 
 ​                G.​bfs​(startNode); 
 ​            } 
 ​            ​break​; 
 ​        ​default​: 
 ​            ​break​; 
 ​        } 
 ​    } 
  
 ​#​include​ ​<​iostream​> 
 ​#​include​ ​<​queue​> 
  
 ​using​ ​namespace​ ​std​; 
  
 ​class​ ​Node 
 ​{ 
 ​private: 
 ​    ​int​ vertexNumber; 
 ​    Node *next; 
  
 ​public: 
 ​    ​Node​() 
 ​    { 
 ​        vertexNumber = ​0​; 
 ​        next = ​nullptr​; 
 ​    } 
 ​    ​Node​(​int​ n) 
 ​    { 
 ​        vertexNumber = n; 
 ​        next = ​nullptr​; 
 ​    } 
 ​    ​friend​ ​class​ ​Graph​; 
 ​}; 
  
 ​class​ ​Graph 
 ​{ 
 ​private: 
 ​    Node **adjList; 
 ​    ​bool​ *visitedList; 
 ​    ​int​ totalV; 
 ​    ​int​ totalE; 
  
 ​    ​void​ ​addEdge​(​int​ source, ​int​ destination) 
 ​    { 
 ​        Node *newnode = ​new​ ​Node​(destination); 
 ​        newnode->​next​ = adjList[source]; 
 ​        adjList[source] = newnode; 
 ​    } 
  
 ​    ​void​ ​clear​() 
 ​    { 
 ​        ​for​ (​int​ i = ​0​; i < totalV; i++) 
 ​        { 
 ​            visitedList[i] = ​false​; 
 ​        } 
 ​    } 
  
 ​public: 
 ​    ​Graph​(​int​ vertices, ​int​ edges) 
 ​    { 
 ​        totalE = edges; 
 ​        totalV = vertices; 
 ​        adjList = ​new​ Node *[vertices]; 
 ​        visitedList = ​new​ ​bool​[vertices]; 
 ​        ​for​ (​int​ i = ​0​; i < vertices; i++) 
 ​        { 
 ​            adjList[i] = ​nullptr​; 
 ​            visitedList[i] = ​false​; 
 ​        } 
 ​    } 
  
 ​    ​void​ ​createGraph​() 
 ​    { 
 ​        ​int​ source, destination; 
 ​        ​for​ (​int​ i = ​0​; i < totalE; i++) 
 ​        { 
 ​            cout << ​"​Enter Source and Destination ​\n​"​; 
 ​            cout << ​"​Source: ​"​; 
 ​            cin >> source; 
 ​            cout << ​"​Destination: ​"​; 
 ​            cin >> destination; 
 ​            ​addEdge​(source, destination); 
 ​            ​addEdge​(destination, source); 
 ​        } 
 ​    } 
  
 ​    ​void​ ​display​() 
 ​    { 
 ​        cout << ​"​Graph is --> ​\n​"​; 
 ​        ​for​ (​int​ i = ​0​; i < totalV; i++) 
 ​        { 
 ​            ​if​ (adjList[i] == ​NULL​) 
 ​            { 
 ​                cout << ​"​No connections for node ​"​ << i << ​"​ ​\n​"​; 
 ​            } 
 ​            ​else 
 ​            { 
 ​                cout << ​"​Node connected to ​"​ << i << ​"​ --> ​"​; 
 ​                Node *temp = adjList[i]; 
 ​                ​while​ (temp != ​NULL​) 
 ​                { 
 ​                    cout << temp->​vertexNumber​ << ​"​ ​"​; 
 ​                    temp = temp->​next​; 
 ​                } 
 ​                cout << ​"​\n​"​; 
 ​            } 
 ​        } 
 ​    } 
  
 ​    ​void​ ​dfs​(​int​ vertexNo) 
 ​    { 
 ​        cout << ​"​At node ​"​ << vertexNo << ​"​\n​"​; 
 ​        visitedList[vertexNo] = ​true​; 
 ​        Node *temp = adjList[vertexNo]; 
 ​        ​while​ (temp) 
 ​        { 
 ​            ​if​ (!visitedList[temp->​vertexNumber​]) 
 ​            { 
 ​                ​dfs​(temp->​vertexNumber​); 
 ​            } 
 ​            temp = temp->​next​; 
 ​        } 
 ​        ​return​; 
 ​    } 
  
 ​    ​void​ ​bfs​(​int​ startnode) 
 ​    { 
 ​        ​clear​(); 
 ​        queue<​int​> que; 
 ​        cout << ​"​Bfs --> ​"​; 
 ​        que.​push​(startnode); 
 ​        visitedList[startnode] = ​true​; 
 ​        ​while​ (!que.​empty​()) 
 ​        { 
 ​            ​int​ temp = que.​front​(); 
 ​            cout << temp << ​"​ ​"​; 
 ​            que.​pop​(); 
 ​            Node *current = adjList[temp]; 
 ​            ​while​ (current != ​nullptr​) ​//​checking for nodes connected to current node 
 ​            { 
 ​                ​if​ (!visitedList[current->​vertexNumber​]) 
 ​                { 
 ​                    visitedList[current->​vertexNumber​] = ​true​; 
 ​                    que.​push​(current->​vertexNumber​); 
 ​                } 
 ​                current = current->​next​; 
 ​            } 
 ​        } 
 ​        cout << ​"​\n​"​; 
 ​        ​clear​(); 
 ​        ​return​; 
 ​    } 
 ​}; 
  
 ​int​ ​main​() 
 ​{ 
 ​    cout << ​"​Enter number of nodes: ​"​; 
 ​    ​int​ node = ​0​, edges = ​0​; 
 ​    cin >> node; 
 ​    cout << ​"​Enter number of edges: ​"​; 
 ​    cin >> edges; 
 ​    Graph ​G​(node, edges); 
 ​    G.​createGraph​(); 
  
 ​    ​int​ choice = ​0​, choice2 = ​0​; 
 ​    ​while​ (choice != ​3​) 
 ​    { 
 ​        cout << ​"​1.Display graph​\n​"​; 
 ​        cout << ​"​2.Traverse the graph​\n​"​; 
 ​        cout << ​"​3.Exit​\n​"​; 
 ​        cout << ​"​Enter Choice: ​"​; 
 ​        cin >> choice; 
 ​        ​switch​ (choice) 
 ​        { 
 ​        ​case​ ​1​: 
 ​            G.​display​(); 
 ​            ​break​; 
 ​        ​case​ ​2​: 
 ​            cout << ​"​1.DFS​\n​"​; 
 ​            cout << ​"​2.BFS​\n​"​; 
 ​            cin >> choice2; 
 ​            ​if​ (choice2 == ​1​) 
 ​            { 
 ​                cout << ​"​Dfs on graph ​\n​"​; 
 ​                cout << ​"​Enter the Start Node​\n​"​; 
 ​                ​int​ startNode; 
 ​                cin >> startNode; 
 ​                G.​dfs​(startNode); 
 ​                cout << ​"​\n​"​; 
 ​            } 
 ​            ​else 
 ​            { 
 ​                cout << ​"​Bfs on graph ​\n​"​; 
 ​                cout << ​"​Enter the Start Node​\n​"​; 
 ​                ​int​ startNode; 
 ​                cin >> startNode; 
 ​                G.​bfs​(startNode); 
 ​            } 
 ​            ​break​; 
 ​        ​default​: 
 ​            ​break​; 
 ​        } 
 ​    }