search

anvaka / ngraph.graph

Graph data structure in JavaScript
BSD 3-Clause "New" or "Revised" License
520 stars 66 forks source link

Finding total of linked nodes? #18

Closed githubuser3141 closed 5 years ago

githubuser3141 commented 5 years ago

Sorry if this is outside the scope of the project, but could you advise on ways to find groups of linked nodes in the graph? I needed to count their total.

Many thanks

anvaka commented 5 years ago

The algorithm for finding all connected components is straightforward. We perform BFS/DFS search from each node and mark visited nodes with a given label. If node was not labeled after BFS/DFS is completed, it means we found a new component. So we create a new label and keep iterating.

Here is a code with example: https://github.com/anvaka/ngraph.graph/blob/master/examples/findConnectedComponents.js

githubuser3141 commented 5 years ago

Thank you very much for this and all your work!