CS607P Labs

The Solution of DFS revolves around the pseudo-code and the actual programming code:

The pseudo-code of DFS is given as:

Graph Traversal Universal Code

DFS(G, u) u.visited = true for each v ∈ G.Adj[u] if v.visited == false DFS(G,v)

init() { For each u ∈ G u.visited = false For each u ∈ G DFS(G, u)

Lab 2

Topic: Simulate DFS

Problem Statement: You are required to simulate DFS technique with the help of following stimulator. Download simulator from the Link

DFS(u) · for each neighbor v of u · if v is unvisited, tree edge, DFS(v) · else if v is explored, bidirectional/back edge · else if v is visited, forward/cross edge

// Program to print BFS traversal from a given

// source vertex. BFS(int s) traverses vertices

// reachable from s.

#include<bits/stdc++.h>

using namespace std;

// This class represents a directed graph using

// adjacency list representation

class Graph

int V; // No. of vertices

// Pointer to an array containing adjacency

// lists

vector<list<int>> adj;

public:

Graph(int V); // Constructor

// function to add an edge to graph

void addEdge(int v, int w);

// prints BFS traversal from a given source s

void BFS(int s);

Graph::Graph(int V)

this->V = V;