2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
In the adjacency list representation, each vertex v v v There is a linked list, each node in the linked list represents a v v v The starting edge. In order to calculate G T G^T GT, we need to traverse G G G , and reverse the direction of the edge, adding G T G^T GT in the corresponding linked list.
Go language implementation：
package main
import (
"fmt"
)
// Graph 使用邻接链表表示
type Graph struct {
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 -> %vn", u, adj)
}
fmt.Println("nTransposed Graph:")
for u, adj := range gT.adjList {
fmt.Printf("%d -> %vn", u, adj)
}
}
time complexity：
In the adjacency matrix representation, we use a two-dimensional array to store edge information, where matrix[u][v] Indicates whether there is a
u
u
u arrive
v
v
v In order to calculate
G
T
G^T
GT, we traverse the upper triangle of the matrix (or lower triangle, depending on your matrix representation habits) and reverse the direction of the edges, that is, matrix[u][v] The value ofmatrixT[v][u]。
Go language implementation(Simplified version, only considering existence, not edge weights):
// 假设使用二维布尔切片表示邻接矩阵
type GraphMatrix [][]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函数
time complexity：
For a directed graph represented by an adjacency list, we can traverse the adjacency list of each vertex and add the adjacent vertices of each vertex to the adjacency list of the transposed vertex of the new graph. The specific steps are as follows:
Time complexity analysis: traversing each vertex of the original graph requires O ( ∣ V ∣ ) O(|V|) O(∣V∣) time, it takes to traverse the adjacency list of each vertex O ( ∣ E ∣ ) O(|E|) O(∣E∣) time, so the total time complexity is O ( ∣ V ∣ + ∣ E ∣ ) O(|V| + |E|) O(∣V∣+∣E∣)。
For a directed graph represented by an adjacency matrix, we can obtain the adjacency matrix of the new graph by transposing the adjacency matrix of the original graph. The specific steps are as follows:
Time complexity analysis: Traversing the adjacency matrix of the original graph requires O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2) time, so the total time complexity is O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)。
The following is the code implemented in Go language:
// 邻接链表表示的有向图转置
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
}
In the adjacency list representation, we can directly traverse the original graph G G GThe adjacency list of each node is then reversed and added to the new graph. G T G^{T} GTon the corresponding node.
type Graph struct {
Vertices []*Node // 存储图中所有节点的指针
}
type Node struct {
Value int
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
}
Therefore, the total time complexity is O ( ∣ V ∣ + ∣ E ∣ ) O(|V| + |E|) O(∣V∣+∣E∣)。
In adjacency matrix representation, we can create a new adjacency matrix and then traverse the original graph G G GThe adjacency matrix of ( i , j ) (i, j) (i,j)Assign to the new matrix ( j , i ) (j, i) (j,i)position, thus completing the reversal of the edge.
type MatrixGraph struct {
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
}
Therefore, the total time complexity is O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)。
For the adjacency list representation, the time complexity of the transposition algorithm is O ( ∣ V ∣ + ∣ E ∣ ) O(|V| + |E|) O(∣V∣+∣E∣), while for the adjacency matrix representation, the time complexity of the transposition algorithm is O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)In practical applications, if the graph is sparse (i.e. ∣ E ∣ |E| ∣E∣Much smaller than ∣ V ∣ 2 |V|^2 ∣V∣2), it is more efficient to use the adjacency list representation. If the graph is dense (i.e. ∣ E ∣ |E| ∣E∣near ∣ V ∣ 2 |V|^2 ∣V∣2), then the adjacency matrix representation may be more appropriate.
In the representation of graphs, adjacency lists and adjacency matrices are both commonly used methods. Adjacency lists are used to represent undirected graphs and directed graphs, while adjacency matrices are usually used to represent undirected graphs. For the transpose of a directed graph, we can operate on the adjacency list and adjacency matrix respectively.
For a directed graph represented by an adjacency list, the transposed graph can be realized by traversing each vertex of the original graph and modifying the outgoing edges of the original graph into incoming edges.
package main
import (
"fmt"
)
// 定义图的顶点结构
type Vertex struct {
Name string
Edges []*Vertex
Visited bool
}
// 计算图的转置
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)
}
}
}
For a directed graph represented by an adjacency matrix, the transposed graph can be achieved by converting each row of the original graph into the corresponding column of the new graph.
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)
}
}
For the transpose of an adjacency list, the algorithm has a time complexity of O(E), where E is the number of edges in the graph. This is because each edge needs to be traversed once.
For the transpose of the adjacency matrix, the time complexity of the algorithm is O(V^2), where V is the number of vertices in the graph. This is because each matrix element needs to be traversed once, and the size of the matrix is V×V.
These algorithms are all valid and run
To implement an algorithm to calculate the directed graph G G G Transpose G T G^{T} GT, we can handle the two representations separately, the adjacency list and the adjacency matrix. Below I will describe the algorithms for both cases and provide code examples in Go.
newAdjList Used to store the transposed graph.adjList。(u, v), add it to newAdjList[v] middle.newAdjList。type Graph struct {
vertices []*Vertex
}
type Vertex struct {
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
}
The running time of this algorithm is O(|V| + |E|), where |V| is the number of vertices and |E| is the number of edges. This is because we need to traverse all vertices and edges exactly once.
newAdjMatrix Used to store the transposed graph.adjMatrix。adjMatrix[i][j], assign it to newAdjMatrix[j][i]。newAdjMatrix。type Graph struct {
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
}
The running time of this algorithm is O(|V|^2), where |V| is the number of vertices. This is because we need to traverse the entire adjacency matrix, and the size of the adjacency matrix is |V| x |V|.
The above code examples are only the core part of the algorithm. In actual applications, you may need to add other functions such as error handling, input and output. In addition, to simplify the code, it is assumed that there are no repeated edges in the graph and the vertex numbers are numbered consecutively starting from 0.
The following is an algorithm written in Go language to calculate G^T from graph G, and the corresponding adjacency list and adjacency matrix representation methods are also given:
package main
import "fmt"
// 图的节点结构体
type Node struct {
Value int // 节点的值
Next *Node // 下一个节点指针
}
// 邻接链表表示法的图结构体
type Graph struct {
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()
}
// 邻接矩阵表示法的图结构体
type Matrix struct {
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)
}
The time complexity of this algorithm is O(V + E), where V is the number of vertices and E is the number of edges. The construction process of the transposed graph requires traversing all the edges of the original graph and adding them in reverse to the transposed graph, so the total time complexity is proportional to the number of vertices and edges.
The transposed graph of a directed graph can be represented by two main data structures: an adjacency list and an adjacency matrix. Below I will introduce the algorithms for both cases and provide example code in Go.
For a graph represented by an adjacency list, we can transpose the graph by traversing the adjacency list of each vertex and then adding a reverse edge to each adjacent vertex. The time complexity of this method is O(V + E), where V is the number of vertices and E is the number of edges.
type Vertex struct {
Value int
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
}
For a graph represented by an adjacency matrix, we can perform the transposition by swapping the rows and columns of the matrix. The time complexity of this method is O(V^2).
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
}
In practice, the choice of algorithm depends on the sparsity of the graph and the available memory. For sparse graphs, an adjacency list may be more memory-efficient, while for dense graphs, an adjacency matrix may be more efficient.
To calculate the directed graph G = ( V , E ) G=(V,E) G=(V,E) Transpose G T = ( V , E T ) G^T=(V,E^T) GT=(V,ET), we can give corresponding algorithms for the two representation methods of adjacency list and adjacency matrix respectively, and analyze their running time.
type Edge struct {
dest int
}
type AdjacencyList struct {
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()
}
}
In this code, we define a Edge structures to represent edges, and aAdjacencyList Structure to represent adjacency linked list.TransposeGraph The function accepts aAdjacencyList Type argument and returns an adjacency list representation of its transposed graph.main In the function, we create a sample graph and calculate and print its transposed graph.
I have devoted myself to the research of technology for more than 30 years. I am proficient in various languages such as Java, Linux, JavaScript, PHP, CSS, etc. I have made many contributions in the field of open source. I have established a developer documentation site to share some problems in technology development for everyone to read.
