数据结构——图的遍历(BFS广度优先)

Dear 丶 2022-04-12 07:20 213阅读 0赞

//无向图  
//邻接矩阵  
//有权值  
//广度优先遍历  
//使用了队列

准备工作：

#include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    
    #define MAX_VERTEX_NUM 20
    #define MAX 20
    #define INF -1
    const int error=-1;
    #define ok 1
    
    typedef struct ArcCell
    {
    	int adj;
    }ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    
    typedef struct 
    {
    	char vexs[MAX][MAX];
    	AdjMatrix arcs;
    	int vexnum,arcnum;
    }MGraph;
    
    typedef struct QNode
    {
    	int data;
    	struct QNode *next;
    }QNode,*QueuePtr;
    
    typedef struct
    {
    	QueuePtr front;
    	QueuePtr rear;
    }LinkQueue;
    
    //函数原型
    void CreateUDN(MGraph &G);
    int LocatVex(MGraph G,char v[MAX]);
    void show(MGraph G);
    int firstAdjVex(MGraph G,int &v);
    int NextAdjVex(MGraph G,int &v,int &w);
    void BFS(MGraph G);
    void InitQueue(LinkQueue &Q);
    void EnQueue(LinkQueue &Q,int x);
    void DeQueue(LinkQueue &Q,int &w);
    
    //全局变量:
    int visited[MAX];

主函数:

int main()
    {
    	MGraph G;
    	CreateUDN(G);
    	show(G);
        BFS(G);
    	return 0;
    }

BFS代码：

void BFS(MGraph G)
    {
    	int i,w,v;
    	LinkQueue Q;
    	InitQueue(Q);
    	for(i=0;i<G.vexnum;i++)
    	{
    		visited[i]=error;
    	}
    	for(i=0;i<G.vexnum;i++)
    	{
    		if(visited[i]==error)
    		{
    			printf("%s -> ",G.vexs[i]);
    			visited[i]=ok;
    			EnQueue(Q,i);
    			while(Q.rear!=Q.front)
    			{
    				DeQueue(Q,v);
    				for(w=firstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
    				{
    					if(visited[w]==error)
    					{
    						visited[w]=ok;
    						printf(" %s -> ",G.vexs[w]);
    						EnQueue(Q,w);
    					}
    				}
    			}
    		}
    	}
    
    }

求邻接点的代码:

int firstAdjVex(MGraph G,int &v)
    {
    	int i;
    	for(i=0;i<G.vexnum;i++)
    	{
    		if(G.arcs[v][i].adj!=error)
    		{
    			return i;
    		}
    	}
    	return error;
    }
    
    int NextAdjVex(MGraph G,int &v,int &w)
    {
    	int i;
    	for(i=w+1;i<G.vexnum;i++)
    	{
    		if(G.arcs[v][i].adj!=error)
    		{
    			return i;
    		}
    	}
    	return error;
    }

使用到关于队列的代码：

void EnQueue(LinkQueue &Q,int x)
    {
    	QNode *p;
    	p=(QueuePtr)malloc(sizeof(QNode));
    	if(!p) exit(0);
    	p->data=x;
    	p->next=NULL;
    	Q.rear->next=p;
    	Q.rear=p;
    	return ;
    }
    
    void InitQueue(LinkQueue &Q)
    {
    	Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
    	if(Q.front==NULL) exit(0);
    	Q.front->next=NULL;
    	Q.rear->next=NULL;
    }
    
    void EnQueue(LinkQueue &Q,int x)
    {
    	QNode *p;
    	p=(QueuePtr)malloc(sizeof(QNode));
    	if(!p) exit(0);
    	p->data=x;
    	p->next=NULL;
    	Q.rear->next=p;
    	Q.rear=p;
    	return ;
    }

创建邻接矩阵的代码：

void CreateUDN(MGraph &G)
    {
    	int i,j,v,w;
    	char v1[MAX],v2[MAX];
    	printf("请输入顶点的个数: ");
    	scanf("%d",&G.vexnum);
    	printf("请输入边的个数: ");
    	scanf("%d",&G.arcnum);
    	for(i=0;i<G.vexnum;i++)
    	{
    		printf("请输入第%d个顶点的名称:",i+1);
    		scanf("%s",G.vexs[i]);
    	}
    	for(i=0;i<G.vexnum;i++)
    	{
    		for(j=0;j<G.vexnum;j++)
    		{
    			G.arcs[i][j].adj=INF;
    		}
    	}
    	for(v=0;v<G.arcnum;v++)
    	{
    		printf("请输入第一个顶点:");
    		scanf("%s",&v1);
    		printf("请输入第二个顶点:");
    		scanf("%s",&v2);
    		i=LocatVex(G,v1);
    		j=LocatVex(G,v2);
    		printf("请输入两顶点之间的权值:");
    		scanf("%d",&w);
    		G.arcs[i][j].adj=w;
    		G.arcs[j][i]=G.arcs[i][j];
    	}
    }
    
    int LocatVex(MGraph G,char v[MAX])
    {
    	int i;
    	for(i=0;i<G.vexnum;i++)
    	{
    		if(strcmp(G.vexs[i],v)==0)
    		{
    			return i;
    		}
    	}
    	return error;
    }
    
    //打印邻接矩阵
    void show(MGraph G)
    {
    	int i,j;
    	for(i=0;i<G.vexnum;i++)
    	{
    		for(j=0;j<G.vexnum;j++)
    		{
    			if(G.arcs[i][j].adj!=error) printf(" %d",G.arcs[i][j].adj);
    			else printf("  ");
    		}
    		printf("\n");
    	}
    }