Connected components from an adjacency matrix using Numpy or Scipy Connected components from an adjacency matrix using Numpy or Scipy numpy numpy

Connected components from an adjacency matrix using Numpy or Scipy


While you could indeed use DFS to find the connected components, SciPy makes it even easier with scipy.sparse.csgraph.connected_components. With your example:

In [3]: connected_components(test)                                                              Out[3]: (2, array([0, 0, 0, 1, 1, 1, 1], dtype=int32))


Well to start, you have an undirected graph. Look at the documentation again and set the directed parameter to false since the default is True.

The first array you get is the nodes reachable from where you start (node 0 = node a) including your starting node.So you start at node a and you can reach b and c. You can't reach the rest of the graph since you have a disconnected graph. DFS is doing what it is supposed to do. You will need to do DFS on the d node to get the second graph.