22.1-4 给定一个多重图G = (V, E)的邻接表表示，给出一个具有O(V+E)时间的算法，来计算其“等价”的无向图G' = (V, E')的邻接表表示，其中E'包哈E中所有的边，且将两个顶点之间的所有所有多重边用一条边代表，并去掉E中所有的环。
该算法如下：
typedef struct node
{
int data;
struct node *pre;
struct node *next;
}VNode;
void Transpose(VNode Adj[], VNode newAdj[], int V)
{
int i;
for(i = 0; i < V; i++)
{
VNode *p = Adj[i].next;
VNode *tmp;
while(p != NULL)
{
/* 消去环和多重边 */
while(p->data == Adj[i].data || p->pre->data == p->data)
{
tmp = p->pre->next = p->next;
free(p);
p = tmp;
}
p = p->next;
}
}
}
阅读(2476) | 评论(0) | 转发(0) |
