Basic Graph Algorithms (DFS, BFS) Gaming Project in C++

Projects Inventory

3 months ago

#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;
}

#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 vertices u and v.
  - void DFS(int start) const: Performs Depth-First Search starting from vertex start.
    - 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 vertex start.
    - Uses a queue to manage the nodes.
    - Marks nodes as visited and prints them.
    - Enqueues unvisited neighbors.
Main Function (main):
- Creates a Graph object with a specified number of vertices.
- Adds edges to the graph using the addEdge method.
- Calls DFS and BFS methods to demonstrate the traversal of the graph starting from vertex 0.

Explanation

Related Posts: