/// <summary> /// 获取或设置图中各结点的名称 /// </summary> /// <param name="index">结点名称从零开始的索引</param> /// <returns>指定索引处结点的名称</returns> publicstringthis[int index] { get { if (index < 0 || index > VertexCount - 1) thrownew IndexOutOfRangeException(); return _vertexNameList[index]; } set { if (index < 0 || index > VertexCount - 1) thrownew IndexOutOfRangeException(); _vertexNameList[index] = value; } }
privateintGetIndex(string vertexName) { //根据结点名字获取结点在数组中的下标 int i; for (i = 0; i < VertexCount; i++) { if (_vertexNameList[i] == vertexName) break; } return i == VertexCount ? -1 : i; }
/// <summary> /// 给邻接矩阵赋值 /// </summary> /// <param name="startVertexName">起始结点的名字</param> /// <param name="endVertexName">终止结点的名字</param> /// <param name="weight">边上的权值或连接关系</param> publicvoidAddEdge(string startVertexName, string endVertexName, double weight = 1) { int i = GetIndex(startVertexName); int j = GetIndex(endVertexName); if (i == -1 || j == -1) thrownew Exception("图中不存在该边."); _adMatrix[i, j] = weight; } } }
for (int count = 1; count < VertexCount; count++) { double min = double.MaxValue; int v = i; for (int k = 0; k < VertexCount; k++) { if (vertexIndex[k] != -1 && lowCost[k] < min) { min = lowCost[k]; v = k; } } spanTree[count] = new SpanTreeNode(_vertexList[v].VertexName, _vertexList[vertexIndex[v]].VertexName, min); vertexIndex[v] = -1;
/// <summary> /// 创建一个 Edge 类的新实例 /// </summary> /// <param name="begin">起点编号</param> /// <param name="end">终点编号</param> /// <param name="weight">权值</param> publicEdge(int begin, int end, double weight = 0.0) { Begin = begin; End = end; Weight = weight; } } } private Edge[] GetEdges() { for (int i = 0; i < VertexCount; i++) _vertexList[i].Visited = false;
List<Edge> result = new List<Edge>();
for (int i = 0; i < VertexCount; i++) { _vertexList[i].Visited = true; EdgeNode p = _vertexList[i].FirstNode; while (p != null) { if (_vertexList[p.Index].Visited == false) { Edge edge = new Edge(i, p.Index, p.Weight); result.Add(edge); } p = p.Next; } } return result.OrderBy(a => a.Weight).ToArray(); }
privateintFind(int[] parent, int f) { while (parent[f] > -1) f = parent[f]; return f; }
/// <summary> /// 克鲁斯卡尔算法 最小生成树 /// </summary> /// <returns></returns> public SpanTreeNode[] MiniSpanTree() { int[] parent = newint[VertexCount]; for (int i = 0; i < VertexCount; i++) { parent[i] = -1; } SpanTreeNode[] tree = new SpanTreeNode[VertexCount]; Edge[] edges = GetEdges();
int count = 1; for (int i = 0; i < edges.Length; i++) { int begin = edges[i].Begin; int end = edges[i].End; int b = Find(parent, begin); int e = Find(parent, end); if (b != e) { parent[e] = b; tree[count] = new SpanTreeNode(_vertexList[end].VertexName, _vertexList[begin].VertexName, edges[i].Weight); count++; } } for (int i = 0; i < parent.Length; i++) { if (parent[i] == -1) { tree[0] = new SpanTreeNode(_vertexList[i].VertexName, "NULL", 0.0); break; } } return tree; }
6. 单源最短路径
6.1 定义
设为连通网,为源点,到其余各顶点的最短路径问题即为单源最短路径问题。
6.2 迪杰特撕拉算法
(迪杰特斯拉)算法(按路径长度递增顺序构造的算法):
初始时为源点,, ,标识被访问。
(1)令,(到的路径长度)。
(2)依次考察的未被访问的邻接点,若,则改变的值,使。
(3)在未被访问顶点中选择最小的顶点,访问。
(4)重复(2)、(3)直至所有顶点都被访问。
例题:
算法实现:
/// <summary> /// 单源最短路径 /// </summary> /// <param name="vName">寻找最短路径的源点</param> /// <returns>源点到各个顶点的最短路径</returns> publicstringShortestPath(string vName) { int v = GetIndex(vName); if (v == -1) { returnstring.Empty; }
string result = string.Empty; double[] dist = newdouble[VertexCount]; string[] path = newstring[VertexCount]; //初始化 for (int i = 0; i < VertexCount; i++) { _vertexList[i].Visited = false; dist[i] = double.MaxValue; path[i] = _vertexList[v].VertexName; } dist[v] = 0.0; _vertexList[v].Visited = true;
for (int i = 0; i < VertexCount - 1; i++) { EdgeNode p = _vertexList[v].FirstNode; while (p != null) { if (_vertexList[p.Index].Visited == false && dist[v] + p.Weight < dist[p.Index]) { dist[p.Index] = dist[v] + p.Weight; path[p.Index] = path[v] + " ->" + _vertexList[p.Index].VertexName; } p = p.Next; }
double min = double.MaxValue; for (int j = 0; j < VertexCount; j++) { if (_vertexList[j].Visited == false && dist[j] < min) { min = dist[j]; v = j; } } _vertexList[v].Visited = true; }
for (int i = 0; i < VertexCount; i++) { result += path[i] + ":" + dist[i] + "\n"; }
for (int i = 0; i < VertexCount; i++) _vertexList[i].Visited = false;
for (int i = 0; i < VertexCount; i++) { if (_vertexList[i].Visited == false) { result = string.Empty; //利用深度优先搜索求非连通图的连通分量 Dfs(i, ref result); lst.InsertAtRear(result); } } result = string.Empty; for (int i = 0; i < lst.Length; i++) { result += "第" + i + "个连通分量为:\n" + lst[i]; } return result; }
Source,Target,Weight San Rapheal,Cross,12 San Rapheal,Oakland,18 Cross,Daly Cit,3 Cross,San Franciso,3 Daly Cit,San Franciso,4 Daly Cit,Cross B,19 San Franciso,Oakland,7 San Franciso,San Mateo,21 Oakland,San Iarenzo,18 Oakland,Dublin,31 San Iarenzo,Hayward,3 San Iarenzo,Dublin,12 Cross B,San Mateo,4 Cross B,Cross C,7 San Mateo,Hayward,13 San Mateo,Redwood City,6 Hayward,Freemont,9 Dublin,San Jose,35 Redwood City,Cross C,5 Redwood City,Palo Alto,6 Cross C,Cupertin,14 Palo Alto,Freemont,9 Palo Alto,Mtn View,6 Freemont,San Jose,24 Mtn View,Cupertin,6 Mtn View,San Jose,8 Cupertin,San Jose,7
深度优先搜索序列:
San Rapheal Cross Daly Cit San Franciso Oakland San Iarenzo Hayward San Mateo Cross B Cross C Redwood City Palo Alto Freemont San Jose Dublin Mtn View Cupertin
广度优先搜索序列:
San Rapheal Cross Oakland Daly Cit San Franciso San Iarenzo Dublin Cross B San Mateo Hayward San Jose Cross C Redwood City Freemont Mtn View Cupertin Palo Alto
最小生成树:
(NULL,San Rapheal) Weight:0 (San Rapheal,Cross) Weight:12 (Cross,Daly Cit) Weight:3 (Cross,San Franciso) Weight:3 (San Franciso,Oakland) Weight:7 (Oakland,San Iarenzo) Weight:18 (San Iarenzo,Hayward) Weight:3 (Hayward,Freemont) Weight:9 (Freemont,Palo Alto) Weight:9 (Palo Alto,Redwood City) Weight:6 (Redwood City,Cross C) Weight:5 (Redwood City,San Mateo) Weight:6 (San Mateo,Cross B) Weight:4 (Palo Alto,Mtn View) Weight:6 (Mtn View,Cupertin) Weight:6 (Cupertin,San Jose) Weight:7 (San Iarenzo,Dublin) Weight:12
最小生成树权值:116
最短路径:
San Rapheal:0 San Rapheal ->Cross:12 San Rapheal ->Oakland:18 San Rapheal ->Cross ->Daly Cit:15 San Rapheal ->Cross ->San Franciso:15 San Rapheal ->Cross ->Daly Cit ->Cross B:34 San Rapheal ->Cross ->San Franciso ->San Mateo:36 San Rapheal ->Oakland ->San Iarenzo:36 San Rapheal ->Oakland ->San Iarenzo ->Dublin:48 San Rapheal ->Oakland ->San Iarenzo ->Hayward:39 San Rapheal ->Cross ->Daly Cit ->Cross B ->Cross C:41 San Rapheal ->Cross ->San Franciso ->San Mateo ->Redwood City:42 San Rapheal ->Oakland ->San Iarenzo ->Hayward ->Freemont:48 San Rapheal ->Cross ->San Franciso ->San Mateo ->Redwood City ->Palo Alto ->Mtn View ->San Jose:62 San Rapheal ->Cross ->San Franciso ->San Mateo ->Redwood City ->Palo Alto:48 San Rapheal ->Cross ->Daly Cit ->Cross B ->Cross C ->Cupertin:55 San Rapheal ->Cross ->San Franciso ->San Mateo ->Redwood City ->Palo Alto ->Mtn View:54