99.png

    1. /*
    2.     写出深度优先遍历的非递归算法（图用邻接表给出）
    3.     分析：
    4.         之前我们也做过将一个递归算法利用栈用非递归的方式算出来，这里同理，我们利用栈来进行深度优先遍历
    5.         算法过程大致如下：从第一个顶点开始进行深度优先遍历，同时置访问位为true，然后将该顶点入栈，
    6.         采用while循环，依次取出栈顶元素，并判断该顶点元素是否已访问，未访问则访问，
    7.         已访问则查看它的firstEdge，当firstEdge也被访问了，查看next，如此循环。
    8. */
    9. #include <stdio.h>
    10. #include <stdlib.h>
    11. #define _CRT_SECURE_NO_WARNINGS
    12. #define MAXSIZE 100
    13. struct Stack {//栈结构
    14.     int *arr;
    15.     int len;
    16.     int top;
    17. };
    18. typedef struct EdgeNode {//边表结点
    19.     int index;//该边所指向的顶点的位置
    20.     int weight;//权值
    21.     EdgeNode *next;//下一个邻接边
    22. }EdgeNode;
    24. typedef struct VertexNode {//顶点表节点
    25.     char info;//顶点信息
    26.     EdgeNode *firstEdge;//指向第一条依附该顶点的边的指针
    27. }VertexNode, Adjlist[MAXSIZE];
    29. typedef struct {
    30.     Adjlist adjlist;//顶点数组
    31.     int numE, numV;//边数、顶点数
    32. }ALGraph;
    33. void DFSUseStack(ALGraph *G, Stack *s) {
    34.     bool push(Stack *, int);
    35.     bool pop(Stack *);
    36.     int top(Stack *);
    37.     bool empty(Stack *);
    38.     int *visited = (int *)malloc(sizeof(int)*G->numV);//设置标记数组
    39.     for (int i = 0; i < G->numV; i++) {
    40.         visited[i] = 0;
    41.     }
    42.     for (int i = 0; i < G->numV; i++) {
    43.         if (visited[i])
    44.             continue;
    45.         int v;
    46.         printf("%c ", G->adjlist[i].info);
    47.         visited[i] = 1;
    48.         push(s, i);//入栈
    49.         EdgeNode *p;
    50.         while (!empty(s)) {//栈内不空
    51.             v = top(s);
    52.             pop(s);
    53.             p = G->adjlist[v].firstEdge;
    54.             while (p) {
    55.                 if (!visited[p->index]) {
    56.                     printf("%c ", G->adjlist[p->index].info);
    57.                     visited[p->index] = 1;
    58.                     push(s, p->index);
    59.                     p = G->adjlist[p->index].firstEdge;//顺腾摸瓜
    60.                 }
    61.                 else {
    62.                     p = p->next;//摸到底了，平级顶点继续找
    63.                 }
    64.             }
    65.             if (p == NULL)
    66.                 pop(s);
    67.             //printf("%c ", G->adjlist[v].info);
    68.             //for (p = G->adjlist[v].firstEdge; p; p = p->next) {
    69.             //    if (!visited[p->index]) {
    70.             //        push(s, p->index);
    71.             //        visited[p->index] = 1;
    72.             //        //p = G->adjlist[p->index].firstEdge;//顺腾摸瓜
    73.             //    }
    74.             //}
    75.         }
    77.     }
    78. }
    79. int main() {
    80.     ALGraph G;
    81.     void createGraphInFile(ALGraph *);
    82.     void dispGraph(ALGraph *);
    83.     createGraphInFile(&G);//创建图
    84.     dispGraph(&G);
    85.     Stack *s = (Stack *)malloc(sizeof(Stack *));
    86.     Stack *createStack(int);
    87.     s = createStack(G.numV);
    88.     DFSUseStack(&G, s);
    89.     return 0;
    90. }