Блог

вот алгоритм 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 amp;amp; 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;
}
  

он возвращает A, что не так в моем коде? пожалуйста, помогите мне

У вас есть несколько проблем в коде (например, не используйте delete[] для объекта, с которым вы создали new , это не массив).

Но проблема, похоже, в том, что требуется ваше смежное определение vertexlist[j].visited==1 , но я думаю, что ваше намерение состоит в том, чтобы искать непросмотренные узлы. Таким образом, вы не найдете никаких узлов, смежных с ‘A’, потому что ни один из них еще не был посещен.