CS607P Quiz

Lab 1

Topic: Depth First Search (DFS)

Problem Statements: You are required to code depth first strategy for the following directed graph in C/C++. Your program is capable to input source vertex.

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 · Lab 3 · Topic: Breadth First Search (BFS)

Problem Statement: You are required to code breadth first strategy for the following directed graph in C/C++. Your program is capable to input source vertex.

// 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;