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:虽然本人的方法有一些愚见,本人就抛砖引玉了
相关文章
- 我们在使用C#做项目的时候,基本上都需要制作登录界面,那么今天我们就来一步步看看,如果简单的实现登录界面呢,本文给出2个例子,由简入难,希望大家能够喜欢。...2020-06-25
- 这篇文章主要介绍了C# 字段和属性的的相关资料,文中示例代码非常详细,供大家参考和学习,感兴趣的朋友可以了解下...2020-11-03
- 这篇文章主要介绍了C#中截取字符串的的基本方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-11-03
- 这篇文章主要介绍了C#实现简单的Http请求的方法,以实例形式较为详细的分析了C#实现Http请求的具体方法,需要的朋友可以参考下...2020-06-25
- 本文给大家分享C#连接SQL数据库和查询数据功能的操作技巧,本文通过图文并茂的形式给大家介绍的非常详细,需要的朋友参考下吧...2021-05-17
- 本文主要介绍了C#中new的几种用法,具有很好的参考价值,下面跟着小编一起来看下吧...2020-06-25
使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序)
这篇文章主要介绍了使用Visual Studio2019创建C#项目(窗体应用程序、控制台应用程序、Web应用程序),小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25- 这篇文章主要介绍了C#开发Windows窗体应用程序的简单操作步骤,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-04-12
- 这篇文章主要介绍了C#从数据库读取图片并保存的方法,帮助大家更好的理解和使用c#,感兴趣的朋友可以了解下...2021-01-16
- 最近做一个小项目不可避免的需要前端脚本与后台进行交互。由于是在asp.net中实现,故问题演化成asp.net中jiavascript与后台c#如何进行交互。...2020-06-25
- 本文通过例子,讲述了C++调用C#的DLL程序的方法,作出了以下总结,下面就让我们一起来学习吧。...2020-06-25
- 轻松学习C#的基础入门,了解C#最基本的知识点,C#是一种简洁的,类型安全的一种完全面向对象的开发语言,是Microsoft专门基于.NET Framework平台开发的而量身定做的高级程序设计语言,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C#变量命名规则小结,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-09-09
- 这篇文章主要介绍了C#绘制曲线图的方法,以完整实例形式较为详细的分析了C#进行曲线绘制的具体步骤与相关技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 本文主要介绍了C# 中取绝对值的函数。具有很好的参考价值。下面跟着小编一起来看下吧...2020-06-25
- 这篇文章主要介绍了c#自带缓存使用方法,包括获取数据缓存、设置数据缓存、移除指定数据缓存等方法,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了c#中(&&,||)与(&,|)的区别详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 这篇文章主要用实例讲解C#递归算法的概念以及用法,文中代码非常详细,帮助大家更好的参考和学习,感兴趣的朋友可以了解下...2020-06-25
- 下面小编就为大家带来一篇C#学习笔记- 随机函数Random()的用法详解。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-06-25
- 这篇文章主要介绍了C#中list用法,结合实例形式分析了C#中list排序、运算、转换等常见操作技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25