深度优先搜索.docx

深度优先搜索private void DFS(int i, ref string DFSResult) /深?度优?先搜?索递Y归函数y vertexListi.Visited = true; DFSResult += vertexListi.VertexName + n; EdgeNode p = vertexListi.FirstNode; while (p != null) if (vertexListp.Index.Visited = true) p = p.Next; else DFS(p.Index, ref DFSResult); / / 得?到?深?度优?先搜?索序列D / / 进?行D深?度优?先搜?索的?起e始?点?名?称? / 深?度优?先搜?索序列D public string DFSTraversal(string StartVertexName) string DFSResult = string.Empty; int i = GetIndex(StartVertexName); if (i != -1) for (int j = 0; j vertexCount; j+) vertexListj.Visited = false; DFS(i, ref DFSResult); return DFSResult; 广度优先搜索 public string BFSTraversal(string StartNodeName) string BFSResult = string.Empty; int i = GetIndex(StartNodeName); if (i != -1) for (int j = 0; j vertexCount; j+) vertexListj.Visited = false; vertexListi.Visited = true; BFSResult += vertexListi.VertexName + n; LinkQueue LQ = new LinkQueue(); LQ.EnQueue(i); while(LQ.IsEmpty()=false) int j = LQ.QueueFront; LQ.DeQueue(); EdgeNode p = vertexListj.FirstNode; while (p != null) if (vertexListp.Index.Visited = false) vertexListp.Index.Visited = true; BFSResult += vertexListp.Index.VertexName + n; p = p.Next; return BFSResult; / / 得?到?连?通网?的?最?小?生成树 / / 树根结点? / 连?通网?的?最?小?生成树 public SpanTreeNode MiniSpanTree(string vName) SpanTreeNode SpanTree = null; int i = GetIndex(vName); if (i != -1) SpanTree = new SpanTreeNodevertexCount; int count = 0; SpanTreecount = new SpanTreeNode(vertexListi.VertexName, NULL, 0.0); count+; Aid aid = new AidvertexCount; for (int j = 0; j vertexCount; j+) aidj.LowCost = double.MaxValue; aidj.VertexIndex = i; EdgeNode p1 = vertexListi.FirstNode; while (p1 != null) aidp1.Index.LowCost = p1.Weight; p1 = p1.Next; aidi.VertexIndex = -1; while (count vertexCount) double min = double.MaxValue; int v = i; for (int k = 0; k vertexCount; k+) if (aidk.VertexIndex != -1 & aidk.LowCost min) min = aidk.LowCost; v = k; SpanTreecount = new SpanTreeNode(vertexListv.VertexName, vertexListaidv.VertexIndex.VertexName, min); aidv.VertexIndex = -1; count+; EdgeNode p2 = vertexListv.FirstNode; while (p2 != null) if (aidp2.Index.VertexIndex != -1 & p2.Weight aidp2.Index.LowCost) aidp2.Index.LowCost = p2.Weight; aidp2.Index.VertexIndex = v; p2 = p2.Next; return SpanTree; / / 单源最?短路径? / / 寻找最?短路径?的?源点? / 源点?到?各个?顶点?的?最?短路径? public string ShortestPath(string vName) string Result = string.Empty; int v = GetIndex(vName); if (v != -1) double Dist = new doublevertexCount; string Path = new stringvertexCount; /初?始?化 for (int i = 0; i vertexCount; i+) vertexListi.Visited = false; Disti = double.MaxValue; Pathi = vertexListv.VertexName; Distv = 0.0; vertexListv.Visited = true; for (int i = 0; i vertexCount - 1; i+) EdgeNode p = vertexListv.FirstNode; while (p != null) if (vertexListp.Index.Visited = false & Distv + p.Weight + vertexListp.Index.VertexName; p = p.Next; double min = double.MaxValue; for (int j = 0; j vertexCount; j+) if (vertexListj.Visited = false & Distj m