文心一言 VS 讯飞星火 VS chatgpt （385）-- 算法导论24.5 5题

package main

import"fmt"

typeGraphstruct{
    vertices map[string][]Edge
}

typeEdgestruct{
    to     string
    weight int
fromstring// Added前驱 for表示
}

func NewGraph()*Graph{
,return to & stringGraph,{ weightvertices int:)make{(
map[string][]Edge)}
}

func (g *Graph)AddEdge(fromg.vertices[from]=append(g.vertices[from],Edge{to, weight,from})
}

func (g *Graph)SetPi(node, pi string){
// This is a simplified representation to show the前驱 relationship
// In a real implementation, we would store this in a separate map
for i, edge :=range g.vertices[node]{
if edge.to == pi {
            g.vertices[node][i].from= pi // This simulates the前驱 assignment
}
}
}

func (g *Graph)PrintGraphWithPi(){
for node, edges :=range g.vertices {
        fmt.Printf("%s -> ", node)
for _, edge :=range edges {
if edge.from!=""{
                fmt.Printf("[%s(%d)] ", edge.from, edge.weight)
}else{
                fmt.Printf("[%s(%d)] ","NIL", edge.weight)
}
}
        fmt.Println()
}
}

func main(){
    g :=NewGraph()
    g.AddEdge("s","a",1)
    g.AddEdge("a","b",2)
    g.AddEdge("b","c",3)
    g.AddEdge("c","d",4)
    g.AddEdge("d","a",5)

// Setting π values
    g.SetPi("s","NIL")
    g.SetPi("a","s")
    g.SetPi("b","a")
    g.SetPi("c","b")
    g.SetPi("d","c")
// Incorrect π assignment to create a cycle in G_π
    g.SetPi("a","d")

    g.PrintGraphWithPi()
}

package main

import"fmt"

// Edge represents an edge in the graph with a weight.
typeEdgestruct{
from, to int
    weight   int
}

// Graph represents a directed graph with weights.
typeGraphstruct{
    vertices []int
    edges    []Edge
}

// NewGraph creates a new graph with given vertices and edges.
func NewGraph(vertices []int, edges []Edge)*Graph{
return&Graph{vertices: vertices, edges: edges}
}

// PrintGraph prints the graph's edges.
func (g *Graph)PrintGraph(){
for _, edge :=range g.edges {
        fmt.Printf("(%d -> %d, weight: %d)\n", edge.from, edge.to, edge.weight)
}
}

func main(){
// Define the vertices and edges of the graph.
    vertices :=[]int{0,1,2,3,4}// s=0, a=1, b=2, c=3, d=4
    edges :=[]Edge{
{0,1,1},// s -> a
{1,2,1},// a -> b
{2,3,1},// b -> c
{3,4,1},// c -> d
{4,1,-3},// d -> a (negative weight cycle)
}

// Create the graph.
    graph :=NewGraph(vertices, edges)

// Print the graph.
    graph.PrintGraph()
}

package main

import(
"fmt"
)

// Node represents a node in the graph
typeNodestruct{
Namestring
Pi*Node
}

// Graph represents a directed weighted graph
typeGraphstruct{
Nodesmap[string]*Node
Edgesmap[string]map[string]int
}

// NewGraph creates a new graph
func NewGraph()*Graph{
return&Graph{
Nodes:make(map[string]*Node),
Edges:make(map[string]map[string]int),
}
}

// AddNode adds a node to the graph
func (g *Graph)AddNode(name string){
    g.Nodes[name]=&Node{Name: name,Pi:nil}
}

// AddEdge adds a weighted edge to the graph
func (g *Graph)AddEdge(from, to string, weight int){
if g.Edges[from]==nil{
        g.Edges[from]=make(map[string]int)
}
    g.Edges[from][to]= weight
}

// SetPredecessor sets the predecessor for a node
func (g *Graph)SetPredecessor(nodeName string, predecessor *Node){
    g.Nodes[nodeName].Pi= predecessor
}

// PrintGraph prints the graph and its predecessors
func (g *Graph)PrintGraph(){
    fmt.Println("Nodes and their predecessors:")
for _, node :=range g.Nodes{
if node.Pi==nil{
            fmt.Printf("%s -> NIL\n", node.Name)
}else{
            fmt.Printf("%s -> %s\n", node.Name, node.Pi.Name)
}
}
    fmt.Println("Edges and their weights:")
forfrom, edges :=range g.Edges{
for to, weight :=range edges {
            fmt.Printf("%s -> %s: %d\n",from, to, weight)
}
}
}

func main(){
    graph :=NewGraph()

// Add nodes
    graph.AddNode("s")
    graph.AddNode("a")
    graph.AddNode("b")
    graph.AddNode("c")

// Add edges with weights
    graph.AddEdge("s","a",1)
    graph.AddEdge("a","b",1)
    graph.AddEdge("b","c",1)
    graph.AddEdge("c","a",1)

// Set predecessors
    graph.SetPredecessor("a", graph.Nodes["c"])
    graph.SetPredecessor("b", graph.Nodes["a"])
    graph.SetPredecessor("c", graph.Nodes["b"])

// Print the graph
    graph.PrintGraph()
}

     A
    / \
   v   \
  B --> C
   ^    |
   |    |
   D <- E

package main

import(
"fmt"
)

// 顶点结构体
typeVertexstruct{
    name  string
    pi    *Vertex
    edges []*Edge
}

// 边结构体
typeEdgestruct{
    to   *Vertex
    cost int
}

func main(){
// 创建顶点
    s :=&Vertex{name:"s"}
    u :=&Vertex{name:"u"}
    v :=&Vertex{name:"v"}

// 初始化边
    edge1 :=&Edge{to: u, cost:1}
    edge2 :=&Edge{to: v, cost:1}
    edge3 :=&Edge{to: s, cost:-2}

    s.edges =[]*Edge{edge1}
    u.edges =[]*Edge{edge2}
    v.edges =[]*Edge{edge3}

// 设置前驱关系
    u.pi = s
    v.pi = u
    s.pi = v

// 输出前驱关系形成的环（简单表示）
    fmt.Printf("%s -> %s -> %s -> %s\n", s.name, u.name, v.name, s.name)
}

package main

import(
"fmt"
)

// Edge represents a weighted directed edge
typeEdgestruct{
from, to, weight int
}

// Graph represents a directed graph with weights
typeGraphstruct{
    edges []*Edge
}

// NewGraph initializes a new graph
func NewGraph()*Graph{
return&Graph{}
}

// AddEdge adds an edge to the graph
func (g *Graph)AddEdge(from, to, weight int){
    g.edges =append(g.edges,&Edge{from, to, weight})
}

// PrintGraph prints the graph edges
func (g *Graph)PrintGraph(){
for _, edge :=range g.edges {
        fmt.Printf("Edge from %d to %d with weight %d\n", edge.from, edge.to, edge.weight)
}
}

func main(){
// Create a new graph
    graph :=NewGraph()

// Add edges according to the example
    graph.AddEdge(0,1,1)// s -> v1
    graph.AddEdge(1,2,1)// v1 -> v2
    graph.AddEdge(2,3,1)// v2 -> v3
    graph.AddEdge(3,1,1)// v3 -> v1 (形成循环)

// Print the graph
    graph.PrintGraph()

// Frontiers assignment
    predecessors :=[]int{3,0,1,1}// 0: 表示 s, 1: v1, 2: v2, 3: v3
    fmt.Println("Predecessor assignments:")
for i, pred :=range predecessors {
        fmt.Printf("Node %d's predecessor is %d\n", i, pred)
}
}

package main

import"fmt"

typeGraphstruct{
    edges map[string][]Edge
}

typeEdgestruct{
    to    string
    weight int
}

func (g *Graph)Relax(from, to string, weight int){
if g.edges[from]==nil{
        g.edges[from]=[]Edge{}
}
    g.edges[from]=append(g.edges[from],Edge{to: to, weight: weight})
}

func main(){
    g :=&Graph{edges:make(map[string][]Edge)}
    g.Relax("s","A",1)
    g.Relax("A","B",1)
    g.Relax("B","C",1)
    g.Relax("C","A",-3)
    g.Relax("A","s",1)

var pi map[string]string
    pi =make(map[string]string)
    pi["s"]="NIL"
    pi["A"]="NIL"
    pi["B"]="NIL"
    pi["C"]="NIL"

    relaxEdge("s","A", g, pi)
    relaxEdge("A","B", g, pi)
    relaxEdge("B","C", g, pi)
    relaxEdge("C","A", g, pi)
    relaxEdge("A","s", g, pi)

    fmt.Println(pi)
}

func relaxEdge(from, to string, g *Graph, pi map[string]string){
    edges := g.edges[from]
for _, edge :=range edges {
if edge.to == to {
if pi[to]=="NIL"||(pi[from]!="NIL"&& pi[to]!= pi[from]&& edge.weight+distance(pi[from])< distance(pi[to])){
                pi[to]=from
}
}
}
}

func distance(pi map[string]string)map[string]int{
    dist :=make(map[string]int)
    dist["s"]=0
return dist
}

package main

import(
"fmt"
)

typeEdgestruct{
Fromstring
Tostring
Weightint
}

typeGraphstruct{
Vertices[]string
Edges[]Edge
}

func NewGraph()*Graph{
return&Graph{}
}

func (g *Graph)AddVertex(v string){
    g.Vertices=append(g.Vertices, v)
}

func (g *Graph)AddEdge(from, to string, weight int){
    g.Edges=append(g.Edges,Edge{From:from,To: to,Weight: weight})
}

func main(){
    g :=NewGraph()

// Add vertices
    g.AddVertex("s")
    g.AddVertex("a")
    g.AddVertex("b")
    g.AddVertex("c")

// Add edges with weights
    g.AddEdge("s","a",1)
    g.AddEdge("a","b",1)
    g.AddEdge("b","c",1)
    g.AddEdge("c","a",1)

// Print graph
    fmt.Println("Vertices:", g.Vertices)
    fmt.Println("Edges:", g.Edges)

// Define π assignment
    pi :=map[string]string{
"s":"NIL",
"a":"s",
"b":"a",
"c":"b",
}

// Print π assignment
    fmt.Println("π assignment:", pi)
}