有向图G=（V，E）的转置是图GT=(V，ET)，其中边<u，w>∈ET当且仅当<w，u>∈E，即GT就是G的所有边反向所组成的图。请按照相邻矩阵和邻接表两种表示法写出从G计算GT的有效算法，并确定算法的时间代价。

相邻矩阵

#include 
    
     #define MAX_VALUE 0//当两个点不相连是路径的权为0#define MAX_NUM 100//最多可存放点的个数typedef char node_type; typedef struct matrix{    node_type vertex[MAX_NUM];//节点信息    int arcs[MAX_NUM][MAX_NUM];//矩阵    int vertexs, brim;//节点数,边数} Graph; bool visit[MAX_NUM]= {
   false};void create(Graph *graph);void printMatrix(Graph *graph);//打印矩阵状态bool transpose(Graph *,Graph *); //转置函数void init(Graph *);  //自定义一个初始化图，也可以使用create自定义图 int main(void){    Graph graph,graphTrans;    // create(&graph);  //自定义图    init(&graph);  //初始化一个图    printf("初始图的邻接矩阵为:\n");    printMatrix(&graph);    transpose(&graph,&graphTrans);    printf("转置后图的邻接矩阵为：\n");    printMatrix(&graphTrans);    return 0;}void init(Graph *graph){    graph->vertexs = 4;    for (int i = 0; i < graph->vertexs; i++ )//初始化矩阵        for ( int j = 0; j < graph->vertexs; j++ )            graph->arcs[i][j] = MAX_VALUE;    graph->arcs[0][3] = 1;    graph->arcs[1][0] = 1;    graph->arcs[1][2] = 1;    graph->arcs[2][0] = 1;    graph->arcs[2][1] = 1;    graph->brim = 5;}  void create(Graph *graph){    int num;    char c;    printf("输入节点个数:\n");    scanf("%d", &graph->vertexs);    getchar();//吃掉回车符    printf("输入节点信息:\n");    for (int i = 0; i < graph->vertexs; i++ )        scanf("%c", &graph->vertex[i]);    getchar();    for (int i = 0; i < graph->vertexs; i++ )//初始化矩阵        for ( int j = 0; j < graph->vertexs; j++ )            graph->arcs[i][j] = MAX_VALUE;    graph->brim = 0;//初始化边数    for (int i = 0; i < graph->vertexs; i++ )    {        printf("输入与%c节点相邻的节点与权值,输入“.”号键结束\n", graph->vertex[i]);        for (int j = 0; j < graph->vertexs; j++ )        {            scanf("%c", &c);            if ( c == '.' )            {                getchar();                break;            }            scanf("%d", &num);            for (int k = 0; k < graph->vertexs; k++ )                if ( graph->vertex[k] == c )                {                    graph->arcs[i][k] = num;                    graph->brim++;                }            getchar();        }    }    // graph->brim /= 2;  //对应无向图}void printMatrix(Graph *graph)//打印矩阵状态{    for ( int i = 0; i < graph->vertexs; i++ )    {        for ( int j = 0; j < graph->vertexs; j++ )            printf("%d ", graph->arcs[i][j]);        printf("\n");    }}bool transpose(Graph *g, Graph *gt){    if(g == NULL || gt == NULL){        return false;     }    gt->vertexs = g->vertexs;    gt->brim = g->brim;    for(int i=0;i
     
      vertexs;i++){        for(int j=i+1;j
      
       vertexs;j++){            gt->arcs[i][j] = g->arcs[j][i];            gt->arcs[j][i] = g->arcs[i][j];        }    }    return true;}复制代码
      
     
    

可见两次循环遍历了顶点，算法复杂度为O(n²)

邻接表

#include 
    
     using namespace std; #define  N 4#define INFINITE 0//顶点结点结构  struct Vertex  {      Vertex * next;/*指向下一个顶点*/    int id;/*节点的标志*/    Vertex():next(NULL),id(0){}  };   //图结构struct Graph{    Vertex *Adj[N];//N个顶点及邻接点头指针    int p[N];//指向遍历树节点的父结点     int d[N];/*节点发现时间*/    int f[N];/*节点结束遍历时间*/    Graph()    {          for(int i = 0; i < N; i++)          {            Adj[i] = new Vertex;            d[i] = 0;            f[i] = 0;            p[i] = 0;        }    }    ~Graph()      {          for(int i = 0; i < N; i++)              delete Adj[i];      }  }; void Print(Graph *g);void Init(Graph *g);bool InsertEdge(Graph *g , int start,int end);bool TransposedMap(Graph *g, Graph *gt);int main(int argc, char const *argv[]){    Graph g;    Graph transG;    Init(&g);    printf("初始的邻接表为\n");    Print(&g);    TransposedMap(&g, &transG);    printf("转置后的邻接表为\n");     Print(&transG);    return 0;}void Init(Graph *g){    Vertex *temp = new Vertex;    temp->id = 3;    g->Adj[0]->next = temp;    temp = new Vertex;    temp->id = 0;    temp->next = new Vertex;    g->Adj[1]->next = temp;    temp = temp->next;    temp->id = 2;    temp = new Vertex;    temp->id = 0;    temp->next = new Vertex;    g->Adj[2]->next = temp;    temp = temp->next;    temp->id = 1;} void Print(Graph *g){    for(int i=0;i
     
      ", i);        Vertex *p = g->Adj[i]->next;        while(p!=NULL){            printf(" %d ", p->id);            p = p->next;        }        printf("\n");    }    printf("\n");}//插入边bool InsertEdge(Graph *g , int start,int end){    Vertex* v = new Vertex();    v->id = end;    Vertex* tmp = g->Adj[start];    while(tmp->next !=NULL)    {        tmp = tmp->next;    }    tmp->next =v;    return true;} /*图的转置方法*/bool TransposedMap(Graph *g,Graph *gt){    if((g == NULL) || (gt == NULL))    {        return false;    }    for(int i=0;i
      
       Adj[i]->next;        while(v!=NULL)        {            InsertEdge(gt,v->id,i);            v = v->next;        }    }    return true;}复制代码
      
     
    

可以看出循环了所有的边，算法复杂度为O（E），E为边的数目。