图的遍历实现实验报告2011021225陈曦路

typedef int InfoType;

typedef int V

ertexType;

typedef int Status;

typedef int QElemType;

typedef int SElemType;

typedef enum{DG,DN,UDG,UDN}GraphKind;//

无向图，无向网，有向

图，有向网

bool visited[MAX_VERTEX_NUM];

typedef struct ArcNode{

int adjvex;//

该弧所指向的顶点在数组中的下标

struct ArcNode *nextarc;

InfoType *info;//

该弧相关信息的指针

}ArcNode;

typedef struct VNode{

V

ertexType data;//

顶点信息

ArcNode *firstarc;//

指向第一条依附该顶点的弧的指针

}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct{

AdjList vertices;

int vexnum,arcnum;//

图的当前顶点数和弧数

int kind;//

图的种类标志

}ALGraph;

typedef struct{

SElemType *base;

SElemType *top;

int stacksize;

}SqStack;

typedef struct QNode{

QElemType data;

struct QNode *next;

}QNode,*QueuePtr;

typedef struct{

QueuePtr front;

QueuePtr rear;

}LinkQueue;

int LocateV

ex(ALGraph G,V

ertexType v){//

返回数组下标值

int i;

for(i=0;i

if(es[i].data==v)

return i;

return -1;

}

void CreateDN(ALGraph &G){ //

构造有向图

G(=DN)

int i,j,k;

ArcNode *p;

V

ertexType v1,v2;

G

.kind=DN;

printf(

输入顶点数

:

scanf(

printf(

输入弧数

:

scanf(

printf(

输入顶点

: n

for(i=0;i<;++i){//

构建表头向量

scanf(

es[ i].firstarc=NULL;//

初始化指针

}

for(k=0;k<;++k){

printf(

第

%d

条弧

: n

scanf(

scanf(

输入一条弧的始点和终点

i=LocateV

ex(G,v1);

j=LocateV

ex(G,v2);//

确定

v1

和

v2

在

G

中的位置

p=(ArcNode*)malloc(sizeof(ArcNode));

p->adjvex=j;

p->nextarc=G

.vertices[i].firstarc; es[i].firstarc=p;

scanf(

}

}

Status Push(SqStack &S,SElemType e){

if(>=ize){

=(S ElemType*)realloc(,(ize+STACKINCREMENT)

*sizeof(SElemType));

if(!)

exit(-2);

=+ize;

ize+=STACKINCREMENT;

}

*++=e;

return 1;

}

Status InitStack(SqStack &S){

=(SElemType*)malloc(STACK_INIT_SIZE*sizeo f(SElemType));

if(!)

exit(-2);

=;

ize=STACK_INIT_SIZE;

return 1;

}

Status Pop(SqStack &S,SElemType &e){

if(==)

return 0;

e=*--;

return 1;

}

Status GetTop(SqStack S,SElemType &e){

if(==)

return 0;

e=*(-1);

return 1;

}