# 鄰接表 > 原文： [https://www.programiz.com/dsa/graph-adjacency-list](https://www.programiz.com/dsa/graph-adjacency-list) #### 在本教程中，您將學習什么是鄰接表。 此外，您還將在 C，C++ ，Java 和 Python 中找到鄰接表的工作示例。 鄰接列表將圖表示為鏈表的數組。 數組的索引表示一個頂點，而其鏈表中的每個元素表示與該頂點形成邊的其他頂點。 * * * ## 鄰接表表示 圖及其等效的鄰接表表示如下。  鄰接表表示 鄰接表在存儲方面非常有效，因為我們只需要存儲邊的值即可。 對于具有數百萬個頂點和邊的稀疏圖，這可能意味著節省了大量空間。 * * * ## 鄰接表結構 最簡單的鄰接表需要一個節點數據結構來存儲頂點，并需要一個圖數據結構來組織節點。 我們接近圖的基本定義-頂點和邊的集合`{V, E}`。 為簡單起見，我們使用未標記圖而不是標記圖，即頂點由其索引 0、1、2、3 標識。 讓我們在這里深入研究數據結構。 ``` struct node { int vertex; struct node* next; }; struct Graph { int numVertices; struct node** adjLists; }; ``` 不要讓`struct node** adjLists`淹沒您。 我們只是說要存儲指向`struct node*`的指針。 這是因為我們不知道圖形將具有多少個頂點，因此無法在編譯時創建鏈表的數組。 * * * ## 鄰接表 C++ 它是相同的結構，但是通過使用 C++ 的內置列表 STL 數據結構，我們使該結構更整潔。 我們還能夠抽象出實現的細節。 ``` class Graph { int numVertices; list<int> *adjLists; public: Graph(int V); void addEdge(int src, int dest); }; ``` * * * ## 鄰接表 Java 我們使用 Java 集合來存儲鏈表數組。 ``` class Graph { private int numVertices; private LinkedList<integer> adjLists[]; } ``` `LinkedList`的類型由要存儲在其中的數據確定。 對于帶標簽的圖形，您可以存儲字典而不是整數 * * * ## 鄰接表 Python Python 得到如此多的愛是有原因的。 一個簡單的頂點及其邊的字典就足以表示一個圖。 您可以按需使頂點本身復雜。 ``` graph = {'A': set(['B', 'C']), 'B': set(['A', 'D', 'E']), 'C': set(['A', 'F']), 'D': set(['B']), 'E': set(['B', 'F']), 'F': set(['C', 'E'])} ``` * * * ## Python，Java 和 C/C++ 示例 ```py # Adjascency List representation in Python class AdjNode: def __init__(self, value): self.vertex = value self.next = None class Graph: def __init__(self, num): self.V = num self.graph = [None] * self.V # Add edges def add_edge(self, s, d): node = AdjNode(d) node.next = self.graph[s] self.graph[s] = node node = AdjNode(s) node.next = self.graph[d] self.graph[d] = node # Print the graph def print_agraph(self): for i in range(self.V): print("Vertex " + str(i) + ":", end="") temp = self.graph[i] while temp: print(" -> {}".format(temp.vertex), end="") temp = temp.next print(" \n") if __name__ == "__main__": V = 5 # Create graph and edges graph = Graph(V) graph.add_edge(0, 1) graph.add_edge(0, 2) graph.add_edge(0, 3) graph.add_edge(1, 2) graph.print_agraph() ``` ```java // Adjascency List representation in Java import java.util.*; class Graph { // Add edge static void addEdge(ArrayList<ArrayList<Integer>> am, int s, int d) { am.get(s).add(d); am.get(d).add(s); } public static void main(String[] args) { // Create the graph int V = 5; ArrayList<ArrayList<Integer>> am = new ArrayList<ArrayList<Integer>>(V); for (int i = 0; i < V; i++) am.add(new ArrayList<Integer>()); // Add edges addEdge(am, 0, 1); addEdge(am, 0, 2); addEdge(am, 0, 3); addEdge(am, 1, 2); printGraph(am); } // Print the graph static void printGraph(ArrayList<ArrayList<Integer>> am) { for (int i = 0; i < am.size(); i++) { System.out.println("\nVertex " + i + ":"); for (int j = 0; j < am.get(i).size(); j++) { System.out.print(" -> " + am.get(i).get(j)); } System.out.println(); } } } ``` ```c // Adjascency List representation in C #include <stdio.h> #include <stdlib.h> struct node { int vertex; struct node* next; }; struct node* createNode(int); struct Graph { int numVertices; struct node** adjLists; }; // Create a node struct node* createNode(int v) { struct node* newNode = malloc(sizeof(struct node)); newNode->vertex = v; newNode->next = NULL; return newNode; } // Create a graph struct Graph* createAGraph(int vertices) { struct Graph* graph = malloc(sizeof(struct Graph)); graph->numVertices = vertices; graph->adjLists = malloc(vertices * sizeof(struct node*)); int i; for (i = 0; i < vertices; i++) graph->adjLists[i] = NULL; return graph; } // Add edge void addEdge(struct Graph* graph, int s, int d) { // Add edge from s to d struct node* newNode = createNode(d); newNode->next = graph->adjLists[s]; graph->adjLists[s] = newNode; // Add edge from d to s newNode = createNode(s); newNode->next = graph->adjLists[d]; graph->adjLists[d] = newNode; } // Print the graph void printGraph(struct Graph* graph) { int v; for (v = 0; v < graph->numVertices; v++) { struct node* temp = graph->adjLists[v]; printf("\n Vertex %d\n: ", v); while (temp) { printf("%d -> ", temp->vertex); temp = temp->next; } printf("\n"); } } int main() { struct Graph* graph = createAGraph(4); addEdge(graph, 0, 1); addEdge(graph, 0, 2); addEdge(graph, 0, 3); addEdge(graph, 1, 2); printGraph(graph); return 0; } ``` ```cpp // Adjascency List representation in C++ #include <bits/stdc++.h> using namespace std; // Add edge void addEdge(vector<int> adj[], int s, int d) { adj[s].push_back(d); adj[d].push_back(s); } // Print the graph void printGraph(vector<int> adj[], int V) { for (int d = 0; d < V; ++d) { cout << "\n Vertex " << d << ":"; for (auto x : adj[d]) cout << "-> " << x; printf("\n"); } } int main() { int V = 5; // Create a graph vector<int> adj[V]; // Add edges addEdge(adj, 0, 1); addEdge(adj, 0, 2); addEdge(adj, 0, 3); addEdge(adj, 1, 2); printGraph(adj, V); } ```