Trong hướng dẫn này, bạn sẽ tìm hiểu danh sách kề là gì. Ngoài ra, bạn sẽ tìm thấy các ví dụ làm việc của danh sách kề trong C, C ++, Java và Python.
Danh sách kề biểu thị một biểu đồ dưới dạng một mảng các danh sách được liên kết.
Chỉ số của mảng đại diện cho một đỉnh và mỗi phần tử trong danh sách liên kết của nó đại diện cho các đỉnh khác tạo thành một cạnh với đỉnh.
Biểu diễn Danh sách gần kề
Biểu đồ và biểu diễn danh sách kề tương đương của nó được hiển thị bên dưới.
Biểu diễn Danh sách gần kề
Danh sách kề là hiệu quả về mặt lưu trữ vì chúng ta chỉ cần lưu trữ các giá trị cho các cạnh. Đối với một đồ thị thưa thớt có hàng triệu đỉnh và cạnh, điều này có nghĩa là rất nhiều không gian được tiết kiệm.
Cấu trúc danh sách gần kề
Danh sách kề đơn giản nhất cần có cấu trúc dữ liệu nút để lưu một đỉnh và cấu trúc dữ liệu đồ thị để tổ chức các nút.
Chúng tôi tiếp cận với định nghĩa cơ bản của đồ thị - tập hợp các đỉnh và cạnh (V, E). Để đơn giản, chúng tôi sử dụng một đồ thị không có nhãn thay vì một đồ thị có nhãn, tức là các đỉnh được xác định bởi các chỉ số 0,1,2,3 của chúng.
Hãy cùng tìm hiểu cấu trúc dữ liệu tại đây.
struct node ( int vertex; struct node* next; ); struct Graph ( int numVertices; struct node** adjLists; );
Đừng để struct node** adjListsáp đảo bạn.
Tất cả những gì chúng tôi đang nói là chúng tôi muốn lưu trữ một con trỏ tới struct node*. Điều này là do chúng ta không biết đồ thị sẽ có bao nhiêu đỉnh và vì vậy chúng ta không thể tạo một mảng Danh sách liên kết tại thời điểm biên dịch.
Danh sách gần kề C ++
Nó là cùng một cấu trúc nhưng bằng cách sử dụng cấu trúc dữ liệu STL danh sách có sẵn của C ++, chúng tôi làm cho cấu trúc sạch hơn một chút. Chúng tôi cũng có thể tóm tắt các chi tiết của việc thực hiện.
class Graph ( int numVertices; list *adjLists; public: Graph(int V); void addEdge(int src, int dest); );
Danh sách gần kề Java
Chúng tôi sử dụng Bộ sưu tập Java để lưu trữ Mảng danh sách được liên kết.
class Graph ( private int numVertices; private LinkedList adjLists(); )
Loại LinkedList được xác định bởi dữ liệu bạn muốn lưu trữ trong đó. Đối với một đồ thị được gắn nhãn, bạn có thể lưu trữ một từ điển thay vì một Số nguyên
Python danh sách gần kề
Có một lý do khiến Python được yêu thích nhiều như vậy. Một từ điển đơn giản về các đỉnh và các cạnh của nó là một đại diện đầy đủ của một đồ thị. Bạn có thể tự làm cho đỉnh phức tạp như bạn muốn.
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')))
Ví dụ về Python, Java và C / C ++
Python Java C C ++ # 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(" ") 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()
// Adjascency List representation in Java import java.util.*; class Graph ( // Add edge static void addEdge(ArrayList 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 am = new ArrayList (V); for (int i = 0; i < V; i++) am.add(new ArrayList()); // 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 am) ( for (int i = 0; i < am.size(); i++) ( System.out.println("Vertex " + i + ":"); for (int j = 0; j " + am.get(i).get(j)); ) System.out.println(); ) ) )
// Adjascency List representation in C #include #include 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 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 numVertices; v++) ( struct node* temp = graph->adjLists(v); printf(" Vertex %d: ", v); while (temp) ( printf("%d -> ", temp->vertex); temp = temp->next; ) printf(""); ) ) 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; )
// Adjascency List representation in C++ #include using namespace std; // Add edge void addEdge(vector adj(), int s, int d) ( adj(s).push_back(d); adj(d).push_back(s); ) // Print the graph void printGraph(vector adj(), int V) ( for (int d = 0; d < V; ++d) ( cout << " Vertex " << d << ":"; for (auto x : adj(d)) cout < " << x; printf(""); ) ) int main() ( int V = 5; // Create a graph vector adj(V); // Add edges addEdge(adj, 0, 1); addEdge(adj, 0, 2); addEdge(adj, 0, 3); addEdge(adj, 1, 2); printGraph(adj, V); )
