图的深度优先遍历DFS非递归 转载

#include <iostream>
using namespace std;

#define PAUSE system("PAUSE")
#define NUM 9

enum COLOR {WHITE,GRAY,BLACK};

typedef struct Node
{
char vertex;
struct Node *next;
}*pNode;

typedef struct NodeLink
{
COLOR color;
char vertex;
int StartTime;
int FinishTime;
struct Node *link;
}*pNodeLink;

typedef struct Stack
{
char vertex[NUM];
int top;
}*pStack;

void InitStack(pStack s)
{
s->top = -1;
}

void Push(pStack s,char vertex)
{
s->top++;
s->vertex[s->top] = vertex;
}

char Pop(pStack s)
{
s->top--;
return s->vertex[s->top+1];
}

char GetStackTop(pStack s)
{
return s->vertex[s->top];
}

bool IsEmpty(pStack s)
{
return (s->top == -1)?(true):(false);
}

pNodeLink CreatLink()
{
char listTable[NUM][4]={{'h','b'},{'h','c','a'},{'i','f','d','b'},{'f','e','c'},{'f','d'},{'g','e','d','c'},{'i','h','f'},{'i','g','b','a'},{'h','g','c'}};
int size[NUM]={2,3,4,3,2,4,3,4,3};

pNodeLink p = new NodeLink[NUM];

for (int i=0;i<NUM;i++)
{
   p[i].color = WHITE;
   p[i].link = NULL;
   p[i].vertex = 'a' + i;

   for (int j=0;j<size[i];j++)
   {
    pNode newNode = new Node[1];
    newNode->vertex = listTable[i][j];
    newNode->next = p[i].link;
    p[i].link = newNode;
   }
}

return p;

}

void DFS(pNodeLink p,char vertex)
{
pStack s = new Stack[1];
pNode ptr;
int time = 0;

InitStack(s);
Push(s,vertex);
cout<<"Visit "<<vertex<<endl;
p[vertex-'a'].color = GRAY;
p[vertex-'a'].StartTime = ++time;

while (!IsEmpty(s))
{
   char c = GetStackTop(s);

   ptr = p[c-'a'].link;

   while (ptr&&p[ptr->vertex-'a'].color!=WHITE)
    ptr = ptr->next;

   if (ptr)
   {
    if (p[ptr->vertex-'a'].color==WHITE)
    {
     cout<<"Visit "<<ptr->vertex<<endl;
     p[ptr->vertex-'a'].color = GRAY;
     p[ptr->vertex-'a'].StartTime = ++time;
     Push(s,ptr->vertex);
    }
   }
   else
   {
    c = Pop(s);
    p[c-'a'].color = BLACK;
    p[c-'a'].FinishTime = ++time;
   }
}

}

void main()
{
pNodeLink p = CreatLink();
DFS(p,'a');
PAUSE;

}