当前位置: 首页> 汽车> 车展 > 国外有没有类似小程序的应用_水印设计在线制作_搜索引擎营销的案例有哪些_广告策划案优秀案例

国外有没有类似小程序的应用_水印设计在线制作_搜索引擎营销的案例有哪些_广告策划案优秀案例

时间:2025/7/12 2:01:37来源:https://blog.csdn.net/m0_56332819/article/details/142856726 浏览次数: 0次
国外有没有类似小程序的应用_水印设计在线制作_搜索引擎营销的案例有哪些_广告策划案优秀案例

已知无向连通图G由顶点集V和边集E组成,|E| > 0,当G中度为奇数的顶点个数为不大于2的偶数时,G存在包含所有边且长度为|E|的路径(称为EL路径)。设图G采用邻接矩阵存储,类型定义如下:

typedef struct {                    // 图的定义int numVertices, numEdges;      // 图中实际的顶点数和边数char VerticesList[MAXV];        // 顶点表,MAXV为已定义常量int Edge[MAXV][MAXV];           // 邻接矩阵
}MGraph;

请设计算法int IsExistEL(MGraph G),判断G是否存在EL路径,若存在,则返回1 ,否则返回0。要求:

⑴ 给出算法的基本设计思想。

⑵ 根据设计思想,采用C或C++语言描述算法,关键之处给出注释。

⑶ 说明你所设计算法的时间复杂度和空间复杂度。

思想:从任意顶点开始深度优先遍历,每当该顶点与其他顶点存在一条边时,该顶点的度数加1,以此完成对所有顶点度的统计,最终要求度为奇数的顶点个数为0或者2。并且要求在遍历的过程中统计连通分量的个数,要求该图为连通图,则连通分量个数为1。

代码:

int countoddDegree==0 //统计度为奇数的顶点个数void DFS(MGraph G,int v,bool visited[]) {visited[v]==true;//访问该顶点int degree=0;//记录顶点的度for(int i=0;i<G.numvertices;++i){if(G.edges[v][i]!=0){//存在边 degree++;//度数+1 if(visited[i]==false){//顶点i还未被访问 DFS(G,v,visited);//深度优先i }}} if(degree%2==1){//度为奇数 countoddDegree++}
}
//以深度优先的方式来验证图是否为连通图 
DFSTraverse(MGraph G,int &numConnected){//统计访问情况bool *visited = (bool*)malloc(sizeof(bool)*G.numVertices);for(int v=0;v<G.numVertices;++v){//初始化visited数组 visited[v]=false;} for(int v=0;v<G.numVertices;++v){if(visited[v]==false){//未被访问,进行深度优先 numConnected++;// 统计连通分量的个数 +1DFS(G,v,visited);}} free(visited);
} 
//判断是否存在EL路径 
int isExistEL(MGraph G){int numConnected = 0;//统计连通分量的个数 DFSTraverse (G,numConnected);//连通分量为1表示图为连通的,度为奇数的顶点个数为0或者2 return numConnected==1&&(countoddDegree==0 ||countoddDegree==2) ? 1:0;
} 

时间复杂度O(n^2),空间复杂度O(n)

关键字:国外有没有类似小程序的应用_水印设计在线制作_搜索引擎营销的案例有哪些_广告策划案优秀案例

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: