Pointer如何实现图结构

在计算机科学中，指针是一种变量，它存储了另一个变量的内存地址。使用指针可以高效地操作数据结构，包括图结构。图是由节点（顶点）和边组成的数据结构，可以用多种方式表示，其中最常见的是邻接矩阵和邻接表。

以下是使用指针实现图结构的两种常见方法：

1. 邻接矩阵表示法： 在这种方法中，使用一个二维数组来表示图。数组的行和列对应于图中的顶点，数组元素表示顶点之间的连接关系。如果顶点i和顶点j之间存在边，则数组的第i行第j列的元素为1（或边的权重），否则为0。

#define MAX_VERTICES 100

int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];

// 初始化图
void initializeGraph(int vertices) {
    for (int i = 0; i < vertices; i++) {
        for (int j = 0; j < vertices; j++) {
            adjacencyMatrix[i][j] = 0;
        }
    }
}

// 添加边
void addEdge(int src, int dest) {
    adjacencyMatrix[src][dest] = 1;
    // 如果是无向图，还需要添加反向边
    // adjacencyMatrix[dest][src] = 1;
}

2. 邻接表表示法： 在这种方法中，每个顶点都有一个链表，链表中存储了所有与该顶点相连的顶点。这种方法比邻接矩阵更节省空间，特别是对于稀疏图。

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

// 边节点结构
typedef struct EdgeNode {
    int dest;
    struct EdgeNode* next;
} EdgeNode;

// 顶点节点结构
typedef struct VertexNode {
    int vertex;
    EdgeNode* firstEdge;
} VertexNode;

// 图结构
typedef struct Graph {
    VertexNode adjList[MAX_VERTICES];
    int numVertices;
} Graph;

// 初始化图
void initializeGraph(Graph* graph, int vertices) {
    graph->numVertices = vertices;
    for (int i = 0; i < vertices; i++) {
        graph->adjList[i].vertex = i;
        graph->adjList[i].firstEdge = NULL;
    }
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    // 创建新边节点
    EdgeNode* newEdge = (EdgeNode*)malloc(sizeof(EdgeNode));
    newEdge->dest = dest;
    newEdge->next = graph->adjList[src].firstEdge;
    graph->adjList[src].firstEdge = newEdge;
    
    // 如果是无向图，还需要添加反向边
    // newEdge = (EdgeNode*)malloc(sizeof(EdgeNode));
    // newEdge->dest = src;
    // newEdge->next = graph->adjList[dest].firstEdge;
    // graph->adjList[dest].firstEdge = newEdge;
}

// 主函数
int main() {
    Graph graph;
    initializeGraph(&graph, 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);
    
    // 图的其他操作...
    
    return 0;
}

在上面的邻接表实现中，我们定义了两个结构体：EdgeNode 和 VertexNode。EdgeNode 表示图中的一条边，包含目标顶点的索引和指向下一个边节点的指针。VertexNode 表示图中的一个顶点，包含顶点的索引和一个指向第一个边节点的指针。Graph 结构体包含了所有的顶点节点和一个表示顶点数量的整数。

使用指针可以灵活地管理内存，例如在添加或删除边时动态分配和释放内存。这种方法适用于需要频繁修改图结构的场景。