非递归图的深度优先遍历算法

支持无向图和有向图，讲道理有向图的代码会比无向图的更容易理解，下面代码都做了兼容

#include 

#include 
#include 
#include 

using namespace std;


#define MAX_NUM 20                   //顶点的最大个数

bool visited[5];               //设置全局数组，记录标记顶点是否被访问过
int global_counter = 10;
typedef struct {
    int Vex[MAX_NUM];
    int Edge[MAX_NUM][MAX_NUM];
    int vexnum;
}Graph;


typedef struct linkNode{
    int data;
    struct linkNode *next;
}linkNode, *Stack;

// 初始化
void init_stact(Stack &S){
    S = (linkNode *)malloc(sizeof(linkNode));
    S->data = 999;//fake
    S->next = NULL;
}

// 入栈
bool push(Stack &S, int value){
    linkNode *p = S;

    if (p == NULL) {
        return false;
    }

    linkNode *q = (linkNode *)malloc(sizeof(linkNode));
    q->data = value;
    q->next = p->next;
    p->next = q;
    
    return true;
}

// 查看栈顶元素
int get_stack_top(Stack S){
    if (S->next==NULL) {
        return false;
    }
    return S->next->data;
    
}

// 出栈
bool pop(Stack &S, int &value){
    if (S->next==NULL) {
        return false;
    }
    linkNode *p = S->next;
    S->next = p->next;
    value = p->data;
    free(p);
    return true;
}


int FirstNeighbor(Graph g, int x){
    for (int i = 1; i<=g.vexnum; i++) {
        if (g.Edge[x][i]>0) {
            return g.Vex[i];
        }
    }
    return -1;
}
// 优化
int NextNeighbor(Graph g, int x, int y){
    for (int i = y+1; i<=g.vexnum; i++) {
        if (g.Edge[x][i]>0) {
            return g.Vex[i];
        }
    }
    return -1;
}
void DFS(Graph g, int v);
void DFSTraverse(Graph g){
    for (int i = 1; i<=g.vexnum; i++) {
        visited[i] = false;
    }
    for (int i = 1; i<=g.vexnum; i++) {
        if (!visited[i]) {
            cout << "分量" << endl;
            DFS(g, i);
        }
    }
}
void DFS(Graph g, int v){

    Stack S;
    init_stact(S);
    
    int p = v, q = 0,kk=10;//kk 用来做防御死循环，正式环境去掉
    
    while ((p > 0||S->next!=NULL)&&kk>0) {
        if (!visited[p] && p > 0) {
            cout << "elements:" << p << endl;
            push(S, p);
            visited[p] = true;
            q = p;
            
            p = FirstNeighbor(g, p);
            if (p > 0) {
                continue;
            }else{
                p = NextNeighbor(g, p, q);
            }
        }else{
            p = get_stack_top(S);//查看栈顶元素
            p = NextNeighbor(g, p, q);
            if (!visited[p] && p > 0) {
                continue;
            }else{
                pop(S, p);
                q = p;
                p = 0;
                
            }
        }
        kk--;
    }
}


int main(){
    std::cout << "welcome, to my world!" << std::endl;
    Graph graph;
    for (int i=1; i<=5; i++) {
        graph.Vex[i] = i;
    }
    for (int i=1; i<=5; i++) {
        for (int j = 1; j<=5; j++) {
            if (i==j) {
                graph.Edge[i][j] = 0;
            }else{
                graph.Edge[i][j] = 0;
            }
            
        }
    }
    graph.Edge[1][2] = 1;
    graph.Edge[1][3] = 1;
    graph.Edge[2][4] = 1;
    graph.Edge[2][5] = 1;
    graph.Edge[4][3] = 1;
    
    graph.Edge[2][1] = 1;
    graph.Edge[3][1] = 1;
    graph.Edge[4][2] = 1;
    graph.Edge[5][2] = 1;
    graph.Edge[3][4] = 1;
    graph.vexnum = 5;

    int p = NextNeighbor(graph, 2, 4);
    cout << p < 
输出
 
welcome, to my world!
 5
 size of:1684
 分量
 elements:1
 elements:2
 elements:4
 elements:5
 elements:3
 Program ended with exit code: 0