1.
BFS
#include <iostream>
#include <list>
#include <queue>
using namespace std;
class Graph {
int vertices; // Number of vertices
list<int> *adjList; // Pointer to an array containing adjacency lists
public:
// Constructor
Graph(int v) {
vertices = v;
adjList = new list<int>[v];
}
// Function to add an edge to the graph
void addEdge(int v, int w) {
adjList[v].push_back(w); // Add w to v's list
}
// BFS traversal from a given source node
void bfs(int start) {
// Mark all the vertices as not visited
bool *visited = new bool[vertices];
for (int i = 0; i < vertices; i++)
visited[i] = false;
// Create a queue for BFS
queue<int> q;
// Mark the current node as visited and enqueue it
visited[start] = true;
q.push(start);
while (!q.empty()) {
// Dequeue a vertex from the queue and print it
start = q.front();
cout << start << " ";
q.pop();
// Get all adjacent vertices of the dequeued vertex
// If adjacent has not been visited, mark it and enqueue it
for (auto adj : adjList[start]) {
if (!visited[adj]) {
visited[adj] = true;
q.push(adj);
}
}
}
}
};
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Breadth First Traversal starting from vertex 2:" << endl;
g.bfs(2);
return 0;
}
2. DFS
#include <iostream>
#include <list>
using namespace std;
class Graph {
int vertices; // Number of vertices
list<int> *adjList; // Pointer to an array containing adjacency lists
public:
// Constructor
Graph(int v) {
vertices = v;
adjList = new list<int>[v];
}
// Function to add an edge to the graph
void addEdge(int v, int w) {
adjList[v].push_back(w); // Add w to v's list
}
// A function used by DFS
void dfsUtil(int v, bool visited[]) {
// Mark the current node as visited and print it
visited[v] = true;
cout << v << " ";
// Recur for all the vertices adjacent to this vertex
for (auto adj : adjList[v]) {
if (!visited[adj])
dfsUtil(adj, visited);
}
}
// DFS traversal of the vertices reachable from v
void dfs(int v) {
// Mark all the vertices as not visited
bool *visited = new bool[vertices];
for (int i = 0; i < vertices; i++)
visited[i] = false;
// Call the recursive helper function to print DFS traversal
dfsUtil(v, visited);
}
};
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
cout << "Depth First Traversal starting from vertex 2:" << endl;
g.dfs(2);
return 0;
}
Problem 1: Shortest Path in an Unweighted Graph
Given an unweighted graph and a source node, find the shortest path from the source node to
all other nodes in the graph.
● Input: An unweighted graph represented as an adjacency list and a source node.
● Output: The shortest path from the source node to every other node in terms of the
number of edges.
● Hint: You can use BFS to find the shortest path in an unweighted graph since BFS
explores the graph level by level, ensuring that you find the shortest path.
Input:
Graph: 0 -> 1 -> 2
| |
v v
3 -> 4
Source: 0
Output:
Distance from 0 to 0: 0
Distance from 0 to 1: 1
Distance from 0 to 2: 2
Distance from 0 to 3: 1
Distance from 0 to 4: 2
Problem 2: Cycle Detection in a Graph
Given a directed graph, detect whether the graph contains a cycle.
● Input: A directed graph represented as an adjacency list.
● Output: Return true if there is a cycle in the graph, false otherwise.
● Hint: Use DFS and keep track of nodes that are currently in the recursion stack. If a
node that is already in the stack is encountered again, a cycle exists.
● Example:
Input:
Graph: 0 -> 1 -> 2 -> 3 -> 1
Output:
True (Cycle exists)
