Scribd
Upload
5 views4 pages

Daa

The document contains implementations of graph traversal algorithms including BFS and DFS, along with Prim's Algorithm for finding the Minimum Spanning Tree (MST). Each algorithm is encapsulated in a Graph class with methods to add edges and perform the respective traversal or MST computation. The main function demonstrates the usage of these algorithms on a sample graph.

Uploaded by

Somay Singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views4 pages

Daa

The document contains implementations of graph traversal algorithms including BFS and DFS, along with Prim's Algorithm for finding the Minimum Spanning Tree (MST). Each algorithm is encapsulated in a Graph class with methods to add edges and perform the respective traversal or MST computation. The main function demonstrates the usage of these algorithms on a sample graph.

Uploaded by

Somay Singh
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

BFS traversal

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Graph {
int V;
vector<vector<int>> adj;

public:
Graph(int V) {
this->V = V;
adj.resize(V);
}

void addEdge(int u, int v) {


adj[u].push_back(v);
adj[v].push_back(u); }

void BFS(int s) {
vector<bool> discovered(V, false);
queue<int> q;

discovered[s] = true;
q.push(s);

cout << "BFS Traversal: ";


while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " ";

for (int v : adj[u]) {


if (!discovered[v]) {
discovered[v] = true;
q.push(v);
}
}
}
cout << endl;
}
};

int main() {
Graph g(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 5);

g.BFS(0);

return 0;
}

DFS traversal
#include <iostream>
#include <vector>
#include <stack>

using namespace std;

class Graph {
int V;
vector<vector<int>> adj;

public:
Graph(int V) {
this->V = V;
adj.resize(V);
}

void addEdge(int u, int v) {


adj[u].push_back(v);
adj[v].push_back(u);
}

void DFS(int s) {
vector<bool> discovered(V, false);
vector<int> parent(V, -1);
stack<int> st;

st.push(s);

cout << "DFS Traversal: ";


while (!st.empty()) {
int u = st.top();
st.pop();

if (!discovered[u]) {
discovered[u] = true;
cout << u << " ";

for (int v : adj[u]) {


if (!discovered[v]) {
st.push(v);
parent[v] = u;
}
}
}
}
cout << endl;
}
};

int main() {
Graph g(6);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 5);

g.DFS(0);

return 0;
}

Prim’s Algorithm
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int, int> pii; // (weight, vertex)

void primMST(int V, vector<vector<pii>> &adj) {


vector<int> key(V, 1e9);
vector<int> parent(V, -1);
vector<bool> inMST(V, false);

priority_queue<pii, vector<pii>, greater<pii>> pq;


key[0] = 0;
pq.push({0, 0});

while (!pq.empty()) {
int u = pq.top().second;
pq.pop();

if (inMST[u]) continue;
inMST[u] = true;

for (auto it : adj[u]) {


int weight = it.first;
int v = it.second;
if (!inMST[v] && weight < key[v]) {
key[v] = weight;
parent[v] = u;
pq.push({key[v], v});
}
}
}

cout << "Edges in the MST:\n";


for (int i = 1; i < V; i++) {
cout << parent[i] << " - " << i << "\n";
}
}

int main() {
int V = 5;
vector<vector<pii>> adj(V);

adj[0].push_back({2, 1});
adj[1].push_back({2, 0});

adj[0].push_back({3, 3});
adj[3].push_back({3, 0});

adj[1].push_back({3, 2});
adj[2].push_back({3, 1});

adj[1].push_back({1, 3});
adj[3].push_back({1, 1});

adj[1].push_back({4, 4});
adj[4].push_back({4, 1});

adj[2].push_back({5, 4});
adj[4].push_back({5, 2});

adj[3].push_back({6, 4});
adj[4].push_back({6, 3});

primMST(V, adj);
return 0;
}

You might also like