fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Function to add an edge to the adjacency list
  5. void addEdge(vector<int> adj[], int u, int v) {
  6.     adj[u].push_back(v); // Add v to u's list
  7.     adj[v].push_back(u); // Add u to v's list (for undirected graph)
  8. }
  9.  
  10. // Function to perform DFS using a stack
  11. void DFS(vector<int> adj[], int V, int start) {
  12.     vector<bool> visited(V, false); // To keep track of visited nodes
  13.     stack<int> st; // Stack for DFS
  14.  
  15.     st.push(start); // Push the starting node to the stack
  16.  
  17.     cout << "DFS traversal starting from node " << start << ": ";
  18.     while (!st.empty()) {
  19.         int node = st.top(); // Get the top element
  20.         st.pop();
  21.  
  22.         // If the node is not visited, process it
  23.         if (!visited[node]) {
  24.             cout << node << " ";
  25.             visited[node] = true;
  26.         }
  27.  
  28.         // Push all unvisited neighbors to the stack
  29.         for (int neighbor : adj[node]) {
  30.             if (!visited[neighbor]) {
  31.                 st.push(neighbor);
  32.             }
  33.         }
  34.     }
  35.     cout << endl;
  36. }
  37.  
  38. int main() {
  39.     int V = 12; // Number of vertices
  40.     vector<int> adj[V]; // Adjacency list
  41.  
  42.     // Adding edges
  43.     addEdge(adj, 0, 1);
  44.     addEdge(adj, 0, 4);
  45.     addEdge(adj, 0, 2);
  46.     addEdge(adj, 1, 4);
  47.  
  48.     addEdge(adj, 2, 4);
  49.     addEdge(adj, 2, 9);
  50.     addEdge(adj, 2, 5);
  51.     addEdge(adj, 2, 10);
  52.     addEdge(adj, 9, 11);
  53.     addEdge(adj, 10, 11);
  54.     addEdge(adj, 5, 6);
  55.     addEdge(adj, 5, 7);
  56.     addEdge(adj, 5, 8);
  57.     addEdge(adj, 7, 8);
  58.  
  59.     // Perform DFS starting from node 0
  60.     DFS(adj, V, 0);
  61.  
  62.     return 0;
  63. }
  64.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
DFS traversal starting from node 0: 0 2 10 11 9 5 8 7 6 4 1
https://ideone.com/PQckIo
Implementing DFS code
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!