Раскраска графа в питоне с использованием матрицы смежности

Question

Как я могу реализовать раскраску графа в Python, используя матрицу смежности?Является ли это возможным?Я реализовал это, используя список.Но у него есть некоторые проблемы.Я хочу реализовать это с помощью матрицы.Кто-нибудь может дать мне ответ или предложение на это?

Answer 1

Возможно ли это? Да, конечно. Но есть ли у вас проблемы с созданием графиков или алгоритмов кодирования, которые имеют с ними дело?

Отделение алгоритма от типа данных может упростить вам задачу. Вот пара предложений:

• создать (или использовать) абстрактный тип данных Graph
• код алгоритма раскраски против интерфейса Graph
• затем измените реализацию Graph между списком и матричной формой

Если вы просто хотите использовать Графики, и вам не нужно реализовывать их самостоятельно, быстрый поиск в Google обнаружил эту библиотеку python graph .

Answer 2

Реализация с использованием смежности несколько проще, чем использование списков, поскольку списки занимают больше времени и пространства. У igraph есть быстрый метод соседей, который можно использовать. Однако, используя только матрицу смежности, мы можем предложить собственную версию раскраски графа, которая может не привести к использованию минимального хроматического числа. Быстрая стратегия может быть следующей: Initalize: поместите один отдельный цвет для узлов в каждой строке (где появляется 1) Начало: Используя в качестве ссылки строку узла наивысшей степени (HDN), сравните каждую строку (имеется в виду каждый узел) с HDN и посмотрите, является ли она также его соседом, обнаружив 1. Если да, то измените цвет этих узлов. Продолжайте так, чтобы точно настроить. O (N ^ 2) подход! Надеюсь это поможет.