Как я могу вернуть все пути из одного узла?

Question

У меня есть график и я хотел бы выполнить первый поиск глубины, я хочу вернуть resul как: 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); 

Answer 1

Я побежал через ваш кода, а когда я раскопан

//v = GetAdjUnvisitedVertex(gStack.Peek()); 

линия его выход «A B C D E F G H I J K L M», как правильный ответ. Если у вас есть

v = GetAdjUnvisitedVertex(gStack.Count-1); 

вы не вызывая функцию на правильной вершине, когда вы начинаете перемещения вниз по второму пути в графе (А -> E -> F -> G). Поскольку в gStack есть только верхняя вершина (A), когда она идет по второму пути, вы вызываете GetAdjUnvisitedVertex (0); который вернет следующую соседнюю вершину H и повторит возврат K.