栈的非递归深度优先搜索

原文链接

#include<stdio.h>
#include<stack>
#define MAX 100
using namespace std;

typedef struct
{
    int e[MAX][MAX];
    int ves;
    int edge;
    int book[MAX];//标志判断是否有被访问过 
}MGraph;

void createMGraph(MGraph *G)
{
    int i;
    int j;
    int start;
    int end;

    printf("please input the ves and edge:\n");
    scanf("%d %d",&G->ves,&G->edge);
//初始化
    for(i = 0; i < G->ves; i++)
    {
        for(j = 0; j < G->ves; j++)
            G->e[i][j] = 0;
        G->book[i] = 0;//没被访问过的结点置为0 
    }
//创建邻接矩阵 
    printf("please input the (vi,vj)\n");
    for(i = 0; i < G->edge; i++)
    {
        scanf("%d %d",&start,&end);
        G->e[start][end] = 1;
    }
}

void dfs(MGraph* G,int ves)
{
   stack<int> s;//创建一个栈
   printf("%d ", ves);

   G->book[ves] = 1;//已经访问过结点ves了
   s.push(ves);//入栈

   while(!s.empty())
   {
       int data, i;

       data = s.top();//取top的顶点
       for(i = 0; i < G->ves; i++)
       {
           if(G->e[data][i] != 0 && G->book[i] != 1)
       	   {
           printf("%d ", i);
           G->book[i] = 1;
           s.push(i);
           break;// 开始遍历下一个点的邻接矩阵表
      	   }
       }
       if(i == G->ves)//data相邻的结点都访问结束了,就弹出data
       {
           s.pop();
       }
   }
}

int main()
{
    MGraph G;
    createMGraph(&G);
    dfs(&G,0);
    return 0;
}
/*
输入样例:
8 18
0 1
0 2
1 0
1 3
1 4
2 0
2 5
2 6
3 1
3 7
4 1
4 7
5 2
5 6
6 2
6 5
7 3
7 4
*/

栈的非递归深度优先搜索
栈的非递归深度优先搜索

上一篇:Hibernate之HQL


下一篇:XML与JSON-dom4j+Gson+fastjson