无向图的邻接表表示求度

无向图以邻接表存储是一种常用的图表示方法。邻接表是一种链式存储结构，每个顶点都有一个链表，链表中存储与该顶点相邻的所有顶点。对于无向图来说，每条边会被存储两次，分别在两个顶点的链表中。 以下是邻接表存储无向图的基本结构： 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. **快速访问**：可以快速访问某个顶点的所有邻接顶点。

无向图的邻接表可以使用一个数组来表示，数组中的每个元素都是一个链表，链表中存储了与该顶点相邻的所有顶点。可以使用 STL 中的 vector 和 list 来实现。以下是一个简单的 C++ 代码示例： ```cpp #include <iostream> #include <vector> #include <list> using namespace std; // 无向图邻接表的实现 class Graph { public: Graph(int V) { this->V = V; adjList.resize(V); } // 添加边 void addEdge(int u, int v) { adjList[u].push_back(v); adjList[v].push_back(u); } // 打印邻接表 void printAdjList() { for (int i = 0; i < V; ++i) { cout << i << ": "; for (auto v : adjList[i]) { cout << v << " "; } cout << endl; } } private: int V; // 顶点数 vector<list<int>> adjList; // 邻接表 }; int main() { Graph g(6); g.addEdge(1, 2); g.addEdge(1, 3); g.addEdge(2, 4); g.addEdge(2, 5); g.addEdge(3, 4); g.addEdge(4, 5); g.printAdjList(); return 0; } ``` 输出结果为： ``` 0: 1: 2 3 2: 1 4 5 3: 1 4 4: 2 3 5 5: 2 4 ``` 其中，每行的第一个数字表示顶点的编号，后面的数字表示与该顶点相邻的顶点编号。