7.4. 邻接矩阵

7.4. An Adjacency Matrix

中文英文

实现图的一种最简单方法是使用二维矩阵。在这种矩阵实现中，每一行和每一列都表示图中的一个顶点。存储在行 $v$ 和列 $w$ 交叉处的单元格中的值表示是否存在从顶点 $v$ 到顶点 $w$ 的边。当两个顶点由一条边连接时，我们说它们是 相邻 的。Figure 3 说明了 Figure 2 图的邻接矩阵。每个单元格中的值表示从顶点 $v$ 到顶点 $w$ 的边的权重。

Figure 3: 图的邻接矩阵表示

邻接矩阵的优点是它简单，对于小型图，易于查看哪些节点连接到其他节点。然而，注意到矩阵中的大多数单元格是空的；我们可以说这个矩阵是 稀疏的。矩阵不是存储稀疏数据的高效方式。实际上，在 Python 中，你必须特别创建像 Figure 3 中的矩阵结构。

邻接矩阵在边的数量很大时是图的一个很好的实现。但什么是“很大”？填满矩阵需要多少条边？由于图中每个顶点都有一行和一列，因此填满矩阵所需的边数是 $|V{|}^2$。当每个顶点都与每个其他顶点连接时，矩阵是满的。实际上，很少有实际问题接近这种连接性。本章中我们将讨论的所有问题都涉及稀疏连接的图。

One of the easiest ways to implement a graph is to use a two-dimensional matrix. In this matrix implementation, each of the rows and columns represents a vertex in the graph. The value that is stored in the cell at the intersection of row $v$ and column $w$ indicates if there is an edge from vertex $v$ to vertex $w$. When two vertices are connected by an edge, we say that they are adjacent. Figure 3 illustrates the adjacency matrix for the graph in Figure 2. The value in each cell represents the weight of the edge from vertex $v$ to vertex $w$.

Figure 3: An Adjacency Matrix Representation for a Graph

The advantage of the adjacency matrix is that it is simple, and for small graphs it is easy to see which nodes are connected to other nodes. However, otice that most of the cells in the matrix are empty; we can say that this matrix is sparse. A matrix is not a very efficient way to store sparse data. In fact, in Python you must go out of your way to even create a matrix structure like the one in Figure 3.

The adjacency matrix is a good implementation for a graph when the number of edges is large. But what do we mean by large? How many edges would be needed to fill the matrix? Since there is one row and one column for every vertex in the graph, the number of edges required to fill the matrix is $|V{|}^2$. A matrix is full when every vertex is connected to every other vertex. There are few real problems that approach this sort of connectivity. The problems we will look at in this chapter all involve graphs that are sparsely connected.

---

最后更新: 2024年9月13日
创建日期: 2024年9月9日