1

I need to write an algorithm that, given a social network represented as a graph, finds out if a set of people X form a close relationship. This means that every person in X has a relation with each other.

For example if we have the graph:

enter image description here

The set {H,B,O} form a close friendship since every person in the subgraph is connected to each other.

The set {O,F,K} does not since we can't go from O to F

How would pseudocode for this specific algorithm look like?

1

1 Answer 1

1

What you are asking for is searching for a Clique.

Bron-Kerbosch algorithm will find that for you

BronKerbosch1(R, P, X):
       if P and X are both empty:
           report R as a maximal clique
       for each vertex v in P:
           BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))
           P := P \ {v}
           X := X ⋃ {v}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.