The number of critical nodes in an undirected graph

Question

I have a graph G containing N nodes and E edges. Each edge is non-directional. The goal is to find no. important nodes.

A node that makes a graph disconnected when it is deleted is called a critical node. The goal is to find no. such nodes in the graph.

The solution will be: -

For each node belonging to the graph, remove it from the graph, select a node from the remaining graph, execute dfs, if we can reach everywhere, then this is not important node.

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

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

Answer 1

The most important node is node, which when deleted will reduce the graph by 2 or more disjoint subgraphs.

Thus, the key node is a node that is connected to 2 or more subgraphs that are connected only through this important node ..

A possible solution could be this:

• For each node, I'm in column G:

  • list L: all nodes directly connected to node i

  • if there are 2 nodes u and v in the list L, so there is no path that connects u with v not even i, then I am a critical node

Link: 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; } }