[BiO BB] Script to extract connected subgraphs

Sourangshu Bhattacharya sourangshu at csa.iisc.ernet.in
Sat Jan 28 11:20:00 EST 2006

Just run Breadth First Search (BFS) or Depth First Search (DFS) from 
starting from a random vertex and keep marking the vertices you visit.
when you have got to all the vertices reachable from any of the nodes
(the BFS or DFS ends), start the same with a vertex not visited yet.
At the end of each BFS or DFS you get one connected component. when all 
the vertices are visited, you get all the components !!


Sourangshu Bhattacharya
PhD Student,
Dept. of Computer Science & Automation,
IISc, Bangalore.


On Fri, 27 Jan 2006, Samantha Fox wrote:

> HI again !!
> I was looking for suggestions on how to find connected sub-graphs ?
> I have an undirected graph, and want to find connected sub-graph(s) and then
> ascertain the largest of them.
> Can someone suggest a script or modue that I can make use of ?
> Thanks !
> ~S

More information about the BBB mailing list