已知一个图的邻接矩阵,怎样找出图中所有的圈?

来源:学生作业帮助网 编辑:作业帮 时间:2024/05/05 21:45:13
已知一个图的邻接矩阵,怎样找出图中所有的圈?

已知一个图的邻接矩阵,怎样找出图中所有的圈?
已知一个图的邻接矩阵,怎样找出图中所有的圈?

已知一个图的邻接矩阵,怎样找出图中所有的圈?
看一下邻接矩阵 主对角线 的值,如果第i行i列值为0,则所对应的第i个点没有圈,否则有圈.

假设邻接矩阵为A,Aij(矩阵A的i行j列元素值)表示从第i个节点经过一条边到达节点j的长度,也就是各条边的长度,所以A的对角线元素全为0.
计算B = A*A,那么Bij的值表示从第i个节点经过两条边到达节点j的长度
如此往复,不断计算A*A*A, A*A*A*A...如果某个矩阵对角线元素不等于零,说明有圈,而且你还知道此圈由多少条边形成。...

全部展开

假设邻接矩阵为A,Aij(矩阵A的i行j列元素值)表示从第i个节点经过一条边到达节点j的长度,也就是各条边的长度,所以A的对角线元素全为0.
计算B = A*A,那么Bij的值表示从第i个节点经过两条边到达节点j的长度
如此往复,不断计算A*A*A, A*A*A*A...如果某个矩阵对角线元素不等于零,说明有圈,而且你还知道此圈由多少条边形成。

收起