栈+图的DFS非递归形式（严书风格代码）

王道P221，综合应用题第三题

栈结构及其基本操作：

//栈
typedef struct Stack {
    int top;
    int data[MaxVertexNum]; //栈中存放指向结点的指针
} Stack;

void InitStack(Stack & S) {
    S.top = -1;
}

bool IsEmpty(Stack stk) {
    if(stk.top == -1) return true;
    else return false;
}

bool IsFull(Stack stk) {
    if(stk.top == MaxVertexNum - 1) return true;
    else return false;
}

bool Push(Stack & stk, int p) {
    if(IsFull(stk)) {
        cout << "Stack is full!" << endl;
        return false;
    }
    stk.data[++ stk.top] = p;  //指针加一再进栈
    return true;
}

bool Pop(Stack & stk, int & p) {
    if(IsEmpty(stk)) {
        cout << "Stack is empty!" << endl;
        return false;
    }
    p = stk.data[stk.top -- ];    //先出栈，指针再减一
    return true;
}

DFS的非递归，主要使用栈来维护将要访问的顶点。将栈顶元素出栈并访问，并且将还未访问过的相邻元素加入栈中，如此反复，直到栈空，以下图结构为例：

注意在栈中保存的是结点的编号，也就是上图中的数字，箭头上面的字母表示当前出栈元素，连起来就是输出序列，比如这里的输出序列就是abcde

DFS非递归代码：

bool visited[MaxVertexNum];

void DFS(ALGraph G, int i) {
    Stack stk;
    InitStack(stk);

    visited[i] = true;  //第一个元素加入栈中并标记为访问过
    Push(stk, i);
    
    while(!IsEmpty(stk)) {
        int p;
        Pop(stk, p);   //栈顶元素出栈，并且赋值给p
        cout << G.vertices[p].data << endl;   //输出编号对应的值
        
        ArcNode * cur = G.vertices[p].first;    //访问相邻结点
        while(cur) {
            if(!visited[cur -> adjvex]) {
                visited[cur -> adjvex] = true;
                Push(stk, cur -> adjvex);
            }
            cur = cur -> next;
        }
    }    
}

全部代码：

#include<iostream>
using namespace std;

#define MaxVertexNum 100
#define VertexType char

//栈
typedef struct Stack {
    int top;
    int data[MaxVertexNum]; //栈中存放指向结点的指针
} Stack;

void InitStack(Stack & S) {
    S.top = -1;
}

bool IsEmpty(Stack stk) {
    if(stk.top == -1) return true;
    else return false;
}

bool IsFull(Stack stk) {
    if(stk.top == MaxVertexNum - 1) return true;
    else return false;
}

bool Push(Stack & stk, int p) {
    if(IsFull(stk)) {
        cout << "Stack is full!" << endl;
        return false;
    }
    stk.data[++ stk.top] = p;
    return true;
}

bool Pop(Stack & stk, int & p) {
    if(IsEmpty(stk)) {
        cout << "Stack is empty!" << endl;
        return false;
    }
    p = stk.data[stk.top -- ];
    return true;
}

//边表结点
typedef struct ArcNode { 
    int adjvex;          //存储该结点在顶点表中的下标
    ArcNode * next;      //指向下一个边表
}ArcNode;

//顶点表结点
typedef struct VNode {  
    VertexType data;            //顶点信息
    ArcNode * first;             //指向边表
} VNode, AdjList[MaxVertexNum]; //顶点和顶点表

//图的存储结构
typedef struct {       
    AdjList vertices;  //邻接表
    int vertexnum, arcnum; //维护图的顶点数和边的个数
} ALGraph;


//找到结点x在顶点表中的位置
int LocateVex(ALGraph & G, VertexType x) {
    for(int i = 0; i < G.vertexnum; i ++) {
        if(x == G.vertices[i].data) 
            return i;
    }
    return -1;
}

void CreateALGrapha(ALGraph & G) {
    //cout << "输入顶点数和边数：";
    cin >> G.vertexnum >> G.arcnum;
    for(int i = 0; i < G.vertexnum; ++i) {
        //cout << "输入第" << i + 1 << "个顶点的信息：";
        cin >> G.vertices[i].data;
        G.vertices[i].first = NULL;
    }

    for(int i = 0; i < G.arcnum; ++i) {
        VertexType e1, e2;
        //cout << "输入第" << i + 1 << "条边的顶点：";
        cin >> e1 >> e2;
        ArcNode * e = new ArcNode;
        if(!e) {
            cout << "内存分配失败：" << endl;
            exit(0);
        }
        
        int vi = LocateVex(G, e1);
        int vj = LocateVex(G, e2);

        //e1和e2之间有一条边，先用头插法将e2的边表插到e1的顶点表后
        e -> adjvex = vj;
        e -> next = G.vertices[vi].first;
        G.vertices[vi].first = e;
		
        e = new ArcNode;
        if(!e) {
            cout << "内存分配失败：" << endl;
            exit(0);
        }        
        //再将e1的边表插到e2的顶点表
        e -> adjvex = vi;
        e -> next = G.vertices[vj].first;
        G.vertices[vj].first = e;
    }
}

bool visited[MaxVertexNum];

void DFS(ALGraph G, int i) {
    Stack stk;
    InitStack(stk);
    visited[i] = true;
    Push(stk, i);
    
    while(!IsEmpty(stk)) {
        int p;
        Pop(stk, p);
        cout << G.vertices[p].data << endl;
        
        ArcNode * cur = G.vertices[p].first;

        while(cur) {
            if(!visited[cur -> adjvex]) {
                visited[cur -> adjvex] = true;
                Push(stk, cur -> adjvex);
            }
            cur = cur -> next;
        }
    }
    
}

void DFSTraverse(ALGraph G) {
    for(int i = 0; i < G.vertexnum; ++i) {
        visited[i] = false;
    }

    for(int i = 0; i < G.vertexnum; ++i) {
        if(!visited[i])
            DFS(G, i);
    }
}


int main() {
    ALGraph G;
    CreateALGrapha(G);
    DFSTraverse(G);
    return 0;
}
/*
5 7
a b c d e
a b
a e
b c
b d
b e
c d
d e
*/