分割二分图的邻接矩阵
假设我有一个带有邻接矩阵A的图G.我知道G是二分的。
如何将G中的顶点分成总是形成二分图的两个集合？
谢谢！
没有找到相关结果
已邀请:
1 个回复
蓄荣糖些
，最初将每个元素设置为0。然后在图表中执行深度优先搜索，记录您所使用的“级别编号”。这从1开始，并且在每个边缘遍历时交替在1和2之间。对于到达的每个顶点，将当前级别分配给相应的条目，并且（如果之前为0）递归以处理其子级。之后，的所有元素将为1或2，而表示哪个集合顶点属于。 直观地说，你可以想象在DFS中从父到子的每次遍历都会让你“向下”一个级别，每次遍历都会让你“向上”。通过二分属性，偶数级上的所有顶点可以仅连接到奇数级上的顶点，反之亦然，因此标记节点“偶数”或“奇数”足以将它们分成两组。 如果您的图形包含多个组件，则每个组件当然需要单独的DFS。