使用邻接矩阵在Python中进行图形着色
如何使用邻接矩阵在 python 中实现图形着色？是否可以？我使用列表来实现它。但它有一些问题。我想用矩阵来实现它。有人可以给我答案或建议吗？
How can I implement graph colouring in python using adjacency matrix? Is it possible? I implemented it using list. But it has some problems. I want to implement it using matrix. Can anybody give me the answer or suggestions to this?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
是否可以？是的当然。但是您在制作图表或处理图表的编码算法方面遇到问题吗？
将算法与数据类型分开可能会让您更轻松。这里有一些建议：
如果您只想使用图形，而不需要实现他们自己，通过 Google 快速搜索就找到了这个 python graph 库。
Is it possible? Yes, of course. But are your problems with making Graphs, or coding algorithms that deal with them?
Separating the algorithm from the data type might make it easier for you. Here are a couple suggestions:
If you just want to use Graphs, and don't need to implement them yourself, a quick Google search turned up this python graph library.
使用邻接实现比使用列表更容易一些，因为列表需要更长的时间和空间。 igraph有一个可以使用的快速方法neighbors。然而，仅使用邻接矩阵，我们就可以提出我们自己的图形着色版本，这可能不会导致使用最小色数。快速策略可能如下：
初始化：为每行上的节点设置一种不同的颜色（其中出现 1）
开始：以最高度节点 (HDN) 行作为参考，将每一行（即每个节点）与 HDN 进行比较，通过检测 1 来查看它是否也是其邻居。如果是，则更改该节点的颜色。如此进行微调。 O(N^2) 方法！希望这有帮助。
Implementing using adjacency is somewhat easier than using lists, as lists take a longer time and space. igraph has a quick method neighbors which can be used. However, with adjacency matrix alone, we can come up with our own graph coloring version which may not result in using minimum chromatic number. A quick strategy may be as follows:
Initalize: Put one distinct color for nodes on each row (where a 1 appears)
Start: With highest degree node (HDN) row as a reference, compare each row (meaning each node) with the HDN and see if it is also its neighbor by detecting a 1. If yes, then change that nodes color. Proceed like this to fine-tune. O(N^2) approach! Hope this helps.