Sunday 26 February 2023
here's an example implementation of Breadth-First Search (BFS) algorithm in Python:
from collections import deque
class Graph:
def __init__(self, graph):
self.graph = graph
def bfs(self, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
print(vertex, end=' ')
for neighbor in self.graph[vertex]:
if neighbor not in visited:
queue.append(neighbor)
graph = {0: [1, 2], 1: [2], 2: [0, 3], 3: [3]}
g = Graph(graph)
g.bfs(2)
In this example, we define a Graph class that takes a graph as input and provides a bfs method to perform the BFS traversal. The bfs method initializes a visited set and a queue with the starting vertex.
We then iterate over the queue, popping the first vertex and adding it to the visited set if it hasn't already been visited. We print the vertex and then iterate over its neighbors, adding them to the queue if they haven't been visited yet.
Finally, we create a sample graph as a dictionary and call the bfs method on the starting vertex '2' to begin the search. The output will be the order in which the vertices were visited during the BFS traversal.
here's an example implementation of Breadth-First Search (BFS) algorithm in Java:
import java.util.*;
public class Graph {
private int V;
private List<List<Integer>> adj;
public Graph(int V) {
this.V = V;
adj = new ArrayList<>(V);
for (int i = 0; i < V; ++i) {
adj.add(new ArrayList<>());
}
}
public void addEdge(int v, int w) {
adj.get(v).add(w);
}
public void bfs(int start) {
boolean[] visited = new boolean[V];
LinkedList<Integer> queue = new LinkedList<>();
visited[start] = true;
queue.add(start);
while (queue.size() != 0) {
start = queue.poll();
System.out.print(start + " ");
for (int neighbor : adj.get(start)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
}
public static void main(String[] args) {
Graph g = new Graph(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);
System.out.println("BFS Traversal starting from vertex 2:");
g.bfs(2);
}
}
In this example, we define a Graph class that takes the number of vertices as input and provides an addEdge method to add edges between vertices, as well as a bfs method to perform the BFS traversal.
We initialize a boolean visited array to keep track of visited vertices, and a queue to store vertices to be visited. We then mark the starting vertex as visited and add it to the queue.
We iterate over the queue, polling the first vertex and printing it. We then iterate over its neighbors and add any unvisited neighbors to the queue.
Finally, we create a sample graph and call the bfs method on the starting vertex '2' to begin the search. The output will be the order in which the vertices were visited during the BFS traversal.
Here's an example implementation of Breadth-First Search (BFS) algorithm in PHP:
<?php
class Graph {
private $V;
private $adj;
public function __construct($V) {
$this->V = $V;
$this->adj = array();
for ($i = 0; $i < $V; ++$i) {
$this->adj[$i] = array();
}
}
public function addEdge($v, $w) {
array_push($this->adj[$v], $w);
}
public function bfs($start) {
$visited = array_fill(0, $this->V, false);
$queue = array();
array_push($queue, $start);
$visited[$start] = true;
while (!empty($queue)) {
$start = array_shift($queue);
echo $start." ";
foreach ($this->adj[$start] as $neighbor) {
if (!$visited[$neighbor]) {
$visited[$neighbor] = true;
array_push($queue, $neighbor);
}
}
}
}
}
$g = new Graph(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);
echo "BFS Traversal starting from vertex 2:\n";
$g->bfs(2);
?>
In this example, we define a Graph class that takes the number of vertices as input and provides an addEdge method to add edges between vertices, as well as a bfs method to perform the BFS traversal.
We initialize a boolean visited array to keep track of visited vertices, and a queue to store vertices to be visited. We then mark the starting vertex as visited and add it to the queue.
We iterate over the queue, shifting the first vertex and printing it. We then iterate over its neighbors and add any unvisited neighbors to the queue.
Finally, we create a sample graph and call the bfs method on the starting vertex '2' to begin the search. The output will be the order in which the vertices were visited during the BFS traversal.
Here's an example implementation of Breadth-First Search (BFS) algorithm in Android:
First, create a Graph class to represent the graph:
public class Graph {
private int V;
private LinkedList<Integer>[] adj;
public Graph(int v) {
V = v;
adj = new LinkedList[v];
for (int i = 0; i < v; ++i) {
adj[i] = new LinkedList();
}
}
public void addEdge(int v, int w) {
adj[v].add(w);
}
public LinkedList<Integer>[] getAdj() {
return adj;
}
}
Next, create a BFS method to perform the BFS traversal:
public void bfs(int start) {
boolean[] visited = new boolean[V];
LinkedList<Integer> queue = new LinkedList<Integer>();
visited[start] = true;
queue.add(start);
while (queue.size() != 0) {
start = queue.poll();
System.out.print(start + " ");
LinkedList<Integer> adjList = adj[start];
for (int i = 0; i < adjList.size(); ++i) {
int neighbor = adjList.get(i);
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.add(neighbor);
}
}
}
}
Finally, create a sample graph and call the BFS method on the starting vertex:
Graph g = new Graph(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);
System.out.println("BFS Traversal starting from vertex 2:");
g.bfs(2);
This implementation uses a boolean array to keep track of visited vertices, and a LinkedList to store vertices to be visited. We mark the starting vertex as visited and add it to the queue, then iterate over the queue, removing the first vertex and printing it. We then iterate over its neighbors and add any unvisited neighbors to the queue.
The output will be the order in which the vertices were visited during the BFS traversal.
Here's an example implementation of Breadth-First Search (BFS) algorithm in C++:
First, create a Graph class to represent the graph:
#include <iostream>
#include <list>
#include <queue>
using namespace std;
class Graph {
int V;
list<int>* adj;
public:
Graph(int V);
void addEdge(int v, int w);
void bfs(int start);
};
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::bfs(int start) {
bool* visited = new bool[V];
for (int i = 0; i < V; i++) {
visited[i] = false;
}
queue<int> queue;
visited[start] = true;
queue.push(start);
while (!queue.empty()) {
start = queue.front();
cout << start << " ";
queue.pop();
for (auto i = adj[start].begin(); i != adj[start].end(); ++i) {
if (!visited[*i]) {
visited[*i] = true;
queue.push(*i);
}
}
}
}
Next, create a sample graph and call the BFS method on the starting vertex:
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 << "BFS Traversal starting from vertex 2:" << endl;
g.bfs(2);
cout << endl;
return 0;
}
This implementation uses a bool array to keep track of visited vertices, and a queue to store vertices to be visited. We mark the starting vertex as visited and add it to the queue, then iterate over the queue, removing the front vertex and printing it. We then iterate over its neighbors and add any unvisited neighbors to the queue.
The output will be the order in which the vertices were visited during the BFS traversal.