DGH-DS-编程题-7.24 利用栈编写强连通图的非递归深度优先遍历算法
【问题描述】试利用栈的基本操作编写，按深度优先搜索策略遍历一个完全图的非递归形式的算法。算法中不规定具体的存储结构，而将图Graph看成是一种抽象的数据类型。

【输入形式】输入图的顶点,图的顶点名称以大写的英文字母命名，顶点个数不超过20个，输入顺序以字母的排序作为输入顺序。
【输出形式】在进行深度优先搜索时，根据字母的顺序进行深度优先，以排在最前面的顶点作为遍历的开始点，输出深度优先遍历序列。
【样例输入】CDEFG
【样例输出】CDEFG

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<stack>
#include<cstring>

using namespace std;

bool st[100];

typedef struct{
    int numvex;
    int numEdge;
    char vex[100];
    int arc[100][100];
}MGraph;

void create(MGraph* G){
    char s[100];
    cin >> s;
    G->numvex = strlen(s);
    G->numEdge = G->numvex * (G->numvex + 1) / 2;
    int i = 0,j = 0;
    for(i = 0;i < G->numvex;i ++){
        G->vex[i] = s[i];
        for(j = 0;j < G->numvex;j ++){
            G->arc[i][j] = 1;
        }
    }
}

void dfs(MGraph* G){
    int i = 0,j = 0;
    stack<int> s;
    s.push(i); //将第一个顶点入栈
    while(!s.empty()){
        int k = s.top();
        s.pop();
        cout << G->vex[k];
        for(int j = G->numvex;j > 0;j --){
            if(G->arc[k][j] == 1 && !st[j]){
                s.push(j);
                st[j] = 1;
            }
        }
    }

}

int main(){
    MGraph G;
    create(&G);
    dfs(&G);

    return 0;
}