Удалите все выходящие кромки, кроме кромки с минимальным весом
Опубликовано: 24 Января, 2022
Дан ориентированный граф, имеющий n узлов. Для каждого узла удалите все исходящие ребра, кроме исходящего ребра с минимальным весом. Примените эту операцию удаления для каждого узла, а затем распечатайте окончательный граф, оставшийся там, где каждый узел графа имеет не более одного исходящего ребра, и это тоже с минимальным весом.
Примечание. Здесь график для удобства хранится как матрица смежности.
Примеры :
Вход : Матрица смежности входного графа: | 1 2 3 4 --------------- 1 | 0 3 2 5 2 | 0 2 4 7 3 | 1 2 0 3 4 | 5 2 1 3 Выход : Матрица смежности выходного графа: | 1 2 3 4 --------------- 1 | 0 0 2 0 2 | 0 2 0 0 3 | 1 0 0 0 4 | 0 0 1 0
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Для каждой строки матрицы смежности графа оставьте минимальный элемент (кроме нуля) и сделайте все остальное равным нулю. Сделайте это для каждой строки входной матрицы. Наконец, распечатайте полученную матрицу.
Пример :
C++
// CPP program for minimizing graph #include <bits/stdc++.h> using namespace std; // Utility function for // finding min of a row int minFn( int arr[]) { int min = INT_MAX; for ( int i = 0; i < 4; i++) if (min > arr[i]) min = arr[i]; return min; } // Utility function for minimizing graph void minimizeGraph( int arr[][4]) { int min; // Set empty edges to INT_MAX for ( int i = 0; i < 4; i++) for ( int j = 0; j < 4; j++) if (arr[i][j] == 0) arr[i][j] = INT_MAX; // Finding minimum of each row // and deleting rest of edges for ( int i = 0; i < 4; i++) { // Find minimum element of row min = minFn(arr[i]); for ( int j = 0; j < 4; j++) { // If edge value is not min // set it to zero, also // edge value INT_MAX denotes that // initially edge value was zero if (!(arr[i][j] == min) || (arr[i][j] == INT_MAX)) arr[i][j] = 0; else min = 0; } } // Print result; for ( int i = 0; i < 4; i++) { for ( int j = 0; j < 4; j++) cout << arr[i][j] << " " ; cout << "
" ; } } // Driver Program int main() { // Input Graph int arr[4][4] = { 1, 2, 4, 0, 0, 0, 0, 5, 0, 2, 0, 3, 0, 0, 0, 0 }; minimizeGraph(arr); return 0; } |
Java
// Java program for // minimizing graph import java.io.*; import java.util.*; import java.lang.*; class GFG { // Utility function for // finding min of a row static int minFn( int arr[]) { int min = Integer.MAX_VALUE; for ( int i = 0 ; i < arr.length; i++) if (min > arr[i]) min = arr[i]; return min; } // Utility function // for minimizing graph static void minimizeGraph( int arr[][]) { int min; // Set empty edges // to INT_MAX for ( int i = 0 ; i < arr.length; i++) for ( int j = 0 ; j < arr.length; j++) if (arr[i][j] == 0 ) arr[i][j] = Integer.MAX_VALUE; // Finding minimum of each // row and deleting rest // of edges for ( int i = 0 ; i < arr.length; i++) { // Find minimum // element of row min = minFn(arr[i]); for ( int j = 0 ; j < arr.length; j++) { // If edge value is not // min set it to zero, // also edge value INT_MAX // denotes that initially // edge value was zero if ((arr[i][j] != min) || (arr[i][j] == Integer.MAX_VALUE)) arr[i][j] = 0 ; else min = 0 ; } } // Print result; for ( int i = 0 ; i < arr.length; i++) { for ( int j = 0 ; j < arr.length; j++) System.out.print(arr[i][j] + " " ); System.out.print( "
" ); } } // Driver Code public static void main(String[] args) { // Input Graph int arr[][] = { { 1 , 2 , 4 , 0 }, { 0 , 0 , 0 , 5 }, { 0 , 2 , 0 , 3 }, { 0 , 0 , 0 , 0 } }; minimizeGraph(arr); } } |
Python3
# Python3 program for minimizing graph # Utility function for finding min of a row def minFn(arr): minimum = float ( "inf" ) for i in range ( 0 , 4 ): if minimum > arr[i]: minimum = arr[i] return minimum # Utility function for minimizing graph def minimizeGraph(arr): # Set empty edges to INT_MAX for i in range ( 0 , 4 ): for j in range ( 0 , 4 ): if arr[i][j] = = 0 : arr[i][j] = float ( "inf" ) # Finding minimum of each row # and deleting rest of edges for i in range ( 0 , 4 ): # Find minimum element of row minimum = minFn(arr[i]) for j in range ( 0 , 4 ): # If edge value is not min # set it to zero, also # edge value INT_MAX denotes that # initially edge value was zero if (( not (arr[i][j] = = minimum)) or (arr[i][j] = = float ( "inf" ))): arr[i][j] = 0 else : minimum = 0 # Print result for i in range ( 0 , 4 ): for j in range ( 0 , 4 ): print (arr[i][j], end = " " ) print () # Driver Code if __name__ = = "__main__" : # Input Graph arr = [[ 1 , 2 , 4 , 0 ], [ 0 , 0 , 0 , 5 ], [ 0 , 2 , 0 , 3 ], [ 0 , 0 , 0 , 0 ]] minimizeGraph(arr) # This code is contributed by # Rituraj Jain |
C#
// C# program for // minimizing graph using System; class GFG { // Utility function for // finding min of a row static int minFn( int [] arr) { int min = int .MaxValue; for ( int i = 0; i < arr.Length; i++) if (min > arr[i]) min = arr[i]; return min; } // Utility function // for minimizing graph static void minimizeGraph( int [, ] arr) { int min; // Set empty edges // to INT_MAX for ( int i = 0; i < arr.GetLength(0); i++) for ( int j = 0; j < arr.GetLength(1); j++) if (arr[i, j] == 0) arr[i, j] = int .MaxValue; // Finding minimum of each // row and deleting rest // of edges for ( int i = 0; i < arr.GetLength(0); i++) { // Find minimum // element of row min = minFn(GetRow(arr, i)); for ( int j = 0; j < arr.GetLength(1); j++) { // If edge value is not // min set it to zero, // also edge value INT_MAX // denotes that initially // edge value was zero if ((arr[i, j] != min) || (arr[i, j] == int .MaxValue)) arr[i, j] = 0; else min = 0; } } // Print result; for ( int i = 0; i < arr.GetLength(0); i++) { for ( int j = 0; j < arr.GetLength(1); j++) Console.Write(arr[i, j] + " " ); Console.Write( "
" ); } } public static int [] GetRow( int [, ] matrix, int row) { var rowLength = matrix.GetLength(1); var rowVector = new int [rowLength]; for ( var i = 0; i < rowLength; i++) rowVector[i] = matrix[row, i]; return rowVector; } // Driver Code public static void Main(String[] args) { // Input Graph int [, ] arr = { { 1, 2, 4, 0 }, { 0, 0, 0, 5 }, { 0, 2, 0, 3 }, { 0, 0, 0, 0 } }; minimizeGraph(arr); } } // This code contributed by Rajput-Ji |
PHP
<?php // PHP program for minimizing graph // Utility function for finding // min of a row function minFn( $arr ) { $min = PHP_INT_MAX; for ( $i = 0; $i < 4; $i ++) if ( $min > $arr [ $i ]) $min = $arr [ $i ]; return $min ; } // Utility function for minimizing graph function minimizeGraph( $arr ) { $min ; // Set empty edges to INT_MAX for ( $i = 0; $i < 4; $i ++) for ( $j = 0; $j < 4; $j ++) if ( $arr [ $i ][ $j ] == 0) $arr [ $i ][ $j ] = PHP_INT_MAX; // Finding minimum of each row // and deleting rest of edges for ( $i = 0; $i < 4; $i ++) { // Find minimum element of row $min = minFn( $arr [ $i ]);
РЕКОМЕНДУЕМЫЕ СТАТЬИ |