Запись программы, чтобы проверить, является ли график двусторонним
Я должен записать программу, которые проверяют, является ли график двусторонним.
Я прочитал статьи Википедии об окраске графика и биграфе. Эта статья двух предлагает, чтобы методы протестировали двусторонний как поиск BFS, но я не могу записать программу, реализовав эти методы.
1 ответ
Почему ты не можешь? Ваш вопрос мешает кому-то даже написать программу для вас, поскольку вы даже не упоминаете конкретный язык ...
Идея состоит в том, чтобы начать с помещения случайного узла в очередь FIFO (также здесь ). Раскрасьте его в синий цвет. Затем повторите это, пока в очереди еще остались узлы: удалите элемент из очереди. Раскрасьте его соседей цветом, отличным от цвета извлеченного элемента, и вставьте (поставьте в очередь) каждого соседа в очередь FIFO. Например, если вы удаляете из очереди (извлекаете) элемент (узел), окрашенный в красный цвет, окрашивайте его соседей в синий цвет. Если вы извлечете синий узел, закрасьте его соседей в красный цвет. Если нет конфликтов раскраски, граф двудольный. Если вы закрасите узел двумя разными цветами, значит, он не двудольный.
Как сказал @Moron, то, что я описал, будет работать только для связанных графов. Однако вы можете применить один и тот же алгоритм к каждому связанному компоненту, чтобы он работал для любого графа.