数据结构——图的遍历(BFS广度优先)-蒲公英云

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

Dear 丶 2022-04-12 07:20 344阅读 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");
    }
}