一： 最小生成樹(shù)
1. 概念
首先看如下圖，不知道大家能總結(jié)點(diǎn)什么。
對(duì)于一個(gè)連通圖G，如果其全部頂點(diǎn)和一部分邊構(gòu)成一個(gè)子圖G1，當(dāng)G1滿足：
① 剛好將圖中所有頂點(diǎn)連通。②頂點(diǎn)不存在回路。則稱G1就是G的“生成樹(shù)”。
其實(shí)一句話總結(jié)就是：生成樹(shù)是將原圖的全部頂點(diǎn)以最小的邊連通的子圖，這不，如下的連通圖可以得到下面的兩個(gè)生成樹(shù)。
② 對(duì)于一個(gè)帶權(quán)的連通圖，當(dāng)生成的樹(shù)不同，各邊上的權(quán)值總和也不同，如果某個(gè)生成樹(shù)的權(quán)值最小，則它就是“最小生成樹(shù)”。
2. 場(chǎng)景
實(shí)際應(yīng)用中“最小生成樹(shù)”還是蠻有實(shí)際價(jià)值的，教科書(shū)上都有這么一句話，若用圖來(lái)表示一個(gè)交通系統(tǒng)，每一個(gè)頂點(diǎn)代表一個(gè)城市，
邊代表兩個(gè)城市之間的距離，當(dāng)有n個(gè)城市時(shí)，可能會(huì)有n(n-1)/2條邊，那么怎么選擇(n-1)條邊來(lái)使城市之間的總距離最小，其實(shí)它
的抽象模型就是求“最小生成樹(shù)”的問(wèn)題。
3. prim算法
當(dāng)然如何求“最小生成樹(shù)”問(wèn)題，前人都已經(jīng)給我們總結(jié)好了，我們只要照葫蘆畫(huà)瓢就是了，
第一步：我們建立集合“V,U"，將圖中的所有頂點(diǎn)全部灌到V集合中，U集合初始為空。
第二步： 我們將V1放入U(xiǎn)集合中并將V1頂點(diǎn)標(biāo)記為已訪問(wèn)。此時(shí)：U（V1）。
第三步： 我們尋找V1的鄰接點(diǎn)（V2,V3,V5)，權(quán)值中發(fā)現(xiàn)(V1,V2)之間的權(quán)值最小，此時(shí)我們將V2放入U(xiǎn)集合中并標(biāo)記V2為已訪問(wèn)，
此時(shí)為U（V1，V2）。
第四步： 我們找U集合中的V1和V2的鄰接邊，一陣痙攣后，發(fā)現(xiàn)（V1，V5）的權(quán)值最小，此時(shí)將V5加入到U集合并標(biāo)記為已訪問(wèn)，此時(shí)
U的集合元素為（V1，V2，V5）。
第五步：此時(shí)我們以（V1，V2，V5）為基準(zhǔn)向四周尋找最小權(quán)值的鄰接邊，發(fā)現(xiàn)（V5，V4）的權(quán)值最小，此時(shí)將V4加入到U集合并標(biāo)記
為已訪問(wèn)，此時(shí)U的集合元素為（V1，V2，V5，V4）。
第六步： 跟第五步形式一樣，找到了（V1，V3）的權(quán)值最小，將V3加入到U集合中并標(biāo)記為已訪問(wèn)，最終U的元素為（V1，V2，V5，V4，V3），
最終發(fā)現(xiàn)頂點(diǎn)全部被訪問(wèn)，最小生成樹(shù)就此誕生。
//非鄰接頂點(diǎn)標(biāo)志
int noadj = -1;
//定義一個(gè)輸出總權(quán)值的變量
sum = 0;
//臨時(shí)數(shù)組，用于保存鄰接點(diǎn)的權(quán)值
int[] weight = new int[graph.vertexNum];
//臨時(shí)數(shù)組，用于保存頂點(diǎn)信息
int[] tempvertex = new int[graph.vertexNum];
//取出鄰接矩陣的第一行數(shù)據(jù)，也就是取出第一個(gè)頂點(diǎn)并將權(quán)和邊信息保存于臨時(shí)數(shù)據(jù)中
for (int i = 1; i < graph.vertexNum; i++)
{
//保存于鄰接點(diǎn)之間的權(quán)值
weight[i] = graph.edges[0, i];
//等于0則說(shuō)明V1與該鄰接點(diǎn)沒(méi)有邊
if (weight[i] == short.MaxValue)
tempvertex[i] = noadj;
else
tempvertex[i] = int.Parse(graph.vertex[0]);
}
//從集合V中取出V1節(jié)點(diǎn)，只需要將此節(jié)點(diǎn)設(shè)置為已訪問(wèn)過(guò)，weight為0集合
var index = tempvertex[0] = used;
var min = weight[0] = short.MaxValue;
//在V的鄰接點(diǎn)中找權(quán)值最小的節(jié)點(diǎn)
for (int i = 1; i < graph.vertexNum; i++)
{
index = i;
min = short.MaxValue;
for (int j = 1; j < graph.vertexNum; j++)
{
//用于找出當(dāng)前節(jié)點(diǎn)的鄰接點(diǎn)中權(quán)值最小的未訪問(wèn)點(diǎn)
if (weight[j] < min && tempvertex[j] != 0)
{
min = weight[j];
index = j;
}
}
//累加權(quán)值
sum += min;
Console.Write("({0},{1}) ", tempvertex[index], graph.vertex[index]);
//將取得的最小節(jié)點(diǎn)標(biāo)識(shí)為已訪問(wèn)
weight[index] = short.MaxValue;
tempvertex[index] = 0;
//從最新的節(jié)點(diǎn)出發(fā)，將此節(jié)點(diǎn)的weight比較賦值
for (int j = 0; j < graph.vertexNum; j++)
{
//已當(dāng)前節(jié)點(diǎn)為出發(fā)點(diǎn)，重新選擇最小邊
if (graph.edges[index, j] < weight[j] && tempvertex[j] != used)
{
weight[j] = graph.edges[index, j];
//這里做的目的將較短的邊覆蓋點(diǎn)上一個(gè)節(jié)點(diǎn)的鄰接點(diǎn)中的較長(zhǎng)的邊
tempvertex[j] = int.Parse(graph.vertex[index]);
}
}
}
}
#endregion
二： 最短路徑
1. 概念
求最短路徑問(wèn)題其實(shí)也是非常有實(shí)用價(jià)值的，映射到交通系統(tǒng)圖中，就是求兩個(gè)城市間的最短路徑問(wèn)題，還是看這張圖，我們可以很容易的看出比如
V1到圖中各頂點(diǎn)的最短路徑。
① V1 -> V2 直達(dá)， 權(quán)為2。
② V1 -> V3 直達(dá) 權(quán)為3。
③ V1->V5->V4 中轉(zhuǎn) 權(quán)為3+2=5。
④ V1 -> V5 直達(dá) 權(quán)為3。
、
2. Dijkstra算法
我們的學(xué)習(xí)需要站在巨人的肩膀上，那么對(duì)于現(xiàn)實(shí)中非常復(fù)雜的問(wèn)題，我們肯定不能用肉眼看出來(lái)，而是根據(jù)一定的算法推導(dǎo)出來(lái)的。
Dijkstra思想遵循 “走一步，看一步”的原則。
第一步： 我們需要一個(gè)集合U，然后將V1放入U(xiǎn)集合中，既然走了一步，我們就要看一步，就是比較一下V1的鄰接點(diǎn)（V2，V3，V5），
發(fā)現(xiàn)（V1，V2）的權(quán)值最小，此時(shí)我們將V2放入U(xiǎn)集合中，表示我們已經(jīng)找到了V1到V2的最短路徑。
第二步：然后將V2做中間點(diǎn)，繼續(xù)向前尋找權(quán)值最小的鄰接點(diǎn)，發(fā)現(xiàn)只有V4可以連通，此時(shí)修改V4的權(quán)值為（V1，V2)+(V2，V4)=6。
此時(shí)我們就要看一步，發(fā)現(xiàn)V1到（V3，V4，V5）中權(quán)值最小的是（V1，V5），此時(shí)將V5放入U(xiǎn)集合中，表示我們已經(jīng)找到了
V1到V5的最短路徑。
第三步：然后將V5做中間點(diǎn)，繼續(xù)向前尋找權(quán)值最小的鄰接點(diǎn)，發(fā)現(xiàn)能連通的有V3，V4，當(dāng)我們正想修該V3的權(quán)值時(shí)發(fā)現(xiàn)（V1，V3）的權(quán)值
小于（V1->V5->V3),此時(shí)我們就不修改，將V3放入U(xiǎn)集合中，最后我們找到了V1到V3的最短路徑。
第四步：因?yàn)閂5還沒(méi)有走完，所以繼續(xù)用V5做中間點(diǎn)，此時(shí)只能連通(V5,V4),當(dāng)要修改權(quán)值的時(shí)候，發(fā)現(xiàn)原來(lái)的V4權(quán)值為(V1,V2)+(V2,V4),而
現(xiàn)在的權(quán)值為5，小于先前的6，此時(shí)更改原先的權(quán)值變?yōu)?，將V4放入集合中，最后我們找到了V1到V4的最短路徑。
int[] path = new int[g.vertexNum];
int[] tempvertex = new int[g.vertexNum];
Console.WriteLine("/n請(qǐng)輸入源點(diǎn)的編號(hào)：");
//讓用戶輸入要遍歷的起始點(diǎn)
int vertex = int.Parse(Console.ReadLine()) - 1;
for (int i = 0; i < g.vertexNum; i++)
{
//初始賦權(quán)值
weight[i] = g.edges[vertex, i];
if (weight[i] < short.MaxValue && weight[i] > 0)
path[i] = vertex;
tempvertex[i] = 0;
}
tempvertex[vertex] = 1;
weight[vertex] = 0;
for (int i = 0; i < g.vertexNum; i++)
{
int min = short.MaxValue;
int index = vertex;
for (int j = 0; j < g.vertexNum; j++)
{
//頂點(diǎn)的權(quán)值中找出最小的
if (tempvertex[j] == 0 && weight[j] < min)
{
min = weight[j];
index = j;
}
}
tempvertex[index] = 1;
//以當(dāng)前的index作為中間點(diǎn)，找出最小的權(quán)值
for (int j = 0; j < g.vertexNum; j++)
{
if (tempvertex[j] == 0 && weight[index] + g.edges[index, j] < weight[j])
{
weight[j] = weight[index] + g.edges[index, j];
path[j] = index;
}
}
}
Console.WriteLine("/n頂點(diǎn){0}到各頂點(diǎn)的最短路徑為：（終點(diǎn) < 源點(diǎn)） " + g.vertex[vertex]);
//最后輸出
for (int i = 0; i < g.vertexNum; i++)
{
if (tempvertex[i] == 1)
{
var index = i;
while (index != vertex)
{
var j = index;
Console.Write("{0} < ", g.vertex[index]);
index = path[index];
}
Console.WriteLine("{0}/n", g.vertex[index]);
}
else
{
Console.WriteLine("{0} <- {1}: 無(wú)路徑/n", g.vertex[i], g.vertex[vertex]);
}
}
}
#endregion
最后上一下總的運(yùn)行代碼
namespace MatrixGraph
{
public class Program
{
static void Main(string[] args)
{
MatrixGraphManager manager = new MatrixGraphManager();
//創(chuàng)建圖
MatrixGraph graph = manager.CreateMatrixGraph();
manager.OutMatrix(graph);
int sum = 0;
manager.Prim(graph, out sum);
Console.WriteLine("/n最小生成樹(shù)的權(quán)值為：" + sum);
manager.Dijkstra(graph);
//Console.Write("廣度遞歸:/t");
//manager.BFSTraverse(graph);
//Console.Write("/n深度遞歸:/t");
//manager.DFSTraverse(graph);
Console.ReadLine();
}
}
#region 鄰接矩陣的結(jié)構(gòu)圖
/// <summary>
/// 鄰接矩陣的結(jié)構(gòu)圖
/// </summary>
public class MatrixGraph
{
//保存頂點(diǎn)信息
public string[] vertex;
//保存邊信息
public int[,] edges;
//深搜和廣搜的遍歷標(biāo)志
public bool[] isTrav;
//頂點(diǎn)數(shù)量
public int vertexNum;
//邊數(shù)量
public int edgeNum;
//圖類型
public int graphType;
/// <summary>
/// 存儲(chǔ)容量的初始化
/// </summary>
/// <param name="vertexNum"></param>
/// <param name="edgeNum"></param>
/// <param name="graphType"></param>
public MatrixGraph(int vertexNum, int edgeNum, int graphType)
{
this.vertexNum = vertexNum;
this.edgeNum = edgeNum;
this.graphType = graphType;
vertex = new string[vertexNum];
edges = new int[vertexNum, vertexNum];
isTrav = new bool[vertexNum];
}
}
#endregion
/// <summary>
/// 圖的操作類
/// </summary>
public class MatrixGraphManager
{
#region 圖的創(chuàng)建
/// <summary>
/// 圖的創(chuàng)建
/// </summary>
/// <param name="g"></param>
public MatrixGraph CreateMatrixGraph()
{
Console.WriteLine("請(qǐng)輸入創(chuàng)建圖的頂點(diǎn)個(gè)數(shù)，邊個(gè)數(shù)，是否為無(wú)向圖(0,1來(lái)表示)，已逗號(hào)隔開(kāi)。");
var initData = Console.ReadLine().Split(',').Select(i => int.Parse(i)).ToList();
MatrixGraph graph = new MatrixGraph(initData[0], initData[1], initData[2]);
//我們默認(rèn)“正無(wú)窮大為沒(méi)有邊”
for (int i = 0; i < graph.vertexNum; i++)
{
for (int j = 0; j < graph.vertexNum; j++)
{
graph.edges[i, j] = short.MaxValue;
}
}
Console.WriteLine("請(qǐng)輸入各頂點(diǎn)信息：");
for (int i = 0; i < graph.vertexNum; i++)
{
Console.Write("/n第" + (i + 1) + "個(gè)頂點(diǎn)為:");
var single = Console.ReadLine();
//頂點(diǎn)信息加入集合中
graph.vertex[i] = single;
}
Console.WriteLine("/n請(qǐng)輸入構(gòu)成兩個(gè)頂點(diǎn)的邊和權(quán)值，以逗號(hào)隔開(kāi)。/n");
for (int i = 0; i < graph.edgeNum; i++)
{
Console.Write("第" + (i + 1) + "條邊:/t");
initData = Console.ReadLine().Split(',').Select(j => int.Parse(j)).ToList();
int start = initData[0];
int end = initData[1];
int weight = initData[2];
//給矩陣指定坐標(biāo)位置賦值
graph.edges[start - 1, end - 1] = weight;
//如果是無(wú)向圖，則數(shù)據(jù)呈“二，四”象限對(duì)稱
if (graph.graphType == 1)
{
graph.edges[end - 1, start - 1] = weight;
}
}
return graph;
}
#endregion
#region 輸出矩陣數(shù)據(jù)
/// <summary>
/// 輸出矩陣數(shù)據(jù)
/// </summary>
/// <param name="graph"></param>
public void OutMatrix(MatrixGraph graph)
{
for (int i = 0; i < graph.vertexNum; i++)
{
for (int j = 0; j < graph.vertexNum; j++)
{
if (graph.edges[i, j] == short.MaxValue)
Console.Write("∽/t");
else
Console.Write(graph.edges[i, j] + "/t");
}
//換行
Console.WriteLine();
}
}
#endregion
#region 廣度優(yōu)先
/// <summary>
/// 廣度優(yōu)先
/// </summary>
/// <param name="graph"></param>
public void BFSTraverse(MatrixGraph graph)
{
//訪問(wèn)標(biāo)記默認(rèn)初始化
for (int i = 0; i < graph.vertexNum; i++)
{
graph.isTrav[i] = false;
}
//遍歷每個(gè)頂點(diǎn)
for (int i = 0; i < graph.vertexNum; i++)
{
//廣度遍歷未訪問(wèn)過(guò)的頂點(diǎn)
if (!graph.isTrav[i])
{
BFSM(ref graph, i);
}
}
}
/// <summary>
/// 廣度遍歷具體算法
/// </summary>
/// <param name="graph"></param>
public void BFSM(ref MatrixGraph graph, int vertex)
{
//這里就用系統(tǒng)的隊(duì)列
Queue<int> queue = new Queue<int>();
//先把頂點(diǎn)入隊(duì)
queue.Enqueue(vertex);
//標(biāo)記此頂點(diǎn)已經(jīng)被訪問(wèn)
graph.isTrav[vertex] = true;
//輸出頂點(diǎn)
Console.Write(" ->" + graph.vertex[vertex]);
//廣度遍歷頂點(diǎn)的鄰接點(diǎn)
while (queue.Count != 0)
{
var temp = queue.Dequeue();
//遍歷矩陣的橫坐標(biāo)
for (int i = 0; i < graph.vertexNum; i++)
{
if (!graph.isTrav[i] && graph.edges[temp, i] != 0)
{
graph.isTrav[i] = true;
queue.Enqueue(i);
//輸出未被訪問(wèn)的頂點(diǎn)
Console.Write(" ->" + graph.vertex[i]);
}
}
}
}
#endregion
#region 深度優(yōu)先
/// <summary>
/// 深度優(yōu)先
/// </summary>
/// <param name="graph"></param>
public void DFSTraverse(MatrixGraph graph)
{
//訪問(wèn)標(biāo)記默認(rèn)初始化
for (int i = 0; i < graph.vertexNum; i++)
{
graph.isTrav[i] = false;
}
//遍歷每個(gè)頂點(diǎn)
for (int i = 0; i < graph.vertexNum; i++)
{
//廣度遍歷未訪問(wèn)過(guò)的頂點(diǎn)
if (!graph.isTrav[i])
{
DFSM(ref graph, i);
}
}
}
#region 深度遞歸的具體算法
/// <summary>
/// 深度遞歸的具體算法
/// </summary>
/// <param name="graph"></param>
/// <param name="vertex"></param>
public void DFSM(ref MatrixGraph graph, int vertex)
{
Console.Write("->" + graph.vertex[vertex]);
//標(biāo)記為已訪問(wèn)
graph.isTrav[vertex] = true;
//要遍歷的六個(gè)點(diǎn)
for (int i = 0; i < graph.vertexNum; i++)
{
if (graph.isTrav[i] == false && graph.edges[vertex, i] != 0)
{
//深度遞歸
DFSM(ref graph, i);
}
}
}
#endregion
#endregion
#region prim算法獲取最小生成樹(shù)
/// <summary>
/// prim算法獲取最小生成樹(shù)
/// </summary>
/// <param name="graph"></param>
public void Prim(MatrixGraph graph, out int sum)
{
//已訪問(wèn)過(guò)的標(biāo)志
int used = 0;
//非鄰接頂點(diǎn)標(biāo)志
int noadj = -1;
//定義一個(gè)輸出總權(quán)值的變量
sum = 0;
//臨時(shí)數(shù)組，用于保存鄰接點(diǎn)的權(quán)值
int[] weight = new int[graph.vertexNum];
//臨時(shí)數(shù)組，用于保存頂點(diǎn)信息
int[] tempvertex = new int[graph.vertexNum];
//取出鄰接矩陣的第一行數(shù)據(jù)，也就是取出第一個(gè)頂點(diǎn)并將權(quán)和邊信息保存于臨時(shí)數(shù)據(jù)中
for (int i = 1; i < graph.vertexNum; i++)
{
//保存于鄰接點(diǎn)之間的權(quán)值
weight[i] = graph.edges[0, i];
//等于0則說(shuō)明V1與該鄰接點(diǎn)沒(méi)有邊
if (weight[i] == short.MaxValue)
tempvertex[i] = noadj;
else
tempvertex[i] = int.Parse(graph.vertex[0]);
}
//從集合V中取出V1節(jié)點(diǎn)，只需要將此節(jié)點(diǎn)設(shè)置為已訪問(wèn)過(guò)，weight為0集合
var index = tempvertex[0] = used;
var min = weight[0] = short.MaxValue;
//在V的鄰接點(diǎn)中找權(quán)值最小的節(jié)點(diǎn)
for (int i = 1; i < graph.vertexNum; i++)
{
index = i;
min = short.MaxValue;
for (int j = 1; j < graph.vertexNum; j++)
{
//用于找出當(dāng)前節(jié)點(diǎn)的鄰接點(diǎn)中權(quán)值最小的未訪問(wèn)點(diǎn)
if (weight[j] < min && tempvertex[j] != 0)
{
min = weight[j];
index = j;
}
}
//累加權(quán)值
sum += min;
Console.Write("({0},{1}) ", tempvertex[index], graph.vertex[index]);
//將取得的最小節(jié)點(diǎn)標(biāo)識(shí)為已訪問(wèn)
weight[index] = short.MaxValue;
tempvertex[index] = 0;
//從最新的節(jié)點(diǎn)出發(fā)，將此節(jié)點(diǎn)的weight比較賦值
for (int j = 0; j < graph.vertexNum; j++)
{
//已當(dāng)前節(jié)點(diǎn)為出發(fā)點(diǎn)，重新選擇最小邊
if (graph.edges[index, j] < weight[j] && tempvertex[j] != used)
{
weight[j] = graph.edges[index, j];
//這里做的目的將較短的邊覆蓋點(diǎn)上一個(gè)節(jié)點(diǎn)的鄰接點(diǎn)中的較長(zhǎng)的邊
tempvertex[j] = int.Parse(graph.vertex[index]);
}
}
}
}
#endregion
#region dijkstra求出最短路徑
/// <summary>
/// dijkstra求出最短路徑
/// </summary>
/// <param name="g"></param>
public void Dijkstra(MatrixGraph g)
{
int[] weight = new int[g.vertexNum];
int[] path = new int[g.vertexNum];
int[] tempvertex = new int[g.vertexNum];
Console.WriteLine("/n請(qǐng)輸入源點(diǎn)的編號(hào)：");
//讓用戶輸入要遍歷的起始點(diǎn)
int vertex = int.Parse(Console.ReadLine()) - 1;
for (int i = 0; i < g.vertexNum; i++)
{
//初始賦權(quán)值
weight[i] = g.edges[vertex, i];
if (weight[i] < short.MaxValue && weight[i] > 0)
path[i] = vertex;
tempvertex[i] = 0;
}
tempvertex[vertex] = 1;
weight[vertex] = 0;
for (int i = 0; i < g.vertexNum; i++)
{
int min = short.MaxValue;
int index = vertex;
for (int j = 0; j < g.vertexNum; j++)
{
//頂點(diǎn)的權(quán)值中找出最小的
if (tempvertex[j] == 0 && weight[j] < min)
{
min = weight[j];
index = j;
}
}
tempvertex[index] = 1;
//以當(dāng)前的index作為中間點(diǎn)，找出最小的權(quán)值
for (int j = 0; j < g.vertexNum; j++)
{
if (tempvertex[j] == 0 && weight[index] + g.edges[index, j] < weight[j])
{
weight[j] = weight[index] + g.edges[index, j];
path[j] = index;
}
}
}
Console.WriteLine("/n頂點(diǎn){0}到各頂點(diǎn)的最短路徑為：（終點(diǎn) < 源點(diǎn)） " + g.vertex[vertex]);
//最后輸出
for (int i = 0; i < g.vertexNum; i++)
{
if (tempvertex[i] == 1)
{
var index = i;
while (index != vertex)
{
var j = index;
Console.Write("{0} < ", g.vertex[index]);
index = path[index];
}
Console.WriteLine("{0}/n", g.vertex[index]);
}
else
{
Console.WriteLine("{0} <- {1}: 無(wú)路徑/n", g.vertex[i], g.vertex[vertex]);
}
}
}
#endregion
}
}
算法速成系列至此就全部結(jié)束了，公司給我們的算法培訓(xùn)也于上周五結(jié)束，呵呵，趕一下同步。最后希望大家能對(duì)算法重視起來(lái)，
學(xué)好算法，終身收益。
新聞熱點(diǎn)
疑難解答
圖片精選
