FA1-存储结构¶

邻接表存储结构¶

C
/**
 * 边结点结构体（邻接表中的链表结点）
 * 用于表示从某个顶点出发的边
 */
typedef struct ArcNode {
    int adjvex;              // 边所指向的顶点在顶点数组中的位置（下标）
    struct ArcNode *nextarc; // 指向下一个边结点的指针
    // 可以添加边的权重等其他信息
    // int weight;           // 边的权重（对于带权图）
} ArcNode, *ArcNodePtr;

/**
 * 顶点结构体
 * 每个顶点包含顶点数据和指向第一条边的指针
 */
typedef struct VertexNode {
    int data;                // 顶点的数据信息
    ArcNode *firstarc;       // 指向第一条依附于该顶点的边的指针
} VertexNode, AdjList[MAXSIZE]; // AdjList是顶点数组类型

/**
 * 图的邻接表存储结构
 * 包含顶点数组和图的基本信息
 */
typedef struct {
    int numVertex;           // 顶点数
    int numEdge;             // 边数
    VertexNode adjList[MAXSIZE]; // 顶点数组（邻接表）
} ALGraph; // Adjacency List Graph

邻接表存储结构图解¶

Text Only

图示例：有向图 G = (V, E)
V = {0, 1, 2, 3}
E = {(0,1), (0,2), (1,2), (2,0), (2,3), (3,3)}

邻接表存储结构：
顶点数组：
index 顶点  firstarc
[0]   0  →  1 → 2 → NULL
[1]   1  →  2 → NULL
[2]   2  →  0 → 3 → NULL
[3]   3  →  3 → NULL

边链表结构：
顶点0的边链表：  [1] → [2] → NULL
                 ↓      ↓
顶点1的边链表：  [2] → NULL
                 ↓
顶点2的边链表：  [0] → [3] → NULL
                 ↓
顶点3的边链表：  [3] → NULL

邻接矩阵存储结构¶

C
/**
 * 图的邻接矩阵存储结构
 * 使用二维数组表示顶点间的关系
 */
typedef struct {
    int numVertex;                    // 顶点数
    int numEdge;                      // 边数
    int vertex[MAXSIZE];              // 顶点数组，存储顶点信息
    int edge[MAXSIZE][MAXSIZE];       // 邻接矩阵，存储边的信息
} MGraph; // Matrix Graph

邻接矩阵存储结构图解¶

Text Only

图示例：有向图 G = (V, E)
V = {0, 1, 2, 3}
E = {(0,1), (0,2), (1,2), (2,0), (2,3), (3,3)}

邻接矩阵表示：
顶点数组：[0, 1, 2, 3]

邻接矩阵：
     0  1  2  3
   ┌───────────┐
0  │ 0  1  1  0 │
1  │ 0  0  1  0 │
2  │ 1  0  0  1 │
3  │ 0  0  0  1 │
   └───────────┘

矩阵含义：
edge[i][j] = 1 表示存在从顶点i到顶点j的边
edge[i][j] = 0 表示不存在从顶点i到顶点j的边

两种存储结构的对比¶

空间复杂度对比¶

存储结构	空间复杂度	说明
邻接矩阵	O(V²)	V为顶点数，无论边数多少都需要V²空间
邻接表	O(V+E)	V为顶点数，E为边数，只存储实际存在的边

时间复杂度对比¶

操作	邻接矩阵	邻接表	说明
判断两顶点是否相邻	O(1)	O(degree(V))	degree(V)为顶点V的度数
查找顶点的所有邻接点	O(V)	O(degree(V))	-
插入/删除边	O(1)	O(1)	不考虑查找时间
插入/删除顶点	O(V²)	O(V+E)	邻接矩阵需要移动大量数据

相关操作函数¶

邻接表相关操作¶

C
/**
 * 初始化邻接表图
 * @param G 图的指针
 * @param n 顶点数
 */
void initALGraph(ALGraph *G, int n) {
    G->numVertex = n;
    G->numEdge = 0;

    // 初始化顶点数组
    for (int i = 0; i < n; i++) {
        G->adjList[i].data = i;  // 默认顶点数据为下标
        G->adjList[i].firstarc = NULL;
    }
}

/**
 * 在邻接表中插入一条边
 * @param G 图的指针
 * @param start 起始顶点下标
 * @param end 终止顶点下标
 */
void insertEdgeAL(ALGraph *G, int start, int end) {
    // 创建新的边结点
    ArcNode *newArc = (ArcNode*)malloc(sizeof(ArcNode));
    newArc->adjvex = end;
    newArc->nextarc = G->adjList[start].firstarc;

    // 将新边插入到链表头部
    G->adjList[start].firstarc = newArc;
    G->numEdge++;
}

/**
 * 打印邻接表
 * @param G 图
 */
void printALGraph(ALGraph G) {
    printf("邻接表表示：\n");
    for (int i = 0; i < G.numVertex; i++) {
        printf("顶点 %d: ", G.adjList[i].data);
        ArcNode *p = G.adjList[i].firstarc;
        while (p != NULL) {
            printf("→ %d ", p->adjvex);
            p = p->nextarc;
        }
        printf("→ NULL\n");
    }
}

邻接矩阵相关操作¶

C
/**
 * 初始化邻接矩阵图
 * @param G 图的指针
 * @param n 顶点数
 */
void initMGraph(MGraph *G, int n) {
    G->numVertex = n;
    G->numEdge = 0;

    // 初始化顶点数组
    for (int i = 0; i < n; i++) {
        G->vertex[i] = i;  // 默认顶点数据为下标
    }

    // 初始化邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            G->edge[i][j] = 0;  // 0表示无边
        }
    }
}

/**
 * 在邻接矩阵中插入一条边
 * @param G 图的指针
 * @param start 起始顶点下标
 * @param end 终止顶点下标
 */
void insertEdgeM(MGraph *G, int start, int end) {
    if (G->edge[start][end] == 0) {  // 避免重复添加边
        G->edge[start][end] = 1;
        G->numEdge++;
    }
}

/**
 * 打印邻接矩阵
 * @param G 图
 */
void printMGraph(MGraph G) {
    printf("邻接矩阵表示：\n");
    printf("顶点：");
    for (int i = 0; i < G.numVertex; i++) {
        printf("%3d", G.vertex[i]);
    }
    printf("\n");

    for (int i = 0; i < G.numVertex; i++) {
        printf("%3d: ", G.vertex[i]);
        for (int j = 0; j < G.numVertex; j++) {
            printf("%3d", G.edge[i][j]);
        }
        printf("\n");
    }
}

带权图的扩展¶

邻接表带权图¶

C
/**
 * 带权图的边结点结构体
 */
typedef struct WeightedArcNode {
    int adjvex;                           // 边所指向的顶点位置
    int weight;                           // 边的权重
    struct WeightedArcNode *nextarc;      // 指向下一个边结点
} WeightedArcNode;

/**
 * 带权图的顶点结构体
 */
typedef struct WeightedVertexNode {
    int data;                             // 顶点数据
    WeightedArcNode *firstarc;            // 指向第一条边的指针
} WeightedVertexNode;

/**
 * 带权图的邻接表存储结构
 */
typedef struct {
    int numVertex;                        // 顶点数
    int numEdge;                          // 边数
    WeightedVertexNode adjList[MAXSIZE];  // 顶点数组
} WeightedALGraph;

邻接矩阵带权图¶

C
/**
 * 带权图的邻接矩阵存储结构
 */
typedef struct {
    int numVertex;                        // 顶点数
    int numEdge;                          // 边数
    int vertex[MAXSIZE];                  // 顶点数组
    int edge[MAXSIZE][MAXSIZE];           // 邻接矩阵，存储权重
    // 特殊值表示无边，如：INT_MAX 或 0
} WeightedMGraph;

适用场景分析¶

邻接表适用场景¶

稀疏图：边数远小于顶点数的平方（E << V²）
需要频繁遍历某个顶点的所有邻接点
动态添加/删除边的操作较多
内存空间有限的环境

邻接矩阵适用场景¶

稠密图：边数接近顶点数的平方（E ≈ V²）
需要频繁判断两个顶点是否相邻
需要快速插入/删除边
图的规模较小

关键要点总结¶

结构理解：
邻接表：每个顶点维护一个链表，存储其所有邻接点
邻接矩阵：使用二维数组直接表示顶点间的关系
空间效率：
稀疏图用邻接表更节省空间
稠密图两种结构空间复杂度相近
时间效率：
邻接矩阵在查询操作上更高效
邻接表在遍历操作上更高效
实现复杂度：
邻接矩阵实现简单，易于理解
邻接表需要处理指针操作，实现相对复杂
扩展性：
两种结构都容易扩展以支持带权图、有向图等变体

图的存储结构是图论算法的基础，选择合适的存储结构对算法性能有重要影响。理解两种结构的特点和适用场景是掌握图算法的关键。