源码网商城,靠谱的源码在线交易网站 我的订单 购物车 帮助

源码网商城

C#中 城市线路图的纯算法以及附带求极权值

  • 时间:2022-02-11 00:48 编辑: 来源: 阅读:
  • 扫一扫,手机访问
摘要:C#中 城市线路图的纯算法以及附带求极权值
之前看了很多关于图的遍历的代码 今天我用了常用的数据结构写出来 纯属于算法 性方面还有待提高 时间复杂度最坏情况下O(2^n)  最优:O(n^2) 线路图为双向 带有权值  比如A-B距离是5000km 那么B-A有可能不是5000km 所以我在LoadData方法时候没做交换变量直接存放在集合里面 以起点递归查找下一连接点并返回当作起点节点查找      代码虽然有些乱 本想调整 !
[u]复制代码[/u] 代码如下:
  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;         }  
以下是测试结果:
[u]复制代码[/u] 代码如下:
以重庆开始的所以可能路线 //全部线路图 begin 重庆-北京 重庆-广州 重庆-北京-广州 重庆-北京-长沙 重庆-广州-北京 重庆-广州-长沙 重庆-广州-厦门 重庆-广州-云南 重庆-北京-广州-长沙 重庆-北京-广州-厦门 重庆-北京-广州-云南 重庆-北京-长沙-广州 重庆-北京-长沙-厦门 重庆-北京-长沙-云南 重庆-广州-北京-长沙 重庆-广州-长沙-北京 重庆-广州-长沙-厦门 重庆-广州-长沙-云南 重庆-广州-厦门-长沙 重庆-广州-厦门-云南 重庆-广州-云南-长沙 重庆-广州-云南-厦门 重庆-北京-广州-长沙-厦门 重庆-北京-广州-长沙-云南 重庆-北京-广州-厦门-长沙 重庆-北京-广州-厦门-云南 重庆-北京-广州-云南-长沙 重庆-北京-广州-云南-厦门 重庆-北京-长沙-广州-厦门 重庆-北京-长沙-广州-云南 重庆-北京-长沙-厦门-广州 重庆-北京-长沙-厦门-云南 重庆-北京-长沙-云南-广州 重庆-北京-长沙-云南-厦门 重庆-广州-北京-长沙-厦门 重庆-广州-北京-长沙-云南 重庆-广州-长沙-厦门-云南 重庆-广州-长沙-云南-厦门 重庆-广州-厦门-长沙-北京 重庆-广州-厦门-长沙-云南 重庆-广州-厦门-云南-长沙 重庆-广州-云南-长沙-北京 重庆-广州-云南-长沙-厦门 重庆-广州-云南-厦门-长沙 重庆-北京-广州-长沙-厦门-云南 重庆-北京-广州-长沙-云南-厦门 重庆-北京-广州-厦门-长沙-云南 重庆-北京-广州-厦门-云南-长沙 重庆-北京-广州-云南-长沙-厦门 重庆-北京-广州-云南-厦门-长沙 重庆-北京-长沙-广州-厦门-云南 重庆-北京-长沙-广州-云南-厦门 重庆-北京-长沙-厦门-广州-云南 重庆-北京-长沙-厦门-云南-广州 重庆-北京-长沙-云南-广州-厦门 重庆-北京-长沙-云南-厦门-广州 重庆-广州-北京-长沙-厦门-云南 重庆-广州-北京-长沙-云南-厦门 重庆-广州-厦门-云南-长沙-北京 重庆-广州-云南-厦门-长沙-北京 count:61 //全部线路图 end    搜索重庆到厦门的线路图 //重庆到厦门begin 重庆-广州-厦门 重庆-北京-广州-厦门 重庆-北京-长沙-厦门 重庆-广州-长沙-厦门 重庆-广州-云南-厦门 重庆-北京-广州-长沙-厦门 重庆-北京-广州-云南-厦门 重庆-北京-长沙-广州-厦门 重庆-北京-长沙-云南-厦门 重庆-广州-北京-长沙-厦门 重庆-广州-长沙-云南-厦门 重庆-广州-云南-长沙-厦门 重庆-北京-广州-长沙-云南-厦门 重庆-北京-广州-云南-长沙-厦门 重庆-北京-长沙-广州-云南-厦门 重庆-北京-长沙-云南-广州-厦门 重庆-广州-北京-长沙-云南-厦门 count:17 权最大为:重庆-广州-北京-长沙-云南-厦门:17300 权最小为:重庆-广州-厦门:3000 //重庆到厦门end
最后ps:虽然本人的方法有一些愚见,本人就抛砖引玉了
  • 全部评论(0)
联系客服
客服电话:
400-000-3129
微信版

扫一扫进微信版
返回顶部