天天看點
傳回

文心一言 VS 訊飛星火 VS chatgpt （300）—— 算法導論22.1 4題

四、給定多圖$G=(V,E)$的鄰接連結清單(多圖是允許重複邊和自循環邊的圖)，請給出一個時間為$O(V+E)$的算法，用來計算該圖的“等價”無向圖$G^{'}=(V,E^{'})$的鄰接連結清單表示。這裡$E^{'}$是将$E$中的備援邊和自循環邊删除後餘下的邊。删除餘邊指的是将兩個結點之間的多條邊替換為一條邊。如果要寫代碼，請用go語言。

文心一言：

鄰接連結清單表示

在鄰接連結清單表示中，每個頂點 $v$ 都有一個連結清單，連結清單中的每個節點代表一條從 $v$ 出發的邊。為了計算 $G^T$，我們需要周遊 $G$ 的每條邊，并反轉邊的方向，添加到 $G^T$ 的相應連結清單中。

Go語言實作：

package main

import(
"fmt"
)

// Graph 使用鄰接連結清單表示
typeGraphstruct{
    vertices int
    adjList  map[int][]int
}

// NewGraph 建立一個新的圖
func NewGraph(vertices int)*Graph{
return&Graph{
        vertices: vertices,
        adjList:make(map[int][]int),
}
}

// AddEdge 添加一條邊到圖中
func (g *Graph)AddEdge(u, v int){
    g.adjList[u]=append(g.adjList[u], v)
}

// Transpose 計算圖的轉置
func (g *Graph)Transpose()*Graph{
    gT :=NewGraph(g.vertices)
for u, adj :=range g.adjList {
for _, v :=range adj {
            gT.AddEdge(v, u)// 反轉邊的方向
}
}
return gT
}

func main(){
    g :=NewGraph(4)
    g.AddEdge(0,1)
    g.AddEdge(0,2)
    g.AddEdge(1,2)
    g.AddEdge(2,0)
    g.AddEdge(2,3)

    gT := g.Transpose()

    fmt.Println("Original Graph:")
for u, adj :=range g.adjList {
        fmt.Printf("%d -> %v\n", u, adj)
}

    fmt.Println("\nTransposed Graph:")
for u, adj :=range gT.adjList {
        fmt.Printf("%d -> %v\n", u, adj)
}
}

時間複雜度：

  • • 周遊每條邊的時間複雜度是 $O(E)$，其中 $E$ 是邊的數量。
  • • 對于每條邊，我們執行常數時間的操作（添加到另一個圖的鄰接連結清單中）。
  • • 是以，總的時間複雜度是 $O(E)$。

鄰接矩陣表示

在鄰接矩陣表示中，我們使用一個二維數組來存儲邊的資訊，其中 matrix[u][v] 表示是否存在一條從 $u$ 到 $v$ 的邊。為了計算 $G^T$，我們周遊矩陣的上三角（或下三角，取決于你的矩陣表示習慣），并反轉邊的方向，即将 matrix[u][v] 的值賦給 matrixT[v][u]。

Go語言實作（簡化版，僅考慮存在性，不考慮邊的權重）：

// 假設使用二維布爾切片表示鄰接矩陣
typeGraphMatrix[][]bool

// Transpose 計算圖的轉置
func (g GraphMatrix)Transpose()GraphMatrix{
    n :=len(g)
    gT :=make(GraphMatrix, n)
for i :=range gT {
        gT[i]=make([]bool, n)
}

for i :=0; i < n; i++{
for j :=0; j < n; j++{
            gT[j][i]= g[i][j]// 反轉邊的方向
}
}
return gT
}

// 注意：這裡沒有完整的GraphMatrix類型實作，因為示例僅關注Transpose函數

時間複雜度：

  • • 周遊矩陣的每個元素需要 $O(V^2)$ 時間，其中 $V$ 是頂點的數量。
  • • 是以，總的時間複雜度是 $O(V^2)$。這在頂點數量遠大于邊數量時可能不是最高效的。
文心一言 VS 訊飛星火 VS chatgpt （300）—— 算法導論22.1 4題

在這裡插入圖檔描述

文心一言 VS 訊飛星火 VS chatgpt （300）—— 算法導論22.1 4題

在這裡插入圖檔描述

文心一言 VS 訊飛星火 VS chatgpt （300）—— 算法導論22.1 4題

在這裡插入圖檔描述

文心一言 VS 訊飛星火 VS chatgpt （300）—— 算法導論22.1 4題

在這裡插入圖檔描述

訊飛星火：

對于鄰接連結清單表示的有向圖，我們可以通過周遊每個頂點的鄰接連結清單，将每個頂點的鄰接頂點添加到新圖的轉置頂點的鄰接連結清單中。具體步驟如下：

  1. 1. 建立一個新的鄰接連結清單 $G^{T}$，初始化為空。
  2. 2. 周遊原圖 $G$ 的每個頂點 $v$。
  3. 3. 周遊頂點 $v$ 的鄰接連結清單，将每個鄰接頂點 $u$ 添加到新圖 $G^{T}$ 中頂點 $v$ 的鄰接連結清單中。
  4. 4. 傳回新圖 $G^{T}$。

時間複雜度分析：周遊原圖的每個頂點需要 $O(|V|)$ 的時間，周遊每個頂點的鄰接連結清單需要 $O(|E|)$ 的時間，是以總的時間複雜度為 $O(|V| + |E|)$。

對于鄰接矩陣表示的有向圖，我們可以通過将原圖的鄰接矩陣進行轉置操作來得到新圖的鄰接矩陣。具體步驟如下：

  1. 1. 建立一個新的大小為 $|V| \times |V|$ 的矩陣 $G^{T}$，初始化為全零矩陣。
  2. 2. 周遊原圖的鄰接矩陣 $G$，将 $G[i][j]$ 的值賦給 $G^{T}[j][i]$。
  3. 3. 傳回新圖的鄰接矩陣 $G^{T}$。

時間複雜度分析：周遊原圖的鄰接矩陣需要 $O(|V|^2)$ 的時間，是以總的時間複雜度為 $O(|V|^2)$。

下面是使用 Go 語言實作的代碼：

// 鄰接連結清單表示的有向圖轉置
func transposeAdjList(G map[int][]int)map[int][]int{
    GT :=make(map[int][]int)
for v, neighbors :=range G {
for _, u :=range neighbors {
            GT[u]=append(GT[u], v)
}
}
return GT
}

// 鄰接矩陣表示的有向圖轉置
func transposeAdjMatrix(G [][]int)[][]int{
    n :=len(G)
    GT :=make([][]int, n)
for i :=range GT {
        GT[i]=make([]int, n)
}
for i :=0; i < n; i++{
for j :=0; j < n; j++{
            GT[j][i]= G[i][j]
}
}
return GT
}

360智腦：

鄰接連結清單表示法

在鄰接連結清單表示法中，我們可以直接周遊原圖$G$的每個節點的鄰接連結清單，然後将每條邊的方向反轉後添加到新圖$G^{T}$的相應節點上。

Go語言代碼實作： 

type Graphstruct{
Vertices[]*Node// 存儲圖中所有節點的指針
}

typeNodestruct{
Valueint
Adjacent[]*Node// 存儲與該節點相鄰的所有節點的指針
}

func (g *Graph)Transpose()*Graph{
    transposed :=&Graph{make([]*Node,len(g.Vertices))}
for i, node :=range g.Vertices{
        transposed.Vertices[i]=&Node{node.Value,make([]*Node,0)}
}
for _, node :=range g.Vertices{
for _, adj :=range node.Adjacent{
// 将邊反向添加到轉置圖中
            transposed.Vertices[adj.Value].Adjacent=append(transposed.Vertices[adj.Value].Adjacent, transposed.Vertices[node.Value])
}
}
return transposed
}

時間複雜度分析：

  • • 周遊原圖中的每個節點：$O(|V|)$
  • • 周遊每個節點的鄰接連結清單：$O(|E|)$

是以，總的時間複雜度為 $O(|V| + |E|)$。

鄰接矩陣表示法

在鄰接矩陣表示法中，我們可以建立一個新的鄰接矩陣，然後周遊原圖$G$的鄰接矩陣，将矩陣中的每個元素$(i, j)$指派給新矩陣的$(j, i)$位置，這樣就完成了邊的反轉。

Go語言代碼實作： 

type MatrixGraphstruct{
Matrix[][]bool// 存儲鄰接矩陣
}

func (mg *MatrixGraph)Transpose()*MatrixGraph{
    transposed :=&MatrixGraph{make([][]bool,len(mg.Matrix))}
for i :=range mg.Matrix{
        transposed.Matrix[i]=make([]bool,len(mg.Matrix))
for j :=range mg.Matrix[i]{
// 将邊反向指派到轉置矩陣中
            transposed.Matrix[i][j]= mg.Matrix[j][i]
}
}
return transposed
}

時間複雜度分析：

  • • 建立新的鄰接矩陣：$O(|V|^2)$
  • • 周遊原圖的鄰接矩陣：$O(|V|^2)$

是以，總的時間複雜度為 $O(|V|^2)$。

總結

對于鄰接連結清單表示法，轉置算法的時間複雜度為 $O(|V| + |E|)$，而對于鄰接矩陣表示法，轉置算法的時間複雜度為 $O(|V|^2)$。在實際應用中，如果圖比較稀疏（即$|E|$遠小于$|V|^2$），使用鄰接連結清單表示法會更加高效。如果圖比較稠密（即$|E|$接近$|V|^2$），則鄰接矩陣表示法可能更加合适。

智譜清言：

在圖的表示中，鄰接連結清單和鄰接矩陣都是常用的方法。鄰接連結清單用于表示無向圖和有向圖，而鄰接矩陣通常用于表示無向圖。對于有向圖的轉置，我們可以分别對鄰接連結清單和鄰接矩陣進行操作。

鄰接連結清單的轉置

對于鄰接連結清單表示的有向圖，轉置圖可以通過周遊原圖的每個頂點，并将原圖的出邊修改為入邊來實作。

package main
import(
"fmt"
)
// 定義圖的頂點結構
typeVertexstruct{
Namestring
Edges[]*Vertex
Visitedbool
}
// 計算圖的轉置
func Transpose(g *Vertex){
for _, v :=range g.Edges{
// 周遊頂點v的所有出邊
for _, w :=range v.Edges{
// 在原圖中查找頂點w指向頂點v的邊，并反轉
for i, e :=range w.Edges{
if e == v {
                    w.Edges[i]= v
break
}
}
}
}
}
func main(){
// 建立頂點
    a :=&Vertex{Name:"A"}
    b :=&Vertex{Name:"B"}
    c :=&Vertex{Name:"C"}
// 建立有向圖關系
    a.Edges=[]*Vertex{b, c}
    b.Edges=[]*Vertex{a}
    c.Edges=[]*Vertex{a}
// 列印原圖
    fmt.Println("原圖：")
PrintGraph(a)
// 計算轉置圖
Transpose(a)
// 列印轉置圖
    fmt.Println("轉置圖：")
PrintGraph(a)
}
// PrintGraph 用于列印圖的鄰接連結清單表示
func PrintGraph(g *Vertex){
    g.Visited=true
for _, v :=range g.Edges{
if!v.Visited{
            fmt.Println(g.Name,"->", v.Name)
PrintGraph(v)
}
}
}

鄰接矩陣的轉置

對于鄰接矩陣表示的有向圖，轉置圖可以通過将原圖的每一行變成新圖的對應列來實作。

package main
import(
"fmt"
)
// 計算鄰接矩陣的轉置
func TransposeMatrix(mat [][]int)[][]int{
    transposed :=make([][]int,len(mat[0]))
for i :=range transposed {
        transposed[i]=make([]int,len(mat))
}
for i, row :=range mat {
for j, val :=range row {
if val ==1{
                transposed[j][i]=1
}
}
}
return transposed
}
func main(){
// 建立鄰接矩陣
    originalMatrix :=[][]int{
{0,1,1},
{0,0,1},
{1,0,0},
}
// 計算轉置矩陣
    transposedMatrix :=TransposeMatrix(originalMatrix)
// 列印轉置矩陣
    fmt.Println("轉置矩陣：")
for _, row :=range transposedMatrix {
        fmt.Println(row)
}
}

算法運作時間分析

  1. 1. 對于鄰接連結清單的轉置，算法的時間複雜度為O(E)，其中E是圖中邊的數量。這是因為需要周遊每條邊一次。
  2. 2. 對于鄰接矩陣的轉置，算法的時間複雜度為O(V^2)，其中V是圖中頂點的數量。這是因為需要周遊每個矩陣元素一次，而矩陣的大小為V×V。 這些算法都是有效的，并且運作

天工：

要實作一個算法來計算有向圖 $G$ 的轉置 $G^{T}$，我們可以分别對鄰接連結清單和鄰接矩陣兩種表示法進行處理。下面我将分别描述這兩種情況的算法，并提供Go語言的代碼示例。

鄰接連結清單表示法

算法步驟：

  1. 1. 建立一個新的鄰接連結清單 newAdjList 用于存儲轉置後的圖。
  2. 2. 周遊原圖的鄰接連結清單 adjList。
  3. 3. 對于每條邊 (u, v)，将其添加到 newAdjList[v] 中。
  4. 4. 傳回新的鄰接連結清單 newAdjList。

Go語言代碼示例： 

type Graphstruct{
    vertices []*Vertex
}

typeVertexstruct{
    key      int
    adjacent []*Vertex
}

func (g *Graph)Transpose()*Graph{
    gt :=&Graph{make([]*Vertex,len(g.vertices))}
for i :=range g.vertices {
        gt.vertices[i]=&Vertex{key: i}
}
for _, u :=range g.vertices {
for _, v :=range u.adjacent {
// Add edge (v, u) to the transpose graph.
            gt.vertices[v.key].adjacent =append(gt.vertices[v.key].adjacent, gt.vertices[u.key])
}
}
return gt
}

運作時間分析：

該算法的運作時間是 O(|V| + |E|)，其中 |V| 是頂點的數量，|E| 是邊的數量。這是因為我們需要周遊所有的頂點和邊一次。

鄰接矩陣表示法

算法步驟：

  1. 1. 建立一個新的鄰接矩陣 newAdjMatrix 用于存儲轉置後的圖。
  2. 2. 周遊原圖的鄰接矩陣 adjMatrix。
  3. 3. 對于每個元素 adjMatrix[i][j]，将其指派給 newAdjMatrix[j][i]。
  4. 4. 傳回新的鄰接矩陣 newAdjMatrix。

Go語言代碼示例： 

type Graphstruct{
    matrix [][]bool
}

func (g *Graph)Transpose()*Graph{
    gt :=&Graph{make([][]bool,len(g.matrix))}
for i :=range gt.matrix {
        gt.matrix[i]=make([]bool,len(g.matrix))
}
for i :=range g.matrix {
for j :=range g.matrix[i]{
// Copy the adjacency values with swapped indices.
            gt.matrix[j][i]= g.matrix[i][j]
}
}
return gt
}

運作時間分析：

該算法的運作時間是 O(|V|^2)，其中 |V| 是頂點的數量。這是因為我們需要周遊整個鄰接矩陣，而鄰接矩陣的大小是 |V| x |V|。

以上代碼示例僅為算法的核心部分，實際應用中可能需要添加錯誤處理、輸入輸出等其他功能。此外，為了簡化代碼，假設圖中沒有重複的邊，且頂點編号從0開始連續編号。

chatgpt：

下面是用Go語言編寫的從圖 G 計算出 G^T 的算法，同時給出了對應的鄰接連結清單和鄰接矩陣表示方法：

package main

import"fmt"

// 圖的節點結構體
typeNodestruct{
Valueint// 節點的值
Next*Node// 下一個節點指針
}

// 鄰接連結清單表示法的圖結構體
typeGraphstruct{
Vertices[]*Node// 圖中所有節點的數組
}

// 添加有向邊到鄰接連結清單
func (g *Graph)AddEdge(u, v int){
    newNode :=&Node{Value: v}
if g.Vertices[u]==nil{
        g.Vertices[u]= newNode
}else{
        curr := g.Vertices[u]
for curr.Next!=nil{
            curr = curr.Next
}
        curr.Next= newNode
}
}

// 輸出鄰接連結清單表示的圖資訊
func (g *Graph)Print(){
for i, node :=range g.Vertices{
        fmt.Printf("頂點 %d：", i)
for node !=nil{
            fmt.Printf("%d ", node.Value)
            node = node.Next
}
        fmt.Println()
}
}

// 擷取圖 G 的轉置圖 G^T 的鄰接連結清單表示法
func GetTranspose(g *Graph)*Graph{
    transpose :=&Graph{
Vertices:make([]*Node,len(g.Vertices)),
}

for i, node :=range g.Vertices{
for node !=nil{
            v := node.Value

// 在轉置圖中添加反向邊
            transpose.AddEdge(v, i)

            node = node.Next
}
}

return transpose
}

// 輸出鄰接連結清單表示的轉置圖資訊
func PrintTranspose(g *Graph){
    fmt.Println("轉置圖 G^T：")
    g.Print()
}

// 鄰接矩陣表示法的圖結構體
typeMatrixstruct{
Vertices[][]int// 鄰接矩陣，存儲邊的連接配接關系（0 表示無邊，1 表示有邊）
}

// 初始化鄰接矩陣表示的圖
func InitMatrix(numVertices int)*Matrix{
    matrix :=&Matrix{
Vertices:make([][]int, numVertices),
}

for i :=range matrix.Vertices{
        matrix.Vertices[i]=make([]int, numVertices)
}

return matrix
}

// 添加有向邊到鄰接矩陣
func (m *Matrix)AddEdge(u, v int){
    m.Vertices[u][v]=1
}

// 擷取圖 G 的轉置圖 G^T 的鄰接矩陣表示法
func GetTransposeMatrix(m *Matrix)*Matrix{
    numRows :=len(m.Vertices)
    numCols :=len(m.Vertices[0])

    transpose :=InitMatrix(numRows)

for i :=0; i < numRows; i++{
for j :=0; j < numCols; j++{
if m.Vertices[i][j]==1{
// 在轉置矩陣中添加反向邊
                transpose.AddEdge(j, i)
}
}
}

return transpose
}

// 輸出鄰接矩陣表示的轉置圖資訊
func PrintTransposeMatrix(m *Matrix){
    numRows :=len(m.Vertices)
    numCols :=len(m.Vertices[0])

    fmt.Println("轉置圖 G^T：")
for i :=0; i < numRows; i++{
        fmt.Printf("頂點 %d：", i)
for j :=0; j < numCols; j++{
if m.Vertices[i][j]==1{
                fmt.Printf("%d ", j)
}
}
        fmt.Println()
}
}

func main(){
// 鄰接連結清單表示的有向圖 G
    g :=&Graph{
Vertices:make([]*Node,4),
}

    g.AddEdge(0,1)
    g.AddEdge(1,2)
    g.AddEdge(2,3)
    g.AddEdge(3,1)

// 輸出原始圖 G 的鄰接連結清單表示法
    fmt.Println("原始圖 G：")
    g.Print()

// 擷取轉置圖 G^T 的鄰接連結清單表示法并輸出
    transpose :=GetTranspose(g)
PrintTranspose(transpose)


// 鄰接矩陣表示的有向圖 G
    m :=InitMatrix(4)

    m.AddEdge(0,1)
    m.AddEdge(1,2)
    m.AddEdge(2,3)
    m.AddEdge(3,1)

// 輸出原始圖 G 的鄰接矩陣表示法
    fmt.Println("原始圖 G：")
for _, row :=range m.Vertices{
        fmt.Println(row)
}

// 擷取轉置圖 G^T 的鄰接矩陣表示法并輸出
    transposeMatrix :=GetTransposeMatrix(m)
PrintTransposeMatrix(transposeMatrix)
}

該算法的時間複雜度為 O(V + E)，其中 V 是頂點數，E 是邊數。轉置圖的建構過程需要周遊原始圖的所有邊，并将其反向添加到轉置圖中，是以總的時間複雜度與頂點和邊的數量成正比。

kimi：

有向圖的轉置圖可以通過兩種主要的資料結構表示：鄰接連結清單和鄰接矩陣。下面我将分别介紹這兩種情況下的算法，并提供Go語言的示例代碼。

鄰接連結清單表示

對于鄰接連結清單表示的圖，我們可以通過周遊每個頂點的鄰接清單，然後為每個鄰接點添加一條反向邊來實作圖的轉置。這種方法的時間複雜度是O(V + E)，其中V是頂點數，E是邊數。

Go語言示例代碼： 

type Vertexstruct{
Valueint
Adj[]Vertex
}

func transposeGraph(graph []Vertex)[]Vertex{
    transposed :=make([]Vertex,len(graph))
for _, v :=range graph {
for _, adjV :=range v.Adj{
// 為鄰接點添加反向邊
            found :=false
for _, tV :=range transposed[adjV.Value].Adj{
if tV.Value== v.Value{
                    found =true
break
}
}
if!found {
                transposed[adjV.Value].Adj=append(transposed[adjV.Value].Adj, v)
}
}
}
return transposed
}

鄰接矩陣表示

對于鄰接矩陣表示的圖，我們可以通過交換矩陣的行和列來實作轉置。這種方法的時間複雜度是O(V^2)。

Go語言示例代碼： 

func transposeMatrix(matrix [][]int) [][]int{
    n :=len(matrix)
    transposed :=make([][]int, n)
for i :=0; i < n; i++{
        transposed[i]=make([]int, n)
for j :=0; j < n; j++{
            transposed[i][j]= matrix[j][i]
}
}
return transposed
}

算法分析

  • • 鄰接連結清單：算法需要周遊每個頂點的鄰接清單，對于每條邊，需要在鄰接點的鄰接清單中添加反向邊。如果鄰接點清單的平均長度是k，則算法的時間複雜度是O(V + E * k)。在最壞的情況下，k可以接近V，此時時間複雜度接近O(V^2)。在最好的情況下，k接近1，時間複雜度接近O(E)。
  • • 鄰接矩陣：算法需要周遊矩陣的每個元素，并将行和列交換。由于矩陣是VxV的，是以時間複雜度是O(V^2)。

在實際應用中，選擇哪種算法取決于圖的稀疏程度和可用的記憶體。對于稀疏圖，鄰接連結清單可能更節省記憶體；而對于密集圖，鄰接矩陣可能更高效。

混元：

為了計算有向圖 $G=(V,E)$ 的轉置 $G^T=(V,E^T)$，我們可以分别針對鄰接連結清單和鄰接矩陣兩種表示方法給出相應的算法，并分析其運作時間。

鄰接連結清單表示法

算法描述

  1. 1. 初始化一個空的鄰接連結清單來存儲轉置圖的邊。
  2. 2. 周遊原圖 $G$ 的所有節點。
  3. 3. 對于每個節點 $u$，周遊其鄰接連結清單中的所有鄰居節點 $v$。
  4. 4. 在新的鄰接連結清單中添加一條從 $v$ 到 $u$ 的邊。
  5. 5. 完成周遊後，新的鄰接連結清單即為轉置圖 $G^T$。

運作時間分析

  • • 時間複雜度：$O(|E|)$，其中 $|E|$ 是原圖的邊數。因為我們需要周遊每條邊兩次（一次讀取，一次寫入）。

鄰接矩陣表示法

算法描述

  1. 1. 初始化一個與原圖大小相同的鄰接矩陣來存儲轉置圖的邊。
  2. 2. 周遊原圖 $G$ 的鄰接矩陣。
  3. 3. 對于矩陣中的每個非零元素（即存在邊 $(u, v)$），在轉置圖的鄰接矩陣中對應位置 $(v, u)$ 設定為非零元素。
  4. 4. 完成周遊後，新的鄰接矩陣即為轉置圖 $G^T$。

運作時間分析

  • • 時間複雜度：$O(|V|^2)$，其中 $|V|$ 是原圖的節點數。因為我們需要周遊整個鄰接矩陣。

Go 語言實作（鄰接連結清單表示法） 

type Edgestruct{
    dest int
}

typeAdjacencyListstruct{
    edges map[int][]Edge
}

func TransposeGraph(graph AdjacencyList)AdjacencyList{
    transposed :=AdjacencyList{edges:make(map[int][]Edge)}
for u, neighbors :=range graph.edges {
for _, edge :=range neighbors {
            v := edge.dest
            transposed.edges[v]=append(transposed.edges[v],Edge{dest: u})
}
}
return transposed
}

func main(){
// 示例圖的鄰接連結清單表示
    graph :=AdjacencyList{edges:map[int][]Edge{
0:{{dest:1}},
1:{{dest:2}},
2:{{dest:0}},
}}

// 計算轉置圖
    transposedGraph :=TransposeGraph(graph)

// 列印轉置圖的鄰接連結清單
for u, neighbors :=range transposedGraph.edges {
        fmt.Printf("Node %d -> Nodes: ", u)
for _, edge :=range neighbors {
            fmt.Printf("%d ", edge.dest)
}
        fmt.Println()
}
}

在這段代碼中，我們定義了一個 Edge 結構體來表示邊，以及一個 AdjacencyList 結構體來表示鄰接連結清單。TransposeGraph 函數接受一個 AdjacencyList 類型的參數，并傳回其轉置圖的鄰接連結清單表示。在 main 函數中，我們建立了一個示例圖，并計算并列印了其轉置圖。

文心一言
上一篇: 寶山釋出雷電黃色預警！高溫偃旗息鼓，雨水“暴力”回歸！
下一篇: 必看！零成本創業/副業項目，開啟躺賺之旅！

繼續閱讀