试设计一个求有向无环图中最长路径的算法，并估计其时间复杂度。
【解答】算法如下：int maxlen，path[MAXSIZE]; //数组path用于存储当前路径[br][/br]int mlp[MAXSIZE]; //数组mlp用于存储已发现的最长路径[br][/br]void Get_Longest_Path(ALGraph G)//求一个有向无环图中最长的路径[br][/br]{[br][/br] maxlen=0;[br][/br] FindIndegree(G，indegree);[br][/br] for(i=0;imaxlen&&!G.vertices[i].firstarc) //新的最长路径[br][/br]{[br][/br] for(j=0;j<=len;j++) mlp[j]=path[j]; //保存下来[br][/br] maxlen=len;[br][/br]}[br][/br]else[br][/br]{[br][/br] for(p=G.vertices[i].firstarc;p;p=p->nextarc)[br][/br]{[br][/br] j=p->adjvex;[br][/br] if(!visited[j]) DFS(G，j，len+1);[br][/br] }[br][/br] }//else[br][/br]path[i]=0;[br][/br]visited[i]=0;[br][/br]}//DFS[br][/br]该算法的时间复杂度为[tex=2.5x1.286]1OtWqy85i+gT8VdJzbl6IA==[/tex]。
举一反三
内容
- 0
对于有n个顶点e条边的有向图，求最短路径的Floyd算法的时间复杂度为________
- 1
设计一个基于内部顶点概念的算法，求有向图中两个顶点之间的最长路径的长度，或确定在这些顶点之间存在任意长度的路径。
- 2
中国大学MOOC: 对于有 n 个顶点 e 条边的有向图，求最短路径的 Floyd 算法的时间复杂度为（ ）。
- 3
中国大学MOOC: 对于有 n 个顶点 e 条边的有向图，求最短路径的 Dijkstra 算法的时间复杂度为（ ）。
- 4
上题中判断有向无环图（DAG）是否存在哈密顿路径的算法的时间复杂度是____（请选择最准确项