Comprobar si un gráfico está fuertemente conectado, unilateralmente o débilmente

Dado un grafo dirigido no ponderado G como array de ruta, la tarea es averiguar si el grafo es fuertemente conectado , unilateralmente conectado o débilmente conectado. 

Fuertemente conectado: se dice que un gráfico está fuertemente conectado si cada par de vértices (u, v) en el gráfico contiene un camino entre ellos. En un grafo dirigido no ponderado G, cada par de vértices uyv debe tener un camino en cada dirección entre ellos, es decir, un camino bidireccional. Los elementos de la array de ruta de dicho gráfico contendrán todos los 1 .
Unilateralmente Conectado: Se dice que un grafo es unilateralmente conectado si contiene un camino dirigido de u a v O un camino dirigido de v a u para cada par de vértices u, v. Por lo tanto, al menos para cualquier par de vértices, un vértice debe ser accesible desde el otro. Tal array de ruta preferiría tener elementos de triángulo superior que contengan 1O elementos del triángulo inferior que contienen 1 .
Débilmente conectado: se dice que un gráfico está débilmente conectado si no existe ningún camino entre dos pares de vértices. Por lo tanto, si un grafo G no contiene un camino dirigido (de u a v o de v a u para cada par de vértices u, v), entonces es débilmente conexo. Los elementos de tal array de caminos de este gráfico serían aleatorios.

Ejemplos: 

Entrada: a continuación se muestra el gráfico dado con la array de ruta: 
 

Salida:
Entrada de gráfico fuertemente conectado  : A continuación se muestra el gráfico dado con la array de ruta: 
 

Salida: Gráfico conectado unilateralmente
Entrada: A continuación se muestra el gráfico dado con la array de ruta: 
 

Salida: gráfico débilmente conectado 
 

Acercarse: 

  1. Para que el gráfico esté fuertemente conectado , atraviese la array de ruta dada usando el enfoque discutido en este artículo, verifique si todos los valores en la celda son 1 o no. En caso afirmativo, imprima «Gráfico fuertemente conectado»; de lo contrario, verifique los otros dos gráficos.
  2. Para que el gráfico esté conectado unilateralmente , atraviese la array de ruta dada usando el enfoque discutido en este artículo y verifique lo siguiente: 
    • Si todos los valores por encima de la diagonal principal son 1 y todos los demás valores son 0 .
    • Si todos los valores debajo de la diagonal principal son 1 y todos los demás valores son 0 .
  3. Si se cumple una de las dos condiciones anteriores, entonces el gráfico dado está conectado unilateralmente; de ​​lo contrario, el gráfico es un gráfico débilmente conectado .

A continuación se muestra la implementación del enfoque anterior:
 

C++

// C++ implementation of the approach
 
#include <bits/stdc++.h>
using namespace std;
#define V 3
 
// Function to find the characteristic
// of the given graph
int checkConnected(int graph[][V], int n)
{
 
    // Check whether the graph is
    // strongly connected or not
    bool strongly = true;
 
    // Traverse the path matrix
    for (int i = 0; i < n; i++) {
 
        for (int j = 0; j < n; j++) {
 
            // If all the elements are
            // not equal then the graph
            // is not strongly connected
            if (graph[i][j] != graph[j][i]) {
                strongly = false;
                break;
            }
        }
 
        // Break out of the loop if false
        if (!strongly) {
            break;
        }
    }
    // If true then print strongly
    // connected and return
    if (strongly) {
        cout << "Strongly Connected";
        return 0;
    }
 
    // Check whether the graph is
    // Unilaterally connected by
    // checking Upper Triangle element
    bool uppertri = true;
 
    // Traverse the path matrix
    for (int i = 0; i < n; i++) {
 
        for (int j = 0; j < n; j++) {
 
            // If uppertriangle elements
            // are 0 then break out of the
            // loop and check the elements
            // of lowertriangle matrix
            if (i > j && graph[i][j] == 0) {
                uppertri = false;
                break;
            }
        }
 
        // Break out of the loop if false
        if (!uppertri) {
            break;
        }
    }
 
    // If true then print unilaterally
    // connected and return
    if (uppertri) {
        cout << "Unilaterally Connected";
        return 0;
    }
 
    // Check lowertraingle elements
    bool lowertri = true;
 
    // Traverse the path matrix
    for (int i = 0; i < n; i++) {
 
        for (int j = 0; j < n; j++) {
 
            // If lowertraingle elements
            // are 0 then break cause
            // 1's are expected
            if (i < j && graph[i][j] == 0) {
                lowertri = false;
                break;
            }
        }
 
        // Break out of the loop if false
        if (!lowertri) {
            break;
        }
    }
 
    // If true then print unilaterally
    // connected and return
    if (lowertri) {
        cout << "Unilaterally Connected";
        return 0;
    }
 
    // If elements are in random order
    // unsynchronized then print weakly
    // connected and return
    else {
        cout << "Weakly Connected";
    }
 
    return 0;
}
 
// Driver Code
int main()
{
    // Number of nodes
    int n = 3;
 
    // Given Path Matrix
    int graph[V][V] = {
        { 0, 1, 1 },
        { 0, 0, 1 },
        { 0, 0, 0 },
    };
 
    // Function Call
    checkConnected(graph, n);
    return 0;
}

Java

// Java implementation of the above approach
import java.util.*;
 
class GFG{
     
static final int V = 3;
 
// Function to find the characteristic
// of the given graph
static int checkConnected(int graph[][], int n)
{
     
    // Check whether the graph is
    // strongly connected or not
    boolean strongly = true;
 
    // Traverse the path matrix
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
             
            // If all the elements are
            // not equal then the graph
            // is not strongly connected
            if (graph[i][j] != graph[j][i])
            {
                strongly = false;
                break;
            }
        }
         
        // Break out of the loop if false
        if (!strongly)
        {
            break;
        }
    }
     
    // If true then print strongly
    // connected and return
    if (strongly)
    {
        System.out.print("Strongly Connected");
        return 0;
    }
 
    // Check whether the graph is
    // Unilaterally connected by
    // checking Upper Triangle element
    boolean uppertri = true;
 
    // Traverse the path matrix
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
             
            // If uppertriangle elements
            // are 0 then break out of the
            // loop and check the elements
            // of lowertriangle matrix
            if (i > j && graph[i][j] == 0)
            {
                uppertri = false;
                break;
            }
        }
 
        // Break out of the loop if false
        if (!uppertri)
        {
            break;
        }
    }
 
    // If true then print unilaterally
    // connected and return
    if (uppertri)
    {
        System.out.print("Unilaterally Connected");
        return 0;
    }
 
    // Check lowertraingle elements
    boolean lowertri = true;
 
    // Traverse the path matrix
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
             
            // If lowertraingle elements
            // are 0 then break cause
            // 1's are expected
            if (i < j && graph[i][j] == 0)
            {
                lowertri = false;
                break;
            }
        }
         
        // Break out of the loop if false
        if (!lowertri)
        {
            break;
        }
    }
 
    // If true then print unilaterally
    // connected and return
    if (lowertri)
    {
        System.out.print("Unilaterally Connected");
        return 0;
    }
 
    // If elements are in random order
    // unsynchronized then print weakly
    // connected and return
    else
    {
        System.out.print("Weakly Connected");
    }
    return 0;
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Number of nodes
    int n = 3;
 
    // Given Path Matrix
    int graph[][] = { { 0, 1, 1 },
                      { 0, 0, 1 },
                      { 0, 0, 0 } };
                         
    // Function call
    checkConnected(graph, n);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 implementation of
# the above approach
V = 3
 
# Function to find the
# characteristic of the
# given graph
def checkConnected(graph, n):
  
    # Check whether the graph is
    # strongly connected or not
    strongly = True;
  
    # Traverse the path
    # matrix
    for i in range(n):
        for j in range(n):
  
            # If all the elements are
            # not equal then the graph
            # is not strongly connected
            if (graph[i][j] != graph[j][i]):
                strongly = False;
                break
  
        # Break out of the
        # loop if false
        if not strongly:
           break;
         
    # If true then print
    # strongly connected and return
    if (strongly):
        print("Strongly Connected");
        exit()   
  
    # Check whether the graph is
    # Unilaterally connected by
    # checking Upper Triangle element
    uppertri = True;
  
    # Traverse the path matrix
    for i in range(n):
        for j in range(n):
  
            # If uppertriangle elements
            # are 0 then break out of the
            # loop and check the elements
            # of lowertriangle matrix
            if (i > j and graph[i][j] == 0):
                uppertri = False;
                break;            
  
        # Break out of the
        # loop if false
        if not uppertri:
            break;    
  
    # If true then print
    # unilaterally connected
    # and return
    if uppertri:
        print("Unilaterally Connected");
        exit()
  
    # Check lowertraingle elements
    lowertri = True;
  
    # Traverse the path matrix
    for i in range(n):
        for j in range(n):
  
            # If lowertraingle elements
            # are 0 then break cause
            # 1's are expected
            if (i < j and graph[i][j] == 0):
                lowertri = False;
                break;
  
        # Break out of the
        # loop if false
        if not lowertri:
            break;        
  
    # If true then print
    # unilaterally connected
    # and return
    if lowertri:
        print("Unilaterally Connected")
        exit()
  
    # If elements are in random order
    # unsynchronized then print weakly
    # connected and return
    else:
        print("Weakly Connected")
     
    exit()
 
if __name__ == "__main__":
     
    # Number of nodes
    n = 3;
  
    # Given Path Matrix
    graph = [[0, 1, 1],
             [0, 0, 1],
             [0, 0, 0]];
  
    # Function Call
    checkConnected(graph, n);
     
 # This code is contributed by rutvik_56

C#

// C# implementation of the above approach
using System;
 
class GFG{
     
//static readonly int V = 3;
 
// Function to find the characteristic
// of the given graph
static int checkConnected(int [,]graph, int n)
{
     
    // Check whether the graph is
    // strongly connected or not
    bool strongly = true;
 
    // Traverse the path matrix
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
             
            // If all the elements are
            // not equal then the graph
            // is not strongly connected
            if (graph[i, j] != graph[j, i])
            {
                strongly = false;
                break;
            }
        }
         
        // Break out of the loop if false
        if (!strongly)
        {
            break;
        }
    }
     
    // If true then print strongly
    // connected and return
    if (strongly)
    {
        Console.Write("Strongly Connected");
        return 0;
    }
 
    // Check whether the graph is
    // Unilaterally connected by
    // checking Upper Triangle element
    bool uppertri = true;
 
    // Traverse the path matrix
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++) 
        {
             
            // If uppertriangle elements
            // are 0 then break out of the
            // loop and check the elements
            // of lowertriangle matrix
            if (i > j && graph[i, j] == 0)
            {
                uppertri = false;
                break;
            }
        }
         
        // Break out of the loop if false
        if (!uppertri)
        {
            break;
        }
    }
 
    // If true then print unilaterally
    // connected and return
    if (uppertri)
    {
        Console.Write("Unilaterally Connected");
        return 0;
    }
 
    // Check lowertraingle elements
    bool lowertri = true;
 
    // Traverse the path matrix
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
             
            // If lowertraingle elements
            // are 0 then break cause
            // 1's are expected
            if (i < j && graph[i, j] == 0)
            {
                lowertri = false;
                break;
            }
        }
         
        // Break out of the loop if false
        if (!lowertri)
        {
            break;
        }
    }
 
    // If true then print unilaterally
    // connected and return
    if (lowertri)
    {
        Console.Write("Unilaterally Connected");
        return 0;
    }
 
    // If elements are in random order
    // unsynchronized then print weakly
    // connected and return
    else
    {
        Console.Write("Weakly Connected");
    }
    return 0;
}
 
// Driver Code
public static void Main(String[] args)
{
     
    // Number of nodes
    int n = 3;
 
    // Given Path Matrix
    int [,]graph = { { 0, 1, 1 },
                     { 0, 0, 1 },
                     { 0, 0, 0 } };
                         
    // Function call
    checkConnected(graph, n);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript implementation of the above approach
 
let V = 3;
 
// Function to find the characteristic
// of the given graph
function checkConnected(graph, n)
{
     
    // Check whether the graph is
    // strongly connected or not
    let strongly = true;
 
    // Traverse the path matrix
    for(let i = 0; i < n; i++)
    {
        for(let j = 0; j < n; j++)
        {
             
            // If all the elements are
            // not equal then the graph
            // is not strongly connected
            if (graph[i][j] != graph[j][i])
            {
                strongly = false;
                break;
            }
        }
         
        // Break out of the loop if false
        if (!strongly)
        {
            break;
        }
    }
     
    // If true then print strongly
    // connected and return
    if (strongly)
    {
        document.write("Strongly Connected");
        return 0;
    }
 
    // Check whether the graph is
    // Unilaterally connected by
    // checking Upper Triangle element
    let uppertri = true;
 
    // Traverse the path matrix
    for(let i = 0; i < n; i++)
    {
        for(let j = 0; j < n; j++)
        {
             
            // If uppertriangle elements
            // are 0 then break out of the
            // loop and check the elements
            // of lowertriangle matrix
            if (i > j && graph[i][j] == 0)
            {
                uppertri = false;
                break;
            }
        }
 
        // Break out of the loop if false
        if (!uppertri)
        {
            break;
        }
    }
 
    // If true then print unilaterally
    // connected and return
    if (uppertri)
    {
        document.write("Unilaterally Connected");
        return 0;
    }
 
    // Check lowertraingle elements
    let lowertri = true;
 
    // Traverse the path matrix
    for(let i = 0; i < n; i++)
    {
        for(let j = 0; j < n; j++)
        {
             
            // If lowertraingle elements
            // are 0 then break cause
            // 1's are expected
            if (i < j && graph[i][j] == 0)
            {
                lowertri = false;
                break;
            }
        }
         
        // Break out of the loop if false
        if (!lowertri)
        {
            break;
        }
    }
 
    // If true then print unilaterally
    // connected and return
    if (lowertri)
    {
        document.write("Unilaterally Connected");
        return 0;
    }
 
    // If elements are in random order
    // unsynchronized then print weakly
    // connected and return
    else
    {
        document.write("Weakly Connected");
    }
    return 0;
}
 
 
    // Driver Code
     
    // Number of nodes
    let n = 3;
 
    // Given Path Matrix
    let graph = [[ 0, 1, 1 ],
                      [ 0, 0, 1 ],
                      [ 0, 0, 0 ]];
                         
    // Function call
    checkConnected(graph, n);
 
// This code is contributed by susmitakundugoaldanga.
</script>
Producción: 

Unilaterally Connected

 

Complejidad de Tiempo: O(N 2 )  
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por shreedhar_bhatt y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *