KEMBAR78
Name: Reg No:: BFS Algorithm | PDF | Theoretical Computer Science | Algorithms
Scribd
Upload
49 views4 pages

Name: Reg No:: BFS Algorithm

The document discusses implementations of breadth-first search (BFS) and depth-first search (DFS) graph traversal algorithms in C++. It includes code for a Graph class with methods to add edges and perform BFS and DFS. The BFS method uses a queue to visit and output adjacent unvisited vertices starting from a given start vertex. The DFS method uses recursion to depth-first traverse the graph and output visited vertices starting from a given start vertex. Sample code demonstrates using the Graph class to perform BFS and DFS on a graph with 4 vertices.

Uploaded by

Raviteja Challa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
49 views4 pages

Name: Reg No:: BFS Algorithm

The document discusses implementations of breadth-first search (BFS) and depth-first search (DFS) graph traversal algorithms in C++. It includes code for a Graph class with methods to add edges and perform BFS and DFS. The BFS method uses a queue to visit and output adjacent unvisited vertices starting from a given start vertex. The DFS method uses recursion to depth-first traverse the graph and output visited vertices starting from a given start vertex. Sample code demonstrates using the Graph class to perform BFS and DFS on a graph with 4 vertices.

Uploaded by

Raviteja Challa
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

LAB-10

NAME: CH RAVITEJA REG NO: 18BEC1057

BFS algorithm
1)

#include <iostream>

#include <list>

using namespace std;

class Graph

int numVertices;

list *adjLists;

bool* visited;

public:

Graph(int vertices);

void addEdge(int src, int dest);

void BFS(int startVertex);

};

Graph::Graph(int vertices)

numVertices = vertices;

adjLists = new list[vertices];

void Graph::addEdge(int src, int dest)

adjLists[src].push_back(dest);
adjLists[dest].push_back(src);

void Graph::BFS(int startVertex)

visited = new bool[numVertices];

for(int i = 0; i < numVertices; i++)

visited[i] = false;

list queue;

visited[startVertex] = true;

queue.push_back(startVertex);

list::iterator i;

while(!queue.empty())

int currVertex = queue.front();

cout << "Visited " << currVertex << " ";

queue.pop_front();

for(i = adjLists[currVertex].begin(); i != adjLists[currVertex].end(); ++i)

int adjVertex = *i;

if(!visited[adjVertex])

visited[adjVertex] = true;

queue.push_back(adjVertex);

}
}

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 << "Following is Breadth First Traversal "\n";

g.BFS(2);

return 0;

Output

// starting from vertex 2

2)
Depth First Search

#include<iostream>
#include<list>
using namespace std;

class Graph
{
int V;
list<int> *adj;
void DFSUtil(int v, bool visited[]);
public:
Graph(int V);
void addEdge(int v, int w);
void DFS(int v);
};
Graph::Graph(int V)
{
this->V = V;
adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)


{
adj[v].push_back(w);
}

void Graph::DFSUtil(int v, bool visited[])


{
visited[v] = true;
cout << v << " ";
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (!visited[*i])
DFSUtil(*i, visited);
}
void Graph::DFS(int v)
{
bool *visited = new bool[V];
for (int i = 0; i < V; i++)
visited[i] = false;

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 << "Following is Depth First Traversal"<<endl;


g.DFS(2);

return 0;
}

Output:

//starting from vertex 2

You might also like