DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
Experiment-3.1
Student Name: Varun Pratap UID: 21BCS9015
Branch: CSE Section/Group: IOT_636-A
Semester: 5th Date of Performance:23/10/23
Subject Name: DAA Lab Subject Code: 21CSP-314
1. Aim: Develop a program and analyze complexity to do a depth-first search (DFS) on an
undirected graph. Implementing an application of DFS such as
(i) to find the topological sort of a directed acyclic graph, OR
(ii) to find a path from source to goal in a maze
2. Algorithms:
(i)
Step: 1. Initialize an empty stack to store the topological order.
Step: 2. Initialize a set or array to keep track of visited vertices to avoid revisiting them.
Step: 3. For each unvisited vertex 'v' in the DAG, perform a DFS:
- Call the DFS function with 'v' as the starting vertex.
Step: 4. In the DFS function, do the following:
- Mark the current vertex as visited.
- Recursively visit all unvisited neighbors of the current vertex.
- Push the current vertex onto the stack when all its neighbors have been visited.
Step: 5. After DFS traversal of the entire graph, the stack will contain the topological order in
reverse order.
Step: 6. Create a result list and pop elements from the stack to construct the topological order in
the correct order.
Step: 7. Return the topological order as the output.
End of Algorithm.
(ii)
Step 1: Create a stack data structure to maintain the nodes to be explored.
Step 2: Initialize a 2D boolean matrix called 'visited' to track visited cells. Initialize all cells
as unvisited.
Step 3: Push the starting node (startX, startY) onto the stack.
Step 4: While the stack is not empty:
a) Pop the top node from the stack and mark it as visited.
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
b) If the popped node is the goal node (goalX, goalY), return True as a path has been
found.
c) For each unvisited neighboring cell (newX, newY) that is a valid move:
i) Push the neighboring cell onto the stack.
Step 5: If the stack becomes empty and the goal node has not been reached, return False as
there is no path from (startX, startY) to (goalX, goalY).
End of Algorithm.
3. Code:
(i)
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Graph {
int V; // Number of vertices
vector<vector<int>> adj; // Adjacency list
public:
Graph(int vertices) : V(vertices) {
adj.resize(V);
}
// Function to add a directed edge to the graph
void addEdge(int u, int v) {
adj[u].push_back(v);
}
// Depth-First Search function for topological sort
void DFS(int v, vector<bool>& visited, stack<int>& result) {
visited[v] = true;
for (int u : adj[v]) {
if (!visited[u]) {
DFS(u, visited, result);
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
}
}
result.push(v);
}
// Function to find the topological sort of the graph
vector<int> topologicalSort() {
vector<bool> visited(V, false);
stack<int> result;
for (int i = 0; i < V; i++) {
if (!visited[i]) {
DFS(i, visited, result);
}
}
vector<int> topologicalOrder;
while (!result.empty()) {
topologicalOrder.push_back(result.top());
result.pop();
}
return topologicalOrder;
}
};
int main() {
// Create a directed acyclic graph
Graph g(6);
g.addEdge(5, 2);
g.addEdge(5, 0);
g.addEdge(4, 0);
g.addEdge(4, 1);
g.addEdge(2, 3);
g.addEdge(3, 1);
// Find and print the topological sort
vector<int> topologicalOrder = g.topologicalSort();
cout << "Topological Sort: ";
for (int vertex : topologicalOrder) {
cout << vertex << " ";
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
}
cout << endl;
return 0;
}
(ii)
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int ROWS = 5;
const int COLS = 5;
int maze[ROWS][COLS] = {
{0, 1, 0, 0, 0},
{0, 1, 1, 0, 1},
{0, 0, 0, 0, 0},
{1, 1, 1, 1, 0},
{0, 0, 0, 1, 0}
};
// Define the possible moves (up, down, left, right)
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
struct Node {
int x, y;
};
bool isValid(int x, int y) {
return x >= 0 && x < ROWS && y >= 0 && y < COLS && maze[x][y] == 0;
}
bool dfs(int startX, int startY, int goalX, int goalY) {
stack<Node> st;
st.push({startX, startY});
vector<vector<bool>> visited(ROWS, vector<bool>(COLS, false));
while (!st.empty()) {
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
Node current = st.top();
st.pop();
int x = current.x;
int y = current.y;
if (x == goalX && y == goalY) {
return true; // Goal found
}
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int newX = x + dx[i];
int newY = y + dy[i];
if (isValid(newX, newY) && !visited[newX][newY]) {
st.push({newX, newY});
}
}
}
return false; // Goal not reachable
}
int main() {
int startX = 0;
int startY = 0;
int goalX = 4;
int goalY = 4;
if (dfs(startX, startY, goalX, goalY)) {
cout << "Path from (" << startX << "," << startY << ") to (" << goalX << "," << goalY
<< ") exists!" << endl;
} else {
cout << "Path from (" << startX << "," << startY << ") to (" << goalX << "," << goalY
<< ") does not exist." << endl;
}
return 0;
}
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
3. Output:
(i)
(ii)
4. Time complexity:
(i) The time complexity of the topological sort algorithm is O(V + E), where V is the number
of vertices and E is the number of edges in the graph.
(ii) The time complexity of the DFS algorithm is O(V + E), where V is the number of vertices
(grid cells) and E is the number of edges (possible moves).
DEPARTMENT OF
COMPUTER SCIENCE & ENGINEERING
