2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
Dans la représentation de liste chaînée de contiguïté, chaque sommet vvv Il existe une liste chaînée, et chaque nœud de la liste chaînée représente un esclave vvv Bord de départ.afin de calculer GTG^TgT, nous devons traverser GGg pour chaque bord de , et en inversant la direction du bord, ajoutez à GTG^TgT dans la liste chaînée correspondante.
Aller à l'implémentation du langage：
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)
}
}
complexité temporelle：
Dans la représentation matricielle de contiguïté, nous utilisons un tableau bidimensionnel pour stocker les informations de bord, où matrix[u][v] Indique s'il y a une ligne de euhtoi arriver vvv côté.afin de calculer GTG^TgT, nous parcourons le triangle supérieur (ou le triangle inférieur, selon vos habitudes de représentation matricielle) de la matrice et inversons la direction des bords, c'est-à-dire matrix[u][v] La valeur est attribuée àmatrixT[v][u]。
Aller à l'implémentation du langage(Version simplifiée, ne prend en compte que l'existence et ne prend pas en compte les poids des bords) :
// 假设使用二维布尔切片表示邻接矩阵
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函数
complexité temporelle：
Pour un graphe orienté représenté par une liste d'adjacence, on peut ajouter les sommets adjacents de chaque sommet à la liste d'adjacence du sommet transposé du nouveau graphe en parcourant la liste d'adjacence de chaque sommet. Les étapes spécifiques sont les suivantes :
Analyse de complexité temporelle : parcourir chaque sommet du graphe d'origine nécessite O ( ∣ V ∣ ) O(|V|)O(∣V∣) Le temps nécessaire pour parcourir la liste de contiguïté de chaque sommet est O ( ∣ E ∣ ) O(|E|)O(∣E∣) temps, donc la complexité temporelle totale est O ( ∣ V ∣ + ∣ E ∣ ) O(|V| + |E|)O(∣V∣+∣E∣)。
Pour un graphe orienté représenté par une matrice de contiguïté, on peut obtenir la matrice de contiguïté d'un nouveau graphe en transposant la matrice de contiguïté du graphe d'origine. Les étapes spécifiques sont les suivantes :
Analyse de complexité temporelle : parcourir la matrice d'adjacence du graphe d'origine nécessite O ( ∣ V ∣ 2 ) O(|V|^2)O(∣V∣2) temps, donc la complexité temporelle totale est O ( ∣ V ∣ 2 ) O(|V|^2)O(∣V∣2)。
Voici le code implémenté en langage 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
}
Dans la représentation de liste chaînée de contiguïté, nous pouvons parcourir directement l'image d'origine GGgLa liste de contiguïté de chaque nœud est ensuite ajoutée au nouveau graphique après avoir inversé la direction de chaque arête. GTG^{T}gTsur le nœud correspondant.
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
}
La complexité temporelle totale est donc O ( ∣ V ∣ + ∣ E ∣ ) O(|V| + |E|)O(∣V∣+∣E∣)。
En notation matricielle de contiguïté, nous pouvons créer une nouvelle matrice de contiguïté puis parcourir l'image d'origine GGgmatrice de contiguïté, chaque élément de la matrice (i, j) (i, j)(je,j)affecté à la nouvelle matrice (j, i) (j, i)(j,je)position, complétant ainsi l’inversion du bord.
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
}
La complexité temporelle totale est donc O ( ∣ V ∣ 2 ) O(|V|^2)O(∣V∣2)。
Pour la représentation de liste chaînée de contiguïté, la complexité temporelle de l'algorithme de transposition est O ( ∣ V ∣ + ∣ E ∣ ) O(|V| + |E|)O(∣V∣+∣E∣), et pour la représentation matricielle de contiguïté, la complexité temporelle de l'algorithme de transposition est O ( ∣ V ∣ 2 ) O(|V|^2)O(∣V∣2) .Dans les applications pratiques, si le graphique est relativement clairsemé (c'est-à-dire ∣ E ∣ |E|∣E∣beaucoup plus petit que ∣ V ∣ 2 |V|^2∣V∣2 ), il serait plus efficace d'utiliser la représentation de liste chaînée de contiguïté.Si le graphique est dense (c'est-à-dire ∣ E ∣ |E|∣E∣près ∣ V ∣ 2 |V|^2∣V∣2), alors la représentation matricielle de contiguïté peut être plus appropriée.
Dans la représentation graphique, les listes chaînées de contiguïté et les matrices de contiguïté sont toutes deux des méthodes couramment utilisées. Les listes chaînées de contiguïté sont utilisées pour représenter des graphiques non orientés et orientés, tandis que les matrices de contiguïté sont généralement utilisées pour représenter des graphiques non orientés. Pour la transposition d'un graphe orienté, nous pouvons opérer séparément sur la liste chaînée d'adjacence et la matrice d'adjacence.
Pour un graphe orienté représenté par une liste chaînée de contiguïté, la transposition du graphe peut être réalisée en parcourant chaque sommet du graphe d'origine et en modifiant les arêtes sortantes du graphe d'origine en arêtes entrantes.
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)
}
}
}
Pour un graphe orienté représenté par une matrice de contiguïté, la transposition du graphe peut être réalisée en transformant chaque ligne du graphe d'origine en la colonne correspondante du nouveau graphe.
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)
}
}
Pour la transposition d'une liste chaînée de contiguïté, la complexité temporelle de l'algorithme est O(E), où E est le nombre d'arêtes dans le graphe. En effet, chaque arête doit être traversée une fois.
Pour la transposition de la matrice de contiguïté, la complexité temporelle de l'algorithme est O(V^2), où V est le nombre de sommets dans le graphe. En effet, chaque élément de la matrice doit être parcouru une fois et la taille de la matrice est V×V.
Ces algorithmes sont tous efficaces et exécutés
Implémenter un algorithme pour calculer un graphe orienté GGg transposition de GTG^{T}gT , nous pouvons traiter respectivement les deux représentations de la liste chaînée de contiguïté et de la matrice de contiguïté. Ci-dessous, je décrirai respectivement les algorithmes pour ces deux cas et fournirai des exemples de code en langage Go.
newAdjList Utilisé pour stocker le graphique transposé.adjList。(u, v), ajoutez-le à newAdjList[v] milieu.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
}
Le temps d'exécution de cet algorithme est O(|V| + |E|), où |V| est le nombre de sommets et |E| est le nombre d'arêtes. En effet, nous devons parcourir tous les sommets et arêtes une fois.
newAdjMatrix Utilisé pour stocker le graphique transposé.adjMatrix。adjMatrix[i][j], attribuez-le à 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
}
Le temps d'exécution de cet algorithme est O(|V|^2), où |V| est le nombre de sommets. En effet, nous devons parcourir toute la matrice de contiguïté et la taille de la matrice de contiguïté est de |V| x |V|.
L'exemple de code ci-dessus ne constitue que la partie centrale de l'algorithme. Dans les applications réelles, d'autres fonctions telles que la gestion des erreurs, l'entrée et la sortie peuvent devoir être ajoutées. De plus, pour simplifier le code, on suppose qu’il n’y a pas d’arêtes répétées dans le graphique et que les numéros de sommets sont numérotés consécutivement à partir de 0.
Ce qui suit est un algorithme écrit en langage Go pour calculer G ^ T à partir du graphique G, et les méthodes de liste chaînée de contiguïté et de représentation matricielle de contiguïté correspondantes sont également données :
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)
}
La complexité temporelle de cet algorithme est O(V + E), où V est le nombre de sommets et E est le nombre d'arêtes. Le processus de construction du graphe transposé nécessite de parcourir toutes les arêtes du graphe d'origine et de les ajouter au graphe transposé à l'envers, de sorte que la complexité temporelle totale est proportionnelle au nombre de sommets et d'arêtes.
Les graphes transposés de graphes orientés peuvent être représentés par deux structures de données principales : les listes chaînées de contiguïté et les matrices de contiguïté. Ci-dessous, je présenterai respectivement les algorithmes dans ces deux cas et fournirai un exemple de code en langage Go.
Pour un graphe représenté par une liste chaînée de contiguïté, nous pouvons transposer le graphe en parcourant la liste de contiguïté de chaque sommet puis en ajoutant une arête inverse à chaque point de contiguïté. La complexité temporelle de cette méthode est O(V + E), où V est le nombre de sommets et E est le nombre d’arêtes.
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
}
Pour un graphique représenté par une matrice de contiguïté, nous pouvons implémenter la transposition en échangeant les lignes et les colonnes de la matrice. La complexité temporelle de cette méthode est 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
}
Dans les applications pratiques, l'algorithme à choisir dépend de la rareté du graphique et de la mémoire disponible. Pour les graphiques clairsemés, les listes chaînées de contiguïté peuvent être plus efficaces en termes de mémoire ; pour les graphiques denses, les matrices de contiguïté peuvent être plus efficaces.
Pour calculer un graphe orienté G = ( V , E ) G=(V,E)g=(V,E) transposition de GT = ( V , ET ) G^T=(V,E^T)gT=(V,ET), nous pouvons donner des algorithmes correspondants pour les deux méthodes de représentation de la liste chaînée de contiguïté et de la matrice de contiguïté respectivement, et analyser leur temps d'exécution.
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()
}
}
Dans ce code, nous définissons un Edge structure pour représenter les bords, et unAdjacencyList Structure pour représenter une liste chaînée de contiguïté.TransposeGraph La fonction accepte unAdjacencyList paramètre de type et renvoie une représentation de liste chaînée de contiguïté de son graphe transposé.existermain fonction, nous créons un exemple de graphique, calculons et imprimons son graphique transposé.
Il se consacre à la recherche technologique depuis plus de 30 ans et maîtrise divers langages tels que java, linux, javascript, php, css, etc. Il a apporté de nombreuses contributions dans le domaine de l'open source. station de documentation pour les développeurs pour partager certains problèmes de développement technologique pour référence future.
