欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2023-12-14 15:59:28
之前看了很多关于图的遍历的代码 今天我用了常用的数据结构写出来 纯属于算法 性方面还有待提高 时间复杂度最坏情况下o(2^n)  最优:o(n^2)线路图为双向...

之前看了很多关于图的遍历的代码

今天我用了常用的数据结构写出来 纯属于算法 性方面还有待提高 时间复杂度最坏情况下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:虽然本人的方法有一些愚见,本人就抛砖引玉了

上一篇:

下一篇: