Cấu trúc dữ liệu đồ thị và Algorithms (Thí dụ)

Bởi: Sarah Chen Sarah Chen
Hours cập nhật

⚡ Tóm tắt thông minh

Graph Data Structure is a non-linear collection of vertices and edges where each edge links a pair of vertices. Graphs model real-world networks such as maps, social connections, and web pages, and support many powerful algorithms.

  • 📐 Kết cấu: A graph G = (V, E) pairs a set of vertices (nodes) with a set of edges (links) between them.
  • 🔤 Thuật ngữ: Key terms include vertex, edge, degree, indegree, outdegree, self-loop, and adjacency.
  • 🗂️ Đại diện: Graphs are stored using an adjacency matrix or an adjacency list, each with different space trade-offs.
  • 🧭 Các loại: Directed, undirected, weighted, cyclic, acyclic, complete, bipartite, and more classify graphs by structure.
  • 🌐 Ứng dụng Google Maps routing, social networks, web ranking, and resource dependency all rely on graphs.
Đọc thêm

Cấu trúc dữ liệu đồ thị và Algorithms

Biểu đồ trong cấu trúc dữ liệu là gì?

A graph is a non-linear data structure that consists of vertices and edges, where vertices contain the information or data, and the edges work as a link between a pair of vertices.

It is used to solve real-world problems like finding the best route to the destination location and the route for telecommunications and social networks. Users are considered a node in the Graph, and the wires are the edges connecting the users.

Nếu các cạnh được biểu diễn dưới dạng E và các đỉnh được biểu diễn dưới dạng V thì đồ thị G có thể được viết dưới dạng tập hợp các đỉnh và cạnh, chẳng hạn như G (V, E).

Ví dụ về đồ thị trong cấu trúc dữ liệu

Here is a simple example of a graph data structure:

Ví dụ về đồ thị trong cấu trúc dữ liệu

It is a simple undirected graph (one kind of Graph). Here the set of vertices is: {A, B, C, D, E, F}. Two vertices create an edge. For example, A and B are linked with an edge. However, A and F are not linked with any edges.

Thuật ngữ đồ thị trong cấu trúc dữ liệu

The following are some important terms used in the graph data structure:

Hạn Mô tả Chi tiết
đỉnh đầuEach data element is called a vertex or a node. In the above image, A, B, C, D & E are the vertices.
Cạnh (Cung)Connecting links between two nodes or vertices are called an edge (Arc). It has two ends and is represented as (startingVertex, endingVertex).
Cạnh vô hướngĐó là một cạnh hai chiều.
Biên hướngĐó là một cạnh một chiều.
Cạnh có trọng sốAn edge with a value on it.
Bằng cấpIn a Graph, the number of edges connected to a vertex is called a degree.
Bằng cấpTổng số cạnh đến được kết nối với một đỉnh.
Bằng cấp cao hơnTổng số cạnh đi được kết nối với một đỉnh.
Tự vòng lặpMột cạnh được gọi là tự lặp nếu hai điểm cuối của nó trùng nhau.
Sự gần gũiVertices are said to be adjacent if an edge is connected between them.

NHỮNG BÀI VIẾT LIÊN QUAN

Các loại đồ thị trong cấu trúc dữ liệu

Dưới đây là danh sách phổ biến nhất các loại đồ thị trong cấu trúc dữ liệu:

  • Đồ thị có hướng
  • Đồ thị vô hướng
  • Biểu đồ có trọng số
  • Đồ thị hai chiều
  • Đồ thị vô hạn
  • Đồ thị rỗng
  • Đồ thị tầm thường
  • Đa đồ thị
  • Đồ thị hoàn chỉnh
  • Đồ thị được kết nối
  • Đồ thị tuần hoàn
  • Đồ thị vòng có hướng (DAG)
  • Đồ thị chu kỳ
  • Đồ thị hai bên
  • Đồ thị Euler
  • Đồ thị Hamilton

How to Represent a Graph in Data Structure?

A graph is commonly stored in memory using one of two representations. The choice affects how much memory the graph uses and how fast common operations run.

  • Ma trận kề: A two-dimensional V × V array where cell [i][j] is 1 (or the edge weight) if an edge exists between vertex i and vertex j, and 0 otherwise. It allows O(1) edge lookup but uses O(V²) space, making it best for dense graphs.
  • Danh sách lân cận: An array of lists where each vertex stores a list of its neighbouring vertices. It uses O(V + E) space and is efficient for sparse graphs, which is why most real-world graphs use it.

You can read more about these in the adjacency list and matrix representation of a graph hướng dẫn.

Ứng dụng của cấu trúc dữ liệu đồ thị

A graph has many use cases. There are a lot of algorithms that use Graphs. Here are some of the applications of the Graph:

  • Google Maps uses graphs to find the intersection of two roads and calculate the distance between two locations. For example, dijkstra, for finding the shortest distance between the source and destination location.
  • Facebook uses Graphs to find the mutual friends of the users. Its algorithm considers each user as a node of a graph.
  • For resource allocation, a DAG (Directed Acyclic Graph) is used. It checks the dependency of the resources.
  • Google Công cụ tìm kiếm sử dụng đồ thị để tạo ra thứ hạng cho các trang web.
  • Bản đồping Thiết bị sử dụng cấu trúc dữ liệu đồ thị.
  • A bộ định tuyến and its protocol use the Graph to learn the path to the destination.

Câu Hỏi Thường Gặp

Graph Neural Networks learn from graph-structured data for fraud detection, recommendations, and drug discovery. Knowledge graphs support AI question-answering, and deep learning frameworks model every computation as a graph of operations.

Yes. AI assistants like GitHub Copilot can generate BFS, DFS, Dijkstra, and topological sort implementations from a plain description. You should still test edge cases such as disconnected nodes, cycles, and empty graphs before using the code.

A tree is a special type of graph that is connected and has no cycles, with exactly one path between any two nodes. A graph is more general: it can contain cycles, disconnected parts, and directed or weighted edges.

The two main traversal methods are Breadth-First Search (BFS), which explores level by level using a queue, and Depth-First Search (DFS), which explores as deep as possible using a stack or recursion before backtracnhà vua.

Tóm tắt bài viết này với: