图表示方式 | Representations of Graphs
邻接矩阵 | Adjacency Matrix
邻接矩阵是一种矩阵表示法，其中每个元素表示图中两顶点之间的连通性。设图中有 个顶点，则邻接矩阵为一个 的矩阵 。如果顶点 和顶点 之间有边，则 （或边的权重）；否则 。该方法在稠密图中很高效，但在稀疏图中会浪费大量空间。 An adjacency matrix is a matrix representation where each element indicates the connectivity between two vertices in the graph. If the graph has vertices, the adjacency matrix is a matrix . If there is an edge between vertex and vertex , then (or the weight of the edge); otherwise, . This method is efficient in dense graphs but may waste space in sparse graphs.
特点 | Features
- 时间复杂度 (Time Complexity):
- 检查是否存在一条边：
- 遍历所有边：
- Checking if an edge exists:
- Traversing all edges:
- 空间复杂度 (Space Complexity):
邻接矩阵的压缩存储 | Compressed Adjacency Matrix
在稀疏图中，邻接矩阵的大部分元素是零。为节省空间，可以只存储非零元素及其位置。这种方法称为压缩存储，适用于非常稀疏的图。 In sparse graphs, most elements of an adjacency matrix are zero. To save space, only the non-zero elements and their positions are stored. This method, known as compressed storage, is suitable for very sparse graphs.
邻接表 | Adjacency List
邻接表使用一个数组（或哈希表）来存储每个顶点的邻接顶点列表。每个顶点都包含一个链表（或动态数组），其中存储所有与之相邻的顶点及边的权重（如果有）。这种表示方法在稀疏图中比邻接矩阵更节省空间。 An adjacency list uses an array (or a hash table) to store the list of adjacent vertices for each vertex. Each vertex maintains a linked list (or dynamic array) of all adjacent vertices and the edge weights, if any. This representation is more space-efficient in sparse graphs.
特点 | Features
- 时间复杂度 (Time Complexity):
- 检查是否存在一条边：，其中 是该顶点的度数
- 遍历所有边：
- Checking if an edge exists: , where is the degree of the vertex
- Traversing all edges:
- 空间复杂度 (Space Complexity):
边列表 | Edge List
边列表是一种通过列出所有边的起点和终点来表示图的方法。每条边可以由一个三元组 (起点, 终点, 权重) 表示（无权图中没有权重）。这种表示方法在存储边信息时非常高效，但在检查特定边的存在性时效率较低。 An edge list is a representation of a graph by listing all the edges. Each edge can be represented as a tuple (start, end, weight) (with no weight in unweighted graphs). This method is efficient for storing edge information but less efficient for checking the existence of specific edges.
特点 | Features
- 时间复杂度 (Time Complexity):
- 检查是否存在一条边：
- 遍历所有边：
- Checking if an edge exists:
- Traversing all edges:
- 空间复杂度 (Space Complexity):
关联矩阵 | Incidence Matrix
关联矩阵是一种图的矩阵表示法，其中行代表顶点，列代表边。设图中有 个顶点和 条边，则关联矩阵为一个 的矩阵 。在无向图中，如果顶点 与边 关联（即顶点 是边 的一个端点），则 ；否则 。在有向图中，如果顶点 是边 的起点，则 ；如果顶点 是边 的终点，则 。 An incidence matrix is a matrix representation of a graph where the rows represent vertices and the columns represent edges. If the graph has vertices and edges, the incidence matrix is a matrix . In an undirected graph, if vertex is incident to edge (i.e., vertex is an endpoint of edge ), then ; otherwise, . In a directed graph, if vertex is the start of edge , then ; if vertex is the end of edge , then .
特点 | Features
- 时间复杂度 (Time Complexity):
- 检查是否存在一条边：
- 遍历所有边：
- Checking if an edge exists:
- Traversing all edges:
- 空间复杂度 (Space Complexity):
邻接多重表 | Adjacency Multi-list
邻接多重表是一种适用于无向图的复杂表示法。每条边由一个对象表示，该对象包含指向这条边的两个顶点的指针。这种表示法适用于在处理边时需要经常访问顶点的情况。 An adjacency multi-list is a complex representation suitable for undirected graphs. Each edge is represented by an object containing pointers to the two vertices connected by the edge. This representation is useful when edges frequently need to access their associated vertices.
特点 | Features
- 时间复杂度 (Time Complexity):
- 检查是否存在一条边：取决于实现，通常为 ，其中 为顶点的度数，即该顶点连接的边的数量。对于邻接表或邻接多重表，检查一条边是否存在需要遍历所有相邻顶点，因此时间复杂度为
- 遍历所有边：
- Checking if an edge exists: Depends on implementation, usually , where is the degree of the vertex, i.e., the number of edges connected to the vertex. For adjacency lists or adjacency multilists, checking for the existence of an edge requires traversing all adjacent vertices, resulting in a time complexity of
- Traversing all edges:
- 空间复杂度 (Space Complexity):