图的带权广度优先搜索算法c

以下是带权广度优先搜索算法的C语言实现：

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 100
#define INF 65535

typedef int WeightType;  // 边权类型
typedef char VertexType; // 顶点类型

// 边表结点
typedef struct ArcNode {
    int adjvex;            // 邻接点在顶点数组中的下标
    WeightType weight;     // 边权值
    struct ArcNode *next;  // 指向下一个邻接点的指针
} ArcNode;

// 顶点表结点
typedef struct VNode {
    VertexType data;  // 顶点信息
    ArcNode *first;   // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];

// 图
typedef struct {
    AdjList vertices;  // 邻接表
    int vexnum;        // 顶点数
    int arcnum;        // 边数
} Graph;

// 初始化图
void InitGraph(Graph *G) {
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    getchar(); // 去掉缓冲区中的回车符

    // 初始化顶点表
    for (int i = 0; i < G->vexnum; ++i) {
        printf("请输入第%d个顶点：", i + 1);
        scanf("%c", &G->vertices[i].data);
        G->vertices[i].first = NULL;
        getchar(); // 去掉缓冲区中的回车符
    }

    // 初始化边表
    for (int i = 0; i < G->arcnum; ++i) {
        printf("请输入第%d条边的起点、终点和权值：", i + 1);
        VertexType u, v;
        WeightType w;
        scanf("%c%c%d", &u, &v, &w);
        getchar(); // 去掉缓冲区中的回车符

        // 查找边的起点和终点在顶点表中的下标
        int ui, vi;
        for (ui = 0; ui < G->vexnum; ++ui) {
            if (G->vertices[ui].data == u) {
                break;
            }
        }
        for (vi = 0; vi < G->vexnum; ++vi) {
            if (G->vertices[vi].data == v) {
                break;
            }
        }

        // 添加边到邻接表
        ArcNode *arc = (ArcNode *)malloc(sizeof(ArcNode));
        arc->adjvex = vi;
        arc->weight = w;
        arc->next = G->vertices[ui].first;
        G->vertices[ui].first = arc;
    }
}

// 从顶点i出发进行带权广度优先搜索
void BFS(Graph *G, int i, WeightType *dist) {
    int visited[MAX_VERTEX_NUM] = {0}; // 标记顶点是否被访问过

    // 初始化距离数组
    for (int j = 0; j < G->vexnum; ++j) {
        dist[j] = INF;
    }
    dist[i] = 0;

    visited[i] = 1;
    int queue[MAX_VERTEX_NUM];
    int front = 0, rear = 0;
    queue[rear++] = i;

    while (front != rear) {
        int u = queue[front++];
        ArcNode *arc = G->vertices[u].first;
        while (arc != NULL) {
            int v = arc->adjvex;
            if (!visited[v]) {
                visited[v] = 1;
                dist[v] = dist[u] + arc->weight;
                queue[rear++] = v;
            }
            arc = arc->next;
        }
    }
}

int main() {
    Graph G;
    InitGraph(&G);

    WeightType dist[MAX_VERTEX_NUM]; // 存储从顶点i到其他顶点的最短距离

    printf("请输入起点：");
    VertexType start;
    scanf("%c", &start);
    getchar(); // 去掉缓冲区中的回车符

    // 查找起点在顶点表中的下标
    int si;
    for (si = 0; si < G.vexnum; ++si) {
        if (G.vertices[si].data == start) {
            break;
        }
    }

    BFS(&G, si, dist);

    printf("距离起点%c的最短距离为：\n", start);
    for (int i = 0; i < G.vexnum; ++i) {
        if (dist[i] != INF) {
            printf("%c：%d\n", G.vertices[i].data, dist[i]);
        } else {
            printf("%c：无法到达\n", G.vertices[i].data);
        }
    }

    return 0;
}

该算法的时间复杂度为$O(|V|+|E|log|V|)$，其中$|V|$和$|E|$分别为图的顶点数和边数。