4. Given an adjacency linked list of multi-graph $G=(V,E)$ (multigraph is a graph that allows repeating edges and self-cyclic edges), please give an algorithm with the time $O(V+E)$ to calculate the adjacency linked list representation of the "equivalent" undirected graph $G^{'}=(V,E^{'})$ of the graph. Here $E^{'}$ is the edge left after the redundant edges and self-cyclic edges in $E$ are removed. Removing a cosplor refers to replacing multiple edges between two nodes with a single edge. If you want to write code, use go.
Wenxin's words:
Adjacent linked list representation
In an adjacency linked list representation, each vertex $v$ has a linked list, and each node in the linked list represents an edge from $v$. In order to calculate $G^T$, we need to iterate through each edge of $G$ and reverse the direction of the edge, adding it to the corresponding linked list of $G^T$.
Go language implementation:
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)
}
} Time Complexity:
- • The time complexity of traversing each edge is $O(E)$, where $E$ is the number of edges.
- • For each edge, we perform an operation with a constant time (added to the adjacency linked list of another graph).
- • Therefore, the total time complexity is $O(E)$.
Adjacency matrix representation
In the adjacency matrix representation, we use a two-dimensional array to store the information about the edges, where matrix[u][v] indicates the presence or absence of an edge from $u$ to $v$. To calculate $G^T$, we traverse the upper triangle (or lower triangle, depending on your matrix representation habits) of the matrix and reverse the direction of the edges, i.e., assign the value of matrix[u][v] to matrixT[v][u].
Go implementation (simplified version, only existential, not the weight of edges):
// 假设使用二维布尔切片表示邻接矩阵
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函数 Time Complexity:
- • It takes $O(V^2)$ time to traverse each element of the matrix, where $V$ is the number of vertices.
- • Therefore, the total time complexity is $O(V^2)$. This may not be the most efficient when the number of vertices is much larger than the number of edges.
Insert a description of the picture here
Insert a description of the picture here
Insert a description of the picture here
Insert a description of the picture here
iFLYTEK Spark:
For a directed graph represented by an adjacency linked list, we can add the adjacent vertices of each vertex to the adjacent linked list of the transposed vertices of the new graph by traversing the adjacent linked list of each vertex. The specific steps are as follows:
- 1. Create a new adjacency linked list $G^{T}$ and initialize empty.
- 2. Iterate through each vertex of the original image $G$ $v$.
- 3. Traverse the adjacent linked list of vertices $v$ and add $u$ of each adjacent vertex to the adjacent linked list of vertices $v$ in the new figure $G^{T}$.
- 4. Return to a new figure $G^{T}$.
Time complexity analysis: It takes $O (|) to traverse each vertex of the original graphV|) $, it takes $O(|) to traverse the adjacent linked list of each vertexE|) $, so the total time complexity is $O(|V| + |E|) $。
For the directed graph represented by the 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:
- 1. Create a new size of $|V| \times |The matrix of V|$ $G^{T}$ is initialized as an all-zero matrix.
- 2. 遍历原图的邻接矩阵 $G$，将 $G[i][j]$ 的值赋给 $G^{T}[j][i]$。
- 3. 返回新图的邻接矩阵 $G^{T}$。
Time complexity analysis: $O(|) is required to traverse the adjacency matrix of the original graphV|^2)$, so the total time complexity is $O(|V|^2)$。
Here's the code in 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 Smart Brain:
Adjacency linked list notation
In the adjacency linked list notation, we can directly iterate through the adjacency linked list of each node of the original graph $G$, and then add the direction of each edge to the corresponding node of the new graph $G^{T}$.
Go code implementation:
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
} Time Complexity Analysis:
- • Traverse each node in the original graph: $O (|.) V|) $
- • Traversing the adjacency linked list for each node: $O (|.) E|) $
Therefore, the total time complexity is $O(|V| + |E|) $。
Adjacency matrix notation
In the adjacency matrix notation, we can create a new adjacency matrix, and then iterate through the adjacency matrix of the original graph $G$, and assign each element in the matrix $(i, j)$ to the position of the new matrix $(j, i)$, so that the edge inversion is completed.
Go code implementation:
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
} Time Complexity Analysis:
- • Create a new adjacency matrix: $O (|.) V|^2)$
- • 遍历原图的邻接矩阵：$O(|V|^2)$
Therefore, the total time complexity is $O(|V|^2)$。
summary
For adjacency linked list notation, the time complexity of the transpose algorithm is $O(|V| + |E|) $, while for adjacency matrix notation, the time complexity of the transpose algorithm is $O(|V|^2)$。 In practice, if the graph is sparse (i.e., $|E|$ is much smaller than $|V|^2$), it is more efficient to use adjacency linked list notation. If the graph is dense (i.e., $|E|$ is close to $|V|^2$), an adjacency matrix notation may be more appropriate.
Zhipu Qingyan:
In the representation of graphs, both adjacency linked lists and adjacency matrices are commonly used. Adjacency linked lists are used to represent undirected and directed graphs, while adjacency matrices are often used to represent undirected graphs. For the transpose of directed graphs, we can operate on the adjacency linked list and the adjacency matrix separately.
Transpose of adjacent linked lists
For directed graphs represented by adjacency linked lists, the transpose graph can be achieved by traversing each vertex of the original graph and modifying the outgoing edge of the original graph to the incoming edge.
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)
}
}
} Transpose of adjacency matrices
For directed graphs represented by adjacency matrices, transpose graphs can be achieved by turning each row of the original graph into a 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)
}
} Algorithm runtime analysis
- 1. For the transpose of adjacent linked lists, the time complexity of the algorithm is O(E), where E is the number of edges in the graph. This is because each edge needs to be traversed once.
- 2. For the transpose of adjacency matrices, 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
Heavenly Craftsmanship:
To implement an algorithm to calculate the transpose $G^{T}$ of a directed graph $G$, we can process the adjacency linked list and adjacency matrix representations separately. Below I will describe the algorithm for each of these cases and provide code examples in Go.
Adjacency linked list notation
Algorithm Steps:
- 1. Create a new adjacency linked list newAdjList to store the transposed graphs.
- 2. 遍历原图的邻接链表 adjList。
- 3. For each edge (u, v), add it to newAdjList[v].
- 4. 返回新的邻接链表 newAdjList。
Go code example:
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
} Runtime Analysis:
The running time of the algorithm is O(|V| + |E|), where |V| is the number of vertices, |E| is the number of edges. This is because we need to iterate through all the vertices and edges at once.
Adjacency matrix notation
Algorithm Steps:
- 1. Create a new adjacency matrix, newAdjMatrix, to store the transposed graph.
- 2. 遍历原图的邻接矩阵 adjMatrix。
- 3. 对于每个元素 adjMatrix[i][j]，将其赋值给 newAdjMatrix[j][i]。
- 4. 返回新的邻接矩阵 newAdjMatrix。
Go code example:
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
} Runtime Analysis:
The running time of the 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, and other functions such as error handling, input and output may need to be added in practical applications. Also, to simplify the code, assume that there are no duplicate edges in the graph, and that the vertex numbers are numbered consecutively starting from 0.
chatgpt：
The following is the algorithm for calculating G^T from Figure G written in Go, and the corresponding adjacency linked list and adjacency matrix representations are given:
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)
} The time complexity of the algorithm is O(V + E), where V is the number of vertices and E is the number of edges. The construction process of a transpose graph requires iterating through all the edges of the original graph and adding them back to the transpose graph, so the total time complexity is proportional to the number of vertices and edges.
as:
Transpose graphs of directed graphs can be represented by two main data structures: adjacency linked lists and adjacency matrices. Below I will introduce the algorithm in each of these cases and provide sample code in Go.
Adjacent linked list representation
For graphs represented by adjacency linked lists, we can transpose the graph by iterating through the adjacency list for each vertex and then adding an inverted edge to each adjacency. The time complexity of this method is O(V + E), where V is the number of vertices and E is the number of edges.
Go sample code:
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
} Adjacency matrix representation
For graphs represented by adjacency matrices, we can transpose them by the rows and columns of the fabric. The time complexity of this method is O(V^2).
Go sample code:
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
} Algorithmic analysis
- • Adjacency linked list: The algorithm needs to iterate through the adjacency list of each vertex, and for each edge, it needs to add a reverse edge to the adjacency list of the adjacency points. If the average length of the adjacency list is k, then the time complexity of the algorithm is O(V + E * k). In the worst-case scenario, k can approach V, where the time complexity is close to O(V^2). In the best-case scenario, k is close to 1 and the time complexity is close to O(E).
- • Adjacency matrices: The algorithm needs to traverse each element of the matrix and swap rows and columns. Since the matrix is VxV, the time complexity is O(V^2).
In practice, the choice of algorithm depends on how sparsity the graph is and the memory available. For sparse graphs, adjacent linked lists may be more memory-efficient; For dense graphs, adjacency matrices may be more efficient.
Mixed elements:
In order to calculate the transpose of $G=(V,E)$ of the directed graph $G^T=(V,E^T)$, we can give the corresponding algorithms for the two representations of adjacency linked lists and adjacency matrices, and analyze their running time.
Adjacency linked list notation
Algorithm description
- 1. Initialize an empty adjacency linked list to store the edges of the transposed chart.
- 2. Traverse all the nodes of the original diagram $G$.
- 3. For each node $u$, traverse all neighbor nodes in its adjacency linked list $v$.
- 4. Add an edge from $v$ to $u$ in the new adjacent linked list.
- 5. Once the traversal is complete, the new adjacency linked list is the transpose diagram $G^T$.
Runtime analysis
- • Time complexity: $O (|.) E|) $, where $|E|$ is the number of sides of the original graph. Because we need to iterate over each edge twice (one read, one write).
Adjacency matrix notation
Algorithm description
- 1. Initialize an adjacency matrix of the same size as the original graph to store the edges of the transposed graph.
- 2. Traverse the adjacency matrix of the original figure $G$.
- 3. For each non-zero element in the matrix (i.e., there is an edge $(u, v)$), the corresponding position $(v, u)$ in the adjacency matrix of the transpose graph is set to a non-zero element.
- 4. Once the traversal is complete, the new adjacency matrix is the transpose graph $G^T$.
Runtime analysis
- • Time complexity: $O (|.) V|^2)$, where $|V|$ is the number of nodes in the original graph. Because we need to iterate through the entire adjacency matrix.
Go language implementation (adjacency linked list notation)
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()
}
} In this code, we define an Edge struct to represent edges, and an AdjacencyList struct to represent an adjacency linked list. The TransposeGraph function takes a parameter of type AdjacencyList and returns an adjacency linked list representation of its transposegraph. In the main function, we create an example plot and calculate and print its transpose plot.