无向图的深度优先搜索与有向图的广度优先搜索

 无向图的深度优先搜索与有向图的广度优先搜索

图采用邻接矩阵表示，实现无向图的深度优先搜索与有向图的广度优先搜索。

#include "stdio.h"
#include "stdlib.h"
#define MAX_VERTEX_NUM 20//最大顶点个数 
typedef struct {
	char vexs[MAX_VERTEX_NUM];//存放节点 
	int visited[MAX_VERTEX_NUM];//访问标志
	int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
	int vexnum,arcnum;//结点个数,边的个数 
}mgraph,*Mgraph;


//广度优先遍历需要的循环队列
typedef struct {
    int base[MAX_VERTEX_NUM];
    int front,rear;
}SqQueue;

void InitQueue(SqQueue *Q){
    Q->front = Q->rear = 0;
}

void EnQueue(SqQueue *q,int e){
	q->base[q->rear]=e;
	q->rear++;
}

void DeQueue(SqQueue *q,int *e){
	*e=q->base[q->front];
	q->front++;
}

int emptyQueue(SqQueue *q){			//队列是否满函数 
	if((q->rear+1)%(MAX_VERTEX_NUM-1)==q->front)
		return 1;
	return 0;
}


//增加节点 
void add_vexs(Mgraph *g){
	
	char c;
	printf("请输入节点值,以#结束: \n");
	scanf("%c",&c);
	while(c!='#'){
		(*g)->vexs[(*g)->vexnum]=c;
		(*g)->vexnum++;//累计结点个数 
		getchar();
		scanf("%c",&c);
	}	
	printf("输入完毕！！！\n");
	printf("%d\n",(*g)->vexnum); 
} 
//无向图增加边 
void add_arc_w(Mgraph *g){
	char v1,v2;
	int row=0,col=0;
	printf("请输入边的个数：\n");
	scanf("%d",&((*g)->arcnum));
	printf("请输入每条边的端点\n");  
	for(int i=0;i<(*g)->arcnum;i++)//控制边的个数 
	{
		getchar();
		scanf("%c %c",&v1,&v2);
		for(int j = 0; j < (*g)->vexnum; j++)
		{
			if((*g)->vexs[j] == v1)
				row = j;		
			if((*g)->vexs[j] == v2)
				col=j;	
		}
		(*g)->matrix[row][col] = 1;  
    	printf("matrix[%d][%d]=1\n",row,col);
        (*g)->matrix[col][row] = 1;//行和列在无向图的邻接矩阵是对称的 
	} 	 
	
} 
//有向图增加边
void add_arc_y(Mgraph *g) {
	char v1,v2;
	int row=0,col=0;
	printf("请输入边的个数：\n");
	scanf("%d",&((*g)->arcnum));
	printf("请输入每条边的端点\n");  
	for(int i=0;i<(*g)->arcnum;i++)//控制边的个数 
	{
		getchar();
		scanf("%c %c",&v1,&v2);
		for(int j = 0; j < (*g)->vexnum; j++)
		{
			if((*g)->vexs[j] == v1)
				row = j;		
			if((*g)->vexs[j] == v2)
				col=j;	
		}
		(*g)->matrix[row][col] = 1;  
        printf("matrix[%d][%d]=1\n",row,col); 
	} 	 
}

//初始化图
void init_mgraph(Mgraph *g){
	int i,j;
	(*g)=(Mgraph)malloc(sizeof(mgraph));
	(*g)->vexnum=(*g)->arcnum=0;
	for(i=0;i<MAX_VERTEX_NUM;i++){
		(*g)->vexs[i]=0;//节点值初始化为0
		(*g)->visited[i] = 0;//访问标志初始化为0
	} 
	for(i=0;i<MAX_VERTEX_NUM;i++)
		for(j=0;j<MAX_VERTEX_NUM;j++){
			(*g)->matrix[i][j]=0;//初始化矩阵 
		}
	add_vexs(g);
	add_arc_w(g);
}

 
void visited(Mgraph *g,int i)
{
	printf("%c ",(*g)->vexs[i]);
	(*g)->visited[i] = 1;
}
//深度遍历算法 
void DFS(Mgraph *g,int i)
{
	visited(g,i);
	for (int j = 0; j < (*g)->vexnum; j++)
	{
		if((*g)->matrix[i][j] && !(*g)->visited[j])
		{
 			DFS(g,j); //对v的尚未访问的邻接顶点w
	 	}
	}
}
void DFSTraverse(Mgraph *g){
    int i;
    for (i=0; i<(*g)->vexnum; ++i){
        if (!(*g)->visited[i])
            DFS(g, i);	//对尚未访问的顶点调用DFS
    }
}

//广度遍历算法 
void BFS(Mgraph *g,int nowi,SqQueue *Q){
	int i,j;
	for(i=nowi;i<(*g)->vexnum;i++) 
	{
		if(!(*g)->visited[i]){
			visited(g,i);
			EnQueue(Q,i);//入队 
			while(!emptyQueue(Q)){
				DeQueue(Q,&i);//队首元素出队置为u
			  	for (j=0; j<(*g)->vexnum; ++j){
                    if (!(*g)->visited[j] && (*g)->matrix[i][j]){
                        visited(g,j);
                        EnQueue(Q,j);
                    }//if
               	}//for
           	}
		}//if
	}//for 
}//BFS 
void BFSTraverse(Mgraph *g){
	SqQueue Q;
	InitQueue(&Q);
    int i;
    for (i=0; i<(*g)->vexnum; ++i){
        if (!(*g)->visited[i])
            BFS(g,i,&Q);	//对尚未访问的顶点调用DFS
    }

}

//打印邻接矩阵 
void print_mgraph(Mgraph g){
	printf("邻接矩阵为：\n");
	for(int i=0;i<g->vexnum;i++){
		printf("%3c",g->vexs[i]);
	}
	printf("\n");
	for(int i=0;i<g->vexnum;i++){
		printf("%c ",g->vexs[i]);
		for(int j=0;j<g->vexnum;j++){
			printf("%2d ",g->matrix[i][j]);
		}
		printf("\n");
	}
}

int main(){
	Mgraph g1,g2;//g1为无向图，g2为有向图 
	init_mgraph(&g1);
	print_mgraph(g1); 
	printf("图的DFS遍历结果：\n");
	DFSTraverse(&g1);
	
	getchar();
	printf("\n");
	
	init_mgraph(&g2);
	print_mgraph(g2); 
	printf("图的BFS遍历结果：\n");
	BFSTraverse(&g2);
	return 0;
	
}