Найти все группы соседних узлов графа
У меня есть график и это узлы смежной матрицы. Проблема заключается в том, чтобы найти все узлы, смежные "все ко всем". Например (на картинке) результат должен быть [1,2,3,7] все эти узлы соединены вместе. Для любого вида графа мне нужно получить список всех "всех ко всем" узлов. Как это решить? Благодарю.
1 ответ
Решение
Вы пытаетесь найти клику в графе. Поиск подграфа, являющегося кликой в NP, завершает задачу. Вы можете прочитать материал здесь http://www.dfki.de/~neumann/ie-seminar/presentations/finding_cliques.pdf Они упомянули несколько методов здесь.