C#中 城市线路图的纯算法以及附带求极权值
之前看了很多关于图的遍历的代码
今天我用了常用的数据结构写出来 纯属于算法 性方面还有待提高 时间复杂度最坏情况下o(2^n) 最优：o(n^2)
线路图为双向 带有权值 比如a-b距离是5000km 那么b-a有可能不是5000km 所以我在loaddata方法时候没做交换变量直接存放在集合里面
以起点递归查找下一连接点并返回当作起点节点查找 代码虽然有些乱 本想调整 ！
static list<string[]> maindata = null;
static int isend = 1;
static list<string> fresult = new list<string>();
static void main(string[] args)
{
string begin = "重庆";
string end = "厦门";
loaddata();
program pl = new program();
list<string> beginlist = new list<string>();
beginlist.add(begin);
pl.getf(beginlist);
foreach (string a in fresult)
console.writeline(a);
console.writeline(fresult.count);
//main data end
list<string> searchlist = new list<string>();
string temp = "";
foreach (string f in fresult)
{
if (f.indexof(end) > -1)
{
temp = f.substring(0, f.lastindexof(end) + end.length);
if (searchlist.contains(temp) == false)
searchlist.add(temp);
}
}
console.writeline(begin + "------------->" + end + ":");
foreach (string a in searchlist)
console.writeline(a);
console.writeline(searchlist.count);
//search data a to b
string a1 = "权最大为:" + getmaxquk(searchlist);
console.writeline(a1);
a1 = "权最小为:" + getminquk(searchlist);
console.writeline(a1);
console.readkey();
}
取最大的权值数据
private static string getmaxquk(list<string> nage)
{
string resultsrt = "";
string[] nagearry = null;
int val, maxval = 0;
for (int s = 0; s < nage.count; s++)
{
nagearry = nage[s].split('-');//s个数组
val = getval(nagearry);
if (val > maxval)
{
maxval = val;
resultsrt = nage[s] + ":" + val;
}
nagearry = null;
}
return resultsrt;
}
取最小的权值数据
private static string getminquk(list<string> nage)
{
string resultsrt = "";
string[] nagearry = null;
int val, minval = int.maxvalue;
for (int s = 0; s < nage.count; s++)
{
nagearry = nage[s].split('-');//s个数组
val = getval(nagearry);
if (val < minval)
{
minval = val;
resultsrt = nage[s] + ":" + val;
}
nagearry = null;
}
return resultsrt;
}
具体取权值的方法
private static int getval(string[] findarry)
{
int val = 0;
for (int ss = 0; ss < findarry.length - 1; ss = ss + 1)
{
foreach (string[] aa in maindata)
{
if (aa[0] == findarry[ss] && aa[1] == findarry[ss + 1])
{
val += convert.toint32(aa[2]);
break;
}
}
}
return val;
}
list<string> getf(list<string> beginlist)
{
//此处省略几十行代码 需要完整代码请联系an
if (isend == 0)
return getf(returnlist);
else
return null;
}
加载绑定数据
static void loaddata()
{
list<string[]> backlist = null;
string[] arry = null;
backlist = new list<string[]>();
arry = new string[3];
arry[0] = "重庆";
arry[1] = "北京";
arry[2] = "3000";
backlist.add(arry);
arry = null;
arry = new string[3];
arry[0] = "重庆";
arry[1] = "广州";
arry[2] = "2500";
backlist.add(arry);
arry = null;
arry = new string[3];
arry[0] = "北京";
arry[1] = "重庆";
arry[2] = "3000";
backlist.add(arry);
arry = null;
arry = new string[3];
arry[0] = "北京";
arry[1] = "广州";
arry[2] = "3100";
backlist.add(arry);
arry = null;
arry = new string[3];
arry[0] = "北京";
arry[1] = "长沙";
arry[2] = "2800";
backlist.add(arry);
arry = null;
arry = new string[3];
arry[0] = "长沙";
arry[1] = "北京";
arry[2] = "2800";
backlist.add(arry);
arry = null;
arry = new string[3];
arry[0] = "长沙";
arry[1] = "广州";
arry[2] = "1500";
backlist.add(arry);
arry = null;
arry = new string[3];
arry[0] = "长沙";
arry[1] = "厦门";
arry[2] = "800";
backlist.add(arry);
arry = null;
arry = new string[3];
arry[0] = "广州";
arry[1] = "重庆";
arry[2] = "2500";
backlist.add(arry);
arry = null;
arry = new string[3];
arry[0] = "广州";
arry[1] = "北京";
arry[2] = "3100";
backlist.add(arry);
arry = null;
arry = new string[3];
arry[0] = "广州";
arry[1] = "长沙";
arry[2] = "1500";
backlist.add(arry);
arry = null;
maindata = backlist;
arry = new string[3];
arry[0] = "厦门";
arry[1] = "长沙";
arry[2] = "800";
backlist.add(arry);
arry = null;
arry = new string[3];
arry[0] = "厦门";
arry[1] = "广州";
arry[2] = "500";
backlist.add(arry);
arry = null;
arry = new string[3];
arry[0] = "广州";
arry[1] = "厦门";
arry[2] = "500";
backlist.add(arry);
arry = null;
arry = new string[3];
arry[0] = "广州";
arry[1] = "云南";
arry[2] = "3200";
backlist.add(arry);
arry = null;
arry = new string[3];
arry[0] = "云南";
arry[1] = "广州";
arry[2] = "3200";
backlist.add(arry);
arry = null;
arry = new string[3];
arry[0] = "云南";
arry[1] = "长沙";
arry[2] = "3500";
backlist.add(arry);
arry = null;
arry = new string[3];
arry[0] = "长沙";
arry[1] = "云南";
arry[2] = "3500";
backlist.add(arry);
arry = null;
arry = new string[3];
arry[0] = "云南";
arry[1] = "厦门";
arry[2] = "5400";
backlist.add(arry);
arry = null;
arry = new string[3];
arry[0] = "厦门";
arry[1] = "云南";
arry[2] = "5400";
backlist.add(arry);
arry = null;
}
以下是测试结果：
以重庆开始的所以可能路线
//全部线路图 begin
重庆-北京
重庆-广州
重庆-北京-广州
重庆-北京-长沙
重庆-广州-北京
重庆-广州-长沙
重庆-广州-厦门
重庆-广州-云南
重庆-北京-广州-长沙
重庆-北京-广州-厦门
重庆-北京-广州-云南
重庆-北京-长沙-广州
重庆-北京-长沙-厦门
重庆-北京-长沙-云南
重庆-广州-北京-长沙
重庆-广州-长沙-北京
重庆-广州-长沙-厦门
重庆-广州-长沙-云南
重庆-广州-厦门-长沙
重庆-广州-厦门-云南
重庆-广州-云南-长沙
重庆-广州-云南-厦门
重庆-北京-广州-长沙-厦门
重庆-北京-广州-长沙-云南
重庆-北京-广州-厦门-长沙
重庆-北京-广州-厦门-云南
重庆-北京-广州-云南-长沙
重庆-北京-广州-云南-厦门
重庆-北京-长沙-广州-厦门
重庆-北京-长沙-广州-云南
重庆-北京-长沙-厦门-广州
重庆-北京-长沙-厦门-云南
重庆-北京-长沙-云南-广州
重庆-北京-长沙-云南-厦门
重庆-广州-北京-长沙-厦门
重庆-广州-北京-长沙-云南
重庆-广州-长沙-厦门-云南
重庆-广州-长沙-云南-厦门
重庆-广州-厦门-长沙-北京
重庆-广州-厦门-长沙-云南
重庆-广州-厦门-云南-长沙
重庆-广州-云南-长沙-北京
重庆-广州-云南-长沙-厦门
重庆-广州-云南-厦门-长沙
重庆-北京-广州-长沙-厦门-云南
重庆-北京-广州-长沙-云南-厦门
重庆-北京-广州-厦门-长沙-云南
重庆-北京-广州-厦门-云南-长沙
重庆-北京-广州-云南-长沙-厦门
重庆-北京-广州-云南-厦门-长沙
重庆-北京-长沙-广州-厦门-云南
重庆-北京-长沙-广州-云南-厦门
重庆-北京-长沙-厦门-广州-云南
重庆-北京-长沙-厦门-云南-广州
重庆-北京-长沙-云南-广州-厦门
重庆-北京-长沙-云南-厦门-广州
重庆-广州-北京-长沙-厦门-云南
重庆-广州-北京-长沙-云南-厦门
重庆-广州-厦门-云南-长沙-北京
重庆-广州-云南-厦门-长沙-北京
count:61
//全部线路图 end
搜索重庆到厦门的线路图
//重庆到厦门begin
重庆-广州-厦门
重庆-北京-广州-厦门
重庆-北京-长沙-厦门
重庆-广州-长沙-厦门
重庆-广州-云南-厦门
重庆-北京-广州-长沙-厦门
重庆-北京-广州-云南-厦门
重庆-北京-长沙-广州-厦门
重庆-北京-长沙-云南-厦门
重庆-广州-北京-长沙-厦门
重庆-广州-长沙-云南-厦门
重庆-广州-云南-长沙-厦门
重庆-北京-广州-长沙-云南-厦门
重庆-北京-广州-云南-长沙-厦门
重庆-北京-长沙-广州-云南-厦门
重庆-北京-长沙-云南-广州-厦门
重庆-广州-北京-长沙-云南-厦门
count:17
权最大为:重庆-广州-北京-长沙-云南-厦门:17300
权最小为:重庆-广州-厦门:3000
//重庆到厦门end
最后ps：虽然本人的方法有一些愚见，本人就抛砖引玉了