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

爱被打了一巴掌 2021-12-08 22:37 271阅读 0赞

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

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

#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;
    	
    }