思路：一边遍历，一边倒置边，并添加到新的图中
邻接表实现伪代码：
for each u 属于 Vertex for v 属于 Adj[u] Adj1[v].insert(u);
复杂度：O(V+E);
输入：
3 3 a b b c c a
源代码：
package C22;
import java.util.Iterator;
public class C1_3{
public static Adjacent_List getTransposeGraph(Adjacent_List g){
Adjacent_List Gt = new Adjacent_List(g.getSize());
for(int u=0;u<g.getSize();u++){
Iterator<String> iter = g.getListByVertexIndex(u).iterator();
while(iter.hasNext()){
String vstr = iter.next();
Gt.addEdge(vstr , g.getVertexValue(u)); //添加导致边
}
}
return Gt;
}
public static void main(String[] args) throws Exception {
Adjacent_List adjlist = GraphFactory.getAdjacentListInstance("input\transpose_input.txt");
System.out.println("====原图===");
adjlist.printAllEdges();
Adjacent_List transposeGraph = getTransposeGraph(adjlist);
System.out.println("=====倒置图=====");
transposeGraph.printAllEdges();
}
}二、邻接矩阵实现
思路：遍历二维数组，并A'[i][j] = A[j][i];
伪代码：
for i = 1 to V for j = 1 to V A'[j][i] = A[i][j];
复杂度：O(V^2);
源代码：
package C22;
import java.util.Iterator;
public class C1_3{
public static Adjacent_Matrix getTransposeMatrix(Adjacent_Matrix g){
Adjacent_Matrix Gt = new Adjacent_Matrix(g.getSize());
for(int i=0;i<g.getSize();i++){
for(int j=0;j<g.getSize();j++){
Gt.setEdge(g.getVertexValue(j), g.getVertexValue(i), g.getElement(i, j));
}
}
return Gt;
}
public static void main(String[] args) throws Exception {
Adjacent_Matrix adj_matrix = GraphFactory.getAdjacentMatrixInstance("input\transpose_input.txt");
adj_matrix.printAllEdges();
System.out.println("================");
Adjacent_Matrix Gt = getTransposeMatrix(adj_matrix);
Gt.printAllEdges();
}
}