图---BFS

目录：

• • 实现操作：
  • 结构体定义：
  • 图初始化：
  • 创建图：
  • BFS遍历：
  • 队列初始化：
  • 队列状态判断：
  • 入队：
  • 出队：
  • 测试：
  • 输出结果：
  • 结果分析：

实现操作：

Graph *initgraph(int vexNum);void creat_graph(Graph *graph,char *vexs,int *arcs);void BFS(Graph* G, int* visited, int index);//BFS遍历Queue* initQueue();//初始化队列int isFull(Queue* Q);//判断你是否已满int isEmpty(Queue* Q);//判断是否为空int enQueue(Queue* Q, int data);//入队int deQueue(Queue* Q);//出队

结构体定义：

#include #include #define MAX_SIZE 5typedef struct Graph{    char *vexs;     //  顶点元素    int **arcs;     //  邻接表    int vexNum;     //  顶点数量    int arcsNum;    //  边数量}Graph;typedef struct Queue {    int front;    int rear;    int data[MAX_SIZE];}Queue;

图初始化：

Graph *initgraph(int vexNum){    Graph *graph = (Graph *)malloc(sizeof(Graph));    graph->vexs = (char *)malloc(sizeof(char) * vexNum);    //为顶点元素申请内存空间    graph->arcs = (int **)malloc(sizeof(int *) * vexNum);   //指针数组(存储一维数组首地址)    for(int i = 0;i < vexNum;i++)    { graph->arcs[i] = (int *)malloc(sizeof(int) * vexNum);   //为一维数组申请内存空间    } graph->vexNum = vexNum;     //初始化顶点数量    graph->arcsNum = 0;  //初始化边数量    return graph;}

创建图：

void creat_graph(Graph *graph,char *vexs,int *arcs){    for(int i = 0;i < graph->vexNum;i++)    { graph->vexs[i] = vexs[i];//为顶点赋值 for(int j = 0; j < graph->vexNum;j++) {     graph->arcs[i][j] = *(arcs + i * graph->vexNum + j) ;      //创建邻接表     if(graph->arcs[i][j] != 0)    //二维数组不等于0是存在边，边数加 1  graph->arcsNum ++; }    }    for(int i = 0;i < graph->vexNum;i++)    {  for(int j = 0; j < graph->vexNum;j++) {     printf("%d\t",graph->arcs[i][j]); } printf("\n");    } printf("\n");    graph->arcsNum /= 2;    //无向图两顶点之间是没有方向的，}

BFS遍历：

void BFS(Graph* G, int* flag, int index) {    Queue* Q = initQueue();     //初始化队列    printf("%c\t", G -> vexs[index]);   //访问第一个结点    flag[index] = 1;      //标记已访问    enQueue(Q, index);    //入队    while (!isEmpty(Q)) { int i = deQueue(Q);      //出队 for (int j = 0; j < G -> vexNum; j++) {     //将 i 行全部遍历     if (G -> arcs[i][j] == 1 && !flag[j]) { //未访问过且存在边的关系则访问  printf("%c\t", G -> vexs[j]);  flag[j] = 1;  enQueue(Q, j);     } }    }}

队列初始化：

Queue* initQueue() {    Queue* Q = (Queue*)malloc(sizeof(Queue));    Q->front = Q->rear = 0;    return Q;}

队列状态判断：

int isFull(Queue* Q) {    if ((Q->rear + 1) % MAX_SIZE == Q->front) { return 1;    }    else { return 0;    }}int isEmpty(Queue* Q) {    if (Q->front == Q->rear) { return 1;    }    else { return 0;    }}

入队：

int enQueue(Queue* Q, int data) {    if (isFull(Q)) { return 0;    }    else { Q->data[Q->rear] = data; Q->rear = (Q->rear + 1) % MAX_SIZE; return 1;    }}

出队：

int deQueue(Queue* Q) {    if(isEmpty(Q)) { return -1;    }    else { int data = Q->data[Q->front]; Q->front = (Q->front + 1) % MAX_SIZE; return data;    }}

测试：

#include "graph.h"void main(){    Graph *graph = initgraph(5);    int *flag = (int *)malloc(sizeof(int) * graph->vexNum);    for(int i = 0;i < graph->vexNum;i++)    { flag[i] = 0;    }    int arcs[5][5] = { 0,1,1,1,0, 1,0,1,1,1, 1,1,0,0,0, 1,1,0,0,1, 0,1,0,1,0    }; creat_graph(graph,"ABCDE",(int *)arcs);    printf("BFS遍历结果：\n");    BFS(graph,flag,0);    printf("\n"); system("pause");    return ;}

输出结果：

结果分析：

说明：下图 ② 遍历指向错误，应指向 A 所在行


声明：此文章为学习笔记，如有侵权请联系删除。

三国人物百科