0 结果
1 题目
2 思路
遍历邻接矩阵的每一行和列的非零元素的个数,来统计每个顶点的度(出度和入度和),并记录度为奇数的顶点个数,若个数为0或2,则返回1,否则返回0。
空间复杂度:O(1)
时间复杂度:O(n2)
3 实现
#include<iostream>
#include <vector>
const int MAXV = 6;
typedef struct{
int numVertices,numEdges;
char VerticeList[MAXV];
int Edge[MAXV][MAXV];
}MGraph;
int IsExistEL(MGraph G){
int degree, count = 0;
for (int i = 0; i < G.numVertices; i++) {
degree = 0;
for (int j = 0; j < G.numVertices; ++j) {
degree += G.Edge[i][j];
if(degree % 2 != 0) count++;
}
}
if(count == 0 || count == 2){
return 1;
}else{
return 0;
}
}
int main(){
MGraph G;
for (int i = 0; i < MAXV; ++i) {
for (int j = 0; j < MAXV; ++j) {
G.Edge[i][j] = 0;
}
}
G.Edge[0][1] = 1;
G.Edge[0][3] = 1;
G.Edge[1][0] = 1;
G.Edge[1][2] = 1;
G.Edge[1][4] = 1;
G.Edge[2][1] = 1;
G.Edge[2][3] = 1;
G.Edge[2][4] = 1;
G.Edge[3][0] = 1;
G.Edge[3][2] = 1;
G.Edge[4][1] = 1;
G.Edge[4][2] = 1;
G.numVertices = 5;
G.numEdges = 6;
G.VerticeList[0] = '1';
G.VerticeList[1] = '2';
G.VerticeList[2] = '3';
G.VerticeList[3] = '4';
G.VerticeList[4] = '5';
std::string res = IsExistEL(G)?"是":"否";
std::cout<<"是否存在EL路径:"<<res;
return 0;
}
附录
408历年真题算法题解析
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)