无向图以邻接表存储

无向图以邻接表存储是一种常用的图表示方法。邻接表是一种链式存储结构，每个顶点都有一个链表，链表中存储与该顶点相邻的所有顶点。对于无向图来说，每条边会被存储两次，分别在两个顶点的链表中。 以下是邻接表存储无向图的基本结构： 1. **顶点表**：存储所有顶点的信息，每个顶点对应一个链表。 2. **边表**：每个顶点的链表存储与该顶点相邻的所有顶点。 ### 示例 假设有一个无向图，顶点集合为 {A, B, C, D}，边集合为 {(A, B), (A, C), (B, C), (C, D)}。 ```plaintext A: B -> C B: A -> C C: A -> B -> D D: C ``` ### 邻接表的实现 在编程中，邻接表通常使用数组或链表来实现。以下是使用C语言实现的无向图邻接表： ```c #include <stdio.h> #include <stdlib.h> // 定义邻接表节点 typedef struct Node { int vertex; struct Node* next; } Node; // 定义图 typedef struct Graph { int numVertices; Node** adjLists; } Graph; // 创建一个新的节点 Node* createNode(int v) { Node* newNode = malloc(sizeof(Node)); newNode->vertex = v; newNode->next = NULL; return newNode; } // 创建图 Graph* createGraph(int vertices) { Graph* graph = malloc(sizeof(Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(Node*)); for (int i = 0; i < vertices; i++) graph->adjLists[i] = NULL; return graph; } // 添加边 void addEdge(Graph* graph, int src, int dest) { // 从源顶点添加到目标顶点 Node* newNode = createNode(dest); newNode->next = graph->adjLists[src]; graph->adjLists[src] = newNode; // 从目标顶点添加到源顶点 newNode = createNode(src); newNode->next = graph->adjLists[dest]; graph->adjLists[dest] = newNode; } // 打印图 void printGraph(Graph* graph) { for (int v = 0; v < graph->numVertices; v++) { Node* temp = graph->adjLists[v]; printf("%d: ", v); while (temp) { printf("%d -> ", temp->vertex); temp = temp->next; } printf("NULL\n"); } } // 主函数 int main() { int vertices = 4; Graph* graph = createGraph(vertices); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 1, 2); addEdge(graph, 2, 3); printGraph(graph); return 0; } ``` ### 邻接表的优势 1. **节省空间**：对于稀疏图，邻接表比邻接矩阵更节省空间。 2. **快速访问**：可以快速访问某个顶点的所有邻接顶点。