Удалите все выходящие кромки, кроме кромки с минимальным весом

Опубликовано: 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]);