c语言编程实现图的遍历图算法（按图的深度优先搜索算法和广度优先搜索算法遍历），实现最短路径算法

深度优先搜索算法（DFS）遍历图：

#include <stdio.h>
#include <stdbool.h>

#define MAX_VERTEX_NUM 20 // 最大顶点数
typedef int VertexType; // 顶点数据类型

// 邻接表存储结构
typedef struct ArcNode {
    int adjvex; // 邻接点在数组中的位置下标
    struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;

typedef struct VNode {
    VertexType data; // 顶点数据
    ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices; // 邻接表
    int vexnum, arcnum; // 顶点数和弧数
} ALGraph;

bool visited[MAX_VERTEX_NUM]; // 用于记录顶点是否被访问

// 创建邻接表
void CreateGraph(ALGraph *G) {
    printf("请输入顶点数和边数：");
    scanf("%d %d", &G->vexnum, &G->arcnum);
    getchar(); // 吸收回车符
    printf("请输入各个顶点的数据：\n");
    for (int i = 0; i < G->vexnum; i++) {
        printf("第 %d 个顶点：", i + 1);
        scanf("%c", &G->vertices[i].data);
        getchar(); // 吸收回车符
        G->vertices[i].firstarc = NULL; // 初始化第一个邻接点指针
    }
    printf("请输入各个边的信息：\n");
    for (int k = 0; k < G->arcnum; k++) {
        printf("第 %d 条边：", k + 1);
        VertexType v1, v2;
        scanf("%c %c", &v1, &v2);
        getchar(); // 吸收回车符
        // 查找顶点 v1 在数组中的位置下标
        int i = 0;
        while (i < G->vexnum && G->vertices[i].data != v1) {
            i++;
        }
        // 查找顶点 v2 在数组中的位置下标
        int j = 0;
        while (j < G->vexnum && G->vertices[j].data != v2) {
            j++;
        }
        // 插入边<v1, v2>，即将顶点 v2 插入到顶点 v1 的邻接表中
        ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->nextarc = G->vertices[i].firstarc;
        G->vertices[i].firstarc = p;
    }
}

// 深度优先遍历图
void DFS(ALGraph *G, int v) {
    printf("%c ", G->vertices[v].data); // 访问当前顶点
    visited[v] = true; // 标记当前顶点已被访问
    // 遍历当前顶点的所有邻接点
    ArcNode *p = G->vertices[v].firstarc;
    while (p != NULL) {
        int w = p->adjvex; // 邻接点的位置下标
        if (!visited[w]) { // 若邻接点未被访问，则递归访问它
            DFS(G, w);
        }
        p = p->nextarc; // 处理下一个邻接点
    }
}

// 广度优先遍历图
void BFS(ALGraph *G, int v) {
    int queue[MAX_VERTEX_NUM]; // 辅助队列
    int front = 0, rear = 0; // 队列的头指针和尾指针
    printf("%c ", G->vertices[v].data); // 访问起始顶点
    visited[v] = true; // 标记起始顶点已被访问
    queue[rear++] = v; // 起始顶点入队
    while (front < rear) { // 队列不为空时循环
        int u = queue[front++]; // 出队队头元素
        // 遍历顶点 u 的所有邻接点
        ArcNode *p = G->vertices[u].firstarc;
        while (p != NULL) {
            int w = p->adjvex; // 邻接点的位置下标
            if (!visited[w]) { // 若邻接点未被访问，则访问它并将它入队
                printf("%c ", G->vertices[w].data);
                visited[w] = true;
                queue[rear++] = w;
            }
            p = p->nextarc; // 处理下一个邻接点
        }
    }
}

// 最短路径算法（Dijkstra算法），返回起点到各个顶点的最短路径长度
int* ShortestPath(ALGraph *G, int v0) {
    int *dist = (int *)malloc(sizeof(int) * G->vexnum); // 用于存储起点到各个顶点的最短路径长度
    bool *s = (bool *)malloc(sizeof(bool) * G->vexnum); // 用于存储顶点是否已被确定最短路径
    // 初始化 dist 和 s 数组
    for (int i = 0; i < G->vexnum; i++) {
        dist[i] = INT_MAX; // 起点到每个顶点的初始距离都为无穷大
        s[i] = false; // 所有顶点都未被确定最短路径
    }
    dist[v0] = 0; // 起点到自身的距离为0
    s[v0] = true; // 起点已被确定最短路径
    // 逐步确定起点到其它顶点的最短路径
    ArcNode *p = G->vertices[v0].firstarc;
    while (p != NULL) {
        int w = p->adjvex; // 邻接点的位置下标
        dist[w] = p->weight; // 更新起点到邻接点的距离
        p = p->nextarc; // 处理下一个邻接点
    }
    for (int i = 1; i < G->vexnum; i++) { // i 从1开始，因为起点已被确定最短路径
        int min = INT_MAX, v = -1; // min 表示当前未确定最短路径的顶点中距离起点最近的距离，v 表示该顶点在数组中的位置下标
        // 找出当前未确定最短路径的顶点中距离起点最近的顶点
        for (int j = 0; j < G->vexnum; j++) {
            if (!s[j] && dist[j] < min) {
                min = dist[j];
                v = j;
            }
        }
        if (v == -1) { // 若找不到符合条件的顶点，说明剩下的顶点和起点不连通
            break;
        }
        s[v] = true; // 标记该顶点已被确定最短路径
        // 以该顶点为中介点更新其它未确定最短路径的顶点的距离
        ArcNode *p = G->vertices[v].firstarc;
        while (p != NULL) {
            int w = p->adjvex; // 邻接点的位置下标
            if (!s[w] && dist[v] + p->weight < dist[w]) {
                dist[w] = dist[v] + p->weight;
            }
            p = p->nextarc; // 处理下一个邻接点
        }
    }
    return dist;
}

int main() {
    ALGraph G;
    CreateGraph(&G);
    printf("深度优先遍历：");
    for (int i = 0; i < G.vexnum; i++) {
        visited[i] = false; // 初始化 visited 数组
    }
    DFS(&G, 0);
    printf("\n广度优先遍历：");
    for (int i = 0; i < G.vexnum; i++) {
        visited[i] = false; // 初始化 visited 数组
    }
    BFS(&G, 0);
    printf("\n最短路径：");
    int *dist = ShortestPath(&G, 0);
    for (int i = 0; i < G.vexnum; i++) {
        printf("%d ", dist[i]);
    }
    printf("\n");
    return 0;
}

其中，`CreateGraph` 函数用于创建邻接表，`DFS` 函数用于深度优先遍历图，`BFS` 函数用于广度优先遍历图，`ShortestPath` 函数用于求最短路径。

广度优先搜索算法（BFS）遍历图与深度优先搜索算法（DFS）遍历图的代码类似，只是在遍历时使用了队列而不是栈。

最短路径算法使用的是 Dijkstra 算法，它的基本思想是：从起点开始，逐步确定起点到其它顶点的最短路径。具体实现时，用一个数组 `dist` 来存储起点到各个顶点的最短路径长度，用一个数组 `s` 来记录哪些顶点已被确定最短路径。算法流程如下：

1. 初始化 `dist` 和 `s` 数组。
2. 将起点加入 `s` 数组中，并以起点为中介点更新其它未确定最短路径的顶点的距离。
3. 从未被确定最短路径的顶点中找出距离起点最近的顶点，并将它加入 `s` 数组中。
4. 以该顶点为中介点更新其它未确定最短路径的顶点的距离。
5. 重复步骤3和步骤4，直到所有顶点都被确定最短路径或者剩下的顶点和起点不连通为止。