给出一个连通的无向图 G, G 中边的权仅在 1, 2, 3 中随机取值。试设计一个贪心算法，使得在线性时间内 可以生成最小生成树。给出伪代码并分析时间复杂度

这道题可以使用Kruskal算法来解决，Kruskal算法的核心是将边按照权值从小到大排序，然后依次加入到最小生成树中，如果加入的边使得图出现环，则不加入该边。具体来说，可以按照以下步骤实现：

1.将边按照权值从小到大排序
2.依次遍历每条边，如果该边的两个端点不在同一个连通块中，则加入该边，并将这两个端点所在的连通块合并
3.重复步骤2，直到最小生成树中包含了n-1条边（n为图中节点数）

伪代码如下：

function Kruskal(G):
    E = G.edges.sorted_by_weight()  //按照权值从小到大排序
    T = new Graph()  //最小生成树
    for v in G.vertices:
        make_set(v)  //初始化，每个节点都是一个单独的连通块
    for e in E:
        if find_set(e.u) != find_set(e.v):  //如果两个节点不在同一个连通块中
            T.add_edge(e)  //加入该边
            union(e.u, e.v)  //合并两个连通块
        if len(T.edges) == G.vertices - 1:  //最小生成树已经包含了n-1条边
            break
    return T

时间复杂度为O(mlogm+n^2)，其中m为边数，n为节点数。排序边的时间复杂度为O(mlogm)，依次遍历每条边的时间复杂度为O(m)，每次合并两个连通块的时间复杂度为O(n)，因此总时间复杂度为O(mlogm+n^2)。