邻接链表图Graph——数据结构系列教程(c++版)

#ifndef LINKEDGRAPH_H_INCLUDED
#define LINKEDGRAPH_H_INCLUDED

#include <limits.h> // 用于INT_MAX
#include <stdbool.h>

//************************************************************************************************************************************************************************
//
//      类名：邻接链表图(LinkedGraph),全称：Adjacency List Graph
//
//      概述：一个可复用的数组邻接链表图，存储结构采用链表实现。
//
//      邻接链表：分为V和E集合，其中，V是顶点，E是边。因此，用一个一维数组存放图中所有顶点数据；用单向链表存储顶点间关系（边或弧）的数据。
//
//      功能：包含创建图、添加顶点、添加边、连通测试、最短路径、打印邻接链表、深度优先遍历（DFS）、广度优先遍历（BFS） 等核心功能。
//
//      说明：
//
//************************************************************************************************************************************************************************


#define MAX_VERTEX 100  // 最大顶点数（可根据需求调整）
#define NO_EDGE 0       // 表示无边
#define INF INT_MAX     // 无边/无穷大标记
#define NO_PRE -1       // 路径前驱的无效标记

//========================================================================================================================================================================
//
//                                                                 边节点结构体(EdgeNode)
//
//========================================================================================================================================================================
struct EdgeNode {
    int adjvex;             // 邻接点的顶点索引
    int weight;             // 边的权值
    struct EdgeNode *next; // 指向下一个边节点
};

//========================================================================================================================================================================
//
//                                                                顶点节点结构体(VertexNode)
//
//========================================================================================================================================================================
struct VertexNode {
    char data;           // 顶点数据（如'A'、'B'）
    EdgeNode *firstedge; // 指向第一个邻接边节点
};

//========================================================================================================================================================================
//
//                                                              邻接链表图结构体(LinkedGraph)
//
//========================================================================================================================================================================
struct LinkedGraph
{
    //------------------------------------------------------------------------------------------------------
    //                                          私有成员
    // 注：私有成员只能在该结构体内部访问调用，外部通过该结构体定义(实例化)的变量(对象)不能访问调用）
    //------------------------------------------------------------------------------------------------------
    private:

        //---------------声明私有成员变量---------------

        //---------------声明私有成员函数---------------

        int findMinDist(int dist[], bool visited[], int n);//找到未访问的距离最小的顶点  dist 距离数组  visited 访问标记数组  n 顶点数 距离最小的顶点索引，无则返回-1
        void addEdgeNode(int vIndex, int adjIndex, int weight);// 辅助函数：创建边节点并添加到指定顶点的邻接链表（头插法）
        void printPath(int pre[], int startIndex, int targetIndex);//打印路径（递归回溯前驱数组）  pre 前驱数组  startIndex 起始顶点索引  targetIndex 目标顶点索引
        int dfsCheckConnect(int startIndex, int targetIndex, bool visited[]);//DFS辅助函数：判断从startIndex能否到达targetIndex visited 访问标记数组 能到达返回1，否则返回0
        void dijkstra(int startIndex, int dist[], int pre[]);//Dijkstra算法：计算起始顶点到所有顶点的最短路径 startIndex 起始顶点索引  dist 输出参数：存储起始顶点到各顶点的最短距离  pre 输出参数：存储各顶点的路径前驱索引
        void dfsHelper(int index, bool visited[]);//DFS辅助函数：index 当前顶点索引 visited 访问标记数组

    //------------------------------------------------------------------------------------------------------
    //                                          公共成员
    // 注：公共成员能在该结构体内部访问调用，外部通过该结构体定义(实例化)的变量(对象)也能访问调用）
    //------------------------------------------------------------------------------------------------------
    public:

        //---------------声明私有成员变量---------------

        VertexNode adjList[MAX_VERTEX];// 顶点数组（存储所有顶点）
        int vertexNum;  // 实际顶点数
        int edgeNum;    // 实际边数

        //---------------声明公共成员函数---------------

        // 构造函数：外部通过该结构体定义(实例化)变量(对象)时，自动执行该函数(主要用于初始化成员变量的值)
        LinkedGraph() {
            vertexNum = edgeNum = 0;

            // 初始化所有顶点的邻接表头指针为空
            for (int i = 0; i < MAX_VERTEX; i++) {
                adjList[i].data = '\0';
                adjList[i].firstedge = nullptr;
            }
        }

        int findVertexIndex(char vertex);//查找顶点的索引,未找到返回-1
        int addVertex(char vertex);//添加顶点 vertex 顶点名称（如'A'）
        int addEdge(char v1, char v2, int weight);//添加边（无向图）v1 顶点1 v2 顶点2 weight 边的权值（需>0，NO_EDGE=0表示无边）
        int addDirectedEdge(char v1, char v2, int weight);//添加边（有向图）v1 顶点1 v2 顶点2 weight 边的权值（需>0，NO_EDGE=0表示无边）
        void printAdjacency(); // 打印邻接表
        int isConnected(char v1, char v2);//判断两个顶点是否连通 v1 顶点1 v2 顶点2 连通返回1，不连通返回0，顶点不存在返回-1
        int getShortestPath(char start, char target);//获取两顶点的最短路径（封装Dijkstra） start 起始顶点  target 目标顶点  最短路径长度（INF表示无路径，-1表示顶点不存在）
        void dfs(char start);//深度优先遍历（DFS） start 起始顶点
        void bfs(char start);//广度优先遍历（BFS）start 起始顶点
        void freeGraph();// 手动释放图的内存（邻接链表节点）
        // 析构函数：自动销毁邻接边节点，避免内存泄漏
        ~LinkedGraph() {
            freeGraph();
        }
};

#endif // LINKEDGRAPH_H_INCLUDED
                

LinkedGraph.cpp 程序代码

#include  <stdio.h>
#include  <stdlib.h>
#include  <string.h>
#include "LinkedGraph.h"
//---------------实现私有成员函数---------------

// 找到未访问的距离最小的顶点
int LinkedGraph::findMinDist(int dist[], bool visited[], int n) {
    int min = INF;
    int minIndex = -1;

    for (int i = 0; i < n; i++) {
        if (!visited[i] && dist[i] < min) {
            min = dist[i];
            minIndex = i;
        }
    }
    return minIndex;
}

// 辅助函数：创建边节点并添加到指定顶点的邻接链表（头插法）
void LinkedGraph::addEdgeNode(int vIndex, int adjIndex, int weight) {
    EdgeNode *newNode = (EdgeNode *)malloc(sizeof(EdgeNode));
    if (newNode == NULL) {
        printf("内存分配失败！\n");
        exit(1);
    }
    newNode->adjvex = adjIndex;
    newNode->weight = weight;
    newNode->next = adjList[vIndex].firstedge; // 头插法
    adjList[vIndex].firstedge = newNode;
}

// 打印路径（递归回溯前驱数组）
void LinkedGraph::printPath(int pre[], int startIndex, int targetIndex) {
    if (targetIndex == startIndex) {
        printf("%c", adjList[targetIndex].data);
        return;
    }
    if (pre[targetIndex] == NO_PRE) {
        printf("无路径");
        return;
    }
    printPath(pre, startIndex, pre[targetIndex]);
    printf(" -> %c", adjList[targetIndex].data);
}


// DFS辅助函数：判断连通性
int LinkedGraph::dfsCheckConnect(int startIndex, int targetIndex, bool visited[])
{
    if (startIndex == targetIndex) {
        return 1;
    }

    visited[startIndex] = true;

    // 遍历当前顶点的所有邻接点（链表遍历）
    EdgeNode *p = adjList[startIndex].firstedge;
    while (p != NULL) {
        int adjIndex = p->adjvex;
        if (!visited[adjIndex]) {
            if (dfsCheckConnect(adjIndex, targetIndex, visited)) {
                return 1;
            }
        }
        p = p->next;
    }

    return 0;
}

// Dijkstra算法（适配邻接表）
void LinkedGraph::dijkstra(int startIndex, int dist[], int pre[]) {
    int n = vertexNum;
    bool visited[MAX_VERTEX] = {false};

    // 初始化距离和前驱数组
    for (int i = 0; i < n; i++) {
        dist[i] = INF;
        pre[i] = NO_PRE;
    }
    dist[startIndex] = 0; // 起始顶点到自身距离为0
    visited[startIndex] = true;

    // 先初始化起始顶点的直接邻接点距离
    EdgeNode *p = adjList[startIndex].firstedge;
    while (p != NULL) {
        int adjIndex = p->adjvex;
        dist[adjIndex] = p->weight;
        pre[adjIndex] = startIndex;
        p = p->next;
    }

    // 处理剩余n-1个顶点
    for (int i = 1; i < n; i++) {
        int u = findMinDist(dist, visited, n);
        if (u == -1) break;
        visited[u] = true;

        // 松弛操作：遍历u的所有邻接点（链表遍历）
        p = adjList[u].firstedge;
        while (p != NULL) {
            int v = p->adjvex;
            if (!visited[v] && dist[u] != INF) {
                if (dist[u] + p->weight < dist[v]) {
                    dist[v] = dist[u] + p->weight;
                    pre[v] = u;
                }
            }
            p = p->next;
        }
    }
}

// DFS辅助函数（遍历邻接表）
void LinkedGraph::dfsHelper(int index, bool visited[])
{
    visited[index] = true;
    printf("%c ", adjList[index].data);

    // 遍历当前顶点的所有邻接点（链表）
    EdgeNode *p = adjList[index].firstedge;
    while (p != NULL) {
        int adjIndex = p->adjvex;
        if (!visited[adjIndex]) {
            dfsHelper(adjIndex, visited);
        }
        p = p->next;
    }
}

//---------------实现公共成员函数---------------

// 查找顶点的索引，未找到返回-1
int LinkedGraph::findVertexIndex(char vertex)
{
    for (int i = 0; i < vertexNum; i++) {
        if (adjList[i].data == vertex) {
            return i;
        }
    }
    printf("顶点%c不存在！\n", vertex);
    return -1;
}

// 添加顶点
int LinkedGraph::addVertex(char vertex)
{
    if (vertexNum >= MAX_VERTEX) {
        printf("顶点数已达上限，无法添加！\n");
        return 0;
    }
    adjList[vertexNum].data = vertex;
    adjList[vertexNum].firstedge = nullptr;
    vertexNum++;
    return 1;
}

// 添加边（无向图）
int LinkedGraph::addEdge(char v1, char v2, int weight)
{
    int i = findVertexIndex(v1);
    int j = findVertexIndex(v2);

    if (i == -1 || j == -1 || weight <= 0) {
        return 0;
    }

    // 无向图：双向添加边节点
    addEdgeNode(i, j, weight);
    addEdgeNode(j, i, weight);
    edgeNum++;
    return 1;
}

// 添加边（有向图）
int LinkedGraph::addDirectedEdge(char v1, char v2, int weight)
{
    int i = findVertexIndex(v1);
    int j = findVertexIndex(v2);

    if (i == -1 || j == -1 || weight <= 0) {
        return 0;
    }

    // 有向图：单向添加边节点
    addEdgeNode(i, j, weight);
    edgeNum++;
    return 1;
}

// 打印邻接表
void LinkedGraph::printAdjacency()
{
    printf("\n===== 邻接表（带权）=====\n");
    for (int i = 0; i < vertexNum; i++) {
        printf("%c -> ", adjList[i].data);
        EdgeNode *p = adjList[i].firstedge;
        while (p != nullptr) {
            printf("(%c, %d) ", adjList[p->adjvex].data, p->weight);
            p = p->next;
        }
        printf("\n");
    }
}

// 判断两个顶点是否连通
int LinkedGraph::isConnected(char v1, char v2)
{
    int i = findVertexIndex(v1);
    int j = findVertexIndex(v2);

    if (i == -1 || j == -1) {
        return -1;
    }

    if (i == j) {
        return 1;
    }

    bool visited[MAX_VERTEX] = {false};
    return dfsCheckConnect(i, j, visited);
}

// 获取两顶点的最短路径
int LinkedGraph::getShortestPath(char start, char target) {
    int startIndex = findVertexIndex(start);
    int targetIndex = findVertexIndex(target);
    if (startIndex == -1 || targetIndex == -1) {
        return -1;
    }

    if (startIndex == targetIndex) {
        printf("\n===== 最短路径（%c → %c）=====\n", start, target);
        printf("路径：%c\n", start);
        printf("最短路径长度：0\n");
        return 0;
    }

    int dist[MAX_VERTEX];
    int pre[MAX_VERTEX];
    dijkstra(startIndex, dist, pre);

    printf("\n===== 最短路径（%c → %c）=====\n", start, target);
    if (dist[targetIndex] == INF) {
        printf("路径：无\n");
        printf("最短路径长度：∞（无连通路径）\n");
        return INF;
    } else {
        printf("路径：");
        printPath(pre, startIndex, targetIndex);
        printf("\n最短路径长度：%d\n", dist[targetIndex]);
        return dist[targetIndex];
    }
}

// 深度优先遍历
void LinkedGraph::dfs(char start)
{
    int startIndex = findVertexIndex(start);
    if (startIndex == -1) {
        return;
    }

    bool visited[MAX_VERTEX] = {false};
    printf("\n===== 深度优先遍历（起始：%c）=====\n", start);
    dfsHelper(startIndex, visited);
    printf("\n");
}

// 广度优先遍历
void LinkedGraph::bfs(char start)
{
    int startIndex = findVertexIndex(start);
    if (startIndex == -1) {
        return;
    }

    bool visited[MAX_VERTEX] = {false};
    int queue[MAX_VERTEX];
    int front = 0, rear = 0;

    printf("\n===== 广度优先遍历（起始：%c）=====\n", start);

    // 起始顶点入队
    visited[startIndex] = true;
    queue[rear++] = startIndex;

    while (front < rear) {
        int currIndex = queue[front++];
        printf("%c ", adjList[currIndex].data);

        // 遍历当前顶点的所有邻接点（链表）
        EdgeNode *p = adjList[currIndex].firstedge;
        while (p != nullptr) {
            int adjIndex = p->adjvex;
            if (!visited[adjIndex]) {
                visited[adjIndex] = true;
                queue[rear++] = adjIndex;
            }
            p = p->next;
        }
    }
    printf("\n");
}

// 释放图的内存（释放所有邻接链表节点）
void LinkedGraph::freeGraph()
{
    // 遍历每个顶点
    for (int i = 0; i < vertexNum; i++) {
        EdgeNode *p = adjList[i].firstedge;
        // 释放当前顶点的所有邻接边节点
        while (p != nullptr) {
            EdgeNode *temp = p; // 暂存当前节点
            p = p->next;        // 移动到下一个节点
            free(temp);         // 释放当前节点内存
        }
        // 重置头指针
        adjList[i].firstedge = nullptr;
    }

    // 重置顶点数和边数
    vertexNum = 0;
    edgeNum = 0;
    printf("\n===== 图内存已全部释放 =====\n");
}

main.cpp 测试代码

#include "LinkedGraph.h"
#include <iostream>
#include <string>

int main() {
    //  A ── B
    //  │    │
    //  C ── D ── E
    printf("\n===== 图 =====\n");
    printf("  A ── B\n");
    printf("  │    │\n");
    printf("  C ── D ── E\n");

    //使用MyLibrary函数库中的ArrayGraph(邻接矩阵图结构体)定义graph变量
    //ArrayGraph graph;

    //使用MyLibrary函数库中的LinkedGraph(邻接链表图结构体)定义graph变量
    LinkedGraph graph;

    // 1. 添加顶点（A、B、C、D、E）
    graph.addVertex('A');
    graph.addVertex('B');
    graph.addVertex('C');
    graph.addVertex('D');
    graph.addVertex('E');

    // 2. 添加边（无向图）
    //graph.addEdge('A','B',1);
    //graph.addEdge('A','C',1);
    //graph.addEdge('B','D',1);
    //graph.addEdge('C','D',1);
    //graph.addEdge('D','E',1);

    // 2. 添加边（有向图）
    graph.addDirectedEdge('A','B',5);
    graph.addDirectedEdge('A','C',3);
    graph.addDirectedEdge('B','D',2);
    graph.addDirectedEdge('C','D',4);
    graph.addDirectedEdge('D','E',1);

    // 3. 打印邻接链表
    graph.printAdjacency();

    // 4. 测试连通性函数
    printf("\n===== 顶点连通性测试 =====\n");
    char v1, v2;

    // 测试1：A和B（连通）
    v1 = 'A'; v2 = 'E';
    int res1 = graph.isConnected(v1, v2);
    if (res1 == 1) {
        printf("顶点%c和%c：连通\n", v1, v2);
    } else if (res1 == 0) {
        printf("顶点%c和%c：不连通\n", v1, v2);
    } else {
        printf("顶点%c或%c不存在\n", v1, v2);
    }

    // 5. 测试最短路径（A -> E）
    graph.getShortestPath('A', 'E'); // A→C→D→E，长度3+4+1=8

    // 6. 深度优先遍历（起始：A）
    graph.dfs( 'A');

    // 7 广度优先遍历（起始：A）
    graph.bfs('A');

return 0;
}

输出结果

  A ── B
  │    │
  C ── D ── E

  ===== 邻接链表（带权）=====
  A -> (C, 3) (B, 5)
  B -> (D, 2)
  C -> (D, 4)
  D -> (E, 1)
  E ->

  ===== 顶点连通性测试 =====
  顶点A和E：连通

  ===== 最短路径（A -> E） =====
  路径：A -> B -> D -> E
  最短路径长度：3

  ===== 深度优先遍历（起始：A）=====
  A B D C E

  ===== 广度优先遍历（起始：A）=====
  A B C D E

===== 图内存已全部释放 =====

六、总结

本文详细解析了邻接链表图（LinkedGraph）的原理与代码实现，核心要点：

• 邻接链表通过「顶点数组+邻接链表」存储图，适合稀疏图；
• 核心功能封装为类，区分私有/公共成员，符合面向对象设计；
• 实现了DFS/BFS遍历、Dijkstra最短路径、连通性判断等核心算法；
• 完善的内存管理（构造/析构函数）避免内存泄漏。

该实现可直接复用，也可根据需求扩展（如支持负权边的Bellman-Ford算法、拓扑排序等），是学习图结构和算法的优质实践案例。