public void addVertex(string vnam) { int i = getIndex(vnam); if (i != -1) { Console.WriteLine("\n 该景点已经存在。"); return; } vertices[n] = new Vertex(vnam); n++; }
if (n == 0) { Console.WriteLine("\n 图不存在，你需要先插入一些顶点和边。"); return; }
while (true) { Console.WriteLine("\n 输入起始景点： "); source = Console.ReadLine(); src = getIndex(source); if (src == -1) Console.WriteLine("\n 该起始景点不存在。"); else break; }
for (int j = 0; j < n;] == false) && (Distance[j] < Distance[v])) v = j; }
Final[v] = true;
for (int w = 0; w < n; w++) { if (Final[w] == false) { if (Distance[v] + cost[v, w] < Distance[w]) Distance[w] = Distance[v] + cost[v, w]; } } }
public void bfs()//广度遍历 { Console.Write("广度遍历的结果：" + vertices[0].vname + ","); vertices[0].wasVisited = true; thequeue.Enqueue(vertices[0]); while (thequeue.Count > 0) { int w = getAdjUnvisitedVertex(thequeue.Count - 1); if (w == -1) thequeue.Dequeue(); else { Console.Write(vertices[w].vname + ","); vertices[w].wasVisited = true; thequeue.Enqueue(vertices[w]); } } for (int j = 0; j < n; j++) vertices[j].wasVisited = false; Console.WriteLine();
public void dfs()//深度遍历 { vertices[0].wasVisited = true; Console.Write("深度遍历的结果：" + vertices[0].vname + ","); thestack.Push(vertices[0]); while (thestack.Count > 0)
public Graph() { n = 0; for (int i = 0; i < 10; i++) for (int j = 0; j < 10; j++) { if (i == j) cost[i, j] = 0; else cost[i, j] = infinity; } }
private bool edgeExists() { for (int i = 0; i < 10; i++) for (int j = 0; j < 10; j++) if ((cost[i, j] != 0) && (cost[i, j] != infinity)) return (true); return (false); }
} class Program { static void Main(string[] args) { Graph obj = new Graph(); string a = "V0", b = "V1", c = "V2", d = "V3", e = "V4", f = "V5", g = "V6"; obj.addVertex(a); obj.addVertex(b); obj.addVertex(c); obj.ad
k = j; Console.Write(" --" + lowcost[k] + "-- " + vertices[k].vname); for (j = 0; j < n; j++) { if (cost[k, j] < lowcost[j]) { lowcost[j] = cost[k, j]; } }
Console.WriteLine("\n 从景点 " + source + "到其他所有景点的最短路径 分别是： ");
for (int j = 0; j < n; j++) { if (Distance[j] == infinity) Console.WriteLine(source + "->" + vertices[j].vname + " =No path"); else Console.WriteLine(source + "->" + vertices[j].vname + " = " + Distance[j]); } }
} } } Console.WriteLine(); }
public void findShortestPath()//找图的最短路径 { int[] Distance = new int[10]; bool[] Final = new bool[10]; string source;
int src;
public int getAdjUnvisitedVertex(int v) { for (int j = 0; j < n; j++) if (cost[v, j] != infinity && vertices[j].wasVisited == false) return j; return -1; }
private int getIndex(string vname) { for (int i = 0; i < n; i++) if (vertices[i].vname == vname) return (i); return (-1);//如果在列表中没有找到，返回-1。 }
public void addEdge(string v1, string v2, int a) { int i1, i2; if (n == 0) { Console.WriteLine("\n 不存在任何景点。你需要先增加一个景点。"); return; } while (true) { i1 = getIndex(v1); if (i1 == -1) Console.WriteLine("\n 该起始景点不存在，请重试。"); else break;
for (int i = 0; i < n; i++) Distance[i] = cost[src, i];
Final[src] = true;
for (int i = 0; i < n; i++) { int v = 0; for (int j = 0; j < n; j++) { if (Final[j] == false) { v = j; break; } }
} while (true) { i2 = getIndex(v2); if (i2 == -1) Console.WriteLine("\n 该目的地景点不存在，请重试。"); else break; } cost[i1, i2] = cost[i2, i1] = a; }
public void display() { if (n == 0) { Console.WriteLine("\n 图不存在。"); return; } Console.WriteLine("\n 景点："); for (int i
{ int v = getAdjUnvisitedVertex(thestack.Count - 1);//有问题 if (v == -1) thestack.Pop(); else { vertices[v].wasVisited = true; Console.Write(vertices[v].vname + ","); thestack.Push(vertices[v]); } } for (int j = 0; j < n; j++) vertices[j].wasVisited = false; Console.WriteLine(); }