文章
87
粉丝
0
获赞
0
访问
9.5k
(1)1.将所有点的度数统计出来;2.找出度为奇数的点;3.判断该类型的点的个数是否小于等于2.
(2)int IsExistEL(MGraph G) {
int degrees[G.nV];
memset(degrees, 0, sizeof(degrees));
// 遍历无向图统计所有点的度
for (int i = 0; i < G.nV; i++) {
for (int j = 0; j < G.nV; j++) {
degrees[i] += G.E[i][j];
}
}
int count = 0;
// 遍历degrees数组统计度为奇数的点的个数
for (int i = 0; i < G.nV; i++) {
if (degrees[i] % 2 != 0) {
count++;
}
}
// 检查度为奇数的点个数是否为0或者2
if (count == 0 || count == 2) {
return 1; // 存在EL路径
} else {
return 0; // 不存在EL路径
}
}
(3)时间复杂度O(n^2)空间复杂度O(n)
登录后发布评论
暂无评论,来抢沙发