#include<stdio.h>
#include<stdlib.h>
#include<graph2.h>
#define MAX_VERTEX_NUM 20
#define MAX 40
typedef int InfoType;
typedef char VertexType;
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
InfoType *info;
}ArcNode;
typedef struct VNode
{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
int kind;
}ALGraph;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int SElemType;
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
void InitStack(SqStack &S)
{
S.base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType));
if(!S.base) exit(1);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}
int StackEmpty(SqStack S)
{
if(S.top==S.base)
return 1;
else
return 0;
}
int StackLength(SqStack S)
{
return S.top-S.base;
}
void Push(SqStack &S,SElemType e)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base) exit(1);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
}
int Pop(SqStack &S,SElemType &e)
{
if(S.top==S.base) return 0;
e=*--S.top;
return 1;
}
void print(SqStack S)
{
while(S.top==S.base)
{
printf("%d",*--S.top);
}
}
int LIN[MAX];
datagraph g1;
void DFS(datagraph G,int v)
{
LIN[v]=1;
int w;
for(w=firstadj(G,v);w>=0;w=nextadj(G,v,w))
if(!LIN[w])
{
copy_edge(G,v,w,g1);
display_edge(g1,v,w);
DFS(G,w);
}
}
void DFSTraverse(datagraph G)
{
SqStack S;
InitStack(S);
int v;
for(v=0;v<nodes(g);v++) LIN[v]=0;
do{
if(!LIN[v])
{ int e;
Push(S,v);
if(StackLength(S)==nodes(G))
{
print(S);
Pop(S,e);
LIN[e]=0;
while(!nextadj(G,v,e))
{
Pop(S,e);
v--;
LIN[e]=0;
}
DFS(G,v);
v++;
}
}
}while(v<nodes(g)&&StackEmpty(S));
}
main()
{
load_graph_file(g,"graphs\\bfs.grp");
display_graph("yuantu",g);
copy_all_vertex(g,g1,300,0);
disp_graph("shengdubilishengchengshu",g1);
DFSTraverse(g);
}