C#中 城市線路圖的純算法以及附帶求極權(quán)值
之前看了很多關(guān)于圖的遍歷的代碼
今天我用了常用的數(shù)據(jù)結(jié)構(gòu)寫(xiě)出來(lái) 純屬于算法 性方面還有待提高 時(shí)間復(fù)雜度最壞情況下O(2^n) 最優(yōu)：O(n^2)
線路圖為雙向 帶有權(quán)值 比如A-B距離是5000km 那么B-A有可能不是5000km 所以我在LoadData方法時(shí)候沒(méi)做交換變量直接存放在集合里面
以起點(diǎn)遞歸查找下一連接點(diǎn)并返回當(dāng)作起點(diǎn)節(jié)點(diǎn)查找 代碼雖然有些亂 本想調(diào)整 ！
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 = "廈門(mén)";
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 = "權(quán)最大為:" + GetMaxQuk(searchlist);
Console.WriteLine(a1);
a1 = "權(quán)最小為:" + GetMinQuk(searchlist);
Console.WriteLine(a1);
Console.ReadKey();
}
取最大的權(quán)值數(shù)據(jù)
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個(gè)數(shù)組
val = GetVal(nagearry);
if (val > maxval)
{
maxval = val;
resultsrt = nage[s] + ":" + val;
}
nagearry = null;
}
return resultsrt;
}
取最小的權(quán)值數(shù)據(jù)
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個(gè)數(shù)組
val = GetVal(nagearry);
if (val < minval)
{
minval = val;
resultsrt = nage[s] + ":" + val;
}
nagearry = null;
}
return resultsrt;
}
具體取權(quán)值的方法
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)
{
//此處省略幾十行代碼 需要完整代碼請(qǐng)聯(lián)系an
if (isend == 0)
return GetF(returnlist);
else
return null;
}
加載綁定數(shù)據(jù)
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] = "長(zhǎng)沙";
arry[2] = "2800";
backlist.Add(arry);
arry = null;
arry = new string[3];
arry[0] = "長(zhǎng)沙";
arry[1] = "北京";
arry[2] = "2800";
backlist.Add(arry);
arry = null;
arry = new string[3];
arry[0] = "長(zhǎng)沙";
arry[1] = "廣州";
arry[2] = "1500";
backlist.Add(arry);
arry = null;
arry = new string[3];
arry[0] = "長(zhǎng)沙";
arry[1] = "廈門(mén)";
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] = "長(zhǎng)沙";
arry[2] = "1500";
backlist.Add(arry);
arry = null;
maindata = backlist;
arry = new string[3];
arry[0] = "廈門(mén)";
arry[1] = "長(zhǎng)沙";
arry[2] = "800";
backlist.Add(arry);
arry = null;
arry = new string[3];
arry[0] = "廈門(mén)";
arry[1] = "廣州";
arry[2] = "500";
backlist.Add(arry);
arry = null;
arry = new string[3];
arry[0] = "廣州";
arry[1] = "廈門(mén)";
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] = "長(zhǎng)沙";
arry[2] = "3500";
backlist.Add(arry);
arry = null;
arry = new string[3];
arry[0] = "長(zhǎng)沙";
arry[1] = "云南";
arry[2] = "3500";
backlist.Add(arry);
arry = null;
arry = new string[3];
arry[0] = "云南";
arry[1] = "廈門(mén)";
arry[2] = "5400";
backlist.Add(arry);
arry = null;
arry = new string[3];
arry[0] = "廈門(mén)";
arry[1] = "云南";
arry[2] = "5400";
backlist.Add(arry);
arry = null;
}
以下是測(cè)試結(jié)果：
以重慶開(kāi)始的所以可能路線
//全部線路圖 begin
重慶-北京
重慶-廣州
重慶-北京-廣州
重慶-北京-長(zhǎng)沙
重慶-廣州-北京
重慶-廣州-長(zhǎng)沙
重慶-廣州-廈門(mén)
重慶-廣州-云南
重慶-北京-廣州-長(zhǎng)沙
重慶-北京-廣州-廈門(mén)
重慶-北京-廣州-云南
重慶-北京-長(zhǎng)沙-廣州
重慶-北京-長(zhǎng)沙-廈門(mén)
重慶-北京-長(zhǎng)沙-云南
重慶-廣州-北京-長(zhǎng)沙
重慶-廣州-長(zhǎng)沙-北京
重慶-廣州-長(zhǎng)沙-廈門(mén)
重慶-廣州-長(zhǎng)沙-云南
重慶-廣州-廈門(mén)-長(zhǎng)沙
重慶-廣州-廈門(mén)-云南
重慶-廣州-云南-長(zhǎng)沙
重慶-廣州-云南-廈門(mén)
重慶-北京-廣州-長(zhǎng)沙-廈門(mén)
重慶-北京-廣州-長(zhǎng)沙-云南
重慶-北京-廣州-廈門(mén)-長(zhǎng)沙
重慶-北京-廣州-廈門(mén)-云南
重慶-北京-廣州-云南-長(zhǎng)沙
重慶-北京-廣州-云南-廈門(mén)
重慶-北京-長(zhǎng)沙-廣州-廈門(mén)
重慶-北京-長(zhǎng)沙-廣州-云南
重慶-北京-長(zhǎng)沙-廈門(mén)-廣州
重慶-北京-長(zhǎng)沙-廈門(mén)-云南
重慶-北京-長(zhǎng)沙-云南-廣州
重慶-北京-長(zhǎng)沙-云南-廈門(mén)
重慶-廣州-北京-長(zhǎng)沙-廈門(mén)
重慶-廣州-北京-長(zhǎng)沙-云南
重慶-廣州-長(zhǎng)沙-廈門(mén)-云南
重慶-廣州-長(zhǎng)沙-云南-廈門(mén)
重慶-廣州-廈門(mén)-長(zhǎng)沙-北京
重慶-廣州-廈門(mén)-長(zhǎng)沙-云南
重慶-廣州-廈門(mén)-云南-長(zhǎng)沙
重慶-廣州-云南-長(zhǎng)沙-北京
重慶-廣州-云南-長(zhǎng)沙-廈門(mén)
重慶-廣州-云南-廈門(mén)-長(zhǎng)沙
重慶-北京-廣州-長(zhǎng)沙-廈門(mén)-云南
重慶-北京-廣州-長(zhǎng)沙-云南-廈門(mén)
重慶-北京-廣州-廈門(mén)-長(zhǎng)沙-云南
重慶-北京-廣州-廈門(mén)-云南-長(zhǎng)沙
重慶-北京-廣州-云南-長(zhǎng)沙-廈門(mén)
重慶-北京-廣州-云南-廈門(mén)-長(zhǎng)沙
重慶-北京-長(zhǎng)沙-廣州-廈門(mén)-云南
重慶-北京-長(zhǎng)沙-廣州-云南-廈門(mén)
重慶-北京-長(zhǎng)沙-廈門(mén)-廣州-云南
重慶-北京-長(zhǎng)沙-廈門(mén)-云南-廣州
重慶-北京-長(zhǎng)沙-云南-廣州-廈門(mén)
重慶-北京-長(zhǎng)沙-云南-廈門(mén)-廣州
重慶-廣州-北京-長(zhǎng)沙-廈門(mén)-云南
重慶-廣州-北京-長(zhǎng)沙-云南-廈門(mén)
重慶-廣州-廈門(mén)-云南-長(zhǎng)沙-北京
重慶-廣州-云南-廈門(mén)-長(zhǎng)沙-北京
count:61
//全部線路圖 end
搜索重慶到廈門(mén)的線路圖
//重慶到廈門(mén)begin
重慶-廣州-廈門(mén)
重慶-北京-廣州-廈門(mén)
重慶-北京-長(zhǎng)沙-廈門(mén)
重慶-廣州-長(zhǎng)沙-廈門(mén)
重慶-廣州-云南-廈門(mén)
重慶-北京-廣州-長(zhǎng)沙-廈門(mén)
重慶-北京-廣州-云南-廈門(mén)
重慶-北京-長(zhǎng)沙-廣州-廈門(mén)
重慶-北京-長(zhǎng)沙-云南-廈門(mén)
重慶-廣州-北京-長(zhǎng)沙-廈門(mén)
重慶-廣州-長(zhǎng)沙-云南-廈門(mén)
重慶-廣州-云南-長(zhǎng)沙-廈門(mén)
重慶-北京-廣州-長(zhǎng)沙-云南-廈門(mén)
重慶-北京-廣州-云南-長(zhǎng)沙-廈門(mén)
重慶-北京-長(zhǎng)沙-廣州-云南-廈門(mén)
重慶-北京-長(zhǎng)沙-云南-廣州-廈門(mén)
重慶-廣州-北京-長(zhǎng)沙-云南-廈門(mén)
count:17
權(quán)最大為:重慶-廣州-北京-長(zhǎng)沙-云南-廈門(mén):17300
權(quán)最小為:重慶-廣州-廈門(mén):3000
//重慶到廈門(mén)end
最后ps：雖然本人的方法有一些愚見(jiàn)，本人就拋磚引玉了
相關(guān)文章
C# 使用 OleDbConnection 連接讀取Excel的方法
這篇文章主要介紹了C# 使用 OleDbConnection 連接讀取Excel的方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12
這篇文章主要為大家詳細(xì)介紹了C#正方形圖片的繪制方法，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-10-10
C#使用委托實(shí)現(xiàn)的快速排序算法實(shí)例
這篇文章主要介紹了C#使用委托實(shí)現(xiàn)的快速排序算法,實(shí)例分析了C#委托機(jī)制與快速排序算法的實(shí)現(xiàn)技巧,需要的朋友可以參考下2015-07-07
C#實(shí)現(xiàn)窗體抖動(dòng)的兩種方法
這篇文章主要為大家詳細(xì)介紹了C#實(shí)現(xiàn)窗體抖動(dòng)的兩種方法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-11-11
C#去掉字符串中所有匹配的字符String.Replace方法
在C#中,如果你想要去掉字符串中所有匹配的字符,你可以使用String.Replace方法,本文主要介紹了C#去掉字符串中所有匹配的字符String.Replace方法,具有一定的參考價(jià)值,感興趣的可以了解一下2024-04-04
這篇文章主要介紹了C#的匿名方法,包括匿名方法的定義以及常用方法,并以示例形式說(shuō)明其用法,需要的朋友可以參考下2014-09-09
這篇文章主要介紹了c#和net存取cookies操作示例,需要的朋友可以參考下2014-02-02
WPF中不規(guī)則窗體與WindowsFormsHost控件兼容問(wèn)題的解決方法
這篇文章主要介紹了WPF中不規(guī)則窗體與WindowsFormsHost控件兼容問(wèn)題的解決方法,對(duì)比以往的解決方案,給出了一個(gè)具有普遍性的技巧,具有一定的借鑒價(jià)值,需要的朋友可以參考下2014-11-11
使用C#實(shí)現(xiàn)讀取PDF中所有文本內(nèi)容
這篇文章主要為大家詳細(xì)介紹了如何使用C#實(shí)現(xiàn)讀取PDF中所有文本內(nèi)容,文中的示例代碼簡(jiǎn)潔易懂,具有一定的學(xué)習(xí)價(jià)值,有需要的小伙伴可以了解下2024-02-02
C#操作SQLite數(shù)據(jù)庫(kù)方法小結(jié)
這篇文章介紹了C#操作SQLite數(shù)據(jù)庫(kù)的方法，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-06-06