假设有n个城镇由m条双向道路连接。其中有许多城镇设有警察局。我们想知道每个城镇离最近的警察局的距离。如果城镇本身有一个，则距离为0。
null
例子：
Input : Number of Vertices = 6Number of Edges = 9Towns with Police Station : 1, 5Edges:1 21 62 62 33 65 46 53 45 3
![图片[1]-无权图中的多源最短路径-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_Graph_for_multi_sorce_bfs-1-300x166.png)
Output :1 02 13 14 15 06 1
天真的方法： 我们可以在顶点之间循环，从每个顶点运行BFS，从该顶点找到最近的城镇和警察局。这需要O（V.E）。
使用每个顶点的BFS实现简单方法：
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> |
输出：
1 02 13 14 15 06 1
时间复杂性： O（副总裁） 辅助空间： O（V）
有效方法 更好的方法是使用 Djikstra算法 以一种改良的方式。让我们考虑一个源作为原始源和其他源为顶点，从原始源具有0个代价路径。因此，我们将所有源推到距离为0的Djikstra队列中，并将其余顶点推到距离为无穷大的队列中。现在使用Dijkstra算法计算的每个顶点到原始源的最小距离，实际上是到最近源的距离。
说明： C++实现使用 设置 属于 对 （与源的距离，顶点）根据与源的距离排序。最初，该集合包含距离为0的源和距离为无穷大的所有其他顶点。 在每一步中，我们都会到达距离震源最小的顶点，即集合的第一个元素（第一步中距离为0的震源本身）。我们遍历它的所有相邻顶点，如果任何顶点的距离大于d+1，我们用新的距离替换它在集合中的条目。然后我们从集合中移除当前顶点。我们继续这个过程，直到集合为空。 其思想是，到集合前面顶点的路径不能比当前路径短，因为任何其他路径都是较长路径（>=其长度）和非负路径长度（除非我们考虑负边）的总和。 由于所有源的距离都为0，因此在开始时，相邻的非源顶点的距离将为1。所有顶点将获得距离=距离最近的源的距离。
有效方法的实施：
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) |
输出：
1 02 13 14 15 06 1
时间复杂性 : O（E.logV） 辅助空间： O（V） 更有效的方法 ：更好的方法是使用多源BFS，这是BFS的一种改进。我们将首先将所有源顶点放入队列，而不是标准BFS中的单个顶点。这样，多源BFS将首先访问所有源顶点。之后，它将访问距离所有源顶点1的顶点，然后访问距离所有源顶点2的顶点，依此类推。
以下是上述方法的实施情况：
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> |
输出：
1 02 13 14 15 06 1
时间复杂性 : O（V+E） 辅助空间： O（V）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
