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:
- 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.
- 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 .
- 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>
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