Design And analysis algorithm course Remarks: In all the algorithms, always expl
ID: 3793385 • Letter: D
Question
Design And analysis algorithm courseRemarks: In all the algorithms, always explain their correctness and analyze their com- plexity. The complexity should be as small as possible. A correct algorithm with large complexity, may not get full credit Question 4 Let G be a directed graph. The directed subgraph induced by X CV, has X as vertice, and has all edges with both endpoint in X. This graph is denoted by G(X). We say that the graoh GCX)) is strongly connected if the distance between any pair of vertices is finite (thus for every a,y there is a finite path from a to y and a finite path from y to z). G(X) is a strongly connected componnent if: 1. G(X) is strongly connected and, 2. For every X' so that X CX' and X XX is not a strongly connected graph. Give an algorithm (and describe a data structure if needed) to find the connected componnents in a graph. Warning: You are allowed to use only things tought in class. In particular any algorithm that uses the depth first seatch procedure, will not get any points.
Explanation / Answer
// Program to print BFS traversal from a given source vertex.
#include "stdafx.h"
#include<iostream>
#include <list>
using namespace std;
//This class represents a directed graph
class Graph
{
int X; // Number of vertices
list<int> *adj; // Pointer to an array containing adjacency lists
public:
Graph(int X); // Constructor
void addEdge(int x, int y); // function to add an edge to graph
void BFS(int s); // prints BFS traversal from a given source s
};
Graph::Graph(int X)
{
this->X = X;
adj = new list<int>[X];
}
void Graph::addEdge(int x, int y)
{
adj[x].push_back(y); // Add w to v’s list.
}
void Graph::BFS(int s)
{
// Mark all the vertices as not visited
bool *visited = new bool[X];
for (int i = 0; i < X; i++)
visited[i] = false;
// Create a queue for BFS
list<int> queue;
// Mark the current node as visited and enqueue it
visited[s] = true;
queue.push_back(s);
// 'i' will be used to get all adjacent vertices of a vertex
list<int>::iterator i;
while (!queue.empty())
{
// Dequeue a vertex from queue and print it
s = queue.front();
cout << s << " ";
queue.pop_front();
// Get all adjacent vertices of the dequeued vertex s
// If a adjacent has not been visited, then mark it visited
// and enqueue it
for (i = adj[s].begin(); i != adj[s].end(); ++i)
{
if (!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
}
int main()
{
// Create a graph
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 << "Following is Breadth First Traversal "
<< "(starting from vertex 2) ";
G.BFS(2);
getchar();
}