1,v2,path,d,v ,f ); if(f lag ==0) // 输出没有路径算法的时空分析及改进设想因为图的邻接矩阵是一个| V|× |V| 矩阵,所以邻接矩阵的空间代价为Θ(|V|^2) ,对于有 n 个顶点的和 E 条弧的无向图而言, DFS 对每条边分别沿两个方向进行处理,且每个顶点必须被访问一次,所以总的时间代价为Θ(|V|+|E|) 。综上可知,该程序的时间复杂度为 Max (Θ(|V|^2) ,Θ(|V|+|E|) )。输入和输出的格式输入: 1. 输入城市的编号 for(i=0;i<n;i++) { cout<<" 每个城市的区号( 四位): "<<endl; cin>>v[i]; } 2. 输入查找的城市编号 cout<<" 输入要查找路径的两个城市区号: "<<endl; cin>>v1>>v2; 3. 输入不同两个城市的边的关系 cin>>v1>>v2; while((v1!=0)&&(v2!=0)) { n1=getNum(v,n,v1); n2=getNum(v,n,v2); T.setEdge(n1,n2); T.setEdge(n2,n1); cout<<" 输入不同两个城市的边的关系,区号用空格隔开: "<<endl; cin>>v1>>v2; } 输出: 1. 有简单路径 if (n==v1&&d>=1) { cout<<" 这两个城市间一条的简单路径为:"; flag=1; for (i=0;i<=d;i++) cout<<path[i]<<"-->"; // 输出该条路径} 2. 没有路径 if(f==0) cout<<" 查找的两城市间没有简单路径! "<<endl; 四、测试数据 1. 有路径,输入的图如下: 3000 4000 2000 1000 运行结果, 2. 没有简单路径,输入图如下: 1000 2000 运行结果,
全文预览
