算法设计与分析学习笔记05 | 8月更文挑战

这是我参与8月更文挑战的第5天，活动详情查看： 8月更文挑战

算法设计与分析题目1：

有向图G的邻接表生成G的反向邻接表

1. 输入有向图的顶点数和边数，及各条边的头和尾

2. 设计函数使用邻接表表示建立和输出有向图

3. 设计函数使用邻接表生成有向图的反向邻接表

4.调用函数，输出反向邻接表表示的有向图

根据有向图G的邻接表生成G的反向邻接表的算法如下：
核心代码及注释：

//将有向图的出度邻接表改为按入度建立的反向邻接表

void InvertAdjGraph(AdjGraph gout)

{

 //反向邻接表表示的有向图gin

      AdjGraph gin;

  gin.n = gout.n;

  gin.e = gout.e;

    //设有向图有 n 个顶点，建逆反向邻接表的顶点向量

for (int i = 0; i < gin.n; i++)

{

gin.VexList[i].data = gout.VexList[i].data;

gin.VexList[i].adj = NULL;

}

    //邻接表转为反向邻接表

for (int i = 0; i < gin.n; i++)

//取指向邻接点的指针

{

EdgeNode *p = gout.VexList[i].adj;

        while (p != NULL)

{

int j = p->dest;

//申请结点空间

        EdgeNode *s = (EdgeNode *)malloc(sizeof(EdgeNode));

            s->dest = i;

            s->link = gin.VexList[j].adj;

            gin.VexList[j].adj = s;

//下一个邻接点

            p = p->link;

         }

}

cout << "使用反向邻接表表示有向图G" << endl;

ShowGraph(gin);

}
复制代码

测试结果截图及分析：

本算法主要是使用邻接表来实现的图的建立的，首先要获取图的顶点数和相应的边数，以及每条边的头和尾。之后通过设计函数来建立邻接表表示的有向图G,邻接表表示最主要的是需要将所有在同一个顶点发出的边的顶点链接起来，之后需要将邻接表中的每一条边头和尾逆置，重新进行链接成新的邻接表表示的有向图，这是就是反向邻接表了，最后只需要通过调用函数来打印输出反向邻接表表示的有向图即可。