CODEWITHSUNDEEP
algorithmgraphgraph-theory
Domel
Domel

Reputation: 29

Find groups in a graph

Is there any algorithm that allows me to make groups in a graph? When I write about the group, I mean graph nodes in the group: a parent-node, and child-nodes. There must be one parent and at least one child in such a group. Groups are marked in yellow in the figure. I present two graphs with that groups. Graph nodes are in the groups only if they are closest to the outer part of the graph. Nodes in the middle of the graph are not important to me.

Is there any algorithm to solve that problem? Or do you know a graph problem that is near to my?

Groups

Upvotes: 0

Views: 1103

Answers (2)

Mu-hammed Aly
Mu-hammed Aly

Reputation: 11

If you have a graph and you need to split it into several groups by yourself or by specific query you can use DSU algorithm by adding the chosen nodes to specific parent so that you'll build several components(groups).

Upvotes: 0

n8o
n8o

Reputation: 1943

I think if a node has only one edge, it will be a node of a group.

So first, find all nodes which has only one edge. And group the node with its neighbor node. It would be a group you want to find.

Finally, if there an intersection between two groups, combine the groups and make one group recursively.

Upvotes: 1

Related Questions