최소 제품 스패닝 트리
연결되고 방향이 지정되지 않은 그래프가 주어지면 해당 그래프의 스패닝 트리는 트리인 하위 그래프이며 모든 정점을 함께 연결합니다. 단일 그래프에는 다양한 스패닝 트리가 있을 수 있습니다. 가중치 연결 및 무방향 그래프에 대한 최소 곱 신장 트리는 다른 모든 신장 트리의 가중치 곱보다 작거나 같은 가중치 곱을 갖는 신장 트리입니다. 스패닝 트리의 가중치 곱은 스패닝 트리의 각 모서리에 해당하는 가중치의 곱입니다. 주어진 그래프의 모든 가중치는 단순화를 위해 양수입니다.
예:
Minimum Product that we can obtain is 180 for above graph by choosing edges 0-1 1-2 0-3 and 1-4
이 문제는 Kruskal( https://www.geeksforgeeks.org/dsa/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/ )그리고 꼼꼼한 의 알고리즘을 사용하지만 이러한 알고리즘을 사용하려면 그래프를 수정해야 합니다. 최소 스패닝 트리 알고리즘은 여기서 가중치의 총합을 최소화하려고 시도합니다. 여기서 가중치의 총 곱을 최소화해야 합니다. 우리는 다음의 속성을 사용할 수 있습니다. 로그 이 문제를 극복하기 위해.
우리가 알고 있듯이
log(w1* w2 * w3 * …. * wN) = log(w1) + log(w2) + log(w3) ….. + log(wN)
그래프의 각 가중치를 로그 값으로 대체한 다음 log(wi)의 합을 최소화하여 가중치 곱을 최소화하는 최소 스패닝 트리 알고리즘을 적용합니다.
예를 들어 그래프 단계는 다이어그램 아래에 표시됩니다.
아래 코드에서는 먼저 주어진 입력 그래프에서 로그 그래프를 구성한 다음 해당 그래프가 트리의 총 가중치 합계를 최소화하는 prim의 MST 알고리즘에 대한 입력으로 제공됩니다. 수정된 그래프의 가중치는 실제 입력 그래프의 로그이므로 실제로 스패닝 트리의 가중치 곱을 최소화합니다.
// A C++ program for getting minimum product // spanning tree The program is for adjacency matrix // representation of the graph #include // Number of vertices in the graph #define V 5 // A utility function to find the vertex with minimum // key value from the set of vertices not yet included // in MST int minKey ( int key [] bool mstSet []) { // Initialize min value int min = INT_MAX min_index ; for ( int v = 0 ; v < V ; v ++ ) if ( mstSet [ v ] == false && key [ v ] < min ) min = key [ v ] min_index = v ; return min_index ; } // A utility function to print the constructed MST // stored in parent[] and print Minimum Obtainable // product int printMST ( int parent [] int n int graph [ V ][ V ]) { printf ( 'Edge Weight n ' ); int minProduct = 1 ; for ( int i = 1 ; i < V ; i ++ ) { printf ( '%d - %d %d n ' parent [ i ] i graph [ i ][ parent [ i ]]); minProduct *= graph [ i ][ parent [ i ]]; } printf ( 'Minimum Obtainable product is %d n ' minProduct ); } // Function to construct and print MST for a graph // represented using adjacency matrix representation // inputGraph is sent for printing actual edges and // logGraph is sent for actual MST operations void primMST ( int inputGraph [ V ][ V ] double logGraph [ V ][ V ]) { int parent [ V ]; // Array to store constructed MST int key [ V ]; // Key values used to pick minimum // weight edge in cut bool mstSet [ V ]; // To represent set of vertices not // yet included in MST // Initialize all keys as INFINITE for ( int i = 0 ; i < V ; i ++ ) key [ i ] = INT_MAX mstSet [ i ] = false ; // Always include first 1st vertex in MST. key [ 0 ] = 0 ; // Make key 0 so that this vertex is // picked as first vertex parent [ 0 ] = -1 ; // First node is always root of MST // The MST will have V vertices for ( int count = 0 ; count < V - 1 ; count ++ ) { // Pick the minimum key vertex from the set of // vertices not yet included in MST int u = minKey ( key mstSet ); // Add the picked vertex to the MST Set mstSet [ u ] = true ; // Update key value and parent index of the // adjacent vertices of the picked vertex. // Consider only those vertices which are not yet // included in MST for ( int v = 0 ; v < V ; v ++ ) // logGraph[u][v] is non zero only for // adjacent vertices of m mstSet[v] is false // for vertices not yet included in MST // Update the key only if logGraph[u][v] is // smaller than key[v] if ( logGraph [ u ][ v ] > 0 && mstSet [ v ] == false && logGraph [ u ][ v ] < key [ v ]) parent [ v ] = u key [ v ] = logGraph [ u ][ v ]; } // print the constructed MST printMST ( parent V inputGraph ); } // Method to get minimum product spanning tree void minimumProductMST ( int graph [ V ][ V ]) { double logGraph [ V ][ V ]; // Constructing logGraph from original graph for ( int i = 0 ; i < V ; i ++ ) { for ( int j = 0 ; j < V ; j ++ ) { if ( graph [ i ][ j ] > 0 ) logGraph [ i ][ j ] = log ( graph [ i ][ j ]); else logGraph [ i ][ j ] = 0 ; } } // Applying standard Prim's MST algorithm on // Log graph. primMST ( graph logGraph ); } // driver program to test above function int main () { /* Let us create the following graph 2 3 (0)--(1)--(2) | / | 6| 8/ 5 |7 | / | (3)-------(4) 9 */ int graph [ V ][ V ] = { { 0 2 0 6 0 } { 2 0 3 8 5 } { 0 3 0 0 7 } { 6 8 0 0 9 } { 0 5 7 9 0 } }; // Print the solution minimumProductMST ( graph ); return 0 ; }
Java // A Java program for getting minimum product // spanning tree The program is for adjacency matrix // representation of the graph import java.util.* ; class GFG { // Number of vertices in the graph static int V = 5 ; // A utility function to find the vertex with minimum // key value from the set of vertices not yet included // in MST static int minKey ( int key [] boolean [] mstSet ) { // Initialize min value int min = Integer . MAX_VALUE min_index = 0 ; for ( int v = 0 ; v < V ; v ++ ) { if ( mstSet [ v ] == false && key [ v ] < min ) { min = key [ v ] ; min_index = v ; } } return min_index ; } // A utility function to print the constructed MST // stored in parent[] and print Minimum Obtainable // product static void printMST ( int parent [] int n int graph [][] ) { System . out . printf ( 'Edge Weightn' ); int minProduct = 1 ; for ( int i = 1 ; i < V ; i ++ ) { System . out . printf ( '%d - %d %d n' parent [ i ] i graph [ i ][ parent [ i ]] ); minProduct *= graph [ i ][ parent [ i ]] ; } System . out . printf ( 'Minimum Obtainable product is %dn' minProduct ); } // Function to construct and print MST for a graph // represented using adjacency matrix representation // inputGraph is sent for printing actual edges and // logGraph is sent for actual MST operations static void primMST ( int inputGraph [][] double logGraph [][] ) { int [] parent = new int [ V ] ; // Array to store constructed MST int [] key = new int [ V ] ; // Key values used to pick minimum // weight edge in cut boolean [] mstSet = new boolean [ V ] ; // To represent set of vertices not // yet included in MST // Initialize all keys as INFINITE for ( int i = 0 ; i < V ; i ++ ) { key [ i ] = Integer . MAX_VALUE ; mstSet [ i ] = false ; } // Always include first 1st vertex in MST. key [ 0 ] = 0 ; // Make key 0 so that this vertex is // picked as first vertex parent [ 0 ] = - 1 ; // First node is always root of MST // The MST will have V vertices for ( int count = 0 ; count < V - 1 ; count ++ ) { // Pick the minimum key vertex from the set of // vertices not yet included in MST int u = minKey ( key mstSet ); // Add the picked vertex to the MST Set mstSet [ u ] = true ; // Update key value and parent index of the // adjacent vertices of the picked vertex. // Consider only those vertices which are not yet // included in MST for ( int v = 0 ; v < V ; v ++ ) // logGraph[u][v] is non zero only for // adjacent vertices of m mstSet[v] is false // for vertices not yet included in MST // Update the key only if logGraph[u][v] is // smaller than key[v] { if ( logGraph [ u ][ v ] > 0 && mstSet [ v ] == false && logGraph [ u ][ v ] < key [ v ] ) { parent [ v ] = u ; key [ v ] = ( int ) logGraph [ u ][ v ] ; } } } // print the constructed MST printMST ( parent V inputGraph ); } // Method to get minimum product spanning tree static void minimumProductMST ( int graph [][] ) { double [][] logGraph = new double [ V ][ V ] ; // Constructing logGraph from original graph for ( int i = 0 ; i < V ; i ++ ) { for ( int j = 0 ; j < V ; j ++ ) { if ( graph [ i ][ j ] > 0 ) { logGraph [ i ][ j ] = Math . log ( graph [ i ][ j ] ); } else { logGraph [ i ][ j ] = 0 ; } } } // Applying standard Prim's MST algorithm on // Log graph. primMST ( graph logGraph ); } // Driver code public static void main ( String [] args ) { /* Let us create the following graph 2 3 (0)--(1)--(2) | / | 6| 8/ 5 |7 | / | (3)-------(4) 9 */ int graph [][] = { { 0 2 0 6 0 } { 2 0 3 8 5 } { 0 3 0 0 7 } { 6 8 0 0 9 } { 0 5 7 9 0 } }; // Print the solution minimumProductMST ( graph ); } } // This code has been contributed by 29AjayKumar
Python3 # A Python3 program for getting minimum # product spanning tree The program is # for adjacency matrix representation # of the graph import math # Number of vertices in the graph V = 5 # A utility function to find the vertex # with minimum key value from the set # of vertices not yet included in MST def minKey ( key mstSet ): # Initialize min value min = 10000000 min_index = 0 for v in range ( V ): if ( mstSet [ v ] == False and key [ v ] < min ): min = key [ v ] min_index = v return min_index # A utility function to print the constructed # MST stored in parent[] and print Minimum # Obtainable product def printMST ( parent n graph ): print ( 'Edge Weight' ) minProduct = 1 for i in range ( 1 V ): print ( ' {} - {} {} ' . format ( parent [ i ] i graph [ i ][ parent [ i ]])) minProduct *= graph [ i ][ parent [ i ]] print ( 'Minimum Obtainable product is {} ' . format ( minProduct )) # Function to construct and print MST for # a graph represented using adjacency # matrix representation inputGraph is # sent for printing actual edges and # logGraph is sent for actual MST # operations def primMST ( inputGraph logGraph ): # Array to store constructed MST parent = [ 0 for i in range ( V )] # Key values used to pick minimum key = [ 10000000 for i in range ( V )] # weight edge in cut # To represent set of vertices not mstSet = [ False for i in range ( V )] # Yet included in MST # Always include first 1st vertex in MST # Make key 0 so that this vertex is key [ 0 ] = 0 # Picked as first vertex # First node is always root of MST parent [ 0 ] = - 1 # The MST will have V vertices for count in range ( 0 V - 1 ): # Pick the minimum key vertex from # the set of vertices not yet # included in MST u = minKey ( key mstSet ) # Add the picked vertex to the MST Set mstSet [ u ] = True # Update key value and parent index # of the adjacent vertices of the # picked vertex. Consider only those # vertices which are not yet # included in MST for v in range ( V ): # logGraph[u][v] is non zero only # for adjacent vertices of m # mstSet[v] is false for vertices # not yet included in MST. Update # the key only if logGraph[u][v] is # smaller than key[v] if ( logGraph [ u ][ v ] > 0 and mstSet [ v ] == False and logGraph [ u ][ v ] < key [ v ]): parent [ v ] = u key [ v ] = logGraph [ u ][ v ] # Print the constructed MST printMST ( parent V inputGraph ) # Method to get minimum product spanning tree def minimumProductMST ( graph ): logGraph = [[ 0 for j in range ( V )] for i in range ( V )] # Constructing logGraph from # original graph for i in range ( V ): for j in range ( V ): if ( graph [ i ][ j ] > 0 ): logGraph [ i ][ j ] = math . log ( graph [ i ][ j ]) else : logGraph [ i ][ j ] = 0 # Applying standard Prim's MST algorithm # on Log graph. primMST ( graph logGraph ) # Driver code if __name__ == '__main__' : ''' Let us create the following graph 2 3 (0)--(1)--(2) | / | 6| 8/ 5 |7 | / | (3)-------(4) 9 ''' graph = [ [ 0 2 0 6 0 ] [ 2 0 3 8 5 ] [ 0 3 0 0 7 ] [ 6 8 0 0 9 ] [ 0 5 7 9 0 ] ] # Print the solution minimumProductMST ( graph ) # This code is contributed by rutvik_56
C# // C# program for getting minimum product // spanning tree The program is for adjacency matrix // representation of the graph using System ; class GFG { // Number of vertices in the graph static int V = 5 ; // A utility function to find the vertex with minimum // key value from the set of vertices not yet included // in MST static int minKey ( int [] key Boolean [] mstSet ) { // Initialize min value int min = int . MaxValue min_index = 0 ; for ( int v = 0 ; v < V ; v ++ ) { if ( mstSet [ v ] == false && key [ v ] < min ) { min = key [ v ]; min_index = v ; } } return min_index ; } // A utility function to print the constructed MST // stored in parent[] and print Minimum Obtainable // product static void printMST ( int [] parent int n int [ ] graph ) { Console . Write ( 'Edge Weightn' ); int minProduct = 1 ; for ( int i = 1 ; i < V ; i ++ ) { Console . Write ( '{0} - {1} {2} n' parent [ i ] i graph [ i parent [ i ]]); minProduct *= graph [ i parent [ i ]]; } Console . Write ( 'Minimum Obtainable product is {0}n' minProduct ); } // Function to construct and print MST for a graph // represented using adjacency matrix representation // inputGraph is sent for printing actual edges and // logGraph is sent for actual MST operations static void primMST ( int [ ] inputGraph double [ ] logGraph ) { int [] parent = new int [ V ]; // Array to store constructed MST int [] key = new int [ V ]; // Key values used to pick minimum // weight edge in cut Boolean [] mstSet = new Boolean [ V ]; // To represent set of vertices not // yet included in MST // Initialize all keys as INFINITE for ( int i = 0 ; i < V ; i ++ ) { key [ i ] = int . MaxValue ; mstSet [ i ] = false ; } // Always include first 1st vertex in MST. key [ 0 ] = 0 ; // Make key 0 so that this vertex is // picked as first vertex parent [ 0 ] = - 1 ; // First node is always root of MST // The MST will have V vertices for ( int count = 0 ; count < V - 1 ; count ++ ) { // Pick the minimum key vertex from the set of // vertices not yet included in MST int u = minKey ( key mstSet ); // Add the picked vertex to the MST Set mstSet [ u ] = true ; // Update key value and parent index of the // adjacent vertices of the picked vertex. // Consider only those vertices which are not yet // included in MST for ( int v = 0 ; v < V ; v ++ ) // logGraph[u v] is non zero only for // adjacent vertices of m mstSet[v] is false // for vertices not yet included in MST // Update the key only if logGraph[u v] is // smaller than key[v] { if ( logGraph [ u v ] > 0 && mstSet [ v ] == false && logGraph [ u v ] < key [ v ]) { parent [ v ] = u ; key [ v ] = ( int ) logGraph [ u v ]; } } } // print the constructed MST printMST ( parent V inputGraph ); } // Method to get minimum product spanning tree static void minimumProductMST ( int [ ] graph ) { double [ ] logGraph = new double [ V V ]; // Constructing logGraph from original graph for ( int i = 0 ; i < V ; i ++ ) { for ( int j = 0 ; j < V ; j ++ ) { if ( graph [ i j ] > 0 ) { logGraph [ i j ] = Math . Log ( graph [ i j ]); } else { logGraph [ i j ] = 0 ; } } } // Applying standard Prim's MST algorithm on // Log graph. primMST ( graph logGraph ); } // Driver code public static void Main ( String [] args ) { /* Let us create the following graph 2 3 (0)--(1)--(2) | / | 6| 8/ 5 |7 | / | (3)-------(4) 9 */ int [ ] graph = { { 0 2 0 6 0 } { 2 0 3 8 5 } { 0 3 0 0 7 } { 6 8 0 0 9 } { 0 5 7 9 0 } }; // Print the solution minimumProductMST ( graph ); } } /* This code contributed by PrinciRaj1992 */
JavaScript < script > // A Javascript program for getting minimum product // spanning tree The program is for adjacency matrix // representation of the graph // Number of vertices in the graph let V = 5 ; // A utility function to find the vertex with minimum // key value from the set of vertices not yet included // in MST function minKey ( key mstSet ) { // Initialize min value let min = Number . MAX_VALUE min_index = 0 ; for ( let v = 0 ; v < V ; v ++ ) { if ( mstSet [ v ] == false && key [ v ] < min ) { min = key [ v ]; min_index = v ; } } return min_index ; } // A utility function to print the constructed MST // stored in parent[] and print Minimum Obtainable // product function printMST ( parent n graph ) { document . write ( 'Edge Weight
' ); let minProduct = 1 ; for ( let i = 1 ; i < V ; i ++ ) { document . write ( parent [ i ] + ' - ' + i + ' ' + graph [ i ][ parent [ i ]] + '
' ); minProduct *= graph [ i ][ parent [ i ]]; } document . write ( 'Minimum Obtainable product is ' minProduct + '
' ); } // Function to construct and print MST for a graph // represented using adjacency matrix representation // inputGraph is sent for printing actual edges and // logGraph is sent for actual MST operations function primMST ( inputGraph logGraph ) { let parent = new Array ( V ); // Array to store constructed MST let key = new Array ( V ); // Key values used to pick minimum // weight edge in cut let mstSet = new Array ( V ); // To represent set of vertices not // yet included in MST // Initialize all keys as INFINITE for ( let i = 0 ; i < V ; i ++ ) { key [ i ] = Number . MAX_VALUE ; mstSet [ i ] = false ; } // Always include first 1st vertex in MST. key [ 0 ] = 0 ; // Make key 0 so that this vertex is // picked as first vertex parent [ 0 ] = - 1 ; // First node is always root of MST // The MST will have V vertices for ( let count = 0 ; count < V - 1 ; count ++ ) { // Pick the minimum key vertex from the set of // vertices not yet included in MST let u = minKey ( key mstSet ); // Add the picked vertex to the MST Set mstSet [ u ] = true ; // Update key value and parent index of the // adjacent vertices of the picked vertex. // Consider only those vertices which are not yet // included in MST for ( let v = 0 ; v < V ; v ++ ) // logGraph[u][v] is non zero only for // adjacent vertices of m mstSet[v] is false // for vertices not yet included in MST // Update the key only if logGraph[u][v] is // smaller than key[v] { if ( logGraph [ u ][ v ] > 0 && mstSet [ v ] == false && logGraph [ u ][ v ] < key [ v ]) { parent [ v ] = u ; key [ v ] = logGraph [ u ][ v ]; } } } // print the constructed MST printMST ( parent V inputGraph ); } // Method to get minimum product spanning tree function minimumProductMST ( graph ) { let logGraph = new Array ( V ); // Constructing logGraph from original graph for ( let i = 0 ; i < V ; i ++ ) { logGraph [ i ] = new Array ( V ); for ( let j = 0 ; j < V ; j ++ ) { if ( graph [ i ][ j ] > 0 ) { logGraph [ i ][ j ] = Math . log ( graph [ i ][ j ]); } else { logGraph [ i ][ j ] = 0 ; } } } // Applying standard Prim's MST algorithm on // Log graph. primMST ( graph logGraph ); } // Driver code /* Let us create the following graph 2 3 (0)--(1)--(2) | / | 6| 8/ 5 |7 | / | (3)-------(4) 9 */ let graph = [ [ 0 2 0 6 0 ] [ 2 0 3 8 5 ] [ 0 3 0 0 7 ] [ 6 8 0 0 9 ] [ 0 5 7 9 0 ] ]; // Print the solution minimumProductMST ( graph ); // This code is contributed by rag2127 < /script>
산출:
Edge Weight 0 - 1 2 1 - 2 3 0 - 3 6 1 - 4 5 Minimum Obtainable product is 180
그만큼 시간 복잡도 이 알고리즘의 모든 정점을 반복하는 두 개의 중첩 for 루프가 있으므로 O(V2)입니다.
그만큼 공간 복잡도 이 알고리즘은 입력 그래프를 저장하기 위해 V x V 크기의 2차원 배열을 사용하므로 O(V2)입니다.
