我有一个图表,想要运行深度第一次搜索,我想返回领事: ABCDEFGHIJKLM,但我只得到了ABCDEHK。算法怎么了?谢谢
class Program
{
static void Main(string[] args)
{
//create graph, adjacent matrix
Graph aGraph = new Graph();
aGraph.AddVertex("A");
aGraph.AddVertex("B");
aGraph.AddVertex("C");
aGraph.AddVertex("D");
aGraph.AddVertex("E");
aGraph.AddVertex("F");
aGraph.AddVertex("G");
aGraph.AddVertex("H");
aGraph.AddVertex("I");
aGraph.AddVertex("J");
aGraph.AddVertex("K");
aGraph.AddVertex("L");
aGraph.AddVertex("M");
aGraph.AddEdge(0,1);
aGraph.AddEdge(1,2);
aGraph.AddEdge(2,3);
aGraph.AddEdge(0,4);
aGraph.AddEdge(4,5);
aGraph.AddEdge(5,6);
aGraph.AddEdge(0,7);
aGraph.AddEdge(7,8);
aGraph.AddEdge(8,9);
aGraph.AddEdge(0,10);
aGraph.AddEdge(10,11);
aGraph.AddEdge(11,12);
}
}
//vertex class
public class Vertex {
public bool wasVisited;
public string label;
public Vertex(string label) {
this.label = label;
wasVisited = false;
}
}
//Graph class
public class Graph {
private const int NUM_VERTICES = 20;
private Vertex[] vertices;
private int[,] adjMatrix;
int numVerts;
private Stack gStack;
public Graph() {
vertices = new Vertex[NUM_VERTICES];
adjMatrix = new int[NUM_VERTICES,NUM_VERTICES];
numVerts = 0;
for (int j = 0; j <= NUM_VERTICES-1; j++)
for (int k = 0; k < NUM_VERTICES - 1; k++)
adjMatrix[j, k] = 0;
gStack = new Stack();
}
public void AddVertex(string label)
{
vertices[numVerts] = new Vertex(label);
numVerts++;
}
public void AddEdge(int start, int eend)
{
adjMatrix[start, eend] = 1;
adjMatrix[eend, start] = 1;
}
public void ShowVertex(int v) {
Console.Write(vertices[v].label+" ");
}
private int GetAdjUnvisitedVertex(int v) {
for (int j = 0; j <= numVerts-1; j++) //NUM_VERTICES or numVerts
if ((adjMatrix[v, j] == 1) && (vertices[j].wasVisited == false))
return j;
return -1;
}
public void DepthFirstSearch()
{
vertices[0].wasVisited = true;
ShowVertex(0);
//Stack gStack = new Stack();
gStack.Push(0);
int v;
while (gStack.Count > 0) {
//v = GetAdjUnvisitedVertex(gStack.Peek());
v = GetAdjUnvisitedVertex(gStack.Count-1);
if (v == -1)
gStack.Pop();
else {
vertices[v].wasVisited = true;
ShowVertex(v);
gStack.Push(v);
}
}
for (int j = 0; j <= numVerts - 1; j++) //NUM_VERTICES or numVerts
vertices[j].wasVisited = false;
}原来的算法有这样一行:
//v = GetAdjUnvisitedVertex(gStack.Peek());但是它与函数GetAdjUnvisitedVertex不匹配,所以我更改为行:
v = GetAdjUnvisitedVertex(gStack.Count-1);发布于 2013-12-27 18:25:05
我运行了您的代码,当我取消注释时,
//v = GetAdjUnvisitedVertex(gStack.Peek());线输出"A,B,C,D,E,F,G,H,I,J,K,L,M“,也就是正确的答案。当你有
v = GetAdjUnvisitedVertex(gStack.Count-1);当您开始遍历图中的第二条路径(A,->,E,->,F,->,G)时,没有在正确的顶点上调用函数。由于gStack中只有顶顶点(A),当它沿着第二条路径运行时,您将调用GetAdjUnvisitedVertex(0);它将返回下一个相邻顶点H,并重复返回K。
https://stackoverflow.com/questions/20802196
复制相似问题