DFS只返回一個元素

Question

這裏DFS算法返回，而不是ABCDE

#include <iostream> 
using namespace std; 

class Stack 
{ 

private: 
    static const int size=20; 
     int *st; 
     int top; 
public : 
     Stack(){ 
    st =new int[size]; 
    top=-1; 

     } 
     ~Stack(){ 
      delete[] st; 
      top=-1; 
     } 
     void push(int j){ 
      st[++top]=j; 
       } 
     int pop(){ 
      return st[top--]; 
     } 
     int peek(){ 

      return st[top]; 

     } 
     bool empthy(){ 
      return (top==-1); 

     } 
}; 
class Vertex{ 
public: 
    char label; 
    bool visited; 
public: 
    Vertex(){ 

    } 
    Vertex(char lab){ 
     label=lab; 
     visited=false; 

    } 
    }; 
class Graph{ 
private: 
static const int maxvertex=20; 
     Vertex* vertexlist; 
     int **adj; 
     int nverts; 
     Stack *sstack; 
public: 
    Graph(){ 
    vertexlist=new Vertex[maxvertex]; 
    adj=new int*[maxvertex]; 
    for (int i=0;i<20;i++) 
      adj[i]=new int[maxvertex]; 
    nverts=0; 
     for (int i=0;i<maxvertex;i++){ 
      for (int j=0;j<maxvertex;j++){ 
       adj[i][j]=0; 
      } 
      } 

     sstack=new Stack(); 
    } 
    void add(char lab){ 

     vertexlist[nverts++] = Vertex(lab); 
    } 
    void addedge(int i,int j){ 
     adj[i][j]=1; 
     adj[j][i]=1; 


    } 
    void display(int v){ 
     cout<<vertexlist[v].label<<endl; 

    } 
    int getadjacent(int v){ 

     for (int j=0;j<nverts;j++){ 
      if (adj[v][j]==1 && vertexlist[j].visited==1){ 
        return j; 
      } 


     } 
     return -1; 
    } 
      void dfs(){ 
       vertexlist[0].visited=true;//mark it 
       display(0); 
        sstack->push(0); 
        while(!sstack->empthy()){ 
         int v=getadjacent(sstack->peek()); 
         if (v==-1){ sstack->pop();} 
         else{ 
          vertexlist[v].visited=true; 
         display(v); 
         sstack->push(v); 
         } 
        } 


        for (int j=0;j<nverts;j++){ 

         vertexlist[j].visited=false; 
        } 



      } 



}; 
int main(){ 

    Graph *graph=new Graph(); 
    graph->add('A'); 
    graph->add('B'); 
    graph->add('C'); 
    graph->add('D'); 
    graph->add('E'); 
    graph->addedge(0,1); 
    graph->addedge(1,2); 
    graph->addedge(0,3); 
    graph->addedge(3,4); 
    cout<<" visits : "; 
    graph->dfs(); 
    delete []graph; 







    return 0; 
} 

它返回一個只有一個頂點，什麼是錯在我的代碼？請幫助我

Answer 1

您在代碼中存在一些問題（例如，不要在使用new創建的對象上使用delete[]，它不是數組）。

但問題似乎是您的相鄰定義需要vertexlist[j].visited==1，但我認爲您的意圖是尋找未訪問的節點。所以你沒有發現任何與'A'相鄰的節點，因爲它們都沒有被訪問過。