Supongamos que hay n pueblos conectados por m caminos bidireccionales. Hay s pueblos entre ellos con una estación de policía. Queremos saber la distancia de cada pueblo a la estación de policía más cercana. Si el propio pueblo tiene uno la distancia es 0.
Ejemplo:
Input : Number of Vertices = 6 Number of Edges = 9 Towns with Police Station : 1, 5 Edges: 1 2 1 6 2 6 2 3 3 6 5 4 6 5 3 4 5 3
Output : 1 0 2 1 3 1 4 1 5 0 6 1
Enfoque ingenuo: podemos recorrer los vértices y desde cada vértice ejecutar un BFS para encontrar la ciudad más cercana con estación de policía desde ese vértice. Esto tomará O (VE).
Implementación de enfoque ingenuo usando BFS de cada vértice:
C++
// C++ program to demonstrate distance to
// nearest source problem using BFS
// from each vertex
#include <bits/stdc++.h>
using namespace std;
#define N 100000 + 1
#define inf 1000000
// This array stores the distances of the
// vertices from the nearest source
int dist[N];
// a hash array where source[i] = 1
// means vertex i is a source
int source[N];
// The BFS Queue
// The pairs are of the form (vertex, distance
// from current source)
deque<pair<int, int> > BFSQueue;
// visited array for remembering visited vertices
int visited[N];
// The BFS function
void BFS(vector<int> graph[], int start)
{
// clearing the queue
while (!BFSQueue.empty())
BFSQueue.pop_back();
// push_back starting vertices
BFSQueue.push_back({ start, 0 });
while (!BFSQueue.empty()) {
int s = BFSQueue.front().first;
int d = BFSQueue.front().second;
visited[s] = 1;
BFSQueue.pop_front();
// stop at the first source we reach during BFS
if (source[s] == 1) {
dist[start] = d;
return;
}
// Pushing the adjacent unvisited vertices
// with distance from current source = this
// vertex's distance + 1
for (int i = 0; i < graph[s].size(); i++)
if (visited[graph[s][i]] == 0)
BFSQueue.push_back({ graph[s][i], d + 1 });
}
}
// This function calculates the distance of each
// vertex from nearest source
void nearestTown(vector<int> graph[], int n,
int sources[], int S)
{
// reseting the source hash array
for (int i = 1; i <= n; i++)
source[i] = 0;
for (int i = 0; i <= S - 1; i++)
source[sources[i]] = 1;
// loop through all the vertices and run
// a BFS from each vertex to find the distance
// to nearest town from it
for (int i = 1; i <= n; i++) {
for (int i = 1; i <= n; i++)
visited[i] = 0;
BFS(graph, i);
}
// Printing the distances
for (int i = 1; i <= n; i++)
cout << i << " " << dist[i] << endl;
}
void addEdge(vector<int> graph[], int u, int v)
{
graph[u].push_back(v);
graph[v].push_back(u);
}
// Driver Code
int main()
{ // Number of vertices
int n = 6;
vector<int> graph[n + 1];
// Edges
addEdge(graph, 1, 2);
addEdge(graph, 1, 6);
addEdge(graph, 2, 6);
addEdge(graph, 2, 3);
addEdge(graph, 3, 6);
addEdge(graph, 5, 4);
addEdge(graph, 6, 5);
addEdge(graph, 3, 4);
addEdge(graph, 5, 3);
// Sources
int sources[] = { 1, 5 };
int S = sizeof(sources) / sizeof(sources[0]);
nearestTown(graph, n, sources, S);
return 0;
}
Java
// Java program to demonstrate distance to
// nearest source problem using BFS
// from each vertex
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
class Pair
{
int first, second;
public Pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
class GFG{
static final int N = 100000 + 1;
static final int inf = 1000000;
// This array stores the distances of the
// vertices from the nearest source
static int[] dist = new int[N];
// a hash array where source[i] = 1
// means vertex i is a source
static int[] source = new int[N];
// The BFS Queue
// The pairs are of the form (vertex, distance
// from current source)
static Deque<Pair> BFSQueue = new LinkedList<>();
// deque<pair<int, int> > BFSQueue;
// visited array for remembering visited vertices
static int[] visited = new int[N];
// The BFS function
static void BFS(ArrayList<Integer>[] graph, int start)
{
// Clearing the queue
while (!BFSQueue.isEmpty())
BFSQueue.removeLast();
// push_back starting vertices
BFSQueue.add(new Pair(start, 0));
while (!BFSQueue.isEmpty())
{
int s = BFSQueue.peekFirst().first;
int d = BFSQueue.peekFirst().second;
visited[s] = 1;
BFSQueue.removeFirst();
// Stop at the first source
// we reach during BFS
if (source[s] == 1)
{
dist[start] = d;
return;
}
// Pushing the adjacent unvisited vertices
// with distance from current source = this
// vertex's distance + 1
for(int i = 0; i < graph[s].size(); i++)
if (visited[graph[s].get(i)] == 0)
BFSQueue.add(new Pair(
graph[s].get(i), d + 1));
}
}
// This function calculates the distance of each
// vertex from nearest source
static void nearestTown(ArrayList<Integer>[] graph,
int n, int sources[], int S)
{
// Reseting the source hash array
for(int i = 1; i <= n; i++)
source[i] = 0;
for(int i = 0; i <= S - 1; i++)
source[sources[i]] = 1;
// Loop through all the vertices and run
// a BFS from each vertex to find the distance
// to nearest town from it
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
visited[j] = 0;
BFS(graph, i);
}
// Printing the distances
for(int i = 1; i <= n; i++)
System.out.println(i + " " + dist[i]);
}
static void addEdge(ArrayList<Integer>[] graph,
int u, int v)
{
graph[u].add(v);
graph[v].add(u);
}
// Driver Code
public static void main(String[] args)
{
// Number of vertices
int n = 6;
@SuppressWarnings("unchecked")
ArrayList<Integer>[] graph = new ArrayList[n + 1];
Arrays.fill(graph, new ArrayList<>());
// Edges
addEdge(graph, 1, 2);
addEdge(graph, 1, 6);
addEdge(graph, 2, 6);
addEdge(graph, 2, 3);
addEdge(graph, 3, 6);
addEdge(graph, 5, 4);
addEdge(graph, 6, 5);
addEdge(graph, 3, 4);
addEdge(graph, 5, 3);
// Sources
int sources[] = { 1, 5 };
int S = sources.length;
nearestTown(graph, n, sources, S);
}
}
// This code is contributed by sanjeev2552
Python3
# Python3 program to demonstrate distance to
# nearest source problem using BFS
# from each vertex
N = 100001
inf = 1000000
# This array stores the distances of the
# vertices from the nearest source
dist = [0 for i in range(N)];
# a hash array where source[i] = 1
# means vertex i is a source
source = [0 for i in range(N)];
# The BFS Queue
# The pairs are of the form (vertex, distance
# from current source)
BFSQueue = []
# visited array for remembering visited vertices
visited = [0 for i in range(N)];
# The BFS function
def BFS(graph, start):
# clearing the queue
while (len(BFSQueue) != 0):
BFSQueue.pop();
# append starting vertices
BFSQueue.append([ start, 0 ]);
while (len(BFSQueue) != 0):
s = BFSQueue[0][0];
d = BFSQueue[0][1];
visited[s] = 1;
BFSQueue.pop(0);
# stop at the first source we reach during BFS
if (source[s] == 1):
dist[start] = d;
return;
# Pushing the adjacent unvisited vertices
# with distance from current source = this
# vertex's distance + 1
for i in range(len(graph[s])):
if (visited[graph[s][i]] == 0):
BFSQueue.append([ graph[s][i], d + 1 ]);
# This function calculates the distance of each
# vertex from nearest source
def nearestTown(graph, n, sources, S):
global source, dist
# reseting the source hash array
for i in range(1, n + 1):
source[i] = 0;
for i in range(S):
source[sources[i]] = 1;
# loop through all the vertices and run
# a BFS from each vertex to find the distance
# to nearest town from it
for i in range(1, n + 1):
for j in range(1, n + 1):
visited[j] = 0;
BFS(graph, i);
# Printing the distances
for i in range(1, n + 1):
print('{} {}'.format(i,dist[i]))
def addEdge(graph, u, v):
graph[u].append(v);
graph[v].append(u);
# Driver Code
if __name__=='__main__':
# Number of vertices
n = 6
graph = [[] for i in range(n + 1)];
# Edges
addEdge(graph, 1, 2);
addEdge(graph, 1, 6);
addEdge(graph, 2, 6);
addEdge(graph, 2, 3);
addEdge(graph, 3, 6);
addEdge(graph, 5, 4);
addEdge(graph, 6, 5);
addEdge(graph, 3, 4);
addEdge(graph, 5, 3);
# Sources
sources = [ 1, 5 ]
S = len(sources)
nearestTown(graph, n, sources, S);
# This code is contributed by rutvik_56
C#
// C# program to demonstrate distance to
// nearest source problem using BFS
// from each vertex
using System;
using System.Collections.Generic;
class GFG {
static int N = 100000 + 1;
// This array stores the distances of the
// vertices from the nearest source
static int[] dist = new int[N];
// a hash array where source[i] = 1
// means vertex i is a source
static int[] source = new int[N];
// The BFS Queue
// The pairs are of the form (vertex, distance
// from current source)
static List<Tuple<int,int>> BFSQueue = new List<Tuple<int,int>>();
// deque<pair<int, int> > BFSQueue;
// visited array for remembering visited vertices
static int[] visited = new int[N];
// The BFS function
static void BFS(List<List<int>> graph, int start)
{
// Clearing the queue
while (BFSQueue.Count > 0)
BFSQueue.RemoveAt(BFSQueue.Count - 1);
// push_back starting vertices
BFSQueue.Add(new Tuple<int,int>(start, 0));
while (BFSQueue.Count > 0)
{
int s = BFSQueue[0].Item1;
int d = BFSQueue[0].Item2;
visited[s] = 1;
BFSQueue.RemoveAt(0);
// Stop at the first source
// we reach during BFS
if (source[s] == 1)
{
dist[start] = d;
return;
}
// Pushing the adjacent unvisited vertices
// with distance from current source = this
// vertex's distance + 1
for(int i = 0; i < graph[s].Count; i++)
if (visited[graph[s][i]] == 0)
BFSQueue.Add(new Tuple<int,int>(
graph[s][i], d + 1));
}
}
// This function calculates the distance of each
// vertex from nearest source
static void nearestTown(List<List<int>> graph, int n, int[] sources, int S)
{
// Reseting the source hash array
for(int i = 1; i <= n; i++)
source[i] = 0;
for(int i = 0; i <= S - 1; i++)
source[sources[i]] = 1;
// Loop through all the vertices and run
// a BFS from each vertex to find the distance
// to nearest town from it
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
visited[j] = 0;
BFS(graph, i);
}
// Printing the distances
for(int i = 1; i <= n; i++)
Console.WriteLine(i + " " + dist[i]);
}
static void addEdge(List<List<int>> graph, int u, int v)
{
graph[u].Add(v);
graph[v].Add(u);
}
static void Main() {
// Number of vertices
int n = 6;
List<List<int>> graph = new List<List<int>>();
for(int i = 0; i < n + 1; i++)
{
graph.Add(new List<int>());
}
// Edges
addEdge(graph, 1, 2);
addEdge(graph, 1, 6);
addEdge(graph, 2, 6);
addEdge(graph, 2, 3);
addEdge(graph, 3, 6);
addEdge(graph, 5, 4);
addEdge(graph, 6, 5);
addEdge(graph, 3, 4);
addEdge(graph, 5, 3);
// Sources
int[] sources = { 1, 5 };
int S = sources.Length;
nearestTown(graph, n, sources, S);
}
}
// This code is contributed by divyeshrabadiya07.
Javascript
<script>
// Javascript program to demonstrate distance to
// nearest source problem using BFS
// from each vertex
let N = 100000 + 1;
// This array stores the distances of the
// vertices from the nearest source
let dist = new Array(N);
// a hash array where source[i] = 1
// means vertex i is a source
let source = new Array(N);
// The BFS Queue
// The pairs are of the form (vertex, distance
// from current source)
let BFSQueue = [];
// deque<pair<int, int> > BFSQueue;
// visited array for remembering visited vertices
let visited = new Array(N);
// The BFS function
function BFS(graph, start)
{
// Clearing the queue
while (BFSQueue.length > 0)
BFSQueue.pop();
// push_back starting vertices
BFSQueue.push([start, 0]);
while (BFSQueue.length > 0)
{
let s = BFSQueue[0][0];
let d = BFSQueue[0][1];
visited[s] = 1;
BFSQueue.shift();
// Stop at the first source
// we reach during BFS
if (source[s] == 1)
{
dist[start] = d;
return;
}
// Pushing the adjacent unvisited vertices
// with distance from current source = this
// vertex's distance + 1
for(let i = 0; i < graph[s].length; i++)
if (visited[graph[s][i]] == 0)
BFSQueue.push([graph[s][i], d + 1]);
}
}
// This function calculates the distance of each
// vertex from nearest source
function nearestTown(graph, n, sources, S)
{
// Reseting the source hash array
for(let i = 1; i <= n; i++)
source[i] = 0;
for(let i = 0; i <= S - 1; i++)
source[sources[i]] = 1;
// Loop through all the vertices and run
// a BFS from each vertex to find the distance
// to nearest town from it
for(let i = 1; i <= n; i++)
{
for(let j = 1; j <= n; j++)
visited[j] = 0;
BFS(graph, i);
}
// Printing the distances
for(let i = 1; i <= n; i++)
document.write(i + " " + dist[i] + "</br>");
}
function addEdge(graph, u, v)
{
graph[u].push(v);
graph[v].push(u);
}
// Number of vertices
let n = 6;
let graph = [];
for(let i = 0; i < n + 1; i++)
{
graph.push([]);
}
// Edges
addEdge(graph, 1, 2);
addEdge(graph, 1, 6);
addEdge(graph, 2, 6);
addEdge(graph, 2, 3);
addEdge(graph, 3, 6);
addEdge(graph, 5, 4);
addEdge(graph, 6, 5);
addEdge(graph, 3, 4);
addEdge(graph, 5, 3);
// Sources
let sources = [ 1, 5 ];
let S = sources.length;
nearestTown(graph, n, sources, S);
// This code is contributed by mukesh07.
</script>
Producción:
1 0 2 1 3 1 4 1 5 0 6 1
Tiempo Complejidad: O(VE)
Espacio Auxiliar: O(V)
Método eficiente Un mejor método es utilizar el algoritmo de Djikstra de forma modificada. Consideremos una de las fuentes como la fuente original y las otras fuentes como vértices con caminos de costo 0 desde la fuente original. Por lo tanto, empujamos todas las fuentes a Djikstra Queue con distancia = 0, y el resto de los vértices con distancia = infinito. La distancia mínima de cada vértice desde la fuente original ahora calculada usando el Algoritmo de Dijkstra ahora son esencialmente las distancias desde la fuente más cercana.
Explicación: la implementación de C++ utiliza un conjunto de pares (distancia desde el origen, vértice) ordenados según la distancia desde el origen. Inicialmente, el conjunto contiene las fuentes con distancia = 0 y todos los demás vértices con distancia = infinito.
En cada paso, iremos al vértice con distancia mínima (d) desde la fuente, es decir, el primer elemento del conjunto (la propia fuente en el primer paso con distancia = 0). Pasamos por todos sus vértices adyacentes y si la distancia de cualquier vértice es > d + 1 reemplazamos su entrada en el conjunto con la nueva distancia. Luego eliminamos el vértice actual del conjunto. Continuamos esto hasta que el conjunto esté vacío.
La idea es que no puede haber un camino más corto al vértice en la parte delantera del conjunto que el actual, ya que cualquier otro camino será la suma de un camino más largo (>= su longitud) y una longitud de camino no negativa (a menos que están considerando bordes negativos).
Dado que todas las fuentes tienen una distancia = 0, al principio, los vértices adyacentes que no son fuente obtendrán una distancia = 1. Todos los vértices obtendrán distancia = distancia desde su fuente más cercana.
Implementación del Enfoque Eficiente:
C++
// C++ program to demonstrate
// multi-source BFS
#include <bits/stdc++.h>
using namespace std;
#define N 100000 + 1
#define inf 1000000
// This array stores the distances of the vertices
// from the nearest source
int dist[N];
// This Set contains the vertices not yet visited in
// increasing order of distance from the nearest source
// calculated till now
set<pair<int, int> > Q;
// Util function for Multi-Source BFS
void multiSourceBFSUtil(vector<int> graph[], int s)
{
set<pair<int, int> >::iterator it;
int i;
for (i = 0; i < graph[s].size(); i++) {
int v = graph[s][i];
if (dist[s] + 1 < dist[v]) {
// If a shorter path to a vertex is
// found than the currently stored
// distance replace it in the Q
it = Q.find({ dist[v], v });
Q.erase(it);
dist[v] = dist[s] + 1;
Q.insert({ dist[v], v });
}
}
// Stop when the Q is empty -> All
// vertices have been visited. And we only
// visit a vertex when we are sure that a
// shorter path to that vertex is not
// possible
if (Q.size() == 0)
return;
// Go to the first vertex in Q
// and remove it from the Q
it = Q.begin();
int next = it->second;
Q.erase(it);
multiSourceBFSUtil(graph, next);
}
// This function calculates the distance of
// each vertex from nearest source
void multiSourceBFS(vector<int> graph[], int n,
int sources[], int S)
{
// a hash array where source[i] = 1
// means vertex i is a source
int source[n + 1];
for (int i = 1; i <= n; i++)
source[i] = 0;
for (int i = 0; i <= S - 1; i++)
source[sources[i]] = 1;
for (int i = 1; i <= n; i++) {
if (source[i]) {
dist[i] = 0;
Q.insert({ 0, i });
}
else {
dist[i] = inf;
Q.insert({ inf, i });
}
}
set<pair<int, int> >::iterator itr;
// Get the vertex with lowest distance,
itr = Q.begin();
// currently one of the sources with distance = 0
int start = itr->second;
multiSourceBFSUtil(graph, start);
// Printing the distances
for (int i = 1; i <= n; i++)
cout << i << " " << dist[i] << endl;
}
void addEdge(vector<int> graph[], int u, int v)
{
graph[u].push_back(v);
graph[v].push_back(u);
}
// Driver Code
int main()
{
// Number of vertices
int n = 6;
vector<int> graph[n + 1];
// Edges
addEdge(graph, 1, 2);
addEdge(graph, 1, 6);
addEdge(graph, 2, 6);
addEdge(graph, 2, 3);
addEdge(graph, 3, 6);
addEdge(graph, 5, 4);
addEdge(graph, 6, 5);
addEdge(graph, 3, 4);
addEdge(graph, 5, 3);
// Sources
int sources[] = { 1, 5 };
int S = sizeof(sources) / sizeof(sources[0]);
multiSourceBFS(graph, n, sources, S);
return 0;
}
Python3
# Python3 program to demonstrate # multi-source BFS import math N=100000 + 1 inf=1000000 # This array stores the distances of the vertices # from the nearest source inf = math.inf dist=[inf]*N # This Set contains the vertices not yet visited in # increasing order of distance from the nearest source # calculated till now Q=set() # Util function for Multi-Source BFS def multiSourceBFSUtil(graph, s): for i in range(len(graph[s])): v = graph[s][i] if (dist[s] + 1 < dist[v]) : # If a shorter path to a vertex is # found than the currently stored # distance replace it in the Q if (dist[v],v) in Q: Q.remove((dist[v],v)) dist[v] = dist[s] + 1 Q.add((dist[v], v)) # Stop when the Q is empty . All # vertices have been visited. And we only # visit a vertex when we are sure that a # shorter path to that vertex is not # possible if (len(Q) == 0): return # Go to the first vertex in Q # and remove it from the Q it = min(Q) next=it[1] Q.remove(it) multiSourceBFSUtil(graph, next) # This function calculates the distance of # each vertex from nearest source def multiSourceBFS(graph, n, sources, S): # a hash array where source[i] = 1 # means vertex i is a source source=[0]*(n + 1) for i in range(0,S): source[sources[i]] = 1 for i in range(1,n): if (source[i]) : dist[i] = 0 Q.add((0, i)) else : dist[i] = math.inf Q.add((math.inf, i)) # Get the vertex with lowest distance, itr = min(Q) start=itr[1] Q.remove(itr) multiSourceBFSUtil(graph, start) # Print the distances for i in range(1,n+1): print(i,dist[i]) def addEdge(graph, u, v): graph[u].append(v) graph[v].append(u) # Driver Code if __name__ == '__main__': # Number of vertices n = 6 graph=[[] for _ in range(n+1)] # Edges addEdge(graph, 1, 2) addEdge(graph, 1, 6) addEdge(graph, 2, 6) addEdge(graph, 2, 3) addEdge(graph, 3, 6) addEdge(graph, 5, 4) addEdge(graph, 6, 5) addEdge(graph, 3, 4) addEdge(graph, 5, 3) # Sources sources = (1, 5) S = len(sources) multiSourceBFS(graph, n, sources, S)
Producción:
1 0 2 1 3 1 4 1 5 0 6 1
Complejidad de tiempo : O(E.logV)
Espacio auxiliar: O(V)
Enfoque más eficiente : Un método aún mejor es utilizar el BFS multifuente, que es una modificación de BFS. Pondremos todos los vértices de origen en la cola al principio en lugar que un solo vértice que era en el caso de BFS estándar. De esta manera, Multisource BFS primero visitará todos los vértices de origen. Después de eso, visitará los vértices que están a una distancia de 1 de todos los vértices de origen, luego a una distancia de 2 de todos los vértices de origen y así sucesivamente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to demonstrate Multi-source BFS
#include<bits/stdc++.h>
using namespace std;
#define N 1000000
// This array stores the distances of the vertices
// from the nearest source
int dist[N];
//This boolean array is true if the current vertex
// is visited otherwise it is false
bool visited[N];
void addEdge(vector<int> graph[], int u, int v)
{
//Function to add 2 edges in an undirected graph
graph[u].push_back(v);
graph[v].push_back(u);
}
// Multisource BFS Function
void Multisource_BFS(vector<int> graph[],queue<int>q)
{
while(!q.empty())
{
int k = q.front();
q.pop();
for(auto i:graph[k])
{
if(!visited[i])
{
// Pushing the adjacent unvisited vertices
// with distance from current source = this
// vertex's distance + 1
q.push(i);
dist[i] = dist[k] + 1;
visited[i] = true;
}
}
}
}
// This function calculates the distance of each
// vertex from nearest source
void nearestTown(vector<int> graph[],int n,int sources[],int s)
{
//Create a queue for BFS
queue<int> q;
//Mark all the source vertices as visited and enqueue it
for(int i = 0;i < s; i++)
{
q.push(sources[i]);
visited[sources[i]]=true;
}
Multisource_BFS(graph,q);
//Printing the distances
for(int i = 1; i <= n; i++)
{
cout<< i << " " << dist[i] << endl;
}
}
// Driver code
int main()
{
// Number of vertices
int n = 6;
vector<int> graph[n + 1];
// Edges
addEdge(graph, 1, 2);
addEdge(graph, 1, 6);
addEdge(graph, 2, 6);
addEdge(graph, 2, 3);
addEdge(graph, 3, 6);
addEdge(graph, 5, 4);
addEdge(graph, 6, 5);
addEdge(graph, 3, 4);
addEdge(graph, 5, 3);
// Sources
int sources[] = { 1, 5 };
int S = sizeof(sources) / sizeof(sources[0]);
nearestTown(graph, n, sources, S);
return 0;
}
Java
// Java program to demonstrate Multi-source BFS
import java.util.*;
import java.math.*;
class GFG{
static int N = 1000000;
// This array stores the distances of the vertices
// from the nearest source
static int dist[] = new int[N];
//This boolean array is true if the current vertex
// is visited otherwise it is false
static boolean visited[] = new boolean[N];
static void addEdge(ArrayList<Integer> graph[],
int u, int v)
{
// Function to add 2 edges in an undirected graph
graph[u].add(v);
graph[v].add(u);
}
// Multisource BFS Function
static void Multisource_BFS(ArrayList<Integer> graph[],
Queue<Integer>q)
{
while (!q.isEmpty())
{
int k = q.peek();
q.poll();
for(int i:graph[k])
{
if (!visited[i])
{
// Pushing the adjacent unvisited vertices
// with distance from current source = this
// vertex's distance + 1
q.add(i);
dist[i] = dist[k] + 1;
visited[i] = true;
}
}
}
}
// This function calculates the distance of each
// vertex from nearest source
static void nearestTown(ArrayList<Integer> graph[],
int n, int sources[], int s)
{
// Create a queue for BFS
Queue<Integer> q=new LinkedList<>();
// Mark all the source vertices as
// visited and enqueue it
for(int i = 0;i < s; i++)
{
q.add(sources[i]);
visited[sources[i]] = true;
}
Multisource_BFS(graph, q);
// Printing the distances
for(int i = 1; i <= n; i++)
{
System.out.println(i + " " + dist[i]);
}
}
// Driver code
public static void main(String args[])
{
// Number of vertices
int n = 6;
@SuppressWarnings("unchecked")
ArrayList<Integer> graph[] = new ArrayList[N + 1];
for(int i = 0; i < graph.length; i++)
graph[i] = new ArrayList<Integer>();
// Edges
addEdge(graph, 1, 2);
addEdge(graph, 1, 6);
addEdge(graph, 2, 6);
addEdge(graph, 2, 3);
addEdge(graph, 3, 6);
addEdge(graph, 5, 4);
addEdge(graph, 6, 5);
addEdge(graph, 3, 4);
addEdge(graph, 5, 3);
// Sources
int sources[] = { 1, 5 };
int S = sources.length;
nearestTown(graph, n, sources, S);
}
}
// This code is contributed by Debojyoti Mandal
Python3
# Python3 program to demonstrate Multi-source BFS N = 1000000 # This array stores the distances of the vertices # from the nearest source dist = [0]*(N) # This boolean array is true if the current vertex # is visited otherwise it is false visited = [False]*(N) def addEdge(graph, u, v): # Function to add 2 edges in an undirected graph graph[u].append(v); graph[v].append(u) # Multisource BFS Function def Multisource_BFS(graph, q): while(len(q) > 0): k = q[0] q.pop(0) for i in range(len(graph[k])): if not visited[graph[k][i]]: # Pushing the adjacent unvisited vertices # with distance from current source = this # vertex's distance + 1 q.append(graph[k][i]) dist[graph[k][i]] = dist[k] + 1 visited[graph[k][i]] = True # This function calculates the distance of each # vertex from nearest source def nearestTown(graph, n, sources, s): # Create a queue for BFS q = [] # Mark all the source vertices as visited and enqueue it for i in range(s): q.append(sources[i]) visited[sources[i]]=True Multisource_BFS(graph,q) # Printing the distances for i in range(1, n + 1): print(i, " ", dist[i], sep = "") # Number of vertices n = 6 graph = [] for i in range(n + 1): graph.append([]) # Edges addEdge(graph, 1, 2) addEdge(graph, 1, 6) addEdge(graph, 2, 6) addEdge(graph, 2, 3) addEdge(graph, 3, 6) addEdge(graph, 5, 4) addEdge(graph, 6, 5) addEdge(graph, 3, 4) addEdge(graph, 5, 3) # Sources sources = [ 1, 5 ] S = len(sources) nearestTown(graph, n, sources, S) # This code is contributed by rameshtravel07.
C#
// C# program to demonstrate Multi-source BFS
using System;
using System.Collections.Generic;
class GFG {
static int N = 1000000;
// This array stores the distances of the vertices
// from the nearest source
static int[] dist = new int[N];
//This boolean array is true if the current vertex
// is visited otherwise it is false
static bool[] visited = new bool[N];
static void addEdge(List<List<int>> graph, int u, int v)
{
// Function to add 2 edges in an undirected graph
graph[u].Add(v);
graph[v].Add(u);
}
// Multisource BFS Function
static void Multisource_BFS(List<List<int>> graph, List<int> q)
{
while (q.Count > 0)
{
int k = q[0];
q.RemoveAt(0);
foreach(int i in graph[k])
{
if (!visited[i])
{
// Pushing the adjacent unvisited vertices
// with distance from current source = this
// vertex's distance + 1
q.Add(i);
dist[i] = dist[k] + 1;
visited[i] = true;
}
}
}
}
// This function calculates the distance of each
// vertex from nearest source
static void nearestTown(List<List<int>> graph, int n, int[] sources, int s)
{
// Create a queue for BFS
List<int> q = new List<int>();
// Mark all the source vertices as
// visited and enqueue it
for(int i = 0;i < s; i++)
{
q.Add(sources[i]);
visited[sources[i]] = true;
}
Multisource_BFS(graph, q);
// Printing the distances
for(int i = 1; i <= n; i++)
{
Console.WriteLine(i + " " + dist[i]);
}
}
static void Main() {
// Number of vertices
int n = 6;
List<List<int>> graph = new List<List<int>>();
for(int i = 0; i < N + 1; i++)
graph.Add(new List<int>());
// Edges
addEdge(graph, 1, 2);
addEdge(graph, 1, 6);
addEdge(graph, 2, 6);
addEdge(graph, 2, 3);
addEdge(graph, 3, 6);
addEdge(graph, 5, 4);
addEdge(graph, 6, 5);
addEdge(graph, 3, 4);
addEdge(graph, 5, 3);
// Sources
int[] sources = { 1, 5 };
int S = sources.Length;
nearestTown(graph, n, sources, S);
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// Javascript program to demonstrate Multi-source BFS
let N = 1000000;
// This array stores the distances of the vertices
// from the nearest source
let dist = new Array(N);
dist.fill(0);
// This boolean array is true if the current vertex
// is visited otherwise it is false
let visited = new Array(N);
visited.fill(false);
function addEdge(graph, u, v)
{
// Function to add 2 edges in an undirected graph
graph[u].push(v);
graph[v].push(u);
}
// Multisource BFS Function
function Multisource_BFS(graph, q)
{
while(q.length > 0)
{
let k = q[0];
q.shift();
for(let i = 0; i < graph[k].length; i++)
{
if(!visited[graph[k][i]])
{
// Pushing the adjacent unvisited vertices
// with distance from current source = this
// vertex's distance + 1
q.push(graph[k][i]);
dist[graph[k][i]] = dist[k] + 1;
visited[graph[k][i]] = true;
}
}
}
}
// This function calculates the distance of each
// vertex from nearest source
function nearestTown(graph, n, sources, s)
{
// Create a queue for BFS
let q = [];
// Mark all the source vertices as visited and enqueue it
for(let i = 0;i < s; i++)
{
q.push(sources[i]);
visited[sources[i]]=true;
}
Multisource_BFS(graph,q);
// Printing the distances
for(let i = 1; i <= n; i++)
{
document.write(i + " " + dist[i] + "</br>");
}
}
// Number of vertices
let n = 6;
let graph = [];
for(let i = 0; i < n + 1; i++)
{
graph.push([]);
}
// Edges
addEdge(graph, 1, 2);
addEdge(graph, 1, 6);
addEdge(graph, 2, 6);
addEdge(graph, 2, 3);
addEdge(graph, 3, 6);
addEdge(graph, 5, 4);
addEdge(graph, 6, 5);
addEdge(graph, 3, 4);
addEdge(graph, 5, 3);
// Sources
let sources = [ 1, 5 ];
let S = sources.length;
nearestTown(graph, n, sources, S);
// This code is contributed by decode2207.
</script>
Producción:
1 0 2 1 3 1 4 1 5 0 6 1
Complejidad temporal : O(V+E)
Espacio auxiliar: O(V)
Publicación traducida automáticamente
Artículo escrito por narutouzumaki696 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA