C语言版飞机订票系统

for(i=1;i<=G.vexnum;i++) visited[i]=False; //访问标志数组初始化 for(i=1;i<=G.vexnum;i++)

if(!visited[i]) DFS(G,i); //对尚未访问的顶点调用DFS printf(\); }

void DFS(Graph G,int i)

{//从第i个顶点出发递归地深度遍历图G int w;

visited[i]=True; //访问第i个顶点 printf(\,i);

for(w=FirstAdjVex(G,i);w>0;w=NextAdjVex(G,i,w))

if(!visited[w]) DFS(G,w); //对尚未访问的邻接顶点w调用DFS }

void BFSTraverse(Graph G)

{//按广度优先非递归的遍历图G，使用辅助队列Q和访问标志数组visited int i,u,w;

SqQueue Q;

printf(\广度优先遍历:\);

for(i=1;i<= G.vexnum;i++) visited[i]=False; //访问标志数组初始化 Initial(Q); //初始化队列 for(i=1;i<=G.vexnum;i++) if(!visited[i])

{visited[i]=True; //访问顶点i printf(\,i);

EnQueue(Q,i); //将序号i入队列

while(!QueueEmpty(Q)) //若队列不空，继续 {DeQueue(Q,u); //将队头元素出队列并置为u

for(w=FirstAdjVex(G,u);w>0;w=NextAdjVex(G,u,w))

if(!visited[w]) //对u的尚未访问的邻接顶点w进行访问并入队列 {visited[w]=True; printf(\,w); EnQueue(Q,w);

} } }

printf(\); }

int FirstAdjVex(Graph G,int v)

{//在图G中寻找第v个顶点的第一个邻接顶点 if(!G.AdjList[v]) return 0;

else return(G.AdjList[v]->adjvex); }

int NextAdjVex(Graph G,int v,int u)

{//在图G中寻找第v个顶点的相对于u的下一个邻接顶点 ArcNode *p; p=G.AdjList[v];

while(p->adjvex!=u) p=p->nextarc; //在顶点v的弧链中找到顶点u if(p->nextarc==NULL) return 0; //若已是最后一个顶点，返回

else return(p->nextarc->adjvex); //返回下一个邻接顶点的序号 }

void Initial(SqQueue &Q) {//队列初始化 Q.front=Q.rear=0; }

BOOL QueueEmpty(SqQueue Q)

{//判断队列是否已空，若空返回True,否则返回False if(Q.front==Q.rear) return True; else return False; }

BOOL EnQueue(SqQueue &Q,int ch)

{//入队列，成功返回True，失败返回False

if((Q.rear+1)%MAXQSIZE==Q.front) return False; Q.elem[Q.rear]=ch;

Q.rear=(Q.rear+1)%MAXQSIZE;