【数据结构 | C语言】有向图源点到其余各顶点的最短路径（广度优先遍历）

算法完整代码

示例图代码结果

本文对应书《数据结构（C语言版）》严蔚敏》p188 讲述的源点到其余各点间的最短路径，而不是迪杰斯特拉算法或弗罗伊德算法。本文仅仅通过广度优先搜索结合书上原理写出最短路径算法

上面两种算法，请看主页下一篇博客，或者

void ShortestPath(pGraph graph) {
    // 最短路径数组
    int path[graph->vexnum];
    bool visit[graph->vexnum];
    for (int i=0; ivexnum; i++) {
        visit[i] = path[i] = 0;
    }
    // wfs 队列
    pQueue q = CreateQueue();
    EnQueue(q, graph->data[0]);
    visit[0] = true;
    while (!Empty(q)) { // 队列不为空就一直 wfs
        VNode p = DeQueue(q);   // 取出一个顶点
        // 将未访问连通点添加到队列
        ArcNode *arc = p.firstArc;
        while (arc!=NULL) {
            // 将未访问顶点入队列
            if (visit[arc->adj]==false) {
                EnQueue(q, graph->data[arc->adj]);
            }
            // 判断到该顶点的权值
            if (path[arc->adj]==0 || 
                    path[arc->adj] > path[p.index] + arc->weight) {    // 如果没有路径，添加路径
                path[arc->adj] = path[p.index] + arc->weight;
            }
            arc = arc->nextArc;
        }
    }
    
    // 输出结果
    for (int i=0; ivexnum; i++) {
        printf("%ct", graph->data[i].val);
    }
    printf("n");

    for (int i=0; ivexnum; i++) {
        printf("%dt", path[i]);
    }
    printf("n");
}

# include 
# include 
# include 

# define true 1 
# define false 0
# define MAX_SIZE 20

typedef int bool;
typedef char ElemType;

// 图的邻接表
typedef struct ArcNode {
    int adj;
    int weight; // 权
    struct ArcNode *nextArc;
} ArcNode;

typedef struct {
    ElemType val;
    int index;   
    ArcNode *firstArc;
} VNode, AdjList[MAX_SIZE];

typedef struct {
    AdjList data;
    int vexnum;
} Graph, *pGraph;

// 队列，wfs
typedef struct {
    AdjList data;
    int start, end;
} Queue, *pQueue;

// 图
pGraph CreateGraph();
void AddVex(pGraph graph, ElemType vex);
void AddArc(pGraph graph, ElemType vexa, ElemType vexb, int weight);
// 队列
pQueue CreateQueue();
void EnQueue(pQueue q, VNode node);
VNode DeQueue(pQueue q);
bool Empty(pQueue q);
// wfs
void ShortestPath(pGraph graph);

int main() {
    // 创建图
    pGraph graph = CreateGraph();
    // 添加顶点
    AddVex(graph, 'a');
    AddVex(graph, 'b');
    AddVex(graph, 'c');
    AddVex(graph, 'd');
    AddVex(graph, 'e');
    AddVex(graph, 'f');
    // 添加边
    AddArc(graph, 'a', 'c', 10);
    AddArc(graph, 'a', 'e', 30);
    AddArc(graph, 'a', 'f', 100);
    AddArc(graph, 'b', 'c', 5);
    AddArc(graph, 'c', 'd', 50);
    AddArc(graph, 'd', 'f', 10);
    AddArc(graph, 'e', 'd', 20);
    AddArc(graph, 'e', 'f', 60);
    
    // 最短路径
    ShortestPath(graph);
    return 0;
}

pGraph CreateGraph() {
    pGraph graph = (pGraph) malloc(sizeof(Graph));
    memset(graph, 0, sizeof(Graph));
    return graph;
}

void AddVex(pGraph graph, ElemType vex) {
    graph->data[graph->vexnum].index = graph->vexnum;
    graph->data[graph->vexnum++].val = vex;
}

void AddArc(pGraph graph, ElemType vexa, ElemType vexb, int weight) {
    int index_a, index_b;
    for (int i=0; ivexnum; i++) {
        if (graph->data[i].val == vexa) {
            index_a = i;
        }
        if (graph->data[i].val == vexb) {
            index_b = i;
        }
    }
    // a 到 b
    ArcNode *arc_a = (ArcNode *) malloc(sizeof(ArcNode));
    memset(arc_a, 0, sizeof(ArcNode));
    arc_a->adj = index_b;
    arc_a->weight = weight;

    if (graph->data[index_a].firstArc == NULL) {
        graph->data[index_a].firstArc = arc_a;
    } else {
        ArcNode *p = graph->data[index_a].firstArc;
        while (p->nextArc != NULL) {
            p = p->nextArc;
        }
        p->nextArc = arc_a;
    }
}

pQueue CreateQueue() {
    pQueue q = (pQueue) malloc(sizeof(Queue));
    memset(q, 0, sizeof(Queue));
    return q;
}

void EnQueue(pQueue q, VNode node) {
    q->data[q->end++] = node;
}

VNode DeQueue(pQueue q) {
    return q->data[q->start++];
}

bool Empty(pQueue q) {
    if (q->start == q->end) {
        return true;
    } else {
        return false;
    }
}

void ShortestPath(pGraph graph) {
    // 最短路径数组
    int path[graph->vexnum];
    bool visit[graph->vexnum];
    for (int i=0; ivexnum; i++) {
        visit[i] = path[i] = 0;
    }
    // wfs 队列
    pQueue q = CreateQueue();
    EnQueue(q, graph->data[0]);
    visit[0] = true;
    while (!Empty(q)) { // 队列不为空就一直 wfs
        VNode p = DeQueue(q);   // 取出一个顶点
        // 将未访问连通点添加到队列
        ArcNode *arc = p.firstArc;
        while (arc!=NULL) {
            // 将未访问顶点入队列
            if (visit[arc->adj]==false) {
                EnQueue(q, graph->data[arc->adj]);
            }
            // 判断到该顶点的权值
            if (path[arc->adj]==0 || 
                    path[arc->adj] > path[p.index] + arc->weight) {    // 如果没有路径，添加路径
                path[arc->adj] = path[p.index] + arc->weight;
            }
            arc = arc->nextArc;
        }
    }
    
    // 输出结果
    for (int i=0; ivexnum; i++) {
        printf("%ct", graph->data[i].val);
    }
    printf("n");

    for (int i=0; ivexnum; i++) {
        printf("%dt", path[i]);
    }
    printf("n");
}

output:

a       b       c       d       e       f
0       0       10      50      30      60