ALGORITMO DISTRAK PARA CAMINO MINIMO
// A C++ program for Dijkstra's single source shortest path
algorithm.
// The program is for adjacency matrix representation of the graph
#include <iostream>
using namespace std;
#include <limits.h>
// Number of vertices in the graph
#define V 9
// A utility function to find the vertex with minimum distance value,
from
// the set of vertices not yet included in shortest path tree
int minDistance(int dist[], bool sptSet[])
{
// Initialize min value
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
// A utility function to print the constructed distance array
void printSolution(int dist[])
{
cout <<"Vertex \t Distance from Source" << endl;
for (int i = 0; i < V; i++)
cout << i << " \t\t"<<dist[i]<< endl;
}
// Function that implements Dijkstra's single source shortest path
algorithm
// for a graph represented using adjacency matrix representation
void dijkstra(int graph[V][V], int src)
{
int dist[V]; // The output array. dist[i] will hold the shortest
// distance from src to i
bool sptSet[V]; // sptSet[i] will be true if vertex i is included
in shortest
// path tree or shortest distance from src to i is finalized
// Initialize all distances as INFINITE and stpSet[] as false
for (int i = 0; i < V; i++)
dist[i] = INT_MAX, sptSet[i] = false;
// Distance of source vertex from itself is always 0
dist[src] = 0;
// Find shortest path for all vertices
for (int count = 0; count < V - 1; count++) {
// Pick the minimum distance vertex from the set of vertices
not
// yet processed. u is always equal to src in the first
iteration.
int u = minDistance(dist, sptSet);
// Mark the picked vertex as processed
sptSet[u] = true;
// Update dist value of the adjacent vertices of the picked
vertex.
for (int v = 0; v < V; v++)
// Update dist[v] only if is not in sptSet, there is an
edge from
// u to v, and total weight of path from src to v
through u is
// smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
// print the constructed distance array
printSolution(dist);
}
// driver program to test above function
int main()
{
/* Let us create the example graph discussed above */
int graph[V][V] = { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
dijkstra(graph, 0);
return 0;
}
// This code is contributed by shivanisinghss2110
(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((
import sys
class Graph():
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)]
for row in range(vertices)]
def printSolution(self, dist):
print "Vertex \tDistance from Source"
for node in range(self.V):
print node, "\t", dist[node]
# A utility function to find the vertex with
# minimum distance value, from the set of vertices
# not yet included in shortest path tree
def minDistance(self, dist, sptSet):
# Initialize minimum distance for next node
min = sys.maxint
# Search not nearest vertex not in the
# shortest path tree
for u in range(self.V):
if dist[u] < min and sptSet[u] == False:
min = dist[u]
min_index = u
return min_index
# Function that implements Dijkstra's single source
# shortest path algorithm for a graph represented
# using adjacency matrix representation
def dijkstra(self, src):
dist = [sys.maxint] * self.V
dist[src] = 0
sptSet = [False] * self.V
for cout in range(self.V):
# Pick the minimum distance vertex from
# the set of vertices not yet processed.
# x is always equal to src in first iteration
x = self.minDistance(dist, sptSet)
# Put the minimum distance vertex in the
# shortest path tree
sptSet[x] = True
# Update dist value of the adjacent vertices
# of the picked vertex only if the current
# distance is greater than new distance and
# the vertex in not in the shortest path tree
for y in range(self.V):
if self.graph[x][y] > 0 and sptSet[y] == False and \
dist[y] > dist[x] + self.graph[x][y]:
dist[y] = dist[x] + self.graph[x][y]
self.printSolution(dist)
# Driver program
g = Graph(9)
g.graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]
];
g.dijkstra(0);
////////////////////////////////////////////////////////////
// Program to find Dijkstra's shortest path using STL set
#include<bits/stdc++.h>
using namespace std;
# define INF 0x3f3f3f3f
// This class represents a directed graph using
// adjacency list representation
class Graph
{
int V; // No. of vertices
// In a weighted graph, we need to store vertex
// and weight pair for every edge
list< pair<int, int> > *adj;
public:
Graph(int V); // Constructor
// function to add an edge to graph
void addEdge(int u, int v, int w);
// prints shortest path from s
void shortestPath(int s);
};
// Allocates memory for adjacency list
Graph::Graph(int V)
{
this->V = V;
adj = new list< pair<int, int> >[V];
}
void Graph::addEdge(int u, int v, int w)
{
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
// Prints shortest paths from src to all other vertices
void Graph::shortestPath(int src)
{
// Create a set to store vertices that are being
// processed
set< pair<int, int> > setds;
// Create a vector for distances and initialize all
// distances as infinite (INF)
vector<int> dist(V, INF);
// Insert source itself in Set and initialize its
// distance as 0.
setds.insert(make_pair(0, src));
dist[src] = 0;
/* Looping till all shortest distance are finalized
then setds will become empty */
while (!setds.empty())
{
// The first vertex in Set is the minimum distance
// vertex, extract it from set.
pair<int, int> tmp = *(setds.begin());
setds.erase(setds.begin());
// vertex label is stored in second of pair (it
// has to be done this way to keep the vertices
// sorted distance (distance must be first item
// in pair)
int u = tmp.second;
// 'i' is used to get all adjacent vertices of a vertex
list< pair<int, int> >::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
{
// Get vertex label and weight of current adjacent
// of u.
int v = (*i).first;
int weight = (*i).second;
// If there is shorter path to v through u.
if (dist[v] > dist[u] + weight)
{
/* If distance of v is not INF then it must be in
our set, so removing it and inserting again
with updated less distance.
Note : We extract only those vertices from Set
for which distance is finalized. So for them,
we would never reach here. */
if (dist[v] != INF)
setds.erase(setds.find(make_pair(dist[v], v)));
// Updating distance of v
dist[v] = dist[u] + weight;
setds.insert(make_pair(dist[v], v));
}
}
}
// Print shortest distances stored in dist[]
printf("Vertex Distance from Source\n");
for (int i = 0; i < V; ++i)
printf("%d \t\t %d\n", i, dist[i]);
printf("prueba");
printf("%d \t\t %d\n", 1, dist[1]);
}
// Driver program to test methods of graph class
int main()
{
// create the graph given in above fugure
int V = 9;
Graph g(V);
// making above shown graph
g.addEdge(0, 1, 4);
g.addEdge(0, 7, 8);
g.addEdge(1, 2, 8);
g.addEdge(1, 7, 11);
g.addEdge(2, 3, 7);
g.addEdge(2, 8, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 4, 9);
g.addEdge(3, 5, 14);
g.addEdge(4, 5, 10);
g.addEdge(5, 6, 2);
g.addEdge(6, 7, 1);
g.addEdge(6, 8, 6);
g.addEdge(7, 8, 7);
g.shortestPath(2);
return 0;
}
///////////////////////////////////////////////////////////////////////////////////////
BINARY SEARCH
#include <bits/stdc++.h>
using namespace std;
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not
// present in array
return -1;
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1)
? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}
/////////////////////////////////////////////////////////////////////7
#include <bits/stdc++.h>
using namespace std;
// A recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
// If the element is present at the middle
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not
// present in array
return -1;
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1)
? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}
//////////////////////////////////////////////////////////////////////////7
#include <iostream>
#include <algorithm>
#include <vector>
int main()
{
std::vector<int> haystack {1, 3, 4, 5, 9};
std::vector<int> needles {1, 2, 3};
for (auto needle : needles) {
std::cout << "Searching for " << needle << '\n';
if (std::binary_search(haystack.begin(), haystack.end(), needle))
{
std::cout << "Found " << needle << '\n';
} else {
std::cout << "no dice!\n";
}
}
}
Output:
Searching for 1
Found 1
Searching for 2
no dice!
Searching for 3
Found 3
//////////////////////////////////////////7
PRIMOS
def es_primo(n):
# Comprobamos si n es 2 (unico primo par)
if n == 2:
return True
# Comprobamos si es menor de 2 o es par
if n < 2 or not n % 2:
return False
# Comprobamos si es divisible entre cualquier entero impar entre 3 y sqrt(n)
return not any(n % i == 0 for i in range(3, int(n**0.5) + 1, 2))
////////////////////////////////////
test de fermat
#include <cstring>
#include <iostream>
#include <cstdlib>
#define ll long long
using namespace std;
ll modulo(ll base, ll e, ll mod) {
ll a = 1;
ll b = base;
while (e > 0) {
if (e % 2 == 1)
a = (a * b) % mod;
b = (b * b) % mod;
e = e / 2;
}
return a % mod;
}
bool Fermat(ll m, int iterations) {
if (m == 1) {
return false;
}
for (int i = 0; i < iterations; i++) {
ll x = rand() % (m - 1) + 1;
if (modulo(x, m - 1, m) != 1) {
return false;
}
}
return true;
}
int main() {
int iteration = 70;
ll num;
cout<<"Enter integer to test primality: ";
cin>>num;
if (Fermat(num, iteration))
cout<<num<<" is prime"<<endl;
else
cout<<num<<" is not prime"<<endl;
return 0;
}
///////////////////////////////////////////////////////////////
TEST DE MILLER RABIN
// C++ program Miller-Rabin primality test
#include <bits/stdc++.h>
using namespace std;
// Utility function to do modular exponentiation.
// It returns (x^y) % p
int power(int x, unsigned int y, int p)
{
int res = 1; // Initialize result
x = x % p; // Update x if it is more than or
// equal to p
while (y > 0)
{
// If y is odd, multiply x with result
if (y & 1)
res = (res*x) % p;
// y must be even now
y = y>>1; // y = y/2
x = (x*x) % p;
}
return res;
}
// This function is called for all k trials. It returns
// false if n is composite and returns true if n is
// probably prime.
// d is an odd number such that d*2<sup>r</sup> = n-1
// for some r >= 1
bool miillerTest(int d, int n)
{
// Pick a random number in [2..n-2]
// Corner cases make sure that n > 4
int a = 2 + rand() % (n - 4);
// Compute a^d % n
int x = power(a, d, n);
if (x == 1 || x == n-1)
return true;
// Keep squaring x while one of the following doesn't
// happen
// (i) d does not reach n-1
// (ii) (x^2) % n is not 1
// (iii) (x^2) % n is not n-1
while (d != n-1)
{
x = (x * x) % n;
d *= 2;
if (x == 1) return false;
if (x == n-1) return true;
}
// Return composite
return false;
}
// It returns false if n is composite and returns true if n
// is probably prime. k is an input parameter that determines
// accuracy level. Higher value of k indicates more accuracy.
bool isPrime(int n, int k)
{
// Corner cases
if (n <= 1 || n == 4) return false;
if (n <= 3) return true;
// Find r such that n = 2^d * r + 1 for some r >= 1
int d = n - 1;
while (d % 2 == 0)
d /= 2;
// Iterate given nber of 'k' times
for (int i = 0; i < k; i++)
if (!miillerTest(d, n))
return false;
return true;
}
// Driver program
int main()
{
int k = 4; // Number of iterations
cout << "All primes smaller than 100: \n";
for (int n = 1; n < 100; n++)
if (isPrime(n, k))
cout << n << " ";
return 0;
}
//////////////////////////////////////////7
# Python3 program Miller-Rabin primality test
import random
# Utility function to do
# modular exponentiation.
# It returns (x^y) % p
def power(x, y, p):
# Initialize result
res = 1;
# Update x if it is more than or
# equal to p
x = x % p;
while (y > 0):
# If y is odd, multiply
# x with result
if (y & 1):
res = (res * x) % p;
# y must be even now
y = y>>1; # y = y/2
x = (x * x) % p;
return res;
# This function is called
# for all k trials. It returns
# false if n is composite and
# returns false if n is
# probably prime. d is an odd
# number such that d*2<sup>r</sup> = n-1
# for some r >= 1
def miillerTest(d, n):
# Pick a random number in [2..n-2]
# Corner cases make sure that n > 4
a = 2 + random.randint(1, n - 4);
# Compute a^d % n
x = power(a, d, n);
if (x == 1 or x == n - 1):
return True;
# Keep squaring x while one
# of the following doesn't
# happen
# (i) d does not reach n-1
# (ii) (x^2) % n is not 1
# (iii) (x^2) % n is not n-1
while (d != n - 1):
x = (x * x) % n;
d *= 2;
if (x == 1):
return False;
if (x == n - 1):
return True;
# Return composite
return False;
# It returns false if n is
# composite and returns true if n
# is probably prime. k is an
# input parameter that determines
# accuracy level. Higher value of
# k indicates more accuracy.
def isPrime( n, k):
# Corner cases
if (n <= 1 or n == 4):
return False;
if (n <= 3):
return True;
# Find r such that n =
# 2^d * r + 1 for some r >= 1
d = n - 1;
while (d % 2 == 0):
d //= 2;
# Iterate given nber of 'k' times
for i in range(k):
if (miillerTest(d, n) == False):
return False;
return True;
# Driver Code
# Number of iterations
k = 4;
print("All primes smaller than 100: ");
for n in range(1,100):
if (isPrime(n, k)):
print(n , end=" ");
////////////////////////////////////////////////////////////
RAIZ CUADRADA DE BIG INTEGER
public static BigInteger raiz(BigInteger x) {
BigInteger a= BigInteger.ZERO.setBit(x.bitLength()/2);
BigInteger b= a;
while(true) {
BigInteger c = a.add(x.divide(a)).shiftRight(1);
if (c.equals(a) || c.equals(b))
return c;
b= a;
a= c;
}
}
///////////////////////////////////
QUICK SORT
// Función recursiva para hacer el ordenamiento
void quicksort(int *array, int start, int end)
int pivot;
if (start &lt; end) {
pivot = divide(array, start, end);
// Ordeno la lista de los menores
quicksort(array, start, pivot - 1);
// Ordeno la lista de los mayores
quicksort(array, pivot + 1, end);
//////////////////////////////////////////////////////7
CRIBA DE ERATOSTENES
vector<bool> isPrime;
vector<int> primes;
void criba(int n) {
isPrime = vector<bool>(n, true);
primes = vector<int>();
isPrime[0] = isPrime[1] = false;
for (int i=2; i<n; ++i) {
if (isPrime[i]) {
primes.push_back(i);
for (int h=2; h*i<n; ++h) isPrime[i*h] = 0;
}
}
}
////////////////////////////////////////////////////////////////
/
def criba(n):
primes = []
isPrime = [1 for i in range(n)]
isPrime[0] = isPrime[1] = 0
for i in range(n):
if isPrime[i]:
primes.append(i)
h = 2
while i*h < n:
isPrime[i*h] = 0
h += 1
return primes, isPrime
/////////////////////////////////////////7
def criba_eratostenes(n):
primos = []
no_primos = []
for i in range(2, n + 1):
if i not in no_primos:
primos.append(i)
for j in range(i * i, n + 1, i):
no_primos.append(j)
return primos
/////////////////////////////////////////////////
máximo común divisor
int mcd(int a, int b) {
if(b == 0) return a;
return mcd(b, a%b);
}
def gcd(a, b):
if b == 0: return a
return gcd(b, a%b)
/////////////////////////////////////////7
DFS GRAFOS
# DFS algorithm in Python
# DFS algorithm
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for next in graph[start] - visited:
dfs(graph, next, visited)
return visited
graph = {'0': set(['1', '2']),
'1': set(['0', '3', '4']),
'2': set(['0']),
'3': set(['1']),
'4': set(['2', '3'])}
dfs(graph, '0')
///////////////////////////////////////////////////////////////
///
vector <bool> visited (n, false); // visited[v] es cierto sii
hemos visitado v
vector <vector <int> > G; //grafo G[v] es un vector con los
vecinos de v
// dado un nodo v visita a todos los nodos conectados a v
void dfs (int v) {
if (visited[v]) return;
visited[v] = true;
for (int i = 0; i < G[v].size(); ++i){ //iteramos por todos
los vecinos
int u = G[v][i];
dfs(u); //lo visitamos
}
}
/////////////////////////////////////////////////
// DFS algorithm in C++
#include <iostream>
#include <list>
using namespace std;
class Graph {
int numVertices;
list<int> *adjLists;
bool *visited;
public:
Graph(int V);
void addEdge(int src, int dest);
void DFS(int vertex);
};
// Initialize graph
Graph::Graph(int vertices) {
numVertices = vertices;
adjLists = new list<int>[vertices];
visited = new bool[vertices];
}
// Add edges
void Graph::addEdge(int src, int dest) {
adjLists[src].push_front(dest);
}
// DFS algorithm
void Graph::DFS(int vertex) {
visited[vertex] = true;
list<int> adjList = adjLists[vertex];
cout << vertex << " ";
list<int>::iterator i;
for (i = adjList.begin(); i != adjList.end(); ++i)
if (!visited[*i])
DFS(*i);
}
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.DFS(2);
return 0;
}
///////////////////////////////////////////////////////////////
#include <iostream>
#include <list>
using namespace std;
class Graph{
int V; //Numero de vertices
list<int> *adj; //arreglo de listas de adyacencia
bool *visited; //matriz de visitados.
public:
Graph(int V); //Constructor
void addEdge(int v,int w); //GRAFO Dirigido de v -> w
void DFS(int v); //DFS iniciando de v
};
Graph::Graph(int V){
this->V = V;
adj = new list<int>[V];
this->visited = new bool[this->V];
for(int i=0;i<this->V;i++) this->visited[i] = false;
}
void Graph::addEdge(int v,int w){
adj[v].push_back(w); //agrega w a la posicion v
//adj[w].push_back(v); si fuera no dirigido
}
void Graph::DFS(int v){
this->visited[v] = true; //marca el nodo actual como
visitado e imprimelo
cout << v << " ";
list<int>::iterator it;
for(it = adj[v].begin(); it!=adj[v].end();++it){ //nodos
adyacentes
if(!this->visited[*it]){
DFS(*it);
}
}
}
int main(){
int V = 4;
Graph G(V);
G.addEdge(0,1);
G.addEdge(0,2);
G.addEdge(1,2);
G.addEdge(2,0);
G.addEdge(2,3);
G.addEdge(3,3);
int src = 2;
cout << "La DFS de G es (iniciando de el vertice 2): " <<
endl << endl;
G.DFS(src);
/**
Si el grafo fuera disconexo:
for(int i=0;i<V;i++){
G.DFS(i);
}
*/
return 0;
}
//////////////////////////////////////////////////////////////
BFS GRAFOS
vector <bool> visited;
vector <vector <int> > G;
void bfs(int v){
queue <int> Q; //u otra estructura que sirva de cola
Q.push(v); //empezamos con el nodo origen
while (not Q.empty()){ //mientras nuestra lista tenga nodos
int u = Q.front(); //seleccionamos el primer nodo de la
lista
Q.pop(); //y lo eliminamos
if (not visited[u]){ //si no lo hemos visitado
visited[u] = true;
for (int i = 0; i < G[u].size(); ++i){
int w = G[u][i];
Q.push(w); //ponemos a sus vecinos en la lista
}
}
}
}
/////////////////////////////////////////////////
// Program to print BFS traversal from a given
// source vertex. BFS(int s) traverses vertices
// reachable from s.
#include<iostream>
#include <list>
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
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;
adj = new list<int>[V];
}
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w); // Add w to v’s list.
}
void Graph::BFS(int s)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
for(int i = 0; i < V; 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);
}
}
}
}
// Driver program to test methods of graph class
int main()
{
// Create a graph given in the above diagram
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) \n";
g.BFS(2);
return 0;
}
////////////////////////////////////////////////////////////////
# BFS algorithm in Python
import collections
# BFS algorithm
def bfs(graph, root):
visited, queue = set(), collections.deque([root])
visited.add(root)
while queue:
# Dequeue a vertex from queue
vertex = queue.popleft()
print(str(vertex) + " ", end="")
# If not visited, mark it as visited, and
# enqueue it
for neighbour in graph[vertex]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
if __name__ == '__main__':
graph = {0: [1, 2], 1: [2], 2: [3], 3: [1, 2]}
print("Following is Breadth First Traversal: ")
bfs(graph, 0)
