Minimum Spanning Trees对于无向图$𝐺=(𝑉,𝐸)$，存在一个能够连接所有顶点的无环子集$𝑇⊆𝐸$，由于 𝑇 无环且连接所有顶点，因此 𝑇 一定为一棵树(树是特殊的图，为无环连通图)，被称为生成树(spanning tree)。无向图$𝐺=(𝑉,𝐸)$的所有生成树都恰有$|𝑉|−1$条边。 设边$(𝑢,𝑣)∈𝐸$的权重为$𝑤(𝑢,𝑣)$，生成树权重为$𝑤(𝑇) = \sum_{(𝑢,𝑣)∈𝑇} 𝑤(𝑢,𝑣)$，所有生成树中权重最小的生成树被称为最小权重生成树(minimum-weight spanning tree)，简称最小生成树(minimum spanning tree)。 Growing a minimum spanning tree最小生成树问题的输入为一个无向连通图 $𝐺&#x ...

Elementary Graph AlgorithmsRepresentations of graphs$$G = (V, E)$$$G \to Graph, V \to Vertex, E \to Edge$, 式子说明图是由顶点和边这两个元素组成，那么只要把顶点和边表示出来，图就表示出来了。其中有两种方法，一种是邻接表表示，一种是用矩阵表示，根据不同的情景需要会选取不同的表示方法。 adjacency-list//邻接表可用链表，也可用哈希表 If $G$ is a directed graph, the sum of the lengths of all the adjacency lists is |E|.If $G$ is an undirected graph, the sum of the lengths of all the adjacenc ...