文章
28
粉丝
19
获赞
0
访问
1.4k
(1)设置变量degree用来存储当前顶点的度,初始化count=0用于记录度为奇数的顶点个数
1.初始化degree=0遍历邻接矩阵中每个顶点所在行,若邻接矩阵中元素为1,则degree自增,否则不变;
2.遍历完后判断degree是否为奇数,若是count自增,此时若count大于2,则直接返回false;
3.若count为true,重复1,2直至顶点遍历完毕,此时存在EL回路,返回true
(2)
IsExistEL(MGraph G)
{
int count = 0 ;
for(int i = 0; i< G.numVertices; i++)
{
int degree = 0;
for(int j = 0; j< G.numVertices; j++)
{
if(G.Edge[i][j])
degree++;
}
if(degree%2 == 1)
count++;
if(count > 2)
break;
}
if(count <= 2)
return true;
return false;
}
(3) O(n^2), O(1)
登录后发布评论
暂无评论,来抢沙发