|
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 |
#include <iostream> #include <vector> #include <queue> #include <stack> using namespace std; class Graph { private: int V; // Number of vertices vector<vector<int>> adj; // Adjacency list public: Graph(int vertices) : V(vertices), adj(vertices) {} void addEdge(int u, int v) { adj[u].push_back(v); adj[v].push_back(u); // For undirected graph } void DFS(int start) const { vector<bool> visited(V, false); stack<int> s; s.push(start); while (!s.empty()) { int node = s.top(); s.pop(); if (!visited[node]) { cout << node << " "; visited[node] = true; } for (int neighbor : adj[node]) { if (!visited[neighbor]) { s.push(neighbor); } } } cout << endl; } void BFS(int start) const { vector<bool> visited(V, false); queue<int> q; q.push(start); visited[start] = true; while (!q.empty()) { int node = q.front(); q.pop(); cout << node << " "; for (int neighbor : adj[node]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } cout << endl; } }; int main() { int vertices = 6; // Number of vertices Graph g(vertices); // Adding edges to the graph g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(1, 4); g.addEdge(2, 5); cout << "DFS starting from vertex 0: "; g.DFS(0); cout << "BFS starting from vertex 0: "; g.BFS(0); return 0; } |
Explanation
- Include Libraries:
#include <iostream>: For input and output operations.#include <vector>: For using dynamic arrays (vectors).#include <queue>: For the BFS implementation.#include <stack>: For the DFS implementation.
- Graph Class:
- Private Data Members:
V: Number of vertices.adj: Adjacency list representation of the graph, where each vertex has a list of its neighbors.
- Public Methods:
Graph(int vertices): Constructor to initialize the graph with a given number of vertices.void addEdge(int u, int v): Adds an undirected edge between verticesuandv.void DFS(int start) const: Performs Depth-First Search starting from vertexstart.- Uses a stack to manage the nodes.
- Marks nodes as visited and prints them.
- Pushes unvisited neighbors onto the stack.
void BFS(int start) const: Performs Breadth-First Search starting from vertexstart.- Uses a queue to manage the nodes.
- Marks nodes as visited and prints them.
- Enqueues unvisited neighbors.
- Private Data Members:
- Main Function (
main):- Creates a
Graphobject with a specified number of vertices. - Adds edges to the graph using the
addEdgemethod. - Calls
DFSandBFSmethods to demonstrate the traversal of the graph starting from vertex 0.
- Creates a