图存储结构详解与C代码实现

邻接矩阵

认识邻接矩阵

邻接矩阵就像一个巨大的表格，表的行和列都代表图中的节点。如果节点A和节点B之间有边相连，那么在这个表格中，A行B列（或B行A列，对于无向图来说）的位置上就会标记为1（或者其它表示“有连接”的值）。如果它们之间没有边相连，那么这个位置就标记为0（或其它表示“无连接”的值）。

图 1-28图的邻接矩阵

以图1-28为例，我们来理解图的邻接矩阵。

在无向图中，边是双向的，即如果顶点i与顶点j之间存在一条边，那么从i到j和从j到i都是可达的。因此，在邻接矩阵中，A[i][j]和A[j][i]都会被标记为1，表示这两个顶点之间存在连接。这种表示方式使得我们可以快速判断任意两个顶点之间是否存在边，通过简单地检查对应位置的矩阵元素即可。

对于有向图，情况稍有不同。在有向图中，边是单向的，即存在从顶点i指向顶点j的边并不意味着从j到i也存在边。因此，在邻接矩阵中，我们只在A[i][j]处标记为1，表示存在从i到j的边，而A[j][i]则保持为0或其他默认值，表示不存在从j到i的边。这种表示方式能够准确地反映有向图的特性，使得我们可以轻松地识别出边的方向性。

除了表示图的结构外，邻接矩阵还可以用于表示带权图。在带权图中，每条边都有一个权重，表示两个顶点之间的某种度量或成本。在邻接矩阵中，我们可以将A[i][j]的值设置为边(i, j)的权重，如果i和j之间没有边，则可以将A[i][j]设置为一个特殊值（如无穷大或-1），表示这两个顶点之间不可达。这种表示方式使得我们可以方便地进行基于权重的图算法操作，如最短路径算法等。

邻接矩阵的优点在于其直观性和易于操作性。通过简单的数组索引操作，可以快速访问和修改图的结构信息。此外，邻接矩阵还支持快速的矩阵运算，使得某些图算法（如邻接矩阵的幂运算用于计算可达性）变得简单高效。

邻接矩阵也存在一些缺点。对于稀疏图（即边数相对于顶点数较少的图），邻接矩阵可能会浪费大量的存储空间，因为大部分矩阵元素都是0或默认值。其次，对于大规模的图，邻接矩阵的存储和操作可能会变得非常耗时和内存消耗大。

在选择使用邻接矩阵表示图时，我们需要根据具体的应用场景和需求进行权衡。对于稠密图或需要频繁进行矩阵运算的场景，邻接矩阵可能是一个合适的选择。而对于稀疏图或需要节省存储空间的场景，其他表示方法（如邻接表）可能更为合适。

C语言实现邻接矩阵

下面是一个简单的C语言程序，用于创建和打印图的邻接矩阵表示。

#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 100  // 定义最大顶点数
// 定义图的邻接矩阵表示
typedef struct {
    int matrix[MAX_VERTICES][MAX_VERTICES];  // 邻接矩阵
    int numVertices;  // 顶点数
} Graph;
// 初始化图的邻接矩阵表示
void initializeGraph(Graph *graph, int numVertices) {
    graph->numVertices = numVertices;
    for (int i = 0; i < numVertices; i++) {
        for (int j = 0; j < numVertices; j++) {
            graph->matrix[i][j] = 0;  // 初始化为0，表示没有边相连
        }
    }
}
// 添加边到图的邻接矩阵表示中
void addEdge(Graph *graph, int from, int to, int weight) {
    if (from >= graph->numVertices || to >= graph->numVertices) {
        printf("Invalid vertex index!\n");
        return;
    }
    graph->matrix[from][to] = weight;  // 设置边的权重
    graph->matrix[to][from] = weight;  // 对于无向图，需要设置对称位置的权重
}
// 打印图的邻接矩阵表示
void printGraph(Graph *graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        for (int j = 0; j < graph->numVertices; j++) {
            printf("%d ", graph->matrix[i][j]);
        }
        printf("\n");
    }
}
int main() {
    Graph graph;
    int numVertices, numEdges, from, to, weight;
    
    printf("Enter the number of vertices: ");
    scanf("%d", &numVertices);
    initializeGraph(&graph, numVertices);
    
    printf("Enter the number of edges: ");
    scanf("%d", &numEdges);
    for (int i = 0; i < numEdges; i++) {
        printf("Enter edge %d (from, to, weight): ", i + 1);
        scanf("%d %d %d", &from, &to, &weight);
        addEdge(&graph, from, to, weight);
    }
    
    printf("Adjacency matrix:\n");
    printGraph(&graph);
    
    return 0;
}

上述程序中，首先定义了一个Graph结构体，用于存储邻接矩阵和顶点数。然后实现了三个函数：initializeGraph用于初始化图的邻接矩阵表示，addEdge用于向图中添加边，并设置相应的权重，printGraph用于打印图的邻接矩阵表示。在main函数中，读取用户输入的顶点数和边数，以及每条边的起点、终点和权重，并使用这些信息创建和打印图的邻接矩阵表示。

领接表

认识邻接表

邻接表是另一种存储图的方式。它对于每个节点都建立一个列表，这个列表里存着和这个节点直接相连的其它节点。这样，我们只需要查看某个节点的列表，就可以知道它连接了哪些节点。

图 1-29图的邻接表

以图1-29为例，我们来理解图的邻接表。

在有向图中，每条边都有明确的起点和终点。邻接表为每个顶点维护了一个链表，链表中存储的是从这个顶点出发可以到达的其他顶点。换句话说，每个顶点对应的链表实际上是一个出边列表，记录了从这个顶点出发的所有边的终点。

这种存储方式非常适合处理有向图的遍历和搜索操作。例如，在深度优先搜索（DFS）或广度优先搜索（BFS）中，可以根据当前顶点的邻接表快速找到所有相邻的顶点，并继续搜索过程。此外，邻接表还可以方便地添加或删除边，因为每个顶点的链表都是独立的，修改一个顶点的邻接表不会影响到其他顶点。

对于无向图来说，邻接表的存储方式也类似。但是由于无向图中每条边都是双向的，因此每个顶点的链表中需要存储与该顶点有边相连的所有顶点。换句话说，无向图的邻接表实际上是双向的，每个顶点的链表既包含了指向它的顶点，也包含了从它出发可以到达的顶点。

虽然无向图的邻接表在表示上稍微复杂一些，但它仍然具有许多优点。与有向图一样，无向图的邻接表也支持高效的遍历和搜索操作。此外，由于邻接表使用了链表来存储边信息，因此它可以有效地处理稀疏图（即边数相对较少的图），避免了使用二维数组等数据结构时可能产生的空间浪费。

C语言实现邻接表

下面是一个简单的C语言实现邻接表的例子。

#include <stdio.h>
#include <stdlib.h>
// 定义邻接表中边的结构体
typedef struct Edge {
    int dest;           // 边的目标顶点
    struct Edge* next;  // 指向下一条边的指针
} Edge;
// 定义邻接表中顶点的结构体
typedef struct Vertex {
    int data;           // 顶点的数据
    Edge* firstEdge;    // 指向第一条边的指针
} Vertex;
// 定义图的结构体
typedef struct Graph {
    int numVertices;    // 顶点的数量
    Vertex* vertices;   // 顶点数组
} Graph;
// 创建新的边
Edge* createEdge(int dest) {
    Edge* newEdge = (Edge*)malloc(sizeof(Edge));
    newEdge->dest = dest;
    newEdge->next = NULL;
    return newEdge;
}
// 创建新的顶点
Vertex* createVertex(int data) {
    Vertex* newVertex = (Vertex*)malloc(sizeof(Vertex));
    newVertex->data = data;
    newVertex->firstEdge = NULL;
    return newVertex;
}
// 创建新的图
Graph* createGraph(int numVertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = numVertices;
    graph->vertices = (Vertex*)malloc(numVertices * sizeof(Vertex));
    for (int i = 0; i < numVertices; i++) {
        graph->vertices[i] = *createVertex(i);
    }
    return graph;
}
// 在图中添加边
void addEdge(Graph* graph, int src, int dest) {
    Edge* newEdge = createEdge(dest);
    newEdge->next = graph->vertices[src].firstEdge;
    graph->vertices[src].firstEdge = newEdge;
    // 如果是无向图，还需要添加反向边
    // newEdge = createEdge(src);
    // newEdge->next = graph->vertices[dest].firstEdge;
    // graph->vertices[dest].firstEdge = newEdge;
}
// 打印图的邻接表表示
void printGraph(Graph* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        printf("Vertex %d: ", graph->vertices[i].data);
        Edge* currentEdge = graph->vertices[i].firstEdge;
        while (currentEdge != NULL) {
            printf("%d ", currentEdge->dest);
            currentEdge = currentEdge->next;
        }
        printf("\n");
    }
}
// 释放图的内存
void freeGraph(Graph* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        Edge* currentEdge = graph->vertices[i].firstEdge;
        Edge* nextEdge;
        while (currentEdge != NULL) {
            nextEdge = currentEdge->next;
            free(currentEdge);
            currentEdge = nextEdge;
        }
    }
    free(graph->vertices);
    free(graph);
}
int main() {
    // 创建一个包含5个顶点的图
    Graph* graph = createGraph(5);
    // 添加边
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);
    // 打印邻接表
    printGraph(graph);
    // 释放内存
    freeGraph(graph);
    return 0;
}

示例代码展示了如何使用C语言实现邻接表。createGraph 函数创建一个新的图，createEdge 和 createVertex 函数分别创建新的边和顶点。addEdge 函数用于在图中添加边。printGraph 函数用于打印图的邻接表表示。最后调用freeGraph函数释放内存。

十字链表

认识十字链表

十字链表结合了前面的方法，并加入了对有向图和有向图中边的权值等特殊情况的处理。十字链表可以方便地找到节点的入边和出边。

图 1-30图的十字链表

以图1-30为例，我们来理解图的邻接表。

图1-30是一个有向图，包含A、B、C、D顶点，这些顶点之间存在有向的边，例如A到B、从B到C、从C到D以及可能的反向边或其他边。为了使用十字链表来表示这个有向图，们需要为每个顶点创建一个节点，并在这些节点之间建立相应的链接。

以顶点B为例，可以创建一个包含B信息的节点。然后检查所有从B出发的边。如果B有一条边指向A，那么就需要在B的出边链表中添加一个指向A的节点。同样地，如果B有其他出边，也需要将它们添加到B的出边链表中。类似地，还需要检查所有指向B的边，并在B的入边链表中添加相应的节点。

对于顶点A、C和D，也需要执行相同的操作。最终将得到一个由十字链表表示的有向图，其中每个顶点都与其入弧和出弧相关联。

十字链表在有向图中的应用具有许多优点。它能高效地查找一个顶点的所有入边和出边，这对于许多图算法（如深度优先搜索、广度优先搜索等）来说是非常有用的。由于十字链表采用链式存储结构，它可以灵活地处理稀疏图（即边数相对较少的图），而不会浪费大量的存储空间。

总的来说，选择哪种存储方式主要取决于图的特性和你的需求。如果图很稠密，或者你需要快速判断两个节点是否有边相连，那么邻接矩阵可能更合适。如果图很稀疏，或者你只需要知道每个节点的邻居有哪些，那么邻接表可能更合适。而更复杂的图结构，则可能需要用到十字链表或邻接多重表等更高级的存储方式。

C语言实现十字链表

一个十字链表节点通常包含四个部分：行索引、列索引、值，以及指向同行和同列下一个元素的指针。

下面是一个使用C语言实现的十字链表的基本案例。

#include <stdio.h>
#include <stdlib.h>
// 定义十字链表节点
typedef struct OLNode {
int row;       // 行索引
int col;       // 列索引
int value;     // 元素值
struct OLNode *right; // 同行下一个元素
struct OLNode *down;  // 同列下一个元素
} OLNode, *OLink;
// 定义行指针和列指针
typedef struct {
OLink *rhead;  // 行头指针数组
OLink *chead;  // 列头指针数组
int rows;      // 行数
int cols;      // 列数
int nums;      // 非零元素个数
} CrossList;
// 创建十字链表
CrossList* CreateCrossList(int rows, int cols, int nums) {
CrossList *list = (CrossList*)malloc(sizeof(CrossList));
list->rhead = (OLink*)malloc(rows * sizeof(OLink));
list->chead = (OLink*)malloc(cols * sizeof(OLink));
list->rows = rows;
list->cols = cols;
list->nums = nums;
for (int i = 0; i < rows; i++) {
list->rhead[i] = NULL;
}
for (int j = 0; j < cols; j++) {
list->chead[j] = NULL;
}
return list;
}
// 向十字链表中插入元素
void InsertOL(CrossList *list, int row, int col, int value) {
OLink p, q, s;
// 创建新节点
s = (OLink)malloc(sizeof(OLNode));
s->row = row;
s->col = col;
s->value = value;
s->right = NULL;
s->down = NULL;
// 插入到行链表中
p = list->rhead[row];
if (p == NULL || p->col > col) {
s->right = p;
list->rhead[row] = s;
} else {
while (p->right != NULL && p->right->col < col) {
p = p->right;
}
if (p->col == col) { // 重复元素，不插入
free(s);
return;
}
s->right = p->right;
p->right = s;
}
// 插入到列链表中
q = list->chead[col];
if (q == NULL || q->row > row) {
s->down = q;
list->chead[col] = s;
} else {
while (q->down != NULL && q->down->row < row) {
q = q->down;
}
if (q->row == row) { // 重复元素，不插入
free(s);
return;
}
s->down = q->down;
q->down = s;
}
}
// 主函数，用于测试
int main() {
int rows = 5, cols = 5, nums = 6;
int data[6][3] = {{1, 1, 1}, {2, 2, 2}, {3, 3, 3}, {4, 4, 4}, {1, 5, 5}, {5, 1, 6}};
CrossList *list = CreateCrossList(rows, cols, nums);
for (int i = 0; i < nums; i++) {
InsertOL(list, data[i][0] - 1, data[i][1] - 1, data[i][2]);
}
// TODO: 实现十字链表的遍历、查找、删除等操作
return 0;
}

这个示例代码展示了如何创建十字链表以及向其中插入元素。在实际应用中，可能还需要实现遍历、查找、删除。