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