Encuentra un vértice madre en un gráfico

¿Qué es un Vértice Madre?  
Un vértice madre en un grafo G = (V, E) es un vértice v tal que se puede llegar a todos los demás vértices en G por un camino desde v.

Ejemplo: 

Input  : Below Graph
Output : 5

Puede haber más de un vértice madre en un gráfico. Necesitamos dar salida a cualquiera de ellos. Por ejemplo, en el siguiente gráfico, los vértices 0, 1 y 2 son vértices madre. 

Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.

¿Cómo encontrar el vértice madre? 

• Caso 1: – Gráfico conectado no dirigido: en este caso, todos los vértices son vértices madre, ya que podemos llegar a todos los demás Nodes del gráfico.
• Caso 2: – Gráfico desconectado no dirigido/dirigido : en este caso, no hay vértices madre ya que no podemos llegar a todos los demás Nodes en el gráfico.
• Caso 3:- Gráfico conectado dirigido : en este caso, tenemos que encontrar un vértice -v en el gráfico de modo que podamos llegar a todos los demás Nodes del gráfico a través de un camino dirigido.

Un enfoque ingenuo: 
un enfoque trivial será realizar un DFS/BFS en todos los vértices y averiguar si podemos alcanzar todos los vértices desde ese vértice. Este enfoque requiere un tiempo O(V(E+V)), que es muy ineficiente para gráficos grandes.

¿Podemos hacerlo mejor?  
Podemos encontrar un vértice madre en tiempo O(V+E). La idea se basa en el algoritmo de componentes fuertemente conectados de Kosaraju . En un gráfico de componentes fuertemente conectados, los vértices madre siempre son vértices del componente fuente en el gráfico de componentes. La idea se basa en el siguiente hecho.
Si existe un vértice madre (o vértices), entonces uno de los vértices madre es el último vértice terminado en DFS. (O un vértice madre tiene el tiempo de finalización máximo en el recorrido DFS).
Se dice que un vértice está terminado en DFS si finaliza una llamada recursiva para su DFS, es decir, todos los descendientes del vértice han sido visitados. 

¿Cómo funciona la idea anterior?  
Sea v el último vértice terminado. Básicamente, necesitamos probar que no puede haber una arista de otro vértice u a v si u no es otro vértice madre (O no puede existir un vértice no madre u tal que u-→v es un borde). Puede haber dos posibilidades.

1. La llamada DFS recursiva se realiza para u antes que v. Si existe un borde u-→v, entonces v debe haber terminado antes que u porque v es accesible a través de u y un vértice termina después de todos sus descendientes.
2. La llamada DFS recursiva se realiza para v antes de u. En este caso también, si existe una arista u-→v, entonces v debe terminar antes que u (lo que contradice nuestra suposición de que v termina al final) O u debe ser accesible desde v (lo que significa que u es otro vértice madre) .

Algoritmo: 

1. Haz un recorrido DFS del gráfico dado. Mientras realiza el recorrido, realice un seguimiento del último vértice terminado ‘v’. Este paso toma tiempo O(V+E).
2. Si existe un vértice (o vértices) madre, entonces v debe ser uno (o uno de ellos). Verifica si v es un vértice madre haciendo DFS/BFS desde v. Este paso también requiere tiempo O(V+E).

A continuación se muestra la implementación del algoritmo anterior. 

// C++ program to find a mother vertex in O(V+E) time
#include <bits/stdc++.h>
using namespace std;
 
class Graph
{
    int V;    // No. of vertices
    list<int> *adj;    // adjacency lists
 
    // A recursive function to print DFS starting from v
    void DFSUtil(int v, vector<bool> &visited);
public:
    Graph(int V);
    void addEdge(int v, int w);
    int findMother();
};
 
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}
 
// A recursive function to print DFS starting from v
void Graph::DFSUtil(int v, vector<bool> &visited)
{
    // Mark the current node as visited and print it
    visited[v] = true;
 
    // Recur for all the vertices adjacent to this vertex
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i, visited);
}
 
void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}
 
// Returns a mother vertex if exists. Otherwise returns -1
int Graph::findMother()
{
    // visited[] is used for DFS. Initially all are
    // initialized as not visited
    vector <bool> visited(V, false);
 
    // To store last finished vertex (or mother vertex)
    int v = 0;
 
    // Do a DFS traversal and find the last finished
    // vertex 
    for (int i = 0; i < V; i++)
    {
        if (visited[i] == false)
        {
            DFSUtil(i, visited);
            v = i;
        }
    }
 
    // If there exist mother vertex (or vertices) in given
    // graph, then v must be one (or one of them)
 
    // Now check if v is actually a mother vertex (or graph
    // has a mother vertex).  We basically check if every vertex
    // is reachable from v or not.
 
    // Reset all values in visited[] as false and do
    // DFS beginning from v to check if all vertices are
    // reachable from it or not.
    fill(visited.begin(), visited.end(), false);
    DFSUtil(v, visited);
    for (int i=0; i<V; i++)
        if (visited[i] == false)
            return -1;
 
    return v;
}
 
// Driver program to test above functions
int main()
{
    // Create a graph given in the above diagram
    Graph g(7);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(4, 1);
    g.addEdge(6, 4);
    g.addEdge(5, 6);
    g.addEdge(5, 2);
    g.addEdge(6, 0);
 
    cout << "A mother vertex is " << g.findMother();
 
    return 0;
}

// Java program to find a mother
// vertex in O(V+E) time
import java.util.*;
 
class GFG{
    
static void addEdge(int u, int v,
 ArrayList<ArrayList<Integer>> adj)
{
    adj.get(u).add(v);
}
 
// A recursive function to print DFS starting from v
static void DFSUtil(ArrayList<ArrayList<Integer>> g,
                    int v, boolean[] visited)
{
    // Mark the current node as
    // visited and print it
    visited[v] = true;
     
    // Recur for all the vertices
    // adjacent to this vertex
    for(int x : g.get(v))
    {
        if (!visited[x])
        {
            DFSUtil(g, x, visited);
        }
    }
}
 
// Returns a mother vertex if exists.
// Otherwise returns -1
static int motherVertex(ArrayList<ArrayList<Integer>>g,
                        int V)
{
     
    // visited[] is used for DFS. Initially
    // all are initialized as not visited
    boolean[] visited = new boolean[V];
     
    // To store last finished vertex
    // (or mother vertex)
    int v = -1;
     
    for(int i = 0; i < V; i++)
    {
        if (!visited[i])
        {
            DFSUtil(g, i, visited);
            v = i;
        }
    }
     
    // If there exist mother vertex (or vertices)
    // in given graph, then v must be one
    // (or one of them)
   
    // Now check if v is actually a mother
    // vertex (or graph has a mother vertex).
    // We basically check if every vertex
    // is reachable from v or not.
   
    // Reset all values in visited[] as false
    // and do DFS beginning from v to check
    // if all vertices are reachable from
    // it or not.
    boolean[] check = new boolean[V];
    DFSUtil(g, v, check);
    for(boolean val : check)
    {
        if (!val)
        {
            return -1;
        }
    }
    return v;
}
 
// Driver code
 public static void main(String[] args)
 {
    int V = 7;
    int E = 8;
     
    ArrayList<
    ArrayList<Integer>> adj = new ArrayList<
                                  ArrayList<Integer>>();
    for(int i = 0; i < V; i++)
    {
        adj.add(new ArrayList<Integer>());
    }
    addEdge(0, 1,adj);
    addEdge(0, 2,adj);
    addEdge(1, 3,adj);
    addEdge(4, 1,adj);
    addEdge(6, 4,adj);
    addEdge(5, 6,adj);
    addEdge(5, 2,adj);
    addEdge(6, 0,adj);
     
    System.out.println("The mother vertex is " +
                        motherVertex(adj, V));
}
}
 
// This code is contributed by Tanay Shah

# program to find a mother vertex in O(V+E) time
from collections import defaultdict
 
# This class represents a directed graph using adjacency list
# representation
class Graph:
 
    def __init__(self,vertices):
        self.V = vertices #No. of vertices
        self.graph = defaultdict(list) # default dictionary
 
    # A recursive function to print DFS starting from v
    def DFSUtil(self, v, visited):
 
        # Mark the current node as visited and print it
        visited[v] = True
 
        # Recur for all the vertices adjacent to this vertex
        for i in self.graph[v]:
            if visited[i] == False:
                self.DFSUtil(i, visited)
 
    # Add w to the list of v
    def addEdge(self, v, w):
        self.graph[v].append(w)
 
    # Returns a mother vertex if exists. Otherwise returns -1
    def findMother(self):
 
        # visited[] is used for DFS. Initially all are
        # initialized as not visited
        visited =[False]*(self.V)
 
        # To store last finished vertex (or mother vertex)
        v=0
 
        # Do a DFS traversal and find the last finished
        # vertex
        for i in range(self.V):
            if visited[i]==False:
                self.DFSUtil(i,visited)
                v = i
 
        # If there exist mother vertex (or vertices) in given
        # graph, then v must be one (or one of them)
 
        # Now check if v is actually a mother vertex (or graph
        # has a mother vertex). We basically check if every vertex
        # is reachable from v or not.
 
        # Reset all values in visited[] as false and do
        # DFS beginning from v to check if all vertices are
        # reachable from it or not.
        visited = [False]*(self.V)
        self.DFSUtil(v, visited)
        if any(i == False for i in visited):
            return -1
        else:
            return v
 
# Create a graph given in the above diagram
g = Graph(7)
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(1, 3)
g.addEdge(4, 1)
g.addEdge(6, 4)
g.addEdge(5, 6)
g.addEdge(5, 2)
g.addEdge(6, 0)
print ("A mother vertex is " + str(g.findMother()))
 
# This code is contributed by Neelam Yadav

// C# program to find a mother
// vertex in O(V+E) time
using System;
using System.Collections.Generic;
 
class GFG
{
    
static void addEdge(int u, int v,
 List<List<int>> adj)
{
    adj[u].Add(v);
}
 
// A recursive function to print DFS starting from v
static void DFSUtil(List<List<int>> g,
                    int v, bool[] visited)
{
    // Mark the current node as
    // visited and print it
    visited[v] = true;
     
    // Recur for all the vertices
    // adjacent to this vertex
    foreach(int x in g[v])
    {
        if (!visited[x])
        {
            DFSUtil(g, x, visited);
        }
    }
}
 
// Returns a mother vertex if exists.
// Otherwise returns -1
static int motherVertex(List<List<int>>g,
                        int V)
{
     
    // visited[] is used for DFS. Initially
    // all are initialized as not visited
    bool[] visited = new bool[V];
     
    // To store last finished vertex
    // (or mother vertex)
    int v = -1;  
    for(int i = 0; i < V; i++)
    {
        if (!visited[i])
        {
            DFSUtil(g, i, visited);
            v = i;
        }
    }
     
    // If there exist mother vertex (or vertices)
    // in given graph, then v must be one
    // (or one of them)
   
    // Now check if v is actually a mother
    // vertex (or graph has a mother vertex).
    // We basically check if every vertex
    // is reachable from v or not.
   
    // Reset all values in visited[] as false
    // and do DFS beginning from v to check
    // if all vertices are reachable from
    // it or not.
    bool[] check = new bool[V];
    DFSUtil(g, v, check);
    foreach(bool val in check)
    {
        if (!val)
        {
            return -1;
        }
    }
    return v;
}
 
// Driver code
 public static void Main(String[] args)
 {
    int V = 7;
    int E = 8;   
    List<
    List<int>> adj = new List<List<int>>();
    for(int i = 0; i < V; i++)
    {
        adj.Add(new List<int>());
    }
    addEdge(0, 1,adj);
    addEdge(0, 2,adj);
    addEdge(1, 3,adj);
    addEdge(4, 1,adj);
    addEdge(6, 4,adj);
    addEdge(5, 6,adj);
    addEdge(5, 2,adj);
    addEdge(6, 0,adj);
     
    Console.WriteLine("The mother vertex is " +
                        motherVertex(adj, V));
}
}
 
// This code is contributed by Rajput-Ji

<script>
    // Javascript program to find a mother
    // vertex in O(V+E) time
     
    function addEdge(u, v, adj)
    {
        adj[u].push(v);
    }
 
    // A recursive function to print DFS starting from v
    function DFSUtil(g, v, visited)
    {
        // Mark the current node as
        // visited and print it
        visited[v] = true;
 
        // Recur for all the vertices
        // adjacent to this vertex
        for(let x in g[v])
        {
            if (!visited[x])
            {
                DFSUtil(g, x, visited);
            }
        }
    }
 
    // Returns a mother vertex if exists.
    // Otherwise returns -1
    function motherVertex(g, V)
    {
 
        // visited[] is used for DFS. Initially
        // all are initialized as not visited
        let visited = new Array(V);
        for(let i = 0; i < V; i++)
        {
            visited[i] = false;
        }
         
        // To store last finished vertex
        // (or mother vertex)
        let v = -1; 
        for(let i = 0; i < V; i++)
        {
            if (!visited[i])
            {
                DFSUtil(g, i, visited);
                v = i;
            }
        }
 
        // If there exist mother vertex (or vertices)
        // in given graph, then v must be one
        // (or one of them)
 
        // Now check if v is actually a mother
        // vertex (or graph has a mother vertex).
        // We basically check if every vertex
        // is reachable from v or not.
 
        // Reset all values in visited[] as false
        // and do DFS beginning from v to check
        // if all vertices are reachable from
        // it or not.
        let check = new Array(V);
        for(let i = 0; i < V; i++)
        {
            check[i] = false;
        }
        DFSUtil(g, v, check);
        for(let val in check)
        {
            if (!val)
            {
                return -1;
            }
        }
        return v-1;
    }
     
    let V = 7;
    let E = 8;  
    let adj = [];
    for(let i = 0; i < V; i++)
    {
        adj.push([]);
    }
    addEdge(0, 1,adj);
    addEdge(0, 2,adj);
    addEdge(1, 3,adj);
    addEdge(4, 1,adj);
    addEdge(6, 4,adj);
    addEdge(5, 6,adj);
    addEdge(5, 2,adj);
    addEdge(6, 0,adj);
      
    document.write("The mother vertex is " + motherVertex(adj, V));
 
// This code is contributed by divyesh072019.
</script>

A mother vertex is 5

Tiempo Complejidad : O(V + E)

Este artículo es una contribución de Rachit Belwariar . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.