# 轉置圖

## 查找轉置圖的解決方案類型

### 鄰接表

#### 推薦碼

##### C ++程序查找轉置圖
```#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// Add Edge from node u to v
void addEdge(vector <int> graph[], int u, int v)
{
graph[u].push_back(v);
}

int main()
{
// Construct the Given graph
int n = 7;
vector <int> graph[n];
vector<pair<int,int>> edges = {{0,1},{0,2},{3,2},{3,4},{4,5},{6,5},{6,0}};

for(auto e : edges)

// Print Adjacency list of given Graph
cout<<"The Adjacency List of Given Graph "<<endl;
for(int i=0;i<n;i++)
{
cout<<i<<"->";
for(auto node : graph[i])
cout<<node<<" ";

cout<<endl;
}

// Obtain transpose of the given graph
vector <int> transpose[n];
for(int i=0;i<n;i++)
{
for(auto node : graph[i])
}

// Print Adjacency list of the Transpose
cout<<endl<<"The Adjacency List of Transpose Graph "<<endl;
for(int i=0;i<n;i++)
{
cout<<i<<"->";
for(auto node : transpose[i])
cout<<node<<" ";

cout<<endl;
}

return 0;
}```
```The Adjacency List of Given Graph
0->1 2
1->
2->
3->2 4
4->5
5->
6->5 0

The Adjacency List of Transpose Graph
0->6
1->0
2->0 3
3->
4->3
5->4 6
6->```
##### Java程序查找轉置圖
```import java.util.*;
import java.io.*;

class TutorialCup
{
// Add Edge from node u to v
static void addEdge(ArrayList<ArrayList<Integer>> graph, int u, int v)
{
}

public static void main (String[] args)
{
// Construct the Given graph
int n = 7;
ArrayList<ArrayList<Integer>> graph = new ArrayList<>();

for(int i=0;i<n;i++)

int [][] edges = {{0,1},{0,2},{3,2},{3,4},{4,5},{6,5},{6,0}};

for(int i=0;i<edges.length;i++)

// Print Adjacency list of given Graph
System.out.println("The Adjacency List of Given Graph ");
for(int i=0;i<n;i++)
{
System.out.print(i+"->");

Iterator itr = graph.get(i).iterator();

while(itr.hasNext())
{
int node = (Integer)itr.next();
System.out.print(node+" ");
}

System.out.println();
}

// Obtain transpose of the given graph
ArrayList<ArrayList<Integer>> transpose = new ArrayList<>();

for(int i=0;i<n;i++)

for(int i=0;i<n;i++)
{
Iterator itr = graph.get(i).iterator();

while(itr.hasNext())
{
int node = (Integer)itr.next();
}
}

// Print Adjacency list of the Transpose
System.out.println("\nThe Adjacency List of Transpose Graph ");
for(int i=0;i<n;i++)
{
System.out.print(i+"->");

Iterator itr = transpose.get(i).iterator();

while(itr.hasNext())
{
int node = (Integer)itr.next();
System.out.print(node+" ");
}

System.out.println();
}

}
}```
```The Adjacency List of Given Graph
0->1 2
1->
2->
3->2 4
4->5
5->
6->5 0

The Adjacency List of Transpose Graph
0->6
1->0
2->0 3
3->
4->3
5->4 6
6->```

#### 使用鄰接表對轉置圖進行複雜度分析

1. 時間複雜度：T（n）= O（V + E），鄰接表的迭代遍歷。 因為我們剛剛遍歷了圖中的所有節點。
2. 空間複雜度：A（n）= O（V + E），因為我們需要新的鄰接表來存儲轉置圖。

V =圖形中的頂點數。

E =圖形中的邊數。

### 鄰接矩陣

#### 途徑

1. 使用鄰接矩陣定義圖。
2. 執行鄰接矩陣的轉置以獲得給定圖的轉置。

#### 推薦碼

##### C ++程序查找轉置圖
```#include <iostream>
#include <bits/stdc++.h>
using namespace std;

int main()
{
vector<vector<int>> graph = {{0,1,1,0,0,0,0},
{0,0,0,0,0,0,0},
{0,0,0,0,0,0,0},
{0,0,1,0,1,0,0},
{0,0,0,0,0,1,0},
{0,0,0,0,0,0,0},
{1,0,0,0,0,1,0}};

for(auto node : graph)
{
for(auto neighbor : node)
cout<<neighbor<<" ";

cout<<endl;
}

// Perform Matrix Transpose
for(int i=0;i<graph.size();i++)
{
for(int j=i+1;j<graph[0].size();j++)
swap(graph[i][j],graph[j][i]);
}

// Print the Matrix Transpose
for(auto node : graph)
{
for(auto neighbor : node)
cout<<neighbor<<" ";

cout<<endl;
}

return 0;
}```
```Adjacency Matrix of Given Graph.
0 1 1 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 1 0 1 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 0
1 0 0 0 0 1 0

0 0 0 0 0 0 1
1 0 0 0 0 0 0
1 0 0 1 0 0 0
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 1
0 0 0 0 0 0 0
```
##### Java程序查找轉置圖
```import java.util.*;
import java.io.*;

class TutorialCup
{
public static void main (String[] args)
{
int [][] graph =            {{0,1,1,0,0,0,0},
{0,0,0,0,0,0,0},
{0,0,0,0,0,0,0},
{0,0,1,0,1,0,0},
{0,0,0,0,0,1,0},
{0,0,0,0,0,0,0},
{1,0,0,0,0,1,0}};

for(int i=0;i<graph.length;i++)
{
for(int j=0;j<graph[0].length;j++)
System.out.print(graph[i][j]+" ");

System.out.println();
}

// Perform Matrix Transpose
for(int i=0;i<graph.length;i++)
{
for(int j=i+1;j<graph[0].length;j++)
{
int temp = graph[i][j];
graph[i][j] = graph[j][i];
graph[j][i] = temp;
}
}

// Print the Matrix Transpose
for(int i=0;i<graph.length;i++)
{
for(int j=0;j<graph[0].length;j++)
System.out.print(graph[i][j]+" ");

System.out.println();
}
}
}```
```Adjacency Matrix of Given Graph.
0 1 1 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 1 0 1 0 0
0 0 0 0 0 1 0
0 0 0 0 0 0 0
1 0 0 0 0 1 0

0 0 0 0 0 0 1
1 0 0 0 0 0 0
1 0 0 1 0 0 0
0 0 0 0 0 0 0
0 0 0 1 0 0 0
0 0 0 0 1 0 1
0 0 0 0 0 0 0```

#### 使用鄰接矩陣的轉置圖複雜度分析

1. 時間複雜度：T（n）= O（V x V）這裡，我們還遍歷了圖中每個節點的所有節點。 因此，O（V * V），即多項式時間複雜度。
2. 空間複雜度：A（n）= O（1），不使用額外的空間。 在這裡，我們完成了一個就地任務，我們替換了初始矩陣中的值。 因此佔據了恆定的空間。

V =圖形中的頂點數。

E =圖形中的邊數。