使用邻接矩阵在Python中图着色
我想知道怎么用邻接矩阵在Python中实现图着色。这样做可以吗？我之前用列表实现过，但遇到了一些问题。现在我想用矩阵来实现。有没有人能给我一些答案或建议呢？
2 个回答
0
用邻接矩阵来实现图的处理比用列表简单一些，因为列表需要更多的时间和空间。igraph库里有个快速的方法叫做neighbors，可以用来找邻居节点。不过，仅仅用邻接矩阵，我们也可以自己想出一种图着色的方法，但可能不会得到最小的颜色数。这里有个简单的策略：
初始化：给每一行的节点（也就是有1的地方）上一个不同的颜色。
开始：以度数最高的节点（HDN）所在的行作为参考，比较每一行（也就是每个节点）和HDN，看它们是否是邻居，方法是检查是否有1。如果是邻居，就把那个节点的颜色改掉。接着这样继续调整，直到满意为止。这种方法的时间复杂度是O(N^2)！希望这对你有帮助。
3
这可能吗？当然可以。不过，你的问题是出在制作图形上，还是在编写处理图形的算法上呢？
把算法和数据类型分开可能会让你更容易理解。这里有几个建议：
- 创建（或使用）一个抽象数据类型“图”（Graph）
- 根据图的接口来编写着色算法
- 然后，可以在列表和矩阵的不同实现之间进行变化
如果你只是想使用图形，而不需要自己实现它们，快速在谷歌上搜索一下，找到了这个 python图形库。