算法导论 练习22.1-5

       22.1-5 有向图G = (V, E)的平方图是图G2 = (V, E2)，该图满足下列条件：(u, w)属于E2当且仅当v属于V，有(u, v)属于E，且(v, w)属于E。亦即，如果图G中顶点u和w之间存在着一条恰包含两条边的路径时，则G2必包含该边(u, w)。针对图G邻接表和邻接矩阵两种表示，分别写出根据G产生G2的有效算法，并分析所给出算法的运行时间。

针对邻接矩阵的算法：

void GtoG2(int G[V][V], int G2[V][V], int V)

{

int r, c, c1;

memcpy(G, G2, V*V);

for(r = 0; r < V; r++)

{

for(c = 0; c < V; c++)

if(G[r][c] == 1)

{

for(c1 = 0; c1 < V; c1++)

if(G[c][c1] == 1)    G2[r][c1] = 1;

}

}

}

该算法的时间复杂度为O(V*V*V)。

针对邻接表的算法：

typedef struct node

{

int data;

struct node *next;

}VNode;

void GtoG2(VNode G[], VNode G2[], int V)

{

int i;

VNode *srcline, *dstline, *dstp, *tmp;

for(i = 0; i < V; i++)

{

srcline = G[i].next;

while(srcline != NULL)

{

dstline = G[srcline->data - 1].next;

while(dstline != NULL)

{

dstp = G2[i].next;

while(dstp != NULL && dstp->data != dstline->data)

dstp = dstp->next;

if(dstp == NULL)

{

tmp = G2[i].next;

G2[i].next = (VNode *)malloc(sizeof(VNode));

G2[i].next->data = dstline->data;

G2[i].next->next = tmp;

}

dstline = dstline->next;

}

srcline = srcline->next;

}

}

}

该算法的时间复杂度为O(V*(V+E))

这两种算法的实现，请参考：算法导论 练习22.1-5算法的实现