图形数据结构和 Algorithms （例子）

由： 陈莎拉 陈莎拉
Hours 更新

⚡ 智能摘要

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.

  • 📐 结构体： A graph G = (V, E) pairs a set of vertices (nodes) with a set of edges (links) between them.
  • 🔤 术语： Key terms include vertex, edge, degree, indegree, outdegree, self-loop, and adjacency.
  • 🗂️ 表示： Graphs are stored using an adjacency matrix or an adjacency list, each with different space trade-offs.
  • 🧭 类型： Directed, undirected, weighted, cyclic, acyclic, complete, bipartite, and more classify graphs by structure.
  • 🌐 应用环境： Google Maps routing, social networks, web ranking, and resource dependency all rely on graphs.
阅读更多

图形数据结构和 Algorithms

数据结构中的图是什么？

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.

如果将边表示为 E，将顶点表示为 V，则图 G 可以写成顶点和边的集合，例如 G (V, E).

数据结构中的图示例

Here is a simple example of a graph data structure:

数据结构中的图示例

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.

数据结构中的图形术语

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

术语描述
顶点Each data element is called a vertex or a node. In the above image, A, B, C, D & E are the vertices.
边缘（弧）Connecting links between two nodes or vertices are called an edge (Arc). It has two ends and is represented as (startingVertex, endingVertex).
无向边它是双向边。
有向边它是一条单向边。
加权边缘An edge with a value on it.
学位In a Graph, the number of edges connected to a vertex is called a degree.
入度连接到顶点的传入边的总数。
出度连接到顶点的传出边的总数。
自循环如果一条边的两个端点重合，则称该边为自环。
邻接Vertices are said to be adjacent if an edge is connected between them.

相关文章

数据结构中的图类型

以下是最常见的 数据结构中的图类型:

  • 有向图
  • 无向图
  • 加权图
  • 双向图
  • 无限图
  • 空图
  • 简单图
  • 多图
  • 完整图
  • 连通图
  • 循环图
  • 有向无环图（DAG）
  • 循环图
  • 二分图
  • 欧拉图
  • 汉密尔顿图

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.

  • 邻接矩阵： 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.
  • 邻接表： 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 教程。

图形数据结构的应用

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 搜索引擎使用图表来创建网站排名。
  • 一张地图ping 该设备使用图数据结构。
  • A 路由器 and its protocol use the Graph to learn the path to the destination.

常见问题

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 backtrac王。

总结一下这篇文章：