dfs算法

#include<iostream>

#include<stack>

#include<stdio.h>

#include<stdlib.h>

#define MAX 100

using namespace std;

typedef struct

{

    int edges[MAX][MAX];    //鄰接矩陣

    int n;                  //頂點數

    int e;                  //邊數

}MGraph;

bool visited[MAX];          //标記頂點是否被通路過

void creatMGraph(MGraph &G)    //用引用作參數

{

    int i,j;

    int s,t;                 //存儲頂點編号

    int v;                   //存儲邊的權值

    for(i=0;i<G.n;i++)       //初始化

    {

        for(j=0;j<G.n;j++)

        {

            G.edges[i][j]=0;

        }

        visited[i]=false;

    }

    for(i=0;i<G.e;i++)      //對矩陣相鄰的邊賦權值

    {

        scanf("%d %d %d",&s,&t,&v);   //輸入邊的頂點編号以及權值

        G.edges[s][t]=v;

    }

}

void DFS(MGraph G,int v)      //深度優先搜尋

{

    int i;

    printf("%d ",v);          //通路結點v

    visited[v]=true;

    for(i=0;i<G.n;i++)       //通路與v相鄰的未被通路過的結點

    {

        if(G.edges[v][i]!=0&&visited[i]==false)

        {

            DFS(G,i);

        }

    }

}

void DFS1(MGraph G,int v)   //非遞歸實作

{

    for(int i=0;i<G.n;i++)       //初始化

    {

        visited[i]=false;

    }

    stack<int> s;

    printf("%d ",v);        //通路初始結點

    visited[v]=true;

    s.push(v);              //入棧

    while(!s.empty())

    {

        int i,j;

        i=s.top();          //取棧頂頂點

        for(j=0;j<G.n;j++)  //通路與頂點i相鄰的頂點

        {

            if(G.edges[i][j]!=0&&visited[j]==false)

            {

                printf("%d ",j);     //通路

                visited[j]=true;

                s.push(j);           //通路完後入棧

                break;               //找到一個相鄰未通路的頂點，通路之後則跳出循環

            }

        }

        if(j==G.n)                   //如果與i相鄰的頂點都被通路過，則将頂點i出棧

            s.pop();

    }

}

int main()

{

    int n,e;    //建立的圖的頂點數和邊數

    while(scanf("%d %d",&n,&e)==2&&n>0)

    {

        MGraph G;

         G.n=n;

        G.e=e;

        creatMGraph(G);

        printf("深度遞歸算法: ");

        DFS(G,0);

        printf("\n");

        printf("深度非遞歸算法: ");

        DFS1(G,0);

        printf("\n");

    }

    return 0;

}

// 8 9 0 1 1 0 2 1 1 3 1  1 4 1 2 5 1 2 6 1 5 6 1 3 7 1 4 7 1