图的广度优先遍历:释义详见百度百科

  基本思想: 广度优先搜索使用队列(queue)来实现:
    1、把根节点放到队列的末尾。
    2、每次从队列的头部取出一个元素,查看这个元素所有的下一级元素,把它们放到队列的末尾。并把这个元素记为它下一级元素的前驱。
    3、找到所要找的元素时结束程序。
    4、如果遍历整个树还没有找到,结束程序。

广度优先遍历

1.邻接表

#include <stdio.h>
#include <stdlib.h>
const int maxsize = 1010;
//图的邻接表的存储结构
typedef struct ArcNode {    //边结点
    int adjvex;        //序号
    struct ArcNode *next;
}ArcNode;
typedef struct VNode{    //顶点
    ArcNode *firstarc;
    int no;
}VNode;
typedef struct Graph {      //图
    VNode VNodeList[maxsize];
    int node;    //顶点数
    int edge;    //边数
}Graph;

//创建邻接表
void createGraph(Graph *G){
    int start;
    int end;
    ArcNode *e;

    scanf("%d%d",&(G->node),&(G->edge));        //输入边数和结点数

    for(int i = 0; i < G->node; i++){//输入顶点
        scanf("%d",&(G->VNodeList[i].no));
        G->VNodeList[i].firstarc = NULL;
    }

    for(int i = 0; i < G->edge; i++){
        scanf("%d%d",&start,&end);

        //插入该点指向的边表
        e =(ArcNode*)malloc(sizeof(ArcNode));//分配空间
        e->adjvex = end;
        e->next = G->VNodeList[start].firstarc;
        G->VNodeList[start].firstarc = e;//类似于链表的前插

        //无向图才有下方
        e =(ArcNode*)malloc(sizeof(ArcNode));//分配空间
        e->adjvex = start;
        e->next = G->VNodeList[end].firstarc;
        G->VNodeList[end].firstarc = e;//类似于链表的前插
    }
}

int visited[maxsize] = {0};
void BFS(Graph *g, int v){
    if(g == NULL) return;
    int queue[maxsize];
    int front = -1, rear = 0;
    printf("访问结点:%d\n",g->VNodeList[v].no);
    visited[v] = 1;
    queue[rear++] = v;
    ArcNode* e;

    while(front != rear){
        int u = queue[++front];        //取队首
        e = g->VNodeList[u].firstarc;    //获取第一个邻接点
        while(e!=NULL){        //遍历
            if(visited[e->adjvex] == 0){
                printf("访问结点:%d\n",g->VNodeList[e->adjvex].no);
                visited[e->adjvex] = 1;
                queue[rear++] = e->adjvex;
            }
            e = e.next;
        }
    }
}

2.邻接矩阵

#include <stdio.h>
#include <stdlib.h>
const int maxn = 110;
//图的邻接矩阵的存储结构
typedef struct
{
    int vertex[maxn];   //顶点数组
    int arc[maxn][maxn];  //邻接矩阵
    int vertexnum;   //顶点数
    int arcnum;  //边数
}Graph;

//创建邻接矩阵
void CreateGraph(Graph &G){
    scanf("%d%d",&G.vertexnum,&G.arcnum);    //输入边数,顶点数
    for(int i = 0; i < G.vertexnum; i++)    //输入顶点信息
       scanf("%d",&G.vertex[i]);
    for(int i = 0; i < G.vertexnum; i++)    //将所有边初始化为无穷大
        for(int j = 0; j < G.vertexnum; j++)
            G.arc[i][j] = -1;
    for(int k = 0; k < G.arcnum; k++){
        int start, end, weight;
        scanf("%d%d%d",&start,&end,&weight);    //输入起点,终点,权重
        G.arc[start][end] = weight;
        //无向图才有下方这句
        G.arc[end][start] = G.arc[start][end];  //无向图的邻接矩阵为对称矩阵
    }
}

int visited[maxn] = {0}
void BFS(Graph* g, int v){
    if(g == NULL) return;
    int queue[maxn];
    int front = -1, rear = 0;
    //memset(visited,0,sizeof(visited));        //或者在这初始化数组
    printf("访问结点:%d\n", g->vertex[v]);                 //访问
    visited[v] = 1;                   //顶点v已被访问
    q[rear++] = v;                    //将v入队

    while (front != rear){
        int u = q[++front];                //将队头元素u出队,开始访问u的所有邻接点
        for (int i = 0; i < G.vexnum; i++){
            int w = g->vertex[i];
            if (g->arc[u][i]!=-1 && visited[i] == 0){ //有边,且顶点未被访问
                printf("访问结点:%d\n", w);    //输出顶点
                q[rear++] = i;        //将顶点w入队
                visited[i] = 1;        //置已访问
            }
        }
    }
}
  • alipay
  • wechat