CODEWITHSUNDEEP
graphdepth-first-search
Sr1n4th
Sr1n4th

Reputation: 251

Number of crucial nodes in an Undirected graph

I have a graph G containing N nodes and E edges.Each edge is undirectional.The goal is to find the no. of crucial nodes.

A node which makes the graph disconnected when it is removed is called a crucial node. The goal is to find the no. of such nodes in the graph.

A solution would be:-

For each node belonging to the graph, remove it from the graph, pick a node from the remaining graph, perform dfs, if we are able to reach everywhere then it is not a crucial node.

This solution is O(N*E) or worst case O(N^3).

Is there a O(N^2) solution or O(E) solution because N^3 is a bit too slow.

Upvotes: 4

Views: 185

Answers (1)

Khaled.K
Khaled.K

Reputation: 5940

A crucial node is a node that when removed, will cut the graph into 2 or more disjoint sub-graphs ..

Thus, a crucial node is a node that is connected to 2 or more sub-graphs that are only connected through this crucial node ..

A possible solution might be like this:

  • For every node i in the graph G:

    1. list L: all nodes directly connected to to node i

    2. if there exist 2 nodes u and v in list L such that there is no path that connect u by v not though i, then i is a crucial node

Reference: Wikipedia:Cycle Detection

Example (in Java):

public class CrucialNode
{
    public static ArrayList<Node> crucialVertices (Graph g)
    {
        ArrayList<Node> crucial = new ArrayList<Node> ();

        for (Node n : g.getV()) if (isCrucial(g,n)) crucial.add(n);

        return crucial;
    }

    public static boolean isCrucial (Graph g, Node n)
    {
        Graph h = new Graph(g);

        h.removeVertex(n);

        for (Node u : n.getNext())
        {
            for (Node v : n.getNext())
            {
                if (u.equals(v)) continue;

                if (!h.connected(u,v)) return true;
            }
        }

        return false;
    }
}

Upvotes: 2

Related Questions