图结构邻接表实现：DFS、BFS 及 Dijkstra 算法详解

图（邻接表）- DFS/BFS/Dijkstra 算法

基于一道简单实验，学习用邻接表结构储存图，并且包含 DFS/BFS 两种遍历方式，以及 Dijkstra 算法（朴素版）在本题的使用。

头文件（以及相关内容）

#include <cstdio>
#include <cstdlib>
#define MAX_VERTEX_NUM 20
#define INFINITY 0x3f3f3f3f
typedef char VertexType;

1. 邻接表的构建

包含三个部分：

1. 边节点
   • 所指向边节点的索引（adjvex）
   • 指向下一边节点的指针（nextarc）
2. 顶点节点
   • 储存该节点的信息（data）-----节点名称等
   • 指向边节点的指针（firstarc）
3. 组合成邻接表
   • 顶点数组（vertices）
   • 顶点数（vexnum）
   • 边数（arcnum）

代码如下：

// 边节点结构
typedef struct ArcNode {
    // 该边指向的点节点的索引
    int adjvex;
    // 权值
    int value;
    // 指向下一个边节点的指针
    struct ArcNode* nextarc;
} ArcNode;

// 顶点节点的结构
typedef struct VNode {
    // 顶点节点的数据（顶点节点的名称）
    VertexType data;
    // 指向的第一个边节点
    ArcNode* firstarc;
} VNode, adjList[MAX_VERTEX_NUM];

// 邻接表表示的图的结构
typedef struct ALGraph {
    // 顶点数组
    adjList vertices;
    // 顶点数，边数
    int vexnum, arcnum;
} ALGraph;

2. 两种遍历

复用函数（vis — 表示该顶点是否被访问；Visit 函数 — 访问该节点后的行为：打印节点信息）

int vis[MAX_VERTEX_NUM];
void Visit(const ALGraph &G, int v) {
    printf("%c ", G.vertices[v].data);
}

DFS 遍历

void DFS(const ALGraph &G, int v) {
    vis[v] = 1;
    Visit(G, v);
    ArcNode* p = G.vertices[v].firstarc;
    while (p != NULL) {
        int w = p->adjvex;
        if (!vis[w]) {
            DFS(G, w);
        }
        p = p->nextarc;
    }
}

void DFSTraverse(const ALGraph &G) {
    int n = G.vexnum;
    for (int i = 0; i < n; i++) {
        vis[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            DFS(G, i);
        }
    }
}

BFS 遍历

（为简化演示，不使用 STL 队列，采用双指针的移动来模拟入队、出队操作） 注：front++相当于出队，rear++相当于入队

void BFS(const ALGraph &G, int v) {
    int Queue[MAX_VERTEX_NUM];
    int front = 0, rear = 0;
    vis[v] = 1;
    Visit(G, v);
    Queue[rear++] = v;
    while (front < rear) {
        int u = Queue[front];
        front++;
        ArcNode* p = G.vertices[u].firstarc;
        while (p != NULL) {
            int w = p->adjvex;
            if (!vis[w]) {
                vis[w] = 1;
                Visit(G, w);
                Queue[rear++] = w;
            }
            p = p->nextarc;
        }
    }
}

void BFSTraverse(const ALGraph &G) {
    int n = G.vexnum;
    for (int i = 0; i < n; i++) {
        vis[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            BFS(G, i);
        }
    }
}

3. Dijkstra 算法 (朴素版）

主要核心：

1. 初始化距离：设定源节点到自身的距离为 0，到其他所有节点的距离为 （INFINITY：0x3f3f3f3f）。
2. 贪心选择：每次从未确定最短路径的节点中，选择当前距离源节点最近的节点 u，将其标记为'已确定最短路径'。（dist[u]）
3. 松弛操作：对节点 u 的所有邻接节点 v，尝试通过 u 更新 v 的最短距离。松弛条件：若 dist[v] > dist[u] + w(u, v)，则更新 dist[v] = dist[u] + w(u, v)。
4. 重复步骤 2-3：直到所有节点都被标记为'已确定最短路径'。

Dijkstra 算法贪心选择正确性证明：

1. 前提
   • 图中所有边权非负；
   • S：已确定最短路径的节点集合；
   • dist[u]：当前已知 s 到 u 的最短距离上界。
2. 反证法证明 假设：选 u 时，存在更短的 s→u 路径 P，长度＜dist[u]。拆分路径 P：s→…→x（x∈S，P 上最后一个在 S 中的节点）→y（y∉S，P 上第一个不在 S 中的节点）→…→u。 因 x∈S，其最短路径已确定（dist[x] = 真实最短距离）；又边权非负，所以 s→y 的真实最短距离 ≤ s→x→y 的长度 ≤ 路径 P 的长度（y 到 u 的路径权值≥0，不会缩短）。 结合假设'P 长度＜dist[u]'，可推出：s→y 的真实最短距离 ＜ dist[u]。但 dist[y] 是 s→y 的距离上界（dist[y]≥真实最短距离），因此 dist[y] ＜ dist[u]。 这与「u 是当前未确定节点中 dist 最小的节点」矛盾，故假设不成立。
3. 结论 每次选的 u，其当前 dist[u] 就是 s 到 u 的最短路径，后续不会被更新。

（代码如下：）

// 通过 Dijkstra 算法求最短路径
int Dijkstra(const ALGraph &G, int start) {
    int n = G.vexnum;
    int* dist = (int*)malloc(n * sizeof(int)); // dist[i] 与起点的距离
    int* visited = (int*)malloc(n * sizeof(int)); // visited[i]==1 时，最短路径确定
    
    // 初始化
    for (int i = 0; i < n; i++) {
        dist[i] = INFINITY;
        visited[i] = 0;
    }
    dist[start] = 0;
    
    for (int i = 0; i < n; i++) {
        int u = -1;
        int min_dist = INFINITY;
        
        // (贪心选择)
        // 从未确定的顶点中，找距离起点最近的顶点，找到后该顶点距离起点的最短距离即可确定
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                u = j;
            }
        }
        
        if (u == -1) break;
        visited[u] = 1;
        if (u == n - 1) break;
        
        // 松弛操作
        ArcNode* p = G.vertices[u].firstarc;
        while (p != NULL) {
            int v = p->adjvex;
            int w = p->value;
            if (!visited[v] && dist[u] != INFINITY && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
            p = p->nextarc;
        }
    }
    
    int result = dist[n - 1];
    free(dist);
    free(visited);
    return result;
}

4. 综上所述（完整代码如下）

#include <cstdio>
#include <cstdlib>
#define MAX_VERTEX_NUM 20
#define INFINITY 0x3f3f3f3f
typedef char VertexType;

// 边节点结构
typedef struct ArcNode {
    // 该边指向的点节点的索引
    int adjvex;
    // 权值
    int value;
    // 指向下一个边节点的指针
    struct ArcNode* nextarc;
} ArcNode;

// 顶点节点的结构
typedef struct VNode {
    // 顶点节点的数据（顶点节点的名称）
    VertexType data;
    // 指向的第一个边节点
    ArcNode* firstarc;
} VNode, adjList[MAX_VERTEX_NUM];

// 邻接表表示的图的结构
typedef struct ALGraph {
    // 顶点数组
    adjList vertices;
    // 顶点数，边数
    int vexnum, arcnum;
} ALGraph;

// 返回节点在数组中的索引
int LocateVex(const ALGraph &G, VertexType V) {
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vertices[i].data == V) return i;
    }
    return -1;
}

// 图的创建
int CreateDG(ALGraph &G) {
    // 输入顶点数和边数
    printf("请输入顶点数与边数：\n");
    scanf("%d %d", &G.vexnum, &G.arcnum);
    getchar();
    
    // 输入顶点信息（顶点的名称等）
    printf("请输入%d个顶点的信息：\n", G.vexnum);
    for (int i = 0; i < G.vexnum; i++) {
        scanf("%c", &G.vertices[i].data);
        getchar();
        // 初始化
        G.vertices[i].firstarc = NULL;
    }
    
    // 输入边的信息
    VertexType V1, V2;
    int v;
    ArcNode* p;
    printf("请输入%d条边的信息：\n", G.arcnum);
    for (int k = 0; k < G.arcnum; k++) {
        scanf("%c %c %d", &V1, &V2, &v);
        getchar();
        int i = LocateVex(G, V1);
        int j = LocateVex(G, V2);
        if (i == -1 || j == -1) return 0;
        p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->value = v;
        // 头插法
        p->nextarc = G.vertices[i].firstarc;
        G.vertices[i].firstarc = p;
    }
    return 1;
}

// 遍历
int vis[MAX_VERTEX_NUM];
void Visit(const ALGraph &G, int v) {
    printf("%c ", G.vertices[v].data);
}

// DFS
void DFS(const ALGraph &G, int v) {
    vis[v] = 1;
    Visit(G, v);
    ArcNode* p = G.vertices[v].firstarc;
    while (p != NULL) {
        int w = p->adjvex;
        if (!vis[w]) {
            DFS(G, w);
        }
        p = p->nextarc;
    }
}

void DFSTraverse(const ALGraph &G) {
    int n = G.vexnum;
    for (int i = 0; i < n; i++) {
        vis[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            DFS(G, i);
        }
    }
}

// BFS
void BFS(const ALGraph &G, int v) {
    int Queue[MAX_VERTEX_NUM];
    int front = 0, rear = 0;
    vis[v] = 1;
    Visit(G, v);
    Queue[rear++] = v;
    while (front < rear) {
        int u = Queue[front];
        front++;
        ArcNode* p = G.vertices[u].firstarc;
        while (p != NULL) {
            int w = p->adjvex;
            if (!vis[w]) {
                vis[w] = 1;
                Visit(G, w);
                Queue[rear++] = w;
            }
            p = p->nextarc;
        }
    }
}

void BFSTraverse(const ALGraph &G) {
    int n = G.vexnum;
    for (int i = 0; i < n; i++) {
        vis[i] = 0;
    }
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            BFS(G, i);
        }
    }
}

// 通过 Dijkstra 算法求最短路径
int Dijkstra(const ALGraph &G, int start) {
    int n = G.vexnum;
    int* dist = (int*)malloc(n * sizeof(int));
    int* visited = (int*)malloc(n * sizeof(int));
    
    // 初始化
    for (int i = 0; i < n; i++) {
        dist[i] = INFINITY;
        visited[i] = 0;
    }
    dist[start] = 0;
    
    for (int i = 0; i < n; i++) {
        int u = -1;
        int min_dist = INFINITY;
        
        // (贪心选择)
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                u = j;
            }
        }
        
        if (u == -1) break;
        visited[u] = 1;
        if (u == n - 1) break;
        
        // 松弛操作
        ArcNode* p = G.vertices[u].firstarc;
        while (p != NULL) {
            int v = p->adjvex;
            int w = p->value;
            if (!visited[v] && dist[u] != INFINITY && dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
            }
            p = p->nextarc;
        }
    }
    
    int result = dist[n - 1];
    free(dist);
    free(visited);
    return result;
}

// 主程序
int main() {
    ALGraph G;
    if (CreateDG(G)) {
        printf("成功\n");
    } else printf("失败\n");
    
    // DFS 遍历
    printf("DFS 遍历结果：");
    DFSTraverse(G);
    printf("\n");
    
    // BFS 遍历
    printf("BFS 遍历结果：");
    BFSTraverse(G);
    printf("\n");
    
    int min = Dijkstra(G, 0);
    printf("%d", min);
    return 0;
}

5. 补充（用 DFS/BFS 解决该题）

DFS

#include <cstdio>
#include <cstdlib>
#define MAX_VERTEX_NUM 20
#define INFINITY 0x3f3f3f3f
typedef char VertexType;

// 边节点
typedef struct ArcNode {
    int adjvex;
    int value;
    struct ArcNode* nextarc;
} ArcNode;

// 顶点节点
typedef struct VNode {
    VertexType data;
    ArcNode* firstarc;
} VNode, adjList[MAX_VERTEX_NUM];

// 构建邻接表
typedef struct ALgraph {
    adjList vertices;
    int vexnum, arcnum;
} ALgraph;

// 返回节点的索引
int LocateVex(const ALgraph &G, VertexType e) {
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vertices[i].data == e) {
            return i;
        }
    }
    return -1;
}

// 创建图
int CreateDG(ALgraph &G) {
    printf("请输入顶点数和边数：\n");
    scanf("%d %d", &G.vexnum, &G.arcnum);
    getchar();
    printf("请输入顶点的信息：\n");
    for (int i = 0; i < G.vexnum; i++) {
        scanf("%c", &G.vertices[i].data);
        getchar();
        G.vertices[i].firstarc = NULL;
    }
    printf("请输入边的关系：\n");
    ArcNode* p;
    VertexType V1, V2;
    int v;
    for (int k = 0; k < G.arcnum; k++) {
        scanf("%c %c %d", &V1, &V2, &v);
        getchar();
        int i = LocateVex(G, V1);
        int j = LocateVex(G, V2);
        if (i == -1 || j == -1) {
            return 0;
        }
        p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->value = v;
        p->nextarc = G.vertices[i].firstarc;
        G.vertices[i].firstarc = p;
    }
    return 1;
}

// 用 DFS 求第一个顶点到最后一个顶点的最短路径
int min_dist = INFINITY;
int cur_dist = 0;
int visited[MAX_VERTEX_NUM];

void DFS(const ALgraph &G, int idx) {
    int n = G.vexnum;
    if (idx == n - 1) {
        if (cur_dist < min_dist) min_dist = cur_dist;
        return;
    }
    visited[idx] = 1;
    ArcNode* p = G.vertices[idx].firstarc;
    while (p != NULL) {
        int next_idx = p->adjvex;
        int weight = p->value;
        if (!visited[next_idx]) {
            cur_dist += weight;
            DFS(G, next_idx);
            cur_dist -= weight;
        }
        p = p->nextarc;
    }
    visited[idx] = 0;
}

int main() {
    ALgraph G;
    if (CreateDG(G)) {
        printf("创建成功\n");
    } else printf("创建失败\n");
    
    for (int i = 0; i < G.vexnum; i++) {
        visited[i] = 0;
    }
    DFS(G, 0);
    printf("%d", min_dist);
    return 0;
}

BFS

#include <cstdio>
#include <cstdlib>
#define MAX_VERTEX_NUM 20
#define INFINITY 0x3f3f3f3f
typedef char VertexType;

// 边节点
typedef struct ArcNode {
    int adjvex;
    int value;
    struct ArcNode* nextarc;
} ArcNode;

// 顶点节点
typedef struct VNode {
    VertexType data;
    ArcNode* firstarc;
} VNode, adjList[MAX_VERTEX_NUM];

// 构建邻接表
typedef struct ALgraph {
    adjList vertices;
    int vexnum, arcnum;
} ALgraph;

// 返回节点的索引
int LocateVex(const ALgraph &G, VertexType e) {
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vertices[i].data == e) {
            return i;
        }
    }
    return -1;
}

// 创建图
int CreateDG(ALgraph &G) {
    printf("请输入顶点数和边数：\n");
    scanf("%d %d", &G.vexnum, &G.arcnum);
    getchar();
    printf("请输入顶点的信息：\n");
    for (int i = 0; i < G.vexnum; i++) {
        scanf("%c", &G.vertices[i].data);
        getchar();
        G.vertices[i].firstarc = NULL;
    }
    printf("请输入边的关系：\n");
    ArcNode* p;
    VertexType V1, V2;
    int v;
    for (int k = 0; k < G.arcnum; k++) {
        scanf("%c %c %d", &V1, &V2, &v);
        getchar();
        int i = LocateVex(G, V1);
        int j = LocateVex(G, V2);
        if (i == -1 || j == -1) {
            return 0;
        }
        p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->value = v;
        p->nextarc = G.vertices[i].firstarc;
        G.vertices[i].firstarc = p;
    }
    return 1;
}

// 用 BFS 求第一个顶点到最后一个顶点的最短路径
typedef struct QNode {
    int idx;
    int path_len; // 起点到路径的长度
} QNode;

int BFS(const ALgraph &G) {
    int n = G.vexnum;
    int* dist = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        dist[i] = INFINITY;
    }
    QNode queue[MAX_VERTEX_NUM * 10];
    int front = 0, rear = 0;
    queue[rear].idx = 0;
    queue[rear].path_len = 0;
    rear++;
    
    while (front < rear) {
        QNode cur = queue[front];
        front++;
        int cur_idx = cur.idx;
        int cur_len = cur.path_len;
        
        if (cur_len > dist[cur_idx]) continue;
        
        ArcNode* p = G.vertices[cur_idx].firstarc;
        while (p != NULL) {
            int next_idx = p->adjvex;
            int weight = p->value;
            int new_len = cur_len + weight;
            
            if (new_len < dist[next_idx]) {
                dist[next_idx] = new_len;
                queue[rear].idx = next_idx;
                queue[rear].path_len = new_len;
                rear++;
            }
            p = p->nextarc;
        }
    }
    
    int result = dist[n - 1];
    free(dist);
    return result;
}

int main() {
    ALgraph G;
    if (CreateDG(G)) {
        printf("创建成功\n");
    } else printf("创建失败\n");
    
    int result = BFS(G);
    printf("%d", result);
    return 0;
}