[BiO BB] Script to extract connected subgraphs

[Sourangshu Bhattacharya]

Hi,
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

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

http://people.csa.iisc.ernet.in/sourangshu


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
>