有向图的转置

        所谓有向图的转置，就是将本该从u指向v的边，修改为v指向u，实现访问方向的倒转，此即为图的转置。（更加学术性的定义参见《算法导论》第四版 p343页 22.1-3）

        由于图的实现方式不同，实现图的转置的方式也不同。图的存储方式主要分为两种，第一种是邻接链表的方式，另外一种是邻接矩阵的方式，前者涉及到大量指针的修改，比较繁琐，后者只涉及到矩阵元素的交换，比较简单。

        下面，分别对两种有向图的转置进行介绍：

一、邻接矩阵的转置 

        图的邻接矩阵表示法是通过一个表示边集是否邻接的二维素组实现的。如果u->v有一条边，那么在邻接矩阵中adj[u][v]=1，反之为0（我们在这里讨论的都是无权图）。

        因此，实现图的转置，只需要将邻接矩阵中u->v和v->u的内容进行交换。例如，u->v有边，而v->u没有边，交换的结果会导致u->v没有边，同时v->u有边，即实现了图的转置。

        这种方法的正确性是毋庸置疑的，但其中有一个小细节值得我们关注。 我们在进行遍历的过程中，实则是在操纵u时就已经同时操纵了v，即我们不再需要访问节点v，如果重复访问，将会导致反转后再反转，即负负得正，没有反转。因此，我们只需要遍历一半矩阵即可，这同时降低了时间复杂度。为O(V^2/2+V)=O(V^2)，其中V表示顶点数，同样也是矩阵的一维规模。

        转置部分代码：

//图的转置 通过交换矩阵下标的方式 （只访问图的一半 否则会导致将修改完的内容又重新转置 复原）
void GraphTrans(Graph graph){int size = graph->ver;for(int i=0;iEdge[i][j].weight;graph->Edge[i][j].weight = graph->Edge[j][i].weight;graph->Edge[j][i].weight = temp;}}
}

        基于C语言实现的图的邻接矩阵表示及转置等操作的完整代码如下：

//
// Created by 周龙 on 2021/12/11.
//#include 
#include 
#define MAXSIZE 100
#define INF 12042
//顶点表和边表两个都需要 顶点表用于存放顶点的内容 边表用于修改顶点与边的关系
typedef char Item;
typedef struct{Item info[MAXSIZE];
}*Vertex,VertexNode;typedef struct{int weight;
}*Edge,EdgeNode;//定义图
typedef struct{EdgeNode Edge[MAXSIZE][MAXSIZE];//定义矩阵 表示边VertexNode Vertex;//顶点数组int ver;
}*Graph,GraphNode;//按图的顶点数量进行初始化
Graph Initial(int ver);//以给定的顶点修改图
void Create(Graph graph,EdgeNode edge[6][6],int size);//图的转置
void GraphTrans(Graph graph);//图的遍历
void Traverse(Graph graph);//主函数 用于测试
int main() {int ver = 6;Graph graph = Initial(ver);//有10个顶点int Matrix[6][6]={{0,1,0,1,0,0},{0,0,0,0,0,0},{0,1,0,0,1,1},{0,1,0,0,0,0},{0,1,0,1,0,0},{0,1,0,0,0,1}};EdgeNode edge[6][6];for(int i=0;i<6;i++){for(int j=0;j<6;j++){edge[i][j].weight = Matrix[i][j];}}Create(graph,edge,ver);//根据边集矩阵创建图printf("Before trans:\n");Traverse(graph);//遍历图GraphTrans(graph);//图的转置putchar('\n');printf("After trans:\n");Traverse(graph);return 0;
}//图的转置 通过交换矩阵下标的方式 （只访问图的一半 否则会导致将修改完的内容又重新转置 复原）
void GraphTrans(Graph graph){int size = graph->ver;for(int i=0;iEdge[i][j].weight;graph->Edge[i][j].weight = graph->Edge[j][i].weight;graph->Edge[j][i].weight = temp;}}
}//按图的顶点数量进行初始化
Graph Initial(int ver){Graph graph = (Graph)malloc(sizeof(GraphNode));graph->ver = ver;for(int i=0;iVertex.info[i] = (char)((int)'a'+i);for(int j=0;jEdge[i][j].weight = 0;//置为0 表示全都没有边}}return graph;
}//以给定的边集关系修改图
void Create(Graph graph,EdgeNode edge[6][6],int size){for(int i=0;iEdge[i][j] = edge[i][j];}}graph->ver = size;
}//图的遍历
void Traverse(Graph graph){int size = graph->ver;for(int i=0;iEdge[i][j].weight!=0){printf("%c -> %c\n",graph->Vertex.info[i],graph->Vertex.info[j]);}}}
}

        代码运行结果：

        可见，曾经顺序的关系都已经被逆转了。 

二、邻接表的转置 

        除了上述的使用邻接矩阵表示的边集数组表示图之外，还可以借助链表表示图这一数据结构。维护一个顶点数组，其含有一个next指针，指向其边集。如果存在边，则向顶点数组的next中插入一个节点，即形成边集。

        由于这些节点都是已经创建好的，因此我们在进行转置的时候只需要更改指向就可以了。更改过指向的节点要进行标记（本文中在边集中添加IsReverse进行标记），防止对一个节点进行多次反转，同样会导致负负得正，即没有修改。

        转置部分代码如下：

//反转链表
void Reverse(Graph graph) {/** 由于边表都是已经分配的内存 只修改链接即可* 可以使用visit来标记是否已经被转置 但比较麻烦* 对于转置后的边和原有相同指向的边不易辨别* 考虑在edge中加入IsReverse来判断一个节点是否被反转过了* 每次删除在头部O(1) 每次插入在中部O(V) 这个时间复杂度值得好好讨论* 时间复杂度大约为O(V+E) 不是特别准确*/int buf[graph->v][graph->v];for (int i = 0; i < graph->v; i++) {for (int j = 0; j < graph->v; j++) {buf[i][j] = 0;//表示u v 节点已经被转置了 不需要重复转置}}for (int i = 0; i < graph->v; i++) {Edge temp = graph->vertex[i].next;while (temp) {//temp就是待转置的节点if (temp->IsReverse) {//如果节点已经是被转置过了 则无需转置 且转置完成break;} else {int v = temp->v;temp->v = temp->u;temp->u = v;//修改顶点的指向graph->vertex[i].next = temp->next;//将节点插入temp->IsReverse = 1;temp->next = NULL;//避免重复指向InsertNode(graph, temp);}temp = graph->vertex[i].next;}}
}//向反转链表中插入节点
void InsertNode(Graph graph, Edge edge) {int u = edge->u;//转置 将该边插入到ver[u]上 u、v已经转置修改过if (!graph->vertex[u].next||graph->vertex[u].next->IsReverse) {edge->next = graph->vertex[u].next;//和该边的尾部链接graph->vertex[u].next = edge;//指向该边} else {Edge temp = graph->vertex[u].next;//如果被反转过 则直接插入即可while (temp->next&&!temp->next->IsReverse) {temp = temp->next;}edge->next = temp->next;//链接尾部temp->next = edge;//插入尾部}
}

        基于C语言实现图的邻接矩阵表示方式及图的转置等操作的完整代码如下：

#include 
#include //反转链表
typedef _Bool bool;
enum Color{White,Gray,Black
};
//图的邻接表表示方法
//边集
typedef struct edge{int weight;//权重//边u、vint u;//从u起int v;//到v止struct edge*next;//邻接的边int IsReverse;
}EdgeNode,*Edge;//顶点集
typedef struct{int color;//颜色 用于在DFS中判断有无后向边int u;//顶点下标Edge next;//指向边集的指针int d;
}VertexNode,*Vertex;//定义图
typedef struct{int v;int e;Vertex vertex;//顶点集
}GraphNode,*Graph;//图的初始化 以ver为点集 以edge为边集
Graph Initial(int ver);//向图中插入边 建立图
bool Insert(Graph graph,Edge node);//向待逆转的表中插入该逆转的节点
void InsertNode(Graph graph,Edge edge);void Reverse(Graph graph);//有向图的转置//深度优先遍历
void DepthFirstSearch(Graph graph);//深度优先遍历的递归辅助函数
void DFS_AUX(Graph graph,Vertex node);int main() {int ver = 5;//顶点数为5Graph graph = Initial(ver);//初始化graphEdge *node = (Edge*)malloc(sizeof(Edge)*ver*2);//分配节点//插入邻接边集 构造形如0->1->2->3->4的有向图 或者无向图for(int i=0;i+1u=i;node[i]->v=i+1;node[i]->next=NULL;Insert(graph,node[i]);//这里如果注释掉就构造有向图 如果解除注释就是无向图//node[i+1] = (Edge) malloc(sizeof(EdgeNode));//node[i+1]->u=i+1;node[i+1]->v=i;node[i+1]->next=NULL;//Insert(graph,node[i+1]);}printf("----------------\n");printf("DFS:\n");DepthFirstSearch(graph);//深度优先搜索 //反转图的邻接矩阵Reverse(graph);printf("\nAfter Reverse:\n");printf("----------------\n");printf("DFS:\n");DepthFirstSearch(graph);return 0;
}//反转链表
void Reverse(Graph graph) {/** 由于边表都是已经分配的内存 只修改链接即可* 可以使用visit来标记是否已经被转置 但比较麻烦* 对于转置后的边和原有相同指向的边不易辨别* 考虑在edge中加入IsReverse来判断一个节点是否被反转过了* 每次删除在头部O(1) 每次插入在中部O(V) 这个时间复杂度值得好好讨论* 时间复杂度大约为O(V+E) 不是特别准确*/int buf[graph->v][graph->v];for (int i = 0; i < graph->v; i++) {for (int j = 0; j < graph->v; j++) {buf[i][j] = 0;//表示u v 节点已经被转置了 不需要重复转置}}for (int i = 0; i < graph->v; i++) {Edge temp = graph->vertex[i].next;while (temp) {//temp就是待转置的节点if (temp->IsReverse) {//如果节点已经是被转置过了 则无需转置 且转置完成break;} else {int v = temp->v;temp->v = temp->u;temp->u = v;//修改顶点的指向graph->vertex[i].next = temp->next;//将节点插入temp->IsReverse = 1;temp->next = NULL;//避免重复指向InsertNode(graph, temp);}temp = graph->vertex[i].next;}}
}//向反转链表中插入节点
void InsertNode(Graph graph, Edge edge) {int u = edge->u;//转置 将该边插入到ver[u]上 u、v已经转置修改过if (!graph->vertex[u].next||graph->vertex[u].next->IsReverse) {edge->next = graph->vertex[u].next;//和该边的尾部链接graph->vertex[u].next = edge;//指向该边} else {Edge temp = graph->vertex[u].next;//如果被反转过 则直接插入即可while (temp->next&&!temp->next->IsReverse) {temp = temp->next;}edge->next = temp->next;//链接尾部temp->next = edge;//插入尾部}
}//图的初始化 以ver为点集 以edge为边集
Graph Initial(int ver) {if (ver <= 0) {fprintf(stderr, "Invalid vertex number.\n");return NULL;}Graph graph = (Graph) malloc(sizeof(GraphNode));//创建图graph->v = ver;graph->e = 0;//没有边graph->vertex = (Vertex) malloc(sizeof(VertexNode) * ver);for (int i = 0; i < ver; i++) {graph->vertex[i] = (VertexNode) {White, i, NULL};graph->vertex[i].next = NULL;graph->vertex[i].color = White;}return graph;
}//向图中插入边 建立图
bool Insert(Graph graph, Edge node) {//直接头插即可if (node == NULL) {fprintf(stderr, "The node is null\n");return 0;}if (node->u < 0 || node->u >= graph->v || node->v < 0 || node->v >= graph->v) {fprintf(stderr, "Invalid index of vertex\n");return 0;}int index = node->u;node->IsReverse = 0;//未被逆转graph->e++;node->next = graph->vertex[index].next;graph->vertex[index].next = node;return 1;
}//深度优先遍历
void DepthFirstSearch(Graph graph) {//对所有的节点着色int size = graph->v;//顶点数for (int i = 0; i < size; i++) {graph->vertex[i].color = White;//着白色}for (int i = 0; i < size; i++) {if (graph->vertex[i].color == White) {DFS_AUX(graph, &graph->vertex[i]);printf("\n");}}
}//标定从哪个顶点开始访问 顶点表和边表
void DFS_AUX(Graph graph, Vertex node) {//处理第一次访问的节点node->color = Gray;//着为灰色printf("%d ", node->u);//开始遍历其邻接的节点作为子树的根Edge temp = node->next;while (temp) {//避免重复访问if (graph->vertex[temp->v].color == White) {DFS_AUX(graph, &graph->vertex[temp->v]);//递归地访问}temp = temp->next;}node->color = Black;
}

        运行结果如下： 

      可以看到，在反转前的DFS能够按0->1->2->3->4的方式访问到链表，反转后，由于0->1的边被反转，不存在有效的边，所以只能以0-4为根生成多个连通子图。可见，我们真的实现了图的转置。

        欢迎大家指正！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！