DFS算法的非递归遍历分析

两种写法，一个是边表顶点号全部压栈，一个是类似后序非递归遍历

1、

void DFS(Graph G,int i)
{
    int p,w;
    Stack S;
    InitStack(S);
    Push(S,i);
    visited[i]=true;
    while(!isEmpty(S))
    {
        Pop(S,p);
        printf("%d    ",G.Ver[p].num);
        for(w=FirstNeighbor(G,p);w>=0;w=NextNeighbor(G,p,w))
        {
            if(!visited[w])
            {
                Push(S,w);
                visited[w]=true;
            }
        }
    }
}

2、有一个回头的操作，但是不如第一种直接

void DFS(Graph G,int i)
{
    int p,w;
    Stack S;
    InitStack(S);
    printf("%d    ",G.Ver[i].num);
    visited[i]=true;
    Push(S,i);
    while(!isEmpty(S))
    {
        GetTop(S,p);
        w=FirstNeighbor(G,p);
        if(w!=-1&&!visited[w])
        {
            Push(S,w);
            visited[w]=true;
            printf("%d    ",G.Ver[w].num);    
        }
        else
        {
            Pop(S,p);
            if(isEmpty(S))
                break;
            GetTop(S,w);
            w=NextNeighbor(G,w,p);
            if(w!=-1&&!visited[w])
            {
                printf("%d    ",G.Ver[w].num);
                visited[w]=true;
                Push(S,w);
            }
        }
    
    }            
} 

完整代码

#include <stdio.h> 
#include <stdlib.h> 
#define MaxSize 20

typedef int Elem ;
                                        //邻接表 
typedef struct ArcNode{        //边表 
    int adjvex;                //边表中是顶点号！！ 
    struct ArcNode *next;
}ArcNode;

typedef struct VNode{        //主表 
    Elem num;                //主表中是顶点值！！ 
    struct ArcNode *first; 
}VNode,AdjList[MaxSize];

typedef struct{                    
    AdjList Ver;
    int vernum,edgenum;
}Graph;

typedef struct{
    int data[MaxSize];
    int top;
}Stack;

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

bool isEmpty(Stack S)
{
    if(S.top==-1)
        return true;
    return false;
}

bool isFull(Stack S)
{
    if(S.top==MaxSize-1)
        return true;
    return false;
}

bool Push(Stack &S,int p)
{
    if(isFull(S))
        return false;
    S.data[++S.top]=p;
    return true;
}

bool Pop(Stack &S,int &p)
{
    if(isEmpty(S))
        return false;
    p=S.data[S.top--];
    return true;
}

bool GetTop(Stack S,int &p)
{
    if(isEmpty(S))
        return false;
    p=S.data[S.top];
    return true;
}

void CreateGraph(Graph &G)
{
    G.vernum=G.edgenum=0;
    printf("请输入顶点数:");
    scanf("%d",&G.vernum);
    printf("请输入主表顶点:\n");
    int i,j;
    for(i=0;i<G.vernum;i++)
        scanf("%d",&G.Ver[i].num);
    
    printf("请输入边表顶点号:\n");
    int x;
    for(i=0;i<G.vernum;i++)
    {
        G.Ver[i].first = (ArcNode*)malloc(sizeof(ArcNode));
        G.Ver[i].first->next=NULL;
        printf("%d的边表\n",G.Ver[i].num); 
        ArcNode *p=G.Ver[i].first;
        for(j=0;j<G.vernum;j++)
        {
            scanf("%d",&x);
            if(x==-1)
                break;
            else
            {
                ArcNode *node=(ArcNode*)malloc(sizeof(ArcNode));
                node->adjvex=x;
                node->next=NULL;
                p->next=node;
                p=node;
                G.edgenum++;
            }
        }
    }
}

void displayGraph(Graph G)
{
    int i,j;
    printf("顶点个数:%d\n边数:%d\n",G.vernum,G.edgenum);
    for(i=0;i<G.vernum;i++)
    {
        printf("%d    ",G.Ver[i].num);    
        ArcNode *p=G.Ver[i].first->next;
        while(p)
        {
            printf("-->%d",p->adjvex);
            p=p->next;
        }
        printf("\n");
    } 
}

int FirstNeighbor(Graph G,int x)
{
    if(G.Ver[x].first->next)
        return G.Ver[x].first->next->adjvex;
    return -1;
}

int NextNeighbor(Graph G,int x,int y)
{
    ArcNode *p=G.Ver[x].first->next;
    while(p&&p->adjvex!=y)
        p=p->next;

    if(p->next)
        return p->next->adjvex;    
    return -1;    
}

bool visited[MaxSize];

void DFS(Graph G,int i)
{
    int p,w;
    Stack S;
    InitStack(S);
    printf("%d    ",G.Ver[i].num);
    visited[i]=true;
    Push(S,i);
    while(!isEmpty(S))
    {
        GetTop(S,p);
        w=FirstNeighbor(G,p);
        if(w!=-1&&!visited[w])
        {
            Push(S,w);
            visited[w]=true;
            printf("%d    ",G.Ver[w].num);    
        }
        else
        {
            Pop(S,p);
            if(isEmpty(S))
                break;
            GetTop(S,w);
            w=NextNeighbor(G,w,p);
            if(w!=-1&&!visited[w])
            {
                printf("%d    ",G.Ver[w].num);
                visited[w]=true;
                Push(S,w);
            }
        }
    
    }            
} 

void DFS(Graph G,int i)
{
    int p,w;
    Stack S;
    InitStack(S);
    Push(S,i);
    visited[i]=true;
    while(!isEmpty(S))
    {
        Pop(S,p);
        printf("%d    ",G.Ver[p].num);
        for(w=FirstNeighbor(G,p);w>=0;w=NextNeighbor(G,p,w))
        {
            if(!visited[w])
            {
                Push(S,w);
                visited[w]=true;
            }
        }
    }
}

void DFSbyStack(Graph G)
{
    int i;
    for(i=0;i<G.vernum;i++)
        visited[i]=false;
    for(i=0;i<G.vernum;i++)
        if(!visited[i])
            DFS(G,i);
}

int main()
{
    Graph G;
    CreateGraph(G);
    printf("\n");
    displayGraph(G);
    printf("\n");
    DFSbyStack(G);
    return 0;
}