邻接矩阵的深度优先遍历

废话不多说，直接看代码

t#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define INFINITY INT_MAX
#define  MAX_VERTEX_NUM 20
bool visted[MAX_VERTEX_NUM]; 
typedef char VertexType; 
typedef int VRType; 
typedef int QElemType;
typedef enum {
DG,DN,AG,AN
}Graphkind;
typedef struct ArcCell{//表征图的连接关系  
VRType adj;            //连接关系  
ArcCell *info;         //附加信息  
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
	VertexType vexs[MAX_VERTEX_NUM];//顶点的类型 
	AdjMatrix arcs;//邻接矩阵 
	int vexnum,arcnum;//图的顶点数，边数 
	Graphkind kind;//图的类型 
}Mgraph;
typedef struct QNode{//队列节点 
        QElemType data;
        struct QNode *next;
      }QNode,*QueuePtr;
      typedef struct{
      	QueuePtr front;
      	QueuePtr rear;
	  }LinkQueue;//队列指针 
	  void InitQueue(LinkQueue *Q) {//初始化队列 
	  	(*Q).rear= (*Q).front=(QueuePtr)malloc(sizeof(QNode)) ;
	  	if(!(*Q).front)
	  	exit(-1);
		(*Q).front->next=NULL;
	  }
	  void EnQueue(LinkQueue *Q,QElemType e){//入队操作 
	  	//if(((*Q).rear+1)%MAXQSIZE==(*Q).front)
	  	//exit(-1);
	  	QueuePtr p;
	    (p)=(QueuePtr)malloc(sizeof(QNode)) ;
	  	
		  p->data=e;
		  p->next=NULL;
		  (*Q).rear->next=p;
		  (*Q).rear=p;
	  }
	  void DeQueue(LinkQueue *Q,QElemType *e){//出队操作 
	  //	if((*Q).front==(*Q).rear)
	  //	exit(-1);
	  QueuePtr p;
	  	if((*Q).front==(*Q).rear)
	  	exit(-1);
	  	p=(*Q).front->next;
	  	(*e)=p->data;
	  	(*Q).front->next=p->next;
	  	if((*Q).rear==p){
	  		(*Q).rear=(*Q).front;
	  		free(p);
		  }
	  }
	  int QueueEmpty(LinkQueue Q){//判断队列是否为空 
	  	if((Q).front==(Q).rear)
	  	return 1;
	  	return 0;
	  }
void CreateG(Mgraph &G,int kind)             //创建图  
{  
    int i,j;  
  
    printf("Construct the Graph...\n");  
    if(kind ==1){

    G.vexnum=8;  
    G.arcnum=9; 
	G.kind= AG;
}else{
	G.vexnum=8;  
    G.arcnum=12; 
	G.kind= DG;
	
}
  
    for(i=0;i<MAX_VERTEX_NUM;i++)    //邻接矩阵的初始化  
    {  
        for(j=0;j<MAX_VERTEX_NUM;j++)  
        {  
            G.arcs[i][j].adj=0;  
            G.arcs[i][j].info=NULL;  
        }  
    }  
  
    G.vexs[0]='a';                //顶点赋值  
    G.vexs[1]='b';  
    G.vexs[2]='c';  
    G.vexs[3]='d';  
    G.vexs[4]='e';  
    G.vexs[5]='f';  
    G.vexs[6]='g';  
    G.vexs[7]='h';  
	  if(kind ==1){
    G.arcs[0][1].adj=1;             //邻接矩阵赋值  
    G.arcs[0][1].info=NULL;  
    
    G.arcs[1][0].adj=1;  
    G.arcs[1][0].info=NULL;  
  
    G.arcs[1][3].adj=1;  
    G.arcs[1][3].info=NULL;  
    G.arcs[3][1].adj=1;  
    G.arcs[3][1].info=NULL;  
  
    G.arcs[3][7].adj=1;  
    G.arcs[3][7].info=NULL;  
    G.arcs[7][3].adj=1;  
    G.arcs[7][3].info=NULL;  
  
    G.arcs[4][7].adj=1;  
    G.arcs[4][7].info=NULL;  
    G.arcs[7][4].adj=1;  
    G.arcs[7][4].info=NULL;  
  
    G.arcs[4][1].adj=1;  
    G.arcs[4][1].info=NULL;  
    G.arcs[1][4].adj=1;  
    G.arcs[1][4].info=NULL;  
  
    G.arcs[0][2].adj=1;  
    G.arcs[0][2].info=NULL;  
    G.arcs[2][0].adj=1;  
    G.arcs[2][0].info=NULL;  
  
    G.arcs[2][5].adj=1;  
    G.arcs[2][5].info=NULL;  
    G.arcs[5][2].adj=1;  
    G.arcs[5][2].info=NULL;  
  
    G.arcs[2][6].adj=1;  
    G.arcs[2][6].info=NULL;  
    G.arcs[6][2].adj=1;  
    G.arcs[6][2].info=NULL;  
  
    G.arcs[5][6].adj=1;  
    G.arcs[5][6].info=NULL;  
    G.arcs[6][5].adj=1;  
    G.arcs[6][5].info=NULL;  
    }else{
    	G.arcs[0][1].adj=1;             //邻接矩阵赋值  
        G.arcs[0][1].info=NULL;  
        G.arcs[0][3].adj=1;             //邻接矩阵赋值  
        G.arcs[0][3].info=NULL;  
        G.arcs[1][2].adj=1;  
        G.arcs[1][2].info=NULL; 
        G.arcs[2][5].adj=1;  
        G.arcs[2][5].info=NULL; 
        G.arcs[2][3].adj=1;  
        G.arcs[2][3].info=NULL; 
        G.arcs[3][4].adj=1;  
        G.arcs[3][4].info=NULL; 
        G.arcs[4][2].adj=1;  
        G.arcs[4][2].info=NULL; 
		G.arcs[4][6].adj=1;  
        G.arcs[4][6].info=NULL; 
        G.arcs[5][4].adj=1;  
        G.arcs[5][4].info=NULL; 
        G.arcs[5][7].adj=1;  
        G.arcs[5][7].info=NULL; 
		G.arcs[6][7].adj=1;  
        G.arcs[6][7].info=NULL;
		G.arcs[7][4].adj=1;  
        G.arcs[7][4].info=NULL; 
 
        
	} 
  
    printf("Construction of Graph OK!\n\n");  
    return;  
}
void ShowAdjMat(Mgraph G)           //邻接矩阵的显示  
{  
    int i,j;  
  
    printf("The adjacent matrix is:\n");  
    for(i=0;i<G.vexnum;i++)  
    {  
        for(j=0;j<G.vexnum;j++)  
        {  
            printf("%d ",G.arcs[i][j].adj);  
        }  
        printf("\n");  
    }  
    printf("\n");  
  
    return;  
}  
int GetNextVertex(Mgraph G,int v)   //获取下一顶点  
{  
    int i;  
  
    for(i=0;i<G.vexnum;i++)  
    {  
        if(G.arcs[v][i].adj==1&& visted[i]==false)  
        {  
            return i;  
        }  
    }  
  
    return -1;  
}  
void DFS(Mgraph G,int v)            //深度优先搜索  
{  
    int i;  
    int nextid;  
  
    printf("%c ",G.vexs[v]);  
    visted[v]=true;  
    while(1)  
    {  
        nextid=GetNextVertex(G,v);  
        if(nextid!=-1 && visted[nextid]==false)  
        {  
            DFS(G,nextid);  
        }  
        else  
        {  
            break;  
        }  
    }  
  
}  
  
void DFSTraverse(Mgraph G)          //深度优先搜索  
{  
    int i;  
  
    printf("The depth first traverse result is:\n");  
    for(i=0;i<G.vexnum;i++)  
    {  
        visted[i]=false;  
    }  
  
    for(i=0;i<G.vexnum;i++)  
    {  
        if(visted[i]!=true)  
        {  
            DFS(G,i);  
        }  
    }  
}  

void BFSTraverse(Mgraph G){
	int v,w,u;
	LinkQueue Q; 
	for(v=0;v<G.vexnum;++v) 
	visted[v]=false;
	InitQueue(&Q); //置空的辅助队列Q
	printf("The depth first traverse result is:\n");  
    for(v=0;v<G.vexnum;++v)
    if(!visted[v]) { //v尚未访问
    visted[v]=true;
	printf("%c ",G.vexs[v]); 
	EnQueue(&Q,v);
	while(!QueueEmpty(Q)) {
		DeQueue(&Q,&u);//队头元素出队并置为u
		for(w=u; w>=0; w=GetNextVertex(G,u))
		if(!visted[w]) { //w为u的尚未访问的邻接顶点
		visted[w]=true;
		printf("%c ",G.vexs[w]); 
		EnQueue(&Q,w);
		}//if
		}//while
		}//if
}






int main()  
{  
    Mgraph G,G2;  
  printf("无向图：\n");
    CreateG(G,1);  
    ShowAdjMat(G);  
    DFSTraverse(G);  
  
    printf("\n\n");
    
    
	printf("有向图：\n");  
     CreateG(G2,2);  
    ShowAdjMat(G2);  
    BFSTraverse(G2);  
  
    printf("\n\n"); 
    system("pause");  
    return 0;  
}