deepseek VS chatgpt （399）-- 算法导论25.2 8题

福大大架构师每日一题

发布于 2025-02-19 12:44:47

5200

代码可运行

文章被收录于专栏：福大大架构师每日一题

运行总次数：0

代码可运行

八、给出一个〇时间复杂度的算法来计算有向图的传递闭包。如果要写代码，请用go语言。

chatgpt：

要计算有向图 ( G = (V, E) ) 的传递闭包，可以使用 Floyd-Warshall 算法。该算法的时间复杂度为 ( O(V^3) )，但可以通过某种方式将其优化到 ( O(V E) )。我们可以使用 BFS（宽度优先搜索）来对每个顶点进行访问，从而找到所有可以到达的节点。

下面是用 Go 语言实现的利用 BFS 计算有向图的传递闭包算法。

package main

import (
    "fmt"
)

// Graph struct represents a directed graph using adjacency list
type Graph struct {
    V      int      // Number of vertices
    AdjList [][]int// Adjacency list
}

// NewGraph creates a new directed graph with V vertices
func NewGraph(V int) *Graph {
    return &Graph{
        V:      V,
        AdjList: make([][]int, V),
    }
}

// AddEdge adds a directed edge from src to dest
func (g *Graph) AddEdge(src, dest int) {
    g.AdjList[src] = append(g.AdjList[src], dest)
}

// TransitiveClosure computes the transitive closure of the graph
func (g *Graph) TransitiveClosure() [][]bool {
    // Initialize a 2D slice for the transitive closure
    closure := make([][]bool, g.V)
    for i := range closure {
        closure[i] = make([]bool, g.V)
    }

    // Perform BFS for each vertex
    for i := 0; i < g.V; i++ {
        closure[i][i] = true// A vertex is reachable from itself
        g.bfs(i, closure)
    }

    return closure
}

// bfs performs a BFS from the given start vertex
func (g *Graph) bfs(start int, closure [][]bool) {
    visited := make([]bool, g.V)
    queue := []int{start} // Initialize the queue

    forlen(queue) > 0 {
        // Dequeue a vertex
        v := queue[0]
        queue = queue[1:]

        if visited[v] {
            continue
        }
        visited[v] = true

        // For each adjacent vertex, update the closure
        for _, adj := range g.AdjList[v] {
            if !closure[start][adj] { // Only update if not already visited
                closure[start][adj] = true
                queue = append(queue, adj) // Enqueue the adjacent vertex
            }
        }
    }
}

func main() {
    // Create a directed graph
    g := NewGraph(4)
    g.AddEdge(0, 1)
    g.AddEdge(1, 2)
    g.AddEdge(2, 0)
    g.AddEdge(1, 3)

    // Compute the transitive closure of the graph
    closure := g.TransitiveClosure()

    // Print the transitive closure matrix
    fmt.Println("Transitive Closure:")
    for i := 0; i < g.V; i++ {
        for j := 0; j < g.V; j++ {
            if closure[i][j] {
                fmt.Print("1 ")
            } else {
                fmt.Print("0 ")
            }
        }
        fmt.Println()
    }
}

代码说明

1. Graph 结构：表示有向图的结构体，使用邻接表存储图的边。
2. AddEdge：方法用于添加有向边。
3. TransitiveClosure：计算传递闭包，初始化一个二维布尔数组 closure 来表示每对顶点之间的可达关系。
4. bfs：从给定的起始顶点执行宽度优先搜索，更新传递闭包数组。
5. main：创建一个示例图并输出其传递闭包。

运行这个代码后，会输出图的传递闭包矩阵，其中 1 表示可以从一个顶点到达另一个顶点，0 表示不可达。

deepseek：

要计算有向图 ( G = (V, E) ) 的传递闭包，可以通过对每个节点执行广度优先搜索（BFS）来实现，时间复杂度为 ( O(VE) )。该算法遍历每个节点作为起点，利用 BFS 标记所有可达节点，从而构建传递闭包矩阵。

方法思路

1. 初始化传递闭包矩阵：创建一个 ( V \times V ) 的布尔矩阵 tc，初始时每个节点仅可达自身。
2. 遍历每个节点作为起点：对每个节点执行 BFS，记录从该节点出发可达的所有节点。
3. BFS遍历：在 BFS 过程中，维护一个访问标记数组，避免重复访问，并更新传递闭包矩阵的可达性信息。

该算法的时间复杂度为 ( O(VE) )，因为每个节点执行一次 BFS，每次 BFS 的时间复杂度为 ( O(V + E) )，总时间复杂度为 ( O(V(V + E)) )，在简化后为 ( O(VE) )。

Go代码实现

package main

import"fmt"

func transitiveClosure(n int, adj [][]int) [][]bool {
    tc := make([][]bool, n)
    for i := range tc {
        tc[i] = make([]bool, n)
        tc[i][i] = true// 节点自身可达
    }

    for u := 0; u < n; u++ {
        visited := make([]bool, n)
        queue := []int{u}
        visited[u] = true

        forlen(queue) > 0 {
            v := queue[0]
            queue = queue[1:]
            for _, w := range adj[v] {
                if !visited[w] {
                    visited[w] = true
                    tc[u][w] = true
                    queue = append(queue, w)
                }
            }
        }
    }
    return tc
}

func main() {
    adj := [][]int{
        {1},    // 0 -> 1
        {2},    // 1 -> 2
        {},     // 2 无出边
    }
    n := 3
    tc := transitiveClosure(n, adj)
    for _, row := range tc {
        fmt.Println(row)
    }
}

代码解释

1. 传递闭包矩阵初始化：tc 是一个二维布尔数组，初始时每个节点仅能到达自己。
2. BFS遍历：对每个节点 u 执行 BFS，使用队列处理当前节点的所有邻接节点，标记可达性。
3. 可达性更新：在 BFS 过程中，每访问一个新节点 w，将 tc[u][w] 标记为 true，表示 u 可达 w。

该实现通过逐节点的 BFS 遍历，确保了每个节点的可达性信息被正确记录，最终构建完整的传递闭包矩阵。

通义千问：

传递闭包是一个图论概念，指的是对于一个有向图，其传递闭包是一个图，其中包含所有顶点对之间的边，如果在原图中存在从到的路径的话。

要在一个有向图中计算传递闭包，并且要求时间复杂度为〇，可以使用基于深度优先搜索（DFS）的方法。这个方法的基本思想是对每个顶点执行一次DFS，以发现该顶点可以到达的所有其他顶点。由于每次DFS的时间复杂度是〇，对每个顶点都进行DFS的结果就是总的时间复杂度为〇（假设图是稀疏的，即远小于）。

下面是一个用Go语言实现上述算法的例子：

package main

import (
    "fmt"
)

func dfs(graph [][]int, visited []bool, vertex int) {
    if visited[vertex] {
        return
    }
    visited[vertex] = true
    for _, neighbor := range graph[vertex] {
        if !visited[neighbor] {
            dfs(graph, visited, neighbor)
        }
    }
}

func transitiveClosure(graph [][]int) [][]bool {
    vertexCount := len(graph)
    reachable := make([][]bool, vertexCount)
    for i := range reachable {
        reachable[i] = make([]bool, vertexCount)
        visited := make([]bool, vertexCount)
        dfs(graph, visited, i)
        for j, isVisited := range visited {
            if isVisited {
                reachable[i][j] = true
            }
        }
    }
    return reachable
}

func main() {
    graph := [][]int{
        {1, 2},
        {3},
        {3},
        {},
    }
    fmt.Println("Transitive Closure:")
    result := transitiveClosure(graph)
    for _, row := range result {
        fmt.Println(row)
    }
}

这段代码首先定义了一个dfs函数，用于从给定的起始顶点开始遍历图中的所有可达顶点，并标记这些顶点。然后，transitiveClosure函数通过为图中的每个顶点调用dfs来计算传递闭包。最后，主函数创建了一个示例图并打印了它的传递闭包。

请注意，上述代码中的图是以邻接表的形式表示的，而传递闭包结果则是一个二维布尔数组，其中reachable[u][v]为true意味着在原始图中存在从顶点u到顶点v的路径。

豆包：

有向图的传递闭包是一个布尔矩阵，用于表示图中任意两个顶点之间是否存在路径。可以使用基于广度优先搜索（BFS）的算法来计算有向图的传递闭包，其时间复杂度为，其中是图中顶点的数量，是图中边的数量。

算法思路

1. 对于图中的每个顶点，从开始进行广度优先搜索（BFS）。
2. 在 BFS 过程中，标记所有从可达的顶点。
3. 根据 BFS 的结果更新传递闭包矩阵。

Go 语言实现

package main

import (
    "fmt"
)

// 计算有向图的传递闭包
func transitiveClosure(graph [][]int) [][]bool {
    V := len(graph)
    // 初始化传递闭包矩阵
    closure := make([][]bool, V)
    for i := range closure {
        closure[i] = make([]bool, V)
    }

    // 对每个顶点进行 BFS
    for u := 0; u < V; u++ {
        // 初始化队列和访问标记数组
        queue := []int{u}
        visited := make([]bool, V)
        visited[u] = true

        forlen(queue) > 0 {
            // 出队
            v := queue[0]
            queue = queue[1:]
            // 标记可达性
            closure[u][v] = true

            // 遍历邻接顶点
            for w := 0; w < V; w++ {
                if graph[v][w] == 1 && !visited[w] {
                    visited[w] = true
                    queue = append(queue, w)
                }
            }
        }
    }

    return closure
}

func main() {
    // 示例有向图的邻接矩阵
    graph := [][]int{
        {0, 1, 1, 0},
        {0, 0, 1, 0},
        {1, 0, 0, 1},
        {0, 0, 0, 0},
    }

    // 计算传递闭包
    closure := transitiveClosure(graph)

    // 输出传递闭包矩阵
    for i := range closure {
        for j := range closure[i] {
            if closure[i][j] {
                fmt.Print("1 ")
            } else {
                fmt.Print("0 ")
            }
        }
        fmt.Println()
    }
}

代码解释

1. 初始化传递闭包矩阵：创建一个的布尔矩阵 closure，用于存储传递闭包的结果。
2. 对每个顶点进行 BFS：对于图中的每个顶点，从开始进行 BFS。在 BFS 过程中，使用队列 queue 来存储待访问的顶点，使用 visited 数组来标记已访问的顶点。
3. 更新传递闭包矩阵：在 BFS 过程中，标记所有从可达的顶点。将 closure[u][v] 设置为 true，表示从到存在路径。
4. 输出传递闭包矩阵：遍历传递闭包矩阵，输出结果。

复杂度分析

• 时间复杂度：对于每个顶点，BFS 的时间复杂度为，因为每个边最多被访问一次。由于需要对个顶点进行 BFS，因此总的时间复杂度为。
• 空间复杂度：主要的空间开销是传递闭包矩阵和 BFS 中的队列和访问标记数组，因此空间复杂度为。

文心一言：

传递闭包（Transitive Closure）是一个有向图的扩展，其中如果存在从顶点到顶点的路径，则在传递闭包中存在一条边。计算传递闭包的一个经典算法是 Floyd-Warshall 算法，它的时间复杂度是。

以下是使用 Go 语言实现的 Floyd-Warshall 算法来计算有向图的传递闭包：

package main

import (
    "fmt"
)

// Function to print the 2D slice in a readable format
func printMatrix(matrix [][]bool) {
    for i := range matrix {
        for j := range matrix[i] {
            if matrix[i][j] {
                fmt.Print("1 ")
            } else {
                fmt.Print("0 ")
            }
        }
        fmt.Println()
    }
}

// Floyd-Warshall algorithm to compute the transitive closure of a directed graph
func transitiveClosure(graph [][]bool) [][]bool {
    V := len(graph)
    // Initialize the result matrix same as the input graph matrix.
    // Or we can say the initial values of shortest distances 
    // based on shortest paths considering no intermediate vertex.
    closure := make([][]bool, V)
    for i := range closure {
        closure[i] = make([]bool, V)
        copy(closure[i], graph[i])
    }

    // Pick all vertices as source one by one
    for k := 0; k < V; k++ {
        // Pick all vertices as destination for the above picked source
        for i := 0; i < V; i++ {
            // Pick all vertices as intermediate vertex
            for j := 0; j < V; j++ {
                // Update the result if a shorter path is found.
                closure[i][j] = closure[i][j] || (closure[i][k] && closure[k][j])
            }
        }
    }
    return closure
}

func main() {
    // Example directed graph represented as an adjacency matrix
    graph := [][]bool{
        {false, true, false, false},
        {false, false, true, true},
        {false, false, false, true},
        {false, false, false, false},
    }

    fmt.Println("Graph:")
    printMatrix(graph)

    closure := transitiveClosure(graph)

    fmt.Println("\nTransitive Closure:")
    printMatrix(closure)
}

代码解释

1. Graph Representation:
- • 图用邻接矩阵表示，其中 graph[i][j] 为 true 表示存在从顶点 i 到顶点 j 的边，否则为 false。
2. Initialization:
- • closure 矩阵初始化为与输入图相同的值。
3. Floyd-Warshall 算法:
- • 外层循环 k 表示中间顶点。
- • 中间循环 i 表示源顶点。
- • 内层循环 j 表示目标顶点。
- • 更新 closure[i][j]，如果存在从 i 到 j 的路径（直接或间接通过 k），则 closure[i][j] 设为 true。
4. 打印结果:
- • 使用 printMatrix 函数以可读的格式打印矩阵。

运行结果

给定示例图的邻接矩阵：

传递闭包结果：

Transitive Closure:
0 1 1 1 
0 0 1 1 
0 0 0 1 
0 0 0 0

这个结果显示了从每个顶点出发可以到达的其他顶点。

讯飞星火：

计算有向图的传递闭包是一个经典的图论问题，可以使用Floyd-Warshall算法来解决。该算法的时间复杂度为，其中是图中顶点的数量。

以下是用Go语言实现的Floyd-Warshall算法来计算有向图的传递闭包：

package main

import (
    "fmt"
)

// FloydWarshall computes the transitive closure of a directed graph using the Floyd-Warshall algorithm.
func FloydWarshall(graph [][]bool) [][]bool {
    n := len(graph)
    tc := make([][]bool, n)
    for i := range tc {
        tc[i] = make([]bool, n)
        copy(tc[i], graph[i])
    }

    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if tc[i][k] && tc[k][j] {
                    tc[i][j] = true
                }
            }
        }
    }

    return tc
}

func main() {
    // Example usage:
    // Graph represented as an adjacency matrix where graph[i][j] is true if there is an edge from i to j.
    graph := [][]bool{
        {false, true, false, false},
        {false, false, true, false},
        {true, false, false, true},
        {false, false, false, false},
    }

    tc := FloydWarshall(graph)

    fmt.Println("Transitive Closure:")
    for _, row := range tc {
        for _, val := range row {
            if val {
                fmt.Print("1 ")
            } else {
                fmt.Print("0 ")
            }
        }
        fmt.Println()
    }
}

解释：

1. 输入：graph 是一个布尔类型的二维切片，表示有向图的邻接矩阵。如果 graph[i][j] 为 true，则存在从顶点 i 到顶点 j 的边。
2. 初始化：我们创建一个新的二维切片 tc，它是传递闭包的结果。初始时，tc 与输入的 graph 相同。
3. Floyd-Warshall算法：通过三重循环更新tc。对于每个中间顶点k，检查是否存在从i到k和从k到j的路径。如果存在，则在tc中设置tc[i][j]为true。
4. 输出：打印传递闭包矩阵。

这个代码示例展示了如何使用Floyd-Warshall算法计算有向图的传递闭包，并打印结果。你可以根据需要修改输入图来测试不同的图结构。

360智脑：

传递闭包是指在一个有向图中，对于任意两个顶点 (u) 和 (v)，如果从 (u) 可以到达 (v)，则在传递闭包中存在一条从 (u) 到 (v) 的边。计算传递闭包的一个常见方法是使用 Floyd-Warshall 算法，该算法的时间复杂度为 (O(V^3))。

然而，你要求的是 (O(VE)) 时间复杂度的算法。这可以通过使用基于深度优先搜索（DFS）的方法来实现。具体来说，我们可以对每个顶点执行一次 DFS，记录所有可以到达的顶点。

以下是用 Go 语言实现的代码：

package main

import (
    "fmt"
)

// Graph represents a directed graph using adjacency list representation
type Graph struct {
    V   int
    E   int
    adj map[int][]int
}

// NewGraph creates a new graph with V vertices
func NewGraph(V int) *Graph {
    return &Graph{
        V:   V,
        E:   0,
        adj: make(map[int][]int),
    }
}

// AddEdge adds an edge from u to v
func (g *Graph) AddEdge(u, v int) {
    g.adj[u] = append(g.adj[u], v)
    g.E++
}

// TransitiveClosure computes the transitive closure of the graph
func (g *Graph) TransitiveClosure() [][]bool {
    tc := make([][]bool, g.V)
    for i := range tc {
        tc[i] = make([]bool, g.V)
    }

    for i := 0; i < g.V; i++ {
        visited := make([]bool, g.V)
        g.dfs(i, visited)
        for j := 0; j < g.V; j++ {
            if visited[j] {
                tc[i][j] = true
            }
        }
    }
    return tc
}

// dfs performs a depth-first search starting from vertex v
func (g *Graph) dfs(v int, visited []bool) {
    visited[v] = true
    for _, w := range g.adj[v] {
        if !visited[w] {
            g.dfs(w, visited)
        }
    }
}

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

    tc := g.TransitiveClosure()

    fmt.Println("Transitive Closure:")
    for i := 0; i < g.V; i++ {
        for j := 0; j < g.V; j++ {
            if tc[i][j] {
                fmt.Printf("1 ")
            } else {
                fmt.Printf("0 ")
            }
        }
        fmt.Println()
    }
}

解释

1. Graph 结构体：表示一个有向图，使用邻接表存储。
2. NewGraph 函数：创建一个新的图。
3. AddEdge 方法：添加一条从 u 到 v 的边。
4. TransitiveClosure 方法：计算图的传递闭包。
- • 初始化一个二维布尔数组 tc，用于存储传递闭包的结果。
- • 对每个顶点 i 执行一次 DFS，记录所有可以从 i 到达的顶点。
5. dfs 方法：执行深度优先搜索，标记所有可以从当前顶点到达的顶点。
6. main 函数：示例用法，创建一个图并计算其传递闭包。

这个算法的时间复杂度是 (O(VE))，因为每个顶点最多会被访问 (V) 次，每次访问的复杂度是 (O(E))。

智谱清言：

传递闭包是一个新的有向图，它包含所有可以从一个顶点到达另一个顶点的路径。在数学中，有向图的传递闭包可以通过Warshall算法（也称为Roy-Warshall算法）来计算，该算法的时间复杂度为O(V^3)，但可以通过优化减少到O(VE)。下面是一个使用Go语言实现的O(VE)时间复杂度的算法来计算有向图的传递闭包：

package main
import (
    "fmt"
)
// Graph represents a directed graph using adjacency list representation
type Graph struct {
    V     int
    adj   [][]bool
    trans [][]bool
}
// Initialize the graph
func (g *Graph) Initialize(V int) {
    g.V = V
    g.adj = make([][]bool, V)
    g.trans = make([][]bool, V)
    for i := 0; i < V; i++ {
        g.adj[i] = make([]bool, V)
        g.trans[i] = make([]bool, V)
        for j := 0; j < V; j++ {
            g.trans[i][j] = g.adj[i][j]
        }
    }
}
// AddEdge adds an edge to the graph
func (g *Graph) AddEdge(u, v int) {
    g.adj[u][v] = true
}
// TransitiveClosure computes the transitive closure of the graph
func (g *Graph) TransitiveClosure() {
    for k := 0; k < g.V; k++ {
        for i := 0; i < g.V; i++ {
            for j := 0; j < g.V; j++ {
                g.trans[i][j] = g.trans[i][j] || (g.trans[i][k] && g.trans[k][j])
            }
        }
    }
}
// PrintTransitiveClosure prints the transitive closure of the graph
func (g *Graph) PrintTransitiveClosure() {
    fmt.Println("Transitive Closure:")
    for i := 0; i < g.V; i++ {
        for j := 0; j < g.V; j++ {
            if g.trans[i][j] {
                fmt.Printf("1 ")
            } else {
                fmt.Printf("0 ")
            }
        }
        fmt.Println()
    }
}
func main() {
    // Create a graph given in the above diagram
    g := Graph{}
    g.Initialize(4)
    g.AddEdge(0, 1)
    g.AddEdge(0, 2)
    g.AddEdge(1, 2)
    g.AddEdge(2, 0)
    g.AddEdge(2, 3)
    g.AddEdge(3, 3)
    // Print the solution
    g.TransitiveClosure()
    g.PrintTransitiveClosure()
}

在这个代码中，我们定义了一个Graph结构体，它包含顶点数V、邻接矩阵adj和传递闭包矩阵trans。Initialize函数用于初始化图，AddEdge函数用于添加边，TransitiveClosure函数用于计算传递闭包，而PrintTransitiveClosure函数用于打印传递闭包的结果。注意，这个算法的时间复杂度是O(VE)，因为对于每个顶点k，我们检查所有顶点对(i, j)是否有路径从i到j通过k。如果图的边密度较高（即E接近V^2），这个算法的时间复杂度将接近O(V^3)。对于稀疏图，这个算法的时间复杂度会更接近O(VE)。

天工：

1. 算法原理
- • 传递闭包是一个有向图(G=(V, E))的一个布尔矩阵(T)，其中(T[u][v])为真当且仅当在图(G)中存在从顶点(u)到顶点(v)的路径。
- • 可以使用Floyd - Warshall算法来计算有向图的传递闭包，其时间复杂度为(O(V^3))，算法的基本思想是对于每一对顶点((i, j))，考虑是否可以通过中间顶点(k)来缩短从(i)到(j)的路径。
2. Go语言实现代码如下：

package main

import (
    "fmt"
)

func transitiveClosure(graph [][]bool) [][]bool {
    n := len(graph)
    closure := make([][]bool, n)
    for i := 0; i < n; i++ {
        closure[i] = make([]bool, n)
        for j := 0; j < n; j++ {
            closure[i][j] = graph[i][j]
        }
    }

    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                closure[i][j] = closure[i][j] || (closure[i][k] && closure[k][j])
            }
        }
    }

    return closure
}

3. 使用示例

func main() {
    graph := [][]bool{
        {true, false, false},
        {false, true, false},
        {true, false, true},
    }
    closure := transitiveClosure(graph)
    for _, row := range closure {
        for _, val := range row {
            fmt.Printf("%v ", val)
        }
        fmt.Println()
    }
}

在上述代码中：

• 首先初始化传递闭包矩阵closure为图的邻接矩阵。
• 然后通过三层嵌套循环，按照Floyd - Warshall算法的思想更新传递闭包矩阵。
• 在main函数中创建了一个示例图，并计算和打印其传递闭包矩阵。

kimi：

为了计算有向图 G=(V,E) 的传递闭包，我们可以使用 Floyd-Warshall 算法。Floyd-Warshall 算法是一种动态规划算法，用于在加权图中找到所有顶点对之间的最短路径。在传递闭包的上下文中，我们关心的是是否存在从一个顶点到另一个顶点的路径，而不是路径的长度。算法步骤初始化：创建一个 V×V 的矩阵 T，其中 T[i][j] 表示从顶点 i 到顶点 j 是否存在直接的边。如果存在边，则 T[i][j]=1；否则，T[i][j]=0。对角线上的元素 T[i][i] 初始化为 1，因为每个顶点到自身总是有路径的。迭代：对于每个顶点 k（从 1 到 V），更新矩阵 T。对于每对顶点 (i,j)，如果从 i 到 k 有路径且从 k 到 j 有路径，则从 i 到 j 也存在路径。因此，我们更新 T[i][j] 为 T[i][j] 或 T[i][k] 与 T[k][j] 的逻辑与。输出：最终的矩阵 T 就是图 G 的传递闭包。时间复杂度 Floyd-Warshall 算法的时间复杂度为 O(V3)，因为有三个嵌套的循环，每个循环都遍历所有顶点。 Go 语言实现

package main

import"fmt"

// 传递闭包的Floyd-Warshall算法
func transitiveClosure(V int, E [][2]int) [][]int {
    // 初始化传递闭包矩阵
    T := make([][]int, V)
    for i := range T {
        T[i] = make([]int, V)
        for j := range T[i] {
            T[i][j] = 0
        }
        T[i][i] = 1// 每个顶点到自身有路径
    }

    // 根据边初始化矩阵
    for _, edge := range E {
        i, j := edge[0], edge[1]
        T[i][j] = 1
    }

    // 迭代更新传递闭包矩阵
    for k := 0; k < V; k++ {
        for i := 0; i < V; i++ {
            for j := 0; j < V; j++ {
                T[i][j] = T[i][j] || (T[i][k] && T[k][j])
            }
        }
    }

    return T
}

func main() {
    V := 4
    E := [][2]int{{0, 1}, {1, 2}, {2, 3}, {3, 0}, {1, 3}}

    T := transitiveClosure(V, E)

    // 打印传递闭包矩阵
    for i := 0; i < V; i++ {
        for j := 0; j < V; j++ {
            fmt.Print(T[i][j], " ")
        }
        fmt.Println()
    }
}

输出

这个输出表示在给定的有向图中，从任何顶点到任何其他顶点都存在路径。

腾讯元宝：

计算有向图的传递闭包（即确定任意两个顶点之间是否存在路径）可以使用 Floyd-Warshall 算法。该算法的时间复杂度为，其中是顶点的数量。虽然这与您要求的时间复杂度不符，但在一般情况下，Floyd-Warshall 是计算传递闭包的标准方法之一。

然而，如果您确实需要一个时间复杂度的算法，可以使用 基于广度优先搜索（BFS）或深度优先搜索（DFS）的多次遍历方法。该方法的基本思想是对于每个顶点，执行一次 BFS 或 DFS 来标记所有从可达的顶点。这样，总的时间复杂度为，在稀疏图中接近。

以下是使用 Go 语言实现的基于 BFS 的传递闭包算法：

package main

import (
    "fmt"
)

// Graph represents a directed graph using adjacency list
type Graph struct {
    V     int
    Adj   [][]int
}

// NewGraph creates a new graph with V vertices
func NewGraph(V int) *Graph {
    adj := make([][]int, V)
    for i := range adj {
        adj[i] = []int{}
    }
    return &Graph{V: V, Adj: adj}
}

// AddEdge adds a directed edge from u to v
func (g *Graph) AddEdge(u, v int) {
    g.Adj[u] = append(g.Adj[u], v)
}

// TransitiveClosure computes the transitive closure of the graph
// Returns a 2D slice where closure[i][j] is true if there is a path from i to j
func (g *Graph) TransitiveClosure() [][]bool {
    closure := make([][]bool, g.V)
    for i := 0; i < g.V; i++ {
        closure[i] = make([]bool, g.V)
        closure[i][i] = true// Every vertex is reachable from itself
    }

    for s := 0; s < g.V; s++ {
        visited := make([]bool, g.V)
        queue := []int{s}
        visited[s] = true

        forlen(queue) > 0 {
            u := queue[0]
            queue = queue[1:]
            for _, v := range g.Adj[u] {
                if !visited[v] {
                    visited[v] = true
                    closure[s][v] = true
                    queue = append(queue, v)
                }
            }
        }
    }

    return closure
}

func main() {
    // 示例：创建一个有向图
    // 顶点编号为 0 到 4
    g := NewGraph(4)
    g.AddEdge(0, 1)
    g.AddEdge(0, 2)
    g.AddEdge(1, 2)
    g.AddEdge(2, 0)
    g.AddEdge(2, 3)
    g.AddEdge(3, 3)

    // 计算传递闭包
    closure := g.TransitiveClosure()

    // 输出传递闭包矩阵
    fmt.Println("传递闭包矩阵:")
    for i := 0; i < g.V; i++ {
        for j := 0; j < g.V; j++ {
            if closure[i][j] {
                fmt.Printf("1 ")
            } else {
                fmt.Printf("0 ")
            }
        }
        fmt.Println()
    }
}

代码说明

1. 图的表示：
- • 使用邻接表（Adj）来表示有向图，其中 Adj[u] 存储所有从顶点 u 出发的边。
2. 传递闭包的计算：
- • 初始化一个二维布尔切片 closure，其中 closure[i][j] 表示是否存在从顶点 i 到顶点 j 的路径。
- • 对于每个顶点 s，执行 BFS 来标记所有从 s 可达的顶点，并更新 closure[s][v] 为 true。
3. 主函数：
- • 创建一个示例图并添加边。
- • 调用 TransitiveClosure 方法计算传递闭包。
- • 打印传递闭包矩阵。

希望这个实现能够满足您的需求！

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2025-02-12，如有侵权请联系 cloudcommunity@tencent.com 删除

算法

本文分享自福大大架构师每日一题微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度