Алгоритм нахождения близких отношений в социальной сети (теория графов)

Question

Мне нужно написать алгоритм, который, учитывая социальную сеть, представленную в виде графа, выясняет, образует ли группа людей X близкие отношения . Это означает, что каждый человек в X имеет отношение друг к другу.

Например, если у нас есть график:

Множество {H, B, O} образует тесную дружбу, поскольку каждый человек в подграфе связан друг с другом.

Множество {O, F, K} нет, поскольку мы не можем перейти от O к F

Как будет выглядеть псевдокод для этого конкретного алгоритма?

Answer 1

Вы запрашиваете Клик .

алгоритм Брон-Кербоша найдет, что для вас

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}