c++ - 使用 DFS 进行后序打印

Question

我有一个从邻接表创建的图，我试图以某种方式让 DFS 也打印出图的后序。有人对我如何在 DFS 函数中执行此操作有建议吗？非常感谢

示例输入:

create 6  
insert 0 3 0  
insert 0 1 0  
insert 1 3 0  
insert 1 2 0  
insert 2 1 0  
insert 3 5 0  
insert 3 4 0  
insert 3 2 0  
insert 4 2 0  
insert 5 2 0  
DFS 0

代码:

main.cpp

using namespace std;
#include "graph.h"

//Main Function 
int main(){

string command,command1;
int src,dest,wght,start,size;


cout << "graph>";
    cin>>command; 
    if(command=="create")
    cin>>size;
    graph A(size);  //initial class instance


//handles all I/O
  do{           
        cout << "graph>";
        cin >> command;

        //Creates an array of size "size" for nodes to be added too
        //if(command == "create"){

            //cin>>size;
            //resize(size);

        //}
        //Tests for user insertion of node
        if (command == "insert"){

            cin >> src >> dest >> wght;
            if(src <= size && dest <= size){
                A.insert(src, dest, wght);
            }
            else{
                cout<<"Error! Node does not exist!"<<endl;
            }
        }

        //Tests for user removal of node
        else if(command == "remove"){

            cin >> src >> dest;
            if(src <= size && dest <= size){
                A.remove(src, dest);
            }
            else{
                cout<<"Error! Node does not exist!"<<endl;
            }
        }

        //Tests for user printing of graph
        else if(command == "DFS"){
            cin >> start;
            A.DFS(start);     
        }

        //Tests for user printing of graph
        else if(command == "print"){
            A.print();     
        }

        else{
            if(command != "quit")
                cout<<"Error! Command not supported."<<endl;
        }

    }while(command != "quit" );

 return 0;
}

graph.h

//graph class file
using namespace std;
#include "node.h"

class graph{
    private:
        int h,f;
        int state[30];
        int counter[30];
        class alist* array;
    public:

        //Initializes the Graph and fills it with NULLs
        graph(int h){
            this->h = h;
            array = new alist [h];
            for (int i = 0; i < h; ++i)
                array[i].head = NULL;
        }

        //Creates a new node by calling instance newlist of listnode
        listnode* newlist(int dest){
            listnode* newnode = new listnode;
                newnode->dest = dest;
                    newnode->next = NULL;
            return newnode;
        }

        //Connects the node of the Graph
        void insert(int src, int dest, int weight){

            listnode* newnode = newlist(dest); 
    newnode->next = array[src].head; 
        newnode->weight = weight; 
            array[src].head = newnode;  
                newnode = newlist(src); 
                    newnode->next = array[dest].head;

        }

        //Removes a node from the graph
        void remove(int srcr, int destr){

            for (int i = 0; i < h; ++i){

                listnode* move = array[i].head;
                while (move){
                    if(destr == move->dest){
                        if(srcr==i)
                            array[i].head = NULL;
                    }
                move = move->next;
                }                 
            }
        }

        //Prints the Graph      
        void print(){

            for (int i = 0; i < h; ++i){

                listnode* move = array[i].head;
                while (move){
                    cout<<"("<<i <<","<< move->dest<< ","<< move->weight <<")";
                    move = move->next;
                }  
            }
            cout<<endl;
        }

        //Traverses the graph using DFS     
        int DFS(int start){
            state[start]=1; //marks the node as visited
            if(start==(h)){ //exits once all nodes have been visited
                return 0;}

                listnode* move = array[start].head;

                    cout<<"Visited "<<start<<endl;

                    if(state[start]!=1){
                        DFS(start);}

                    start++;
                    DFS(start);

        }
};

list.h

//list class file
using namespace std;
#include <iostream>
#include <cstdlib>

//Adjacency List
class alist
{
    public:
    class listnode *head;
};

node.h

//node class file
using namespace std;
#include "list.h"

//Nodes
class listnode
{
    public:
    int dest;
    int weight;
    class listnode* next;
};

Answer 1

不要用 C++ 重写你自己的图形类，使用 boost::graph 可能更快。

您的 DFS 实现似乎有误，您没有迭代节点的所有兄弟节点。

最初，您应该将所有状态初始化为白色。当你第一次发现一个节点时，你标记为灰色。然后你递归所有的 DFS节点的 sibling (当节点未标记为 WHITE 时不执行任何操作)。访问完所有兄弟节点后，将该节点标记为黑色。此时，您可以输出节点的索引，这将给你后序遍历