Digraph - Cover all vertices with the least number of vertices


  • 0
    R

    Given a directed graph G (can contain sub graphs and cycles), find the minimum number of vertices from which all nodes are reachable.

    For example:

    Nodes:
        0, 1, 2, 3, 4, 5
    
    Edges:
        1 <- 0
        0 <- 1 <- 2
        3 <- 1 <- 2
        2 <- 5
        4 <- 5
    
    Representation:
        --> 4
      /
     5 --> 2 --> 1 <--> 0
                  \
                    --> 3
    Matrix:
    g = [[1, 1, 0, 0, 0, 0],
         [1, 1, 1, 0, 0, 0],
         [0, 0, 1, 0, 0, 1],
         [0, 1, 0, 1, 0, 0],
         [0, 0, 0, 0, 1, 1],
         [0, 0, 0, 0, 0, 1]]
    

    Return 1 (node number 5). From node number 5 all other nodes are reachable.

    If we remove edge 2 <- 5, the result is 2, because we need at least nodes number 5 and 2 to visit all nodes.

    Representation of the graph if we remove the edge between nodes 2 and 5.

     5 --> 4
    
     2 --> 1 <--> 0
            \
              --> 3
    

    I attempted to solve this problem by finding for every node j, and array of all nodes reachable from j. Basically, I did a DFS on every node, and the result looks like this:

    {
        0: [True, True, False, True, False, False],
        1: [True, True, False, True, False, False],
        2: [True, True, True, True, False, False],
        3: [False, False, False, True, False, False],
        4: [False, False, False, False, True, False],
        5: [True, True, True, True, True, True]
    }
    

    This means that from node 0, I can reach nodes number 0, 1, 3. From node 1 I can reach nodes 0, 1 and 3. From node 5, I can reach all nodes.

    Is this a good approach to solve the problem? Having this dictionary, how can I find the smallest group of nodes from which I can reach all nodes?


  • 0
    R

    Finally, I came up with this solution. I think it solves the problem in O(V^2) where V is the number of vertices/nodes in the graph.

    At the end are three test cases if anyone wants to run this code.

    def adjacent_nodes(graph, start):
        """Given a node `start` it returns a list which shows
        which nodes are reachable from `start`. If the list 
        return by start looks like [True True False True], that means
        that nodes 0, 1 and 3 are reachable from node K.
        
        Time Complexity: # O(V + E), where V = number of vertices 
        and E the number of edges."""
        nodes = len(graph)
    
        visited = [False] * nodes
        followers = [start]
    
        # O(V + E)
        while followers:
            current_node = followers.pop()
            if visited[current_node]:
                continue
    
            visited[current_node] = True
    
            for i in range(nodes):
                if graph[i][current_node] == 1:
                    followers.append(i)
    
        return visited
    
    
    def followers_per_node(graph):
        """Create a matrix (V*V) where in which row K shows
        all nodes that are reachable from K. If row K looks
        like [True True False True] means that nodes 0, 1 
        and 3 are reachable from node K.
        
        Time Complexity: O(V * (V + E)) = O(V^2 + V * E), where
        V = number of vertices and E the number of edges.
        """
        nodes = len(graph)
        return [adjacent_nodes(graph, node) for node in range(nodes)]
    
    
    def minimal_nodes_set(graph):
        """Return the minimal set of nodes needed to reach
        all the nodes of the graph.
        
        Time Complexity: O(V^2)."""
        graph_size = len(graph)
        node_followers = followers_per_node(graph)
        solution = set(range(graph_size))
    
        # TC: O(V^2)
        # If a node K is reachable from a node J, that means that K
        # and J are part of the same graph and that K is not part
        # of the solution.
        for node in range(graph_size):
            for comparison_node, followers in enumerate(node_followers):
                if comparison_node == node:
                    continue
    
                if followers[node] and node in solution:
                    solution.remove(node)
    
        return solution
    
    
    if __name__ == "__main__":
        g1 = [[1, 1, 0, 0, 0, 0],
              [1, 1, 1, 0, 0, 0],
              [0, 0, 1, 0, 0, 0],
              [0, 1, 0, 1, 0, 0],
              [0, 0, 0, 0, 1, 1],
              [0, 0, 0, 0, 0, 1]]
        print(minimal_nodes_set(g1))  # => {2, 5}
    
        g2 = [[1, 0],
              [0, 1]]
        print(minimal_nodes_set(g2))  # => {0, 1}
    
        g3 = [[1, 0],
              [1, 1]]
        print(minimal_nodes_set(g3))  # => {0}
    

  • 0
    D

    What if you found all vertices with no incoming edges and started BFS from those vertices? If you run out of vertices with no incoming edges, then that means the rest of the vertices are either in a cycle or completely separated.

    Each time you have to search from a new vertex, you would add 1 to your overall total vertices required.

    Effectively you would run DFS on each "connected component", making the overall runtime O(E + V) to find the number of necessary vertices to explore all other vertices.

    Is this a viable solution or am I mistaken?


  • 3
    E

    It's the number of strongly-connected components that aren't reachable from any outside vertex.
    http://www.geeksforgeeks.org/strongly-connected-components/


  • 0
    R

    @danielcplau said in Digraph - Cover all vertices with the least number of vertices:

    What if you found all vertices with no incoming edges and started BFS from those vertices? If you run out of vertices with no incoming edges, then that means the rest of the vertices are either in a cycle or completely separated.

    Each time you have to search from a new vertex, you would add 1 to your overall total vertices required.

    Effectively you would run DFS on each "connected component", making the overall runtime O(E + V) to find the number of necessary vertices to explore all other vertices.

    Is this a viable solution or am I mistaken?

    I think your solution should be valid. How would you find the vertices with no incoming edges?, and what time complexity would have the operation?


  • 0
    R

    @elastico said in Digraph - Cover all vertices with the least number of vertices:

    It's the number of strongly-connected components that aren't reachable from any outside vertex.
    http://www.geeksforgeeks.org/strongly-connected-components/

    What if you have a graph like this:

      B --> A
      
      C --> A
    

    How many strongly connected components are there? The solution to this case should be 2 nodes (B, C). Because node A is reachable from both B and C. If there are 2 strongly connected components, then I think you are right.


  • 0
    D

    @ricg You keep track when you're building the graph of directed vertices, so whenever node A points to node B, node B's incoming edges increase by one. At the end of this you do a quick search and keep track of all vertices with no incoming edges. Should be no more than O(E + V)


  • 3
    E

    @ricg Strongly-connected components that are not reachable by outside vertex.

    There are 3 strongly-connected components A,B,C but A has incoming edge while B and C do not.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.