创建图的算法及生成最小生成树用高级语言编程实现

创建图的算法有很多种，其中最常用的是邻接矩阵、邻接表以及一些特殊用途的数据结构如有向无环图(DAG)中的拓扑排序算法。生成最小生成树的问题通常涉及到Prim算法或Kruskal算法。

**Prim算法**：
这是一个贪心算法，从一个顶点开始，逐步添加边，每次选择当前未加入集合的节点中到已形成集合的节点距离最近的那个节点。以下是用Python实现的一个基本版本：

import heapq

def prim(graph, start):
    mst = [(0, start)]
    visited = set()
    
    while mst:
        weight, vertex = heapq.heappop(mst)
        if vertex not in visited:
            visited.add(vertex)
            for neighbor, edge_weight in graph[vertex].items():
                if neighbor not in visited:
                    heapq.heappush(mst, (edge_weight, neighbor))
                    
    return visited, mst

# 示例：假设graph是一个字典，键是顶点，值是邻接字典，存储相邻顶点及其权重
graph = {1: {2: 4, 3: 5}, 2: {1: 4, 3: 1}, 3: {1: 5, 2: 1}}
start_node = 1
min_mst, tree_edges = prim(graph, start_node)

**Kruskal算法**：
这个算法则是通过将边按权重从小到大排序，然后依次添加边，如果新添加的边不会形成环，则加入最小生成树。这里同样可以用Python实现：

def kruskal(graph):
    edges = sorted(graph.items(), key=lambda x: x[1])
    mst = []
    visited = set()

    for edge in edges:
        u, v, weight = edge
        if u not in visited and v not in visited:
            mst.append(edge)
            visited.update({u, v})

    return mst

# 使用类似graph字典表示的图
kruskal_tree = kruskal(graph)