文心一言 VS 讯飞星火 VS chatgpt （343）-- 算法导论23.2 2题

标签：parent -- graph 最小 int VS 文心 key 顶点

二、假定我们用邻接矩阵来表示图 G = ( V , E ) G=(V,E) G=(V,E)。请给出Prim算法的一种简单实现，使其运行时间为 O ( V 2 ) O(V^2) O(V2)。如果要写代码，请用go语言。

文心一言：

Prim算法是一种用于计算加权无向图的最小生成树的贪心算法。当使用邻接矩阵来表示图时，算法的时间复杂度通常是 O ( V 2 ) O(V^2) O(V2)，因为我们需要检查所有可能的边来构建最小生成树。下面是用Go语言实现的Prim算法的一个简单版本：

package main

import (
	"fmt"
	"math"
)

// Graph represents a graph using an adjacency matrix
type Graph struct {
	vertices int
	matrix   [][]float64
	inMST    []bool // Marks vertices that are already in the MST
}

// NewGraph creates a new graph with the given number of vertices
func NewGraph(vertices int) *Graph {
	return &Graph{
		vertices: vertices,
		matrix:   make([][]float64, vertices),
		inMST:    make([]bool, vertices),
	}
}

// AddEdge adds an edge with the given weight between the vertices u and v
func (g *Graph) AddEdge(u, v, weight float64) {
	g.matrix[u] = append(g.matrix[u], make([]float64, g.vertices)...)
	g.matrix[v] = append(g.matrix[v], make([]float64, g.vertices)...)
	g.matrix[u][v] = weight
	g.matrix[v][u] = weight
}

// Prim finds and prints the minimum spanning tree (MST) using Prim's algorithm
func (g *Graph) Prim(startVertex int) {
	// Initialize key values for all vertices
	keys := make([]float64, g.vertices)
	for i := range keys {
		keys[i] = math.Inf(1)
	}
	keys[startVertex] = 0
	parent := make([]int, g.vertices)

	for i := 0; i < g.vertices; i++ {
		// Find the vertex with the minimum key that is not in MST
		u := -1
		minKey := math.Inf(1)
		for v := 0; v < g.vertices; v++ {
			if !g.inMST[v] && keys[v] < minKey {
				u = v
				minKey = keys[v]
			}
		}

		// Add the vertex to MST
		g.inMST[u] = true
		fmt.Printf("(%d is added to MST)\n", u)

		// Update key values of adjacent vertices
		for v := 0; v < g.vertices; v++ {
			if g.matrix[u][v] > 0 && !g.inMST[v] && g.matrix[u][v] < keys[v] {
				parent[v] = u
				keys[v] = g.matrix[u][v]
			}
		}
	}

	// Optionally, print the MST edges
	for i := 1; i < g.vertices; i++ {
		fmt.Printf("(%d - %d) - %f\n", parent[i], i, g.matrix[parent[i]][i])
	}
}

func main() {
	g := NewGraph(5)
	g.AddEdge(0, 1, 10)
	g.AddEdge(0, 3, 6)
	g.AddEdge(0, 4, 5)
	g.AddEdge(1, 2, 15)
	g.AddEdge(1, 3, 4)
	g.AddEdge(2, 3, 14)
	g.AddEdge(3, 4, 2)

	g.Prim(0)
}

注意：

此实现中，AddEdge函数为了简化实现，总是假设图是完全图（即每个顶点与其他所有顶点都可能有边），即使在实际中图可能不是完全图。这可能导致内存浪费，但简化了代码。
在Prim函数中，我们初始化了一个keys数组来存储每个顶点到MST中的最小边的权重（也称为键）。开始时，除了起始顶点外，所有顶点的键都设置为无穷大。
我们遍历所有顶点，找到不在MST中但键值最小的顶点，将其加入MST，并更新其相邻顶点的键值（如果找到更小的边）。
最后，我们可以选择打印MST的边。

在这里插入图片描述

讯飞星火：

Prim算法是一种用于求解最小生成树的贪心算法。以下是使用Go语言实现的Prim算法，时间复杂度为O(V^2)：

package main

import (
	"fmt"
	"math"
)

const inf = math.MaxInt32

func prim(graph [][]int, n int) int {
	visited := make([]bool, n)
	minDist := make([]int, n)
	for i := range minDist {
		minDist[i] = inf
	}
	minDist[0] = 0
	totalWeight := 0

	for i := 0; i < n; i++ {
		u := -1
		for v := 0; v < n; v++ {
			if !visited[v] && (u == -1 || minDist[v] < minDist[u]) {
				u = v
			}
		}
		if u == -1 {
			break
		}
		visited[u] = true
		totalWeight += minDist[u]

		for v := 0; v < n; v++ {
			if graph[u][v] != 0 && !visited[v] && graph[u][v] < minDist[v] {
				minDist[v] = graph[u][v]
			}
		}
	}
	return totalWeight
}

func main() {
	graph := [][]int{
		{0, 9, 75, 0, 0},
		{9, 0, 95, 19, 42},
		{75, 95, 0, 51, 66},
		{0, 19, 51, 0, 31},
		{0, 42, 66, 31, 0},
	}
	n := len(graph)
	result := prim(graph, n)
	fmt.Println("Minimum weight of the spanning tree:", result)
}

这段代码首先定义了一个prim函数，它接受一个邻接矩阵graph和顶点数n作为输入。然后，它使用一个布尔数组visited来跟踪已访问的顶点，以及一个整数数组minDist来存储从起始顶点到每个顶点的最小距离。接下来，它遍历所有顶点，找到未访问的具有最小距离的顶点，并将其标记为已访问。最后，它更新与该顶点相邻的顶点的最小距离。这个过程重复直到所有顶点都被访问。最后，返回最小生成树的总权重。

360智脑：

Prim算法是一种用于在加权无向图中寻找最小生成树的算法。以下是使用Go语言实现的Prim算法的简单版本，其运行时间为 O ( V 2 ) O(V^2) O(V2)，其中 V V V是图中顶点的数量。

package main

import "fmt"

// 定义一个函数来实现Prim算法
func prim(graph [][]int) {
    V := len(graph) // 获取顶点数
    inMST := make([]bool, V) // 记录顶点是否已经在MST中
    key := make([]int, V) // 存储每个顶点到MST的最小权重
    parent := make([]int, V) // 存储MST的父节点

    // 初始化key为无穷大，除了第一个顶点
    for i := 0; i < V; i++ {
        key[i] = int(^uint(0) >> 1) // 使用最大整数值表示无穷大
    }
    key[0] = 0 // 从第一个顶点开始
    parent[0] = -1 // 第一个顶点没有父节点

    // 将V个顶点加入MST
    for count := 0; count < V-1; count++ {
        minKey := int(^uint(0) >> 1) // 初始化最小key为无穷大
        u := -1 // 初始化u为未选择

        // 找到不在MST中且key值最小的顶点
        for v := 0; v < V; v++ {
            if !inMST[v] && key[v] < minKey {
                minKey = key[v]
                u = v
            }
        }

        // 标记u为已在MST中
        inMST[u] = true

        // 更新相邻顶点的key值和parent
        for v := 0; v < V; v++ {
            if graph[u][v] != 0 && !inMST[v] && graph[u][v] < key[v] {
                key[v] = graph[u][v]
                parent[v] = u
            }
        }
    }

    // 打印MST
    fmt.Println("Edge \tWeight")
    for i := 1; i < V; i++ {
        fmt.Printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]])
    }
}

func main() {
    // 示例图的邻接矩阵
    graph := [][]int{
        {0, 2, 0, 6, 0},
        {2, 0, 3, 8, 5},
        {0, 3, 0, 0, 7},
        {6, 8, 0, 0, 9},
        {0, 5, 7, 9, 0},
    }

    prim(graph)
}

在这个实现中，我们首先初始化所有顶点的key值为无穷大，除了起始顶点。然后，我们迭代V-1次，每次选择一个不在MST中的顶点，该顶点具有与MST相连的最小权重边。我们将这个顶点添加到MST中，并更新其相邻顶点的key值和parent指针。最后，我们打印出构成最小生成树的所有边及其权重。

请注意，这个实现假设输入的邻接矩阵是非负的，并且不包含自环（即对角线上的元素为0）。如果图可能包含负权重边，那么需要对算法进行适当的修改。此外，这个实现的时间复杂度为 O ( V 2 ) O(V^2) O(V2)，适用于稠密图。对于稀疏图，可以使用优先队列（如二叉堆或斐波那契堆）来优化Prim算法，使其时间复杂度达到 O ( E + V log ⁡ V ) O(E + V \log V) O(E+VlogV)，其中 E E E是边的数量。

智谱清言：

Prim算法是一种用于求解加权无向图的最小生成树的贪心算法。下面是使用Go语言实现Prim算法的一个简单版本，该实现的时间复杂度为 O ( V 2 ) O(V^2) O(V2)，其中 V V V是顶点的数量。

package main
import (
	"fmt"
	"math"
)
func primAlgorithm(graph [][]int, startVertex int) (int, []int) {
	V := len(graph)
	selected := make([]bool, V)
	selected[startVertex] = true
	selectedVertices := []int{startVertex}
	minWeight := 0
	for len(selectedVertices) < V {
		minEdgeWeight := math.MaxInt64
		from := -1
		to := -1
		for _, u := range selectedVertices {
			for v := 0; v < V; v++ {
				if !selected[v] && graph[u][v] > 0 && graph[u][v] < minEdgeWeight {
					minEdgeWeight = graph[u][v]
					from = u
					to = v
				}
			}
		}
		if from != -1 && to != -1 {
			selected[to] = true
			selectedVertices = append(selectedVertices, to)
			minWeight += minEdgeWeight
			fmt.Printf("Edge from %d to %d with weight %d\n", from, to, minEdgeWeight)
		}
	}
	return minWeight, selectedVertices
}
func main() {
	// Example graph represented as an adjacency matrix
	graph := [][]int{
		{0, 3, 0, 2, 0, 0, 0},
		{3, 0, 4, 0, 0, 0, 0},
		{0, 4, 0, 5, 0, 0, 0},
		{2, 0, 5, 0, 10, 0, 0},
		{0, 0, 0, 10, 0, 6, 0},
		{0, 0, 0, 0, 6, 0, 1},
		{0, 0, 0, 0, 0, 1, 0},
	}
	startVertex := 0
	minWeight, selectedVertices := primAlgorithm(graph, startVertex)
	fmt.Printf("Minimum weight of the spanning tree: %d\n", minWeight)
	fmt.Println("Selected vertices in the spanning tree:", selectedVertices)
}

在这个实现中，我们使用了一个二维数组graph来表示图的邻接矩阵，其中graph[i][j]表示顶点i和顶点j之间的边的权重。如果两个顶点之间没有直接连接，则对应的值为0。selected数组用于跟踪哪些顶点已经被添加到最小生成树中。我们从指定的起始顶点开始，每次迭代选择连接已选顶点和未选顶点之间权重最小的边，并将新顶点添加到最小生成树中。
请注意，这个实现没有使用优先队列来优化算法，因此它的时间复杂度是 O ( V 2 ) O(V^2) O(V2)。如果使用优先队列，可以进一步优化Prim算法的时间复杂度到 O ( E log ⁡ V ) O(E \log V) O(ElogV)，其中 E E E是边的数量。

天工：

Prim算法的Go语言实现

为了实现Prim算法以 O ( V 2 ) O(V^2) O(V2)的时间复杂度找到最小生成树，我们可以采用以下步骤：

初始化一个最小生成树的边集合。
选择一个顶点开始，将它加入到当前的树中。
每次从剩下的顶点中选择一个与当前树中顶点相连且权重最小的边，将对应的顶点加入树中。
重复步骤3，直到所有的顶点都被加入到树中。

下面是使用邻接矩阵表示图的Go语言代码实现：

package main

import (
	"fmt"
	"math"
)

// 图的顶点数
const V = 5

// 边的权重
type EdgeWeight struct {
	v   int
	weight int
}

// 辅助函数，用于获取最小权重的边
func getMinKey(key []int, mstSet []bool) int {
	min := math.MaxInt32
	minIndex := -1

	for v := 0; v < V; v++ {
		if mstSet[v] == false && key[v] < min {
			min = key[v]
			minIndex = v
		}
	}
	return minIndex
}

// Prim算法实现
func primMST(graph [][]int) {
	key := make([]int, V)
	parent := make([]int, V)
	mstSet := make([]bool, V)

	for i := 0; i < V; i++ {
		key[i] = math.MaxInt32
		mstSet[i] = false
	}
	key[0] = 0
	parent[0] = -1

	for count := 0; count < V-1; count++ {
		u := getMinKey(key, mstSet)
		mstSet[u] = true

		for v := 0; v < V; v++ {
			if graph[u][v] > 0 && mstSet[v] == false && graph[u][v] < key[v] {
				parent[v] = u
				key[v] = graph[u][v]
			}
		}
	}

	// 打印最小生成树的边和权重
	for i := 1; i < V; i++ {
		fmt.Printf("%d - %d: %d\n", parent[i], i, graph[i][parent[i]])
	}
}

func main() {
	// 邻接矩阵表示
	graph := [][]int{
		{0, 2, 0, 6, 0},
		{2, 0, 3, 8, 5},
		{0, 3, 0, 0, 7},
		{6, 8, 0, 0, 9},
		{0, 5, 7, 9, 0},
	}

	primMST(graph)
}

这段代码首先初始化了所有必要的数据结构，然后通过Prim算法构建最小生成树，并最终打印出最小生成树的每条边及其权重。

chatgpt：

下面是用 Go 语言实现的 Prim 算法，该算法使用邻接矩阵表示图，运行时间为 ( O(V^2) )。

Prim 算法的简单实现

使用邻接矩阵表示图的 Prim 算法可以用一个简单的实现，主要思路是用一个数组 key 来跟踪每个顶点的最小边权值，同时用一个布尔数组 inMST 来标记已经加入最小生成树的顶点。

Go 语言代码

package main

import (
    "fmt"
    "math"
)

const INF = math.MaxInt32 // 表示无穷大的常量

func prim(graph [][]int) {
    V := len(graph)
    key := make([]int, V)          // 各顶点的最小权重
    parent := make([]int, V)       // 记录每个顶点的父顶点
    inMST := make([]bool, V)       // 顶点是否在最小生成树中

    // 初始化所有key为无穷大，parent为-1，inMST为false
    for i := 0; i < V; i++ {
        key[i] = INF
        parent[i] = -1
        inMST[i] = false
    }

    // 从第一个顶点开始
    key[0] = 0 // 使得第一个顶点被选中
    parent[0] = -1

    for count := 0; count < V-1; count++ {
        u := minKey(key, inMST, V)
        inMST[u] = true // 将u加入生成树

        // 更新key和parent数组
        for v := 0; v < V; v++ {
            // 如果graph[u][v]存在，且v未在树中，且权重小于key[v]
            if graph[u][v] != 0 && !inMST[v] && graph[u][v] < key[v] {
                key[v] = graph[u][v]
                parent[v] = u
            }
        }
    }

    // 输出生成树的边
    printMST(parent, graph)
}

// 辅助函数：找到当前键值最小且未被选中的顶点
func minKey(key []int, inMST []bool, V int) int {
    min := INF
    minIndex := -1

    for v := 0; v < V; v++ {
        if key[v] < min && !inMST[v] {
            min = key[v]
            minIndex = v
        }
    }

    return minIndex
}

// 输出最小生成树的边
func printMST(parent []int, graph [][]int) {
    fmt.Println("边 \t 权重")
    for i := 1; i < len(parent); i++ {
        fmt.Printf("%d - %d \t %d\n", parent[i], i, graph[parent[i]][i])
    }
}

func main() {
    // 创建邻接矩阵表示图
    graph := [][]int{
        {0, 2, 0, 6, 0},
        {2, 0, 3, 8, 5},
        {0, 3, 0, 0, 7},
        {6, 8, 0, 0, 9},
        {0, 5, 7, 9, 0},
    }

    prim(graph) // 调用Prim算法
}

代码说明

邻接矩阵：用二维切片 graph 表示图，graph[i][j] 表示顶点 i 到 j 的边的权重，若不存在则为0。
初始化：初始化 key 数组为无穷大，parent 数组为 -1，inMST 数组为 false。
选择顶点：通过 minKey 函数找到当前未在生成树中、具有最小键值的顶点。
更新键值和父顶点：在每次选择后更新与当前顶点相连的其他顶点的键值和父顶点记录。
输出结果：最后输出生成树的边和权重。

运行时间

该实现的运行时间为 ( O(V^2) )，适合中小规模的图，因为它使用了简单的数组形式来处理优先队列的功能。

kimi：

Prim算法是一种用于在加权无向图中找到最小生成树的算法。在用邻接矩阵表示的图中，Prim算法可以通过以下步骤实现：

初始化：选择一个起始顶点，将其加入最小生成树的集合中。
循环：在每次迭代中，找到与最小生成树集合连接的边中权重最小的边，并将这条边的另一端顶点加入到最小生成树集合中。
重复：直到所有顶点都被加入到最小生成树集合中。

为了使算法的运行时间为 O ( V 2 ) O(V^2) O(V2)，我们可以使用一个简单的数组来跟踪每个顶点是否已经被加入到最小生成树集合中，以及一个数组来存储每个顶点到最小生成树集合的最小边的权重。

以下是使用Go语言实现的Prim算法的代码示例：

package main

import "fmt"

// 定义图的结构
type Graph struct {
	V   int     // 顶点的数量
	adj [][]int // 邻接矩阵
}

// Prim算法实现
func Prim(graph *Graph) []int {
	V := graph.V
	minEdge := make([]int, V) // 存储到最小生成树集合的最小边的权重
	key := make([]int, V)     // 存储每个顶点到最小生成树集合的最小权重
	mstSet := make([]bool, V)  // 标记顶点是否已经在最小生成树集合中
	parent := make([]int, V)   // 存储最小生成树的父节点

	for i := range key {
		key[i] = 1 << 32 // 初始化为一个很大的数
	}
	key[0] = 0 // 从顶点0开始构建最小生成树
	minEdge[0] = 0

	for count := 0; count < V-1; count++ {
		// 找到未加入最小生成树集合中权重最小的顶点
		min := 1<<32 - 1
		u := -1
		for v := 0; v < V; v++ {
			if !mstSet[v] && key[v] < min {
				min = key[v]
				u = v
			}
		}

		mstSet[u] = true // 将顶点u加入最小生成树集合

		// 更新与顶点u相连的顶点的权重
		for v := 0; v < V; v++ {
			if graph.adj[u][v] != 0 && !mstSet[v] && graph.adj[u][v] < key[v] {
				parent[v] = u
				key[v] = graph.adj[u][v]
				minEdge[v] = graph.adj[u][v]
			}
		}
	}

	// 打印构建的最小生成树
	fmt.Println("Edge   Weight")
	for i := 1; i < V; i++ {
		fmt.Printf("%d - %d    %d \n", parent[i], i, minEdge[i])
	}
	return parent
}

func main() {
	// 示例图的邻接矩阵
	adjMatrix := [][]int{
		{0, 2, 0, 6, 0},
		{2, 0, 3, 8, 5},
		{0, 3, 0, 0, 7},
		{6, 8, 0, 0, 9},
		{0, 5, 7, 9, 0},
	}
	g := Graph{5, adjMatrix}
	Prim(&g)
}

在这个实现中，我们使用了一个简单的数组来跟踪每个顶点是否已经被加入到最小生成树集合中，以及一个数组来存储每个顶点到最小生成树集合的最小边的权重。这个实现的时间复杂度是 O ( V 2 ) O(V^2) O(V2)，因为每次循环中我们都需要遍历所有的顶点来找到最小边。

混元：

Prim算法是一种贪心算法，用于找到无向图的最小生成树。在邻接矩阵表示的图中，Prim算法的时间复杂度可以通过使用一个优先队列（或者简单的数组）来优化到 O ( V 2 ) O(V^2) O(V2)。

以下是Go语言实现的Prim算法，它使用了邻接矩阵来表示图，并且时间复杂度为 O ( V 2 ) O(V^2) O(V2)：

package main

import (
	"fmt"
)

// 定义无穷大的常量
const INF = 1 << 30

// prim函数实现了Prim算法
func prim(graph [][]int) []int {
	n := len(graph) // 图中顶点的数量
	key := make([]int, n) // 存储每个顶点到最小生成树的最短距离
	mstSet := make([]bool, n) // 标记每个顶点是否已经包含在最小生成树中
	parent := make([]int, n) // 存储最小生成树中每个顶点的父节点

	// 初始化key数组为无穷大，除了第一个顶点为0
	for i := range key {
		key[i] = INF
	}
	key[0] = 0

	// 找到最小生成树
	for count := 0; count < n; count++ {
		// 选取key值最小的顶点u
		u := -1
		for i := 0; i < n; i++ {
			if !mstSet[i] && (u == -1 || key[i] < key[u]) {
				u = i
			}
		}

		// 将顶点u加入到最小生成树中
		mstSet[u] = true

		// 更新与u相邻的顶点的key值和parent值
		for v := 0; v < n; v++ {
			if graph[u][v] != 0 && !m8tSet[v] && graph[u][v] < key[v] {
				parent[v] = u
				key[v] = graph[u][v]
			}
		}
	}

	return parent
}

func main() {
	// 示例图的邻接矩阵表示
	graph := [][]int{
		{0, 2, 0, 6, 0},
		{2, 0, 3, 8, 5},
		{0, 3, 0, 0, 7},
		{6, 8, 0, 0, 9},
		{0, 5, 7, 9, 0},
	}

	parent := prim(graph)
	fmt.Println("Edge \tWeight")
	for i := 1; i < len(graph); i++ {
		fmt.Println(parent[i], "-", i, "\t", graph[i][parent[i]])
	}
}

在这个实现中，我们使用了一个数组key来存储每个顶点到最小生成树的最短距离，初始时除了起始顶点外，其他顶点的key值都设置为无穷大。我们还使用了一个布尔数组mstSet来标记每个顶点是否已经被加入到最小生成树中。parent数组用于记录最小生成树的结构。

算法的核心是一个循环，它会重复选择key值最小的顶点并将其加入到最小生成树中，然后更新与该顶点相邻的其他顶点的key值和parent值。这个过程会一直持续，直到所有顶点都被加入到最小生成树中。

注意：在实际应用中，如果图的边数远小于顶点数的平方，使用邻接表表示图并配合优先队列（如二叉堆）来实现Prim算法会更加高效。

标签：parent,--,graph,最小,int,VS,文心,key,顶点
From： https://blog.csdn.net/weixin_48502062/article/details/142062313