37.2° Blog

1. 删除弧（邻接表）

问题

G是一个使用邻接表存储结构存储的无向图，设计算法删除G中顶点src到dest的边。

分析

• 邻接表就是链表的集合(数组)；
• 访问src对应的头节点，删除src链中为dst的数据结点；
• 访问dst对应的头节点，删除dst链中为src的数据结点；

算法思想

• 调用两次删除一条弧的函数，即可删除邻接表中无向图中的两条弧；
• 删除邻接表其中一条弧时，分两种情况讨论；
• 如果删除结点是头结点的下一个，为防止链断开，需要特殊处理；
• 如果删除的结点不是头节点的下一个，需要循环链表，查找要删除的结点，注意保存父节点。

代码

// 删除邻接表图中的一条边
bool deleteALGOneArc(ALGraph* G, VertexType src, VertexType dst)
{
    if (G == NULL)
        return false;
    ArcNode* pNextArcNode = G->vertices[src].first;
    // 如果删除的结点在头结点之后
    if (pNextArcNode->adjvex == dst)
    {
        G->vertices[src].first = pNextArcNode->next;
        //free(pNextArcNode);
        //return true;
    }
    // 如果删除的结点不在头结点
    else
    {
        ArcNode* ppNextArcNode = pNextArcNode;
        while (pNextArcNode != NULL && pNextArcNode->adjvex != dst)
        {
            ppNextArcNode = pNextArcNode;
            pNextArcNode = pNextArcNode->next;
        }
        ppNextArcNode->next = pNextArcNode->next;
    }
    free(pNextArcNode);
    return true;
}

// 删除邻接表无向图中的边（两条）
bool deleteALG2Arc(ALGraph* G, VertexType src, VertexType dst)
{
    if (G == NULL)
        return false;
    if (G->kind != UDG)
        return false;
    return deleteALGOneArc(G, src, dst) && deleteALGOneArc(G, dst, src);
}

2.alG转化为mG

问题

设计算法将邻接表表示的网alG转化为邻接矩阵表示的网mG。

分析

要知道每一条链头结点和弧结点之间关联起来后构成的信息。

• 扫描邻接表数组vertice表的Vi行；
• 如果链中存在弧结点(Vj,Wj)，
• 那么就在邻接矩阵的二维数组arcs的第Vi行Vj列写入Wj，
• 代表Vi->Vj存在一条Wj的边。

算法思想

• 宏观信息（类型、顶点数量、边数量）对应较为简单
• 处理顶点向量：将邻接表中的顶点信息存入到邻接矩阵顶点向量对应的位置就即可；
• 边信息：先读取邻接表中源点（src）、终点（dst）和权值信息，将数据存入邻接矩阵中(src,dst)位置存weight

代码

// 邻接表表示的网alG转化为邻接矩阵表示的网mG
bool ALGraph2MGraph(ALGraph alG, MGraph* mG)
{
    if (mG == NULL)
        return false;
    // 宏观信息，图的类型，顶点数量，边数量
    mG->arcnum = alG.arcnum;
    mG->kind = alG.kind;
    mG->vexnum = alG.vexnum;

    // 微观信息：mG的顶点向量、mG的边信息
    VertexType src = 0;     // 源点信息
    VertexType dst = 0;     // 终点信息
    int weight = 0;         // 权重信息
    for (int i = 1; i <= alG.vexnum; i++)
    {
        // 处理顶点向量
        // 将邻接表中的顶点信息存入到邻接矩阵顶点向量对应的位置
        mG->vexs[i] = alG.vertices[i].data;

        // 处理边信息
        src = alG.vertices[i].data;
        ArcNode*  pArcNode = alG.vertices[i].first;
        while (pArcNode != NULL)
        {
            dst = pArcNode->adjvex;
            weight = pArcNode->weight;
            // 将数据存入邻接矩阵中(src,dst)位置存weight
            mG->arcs[src][dst].weight = weight;
            // 更新 pArcNode，指向下一个位置
            pArcNode = pArcNode->next;
        }
    }

    return true;
}

测试

数据准备

顶点数据：vSet.txt

1
2
3
4
5
6

弧数据：arcSet.txt

1 2 1
1 3 9
1 4 8
3 2 3
4 5 7
5 3 5
6 4 2
6 5 1

读入顶点、弧数据

// 读取顶点信息
    // 顶点信息从0开始存储，注意和矩阵映射
    VertexType vexSet[MAX_VERTEX];
    int vexLength = 0;
    FILE* fpVex = fopen("../data/DS08/vSet.txt", "r");
    if (fpVex != NULL)
    {
        while (!feof(fpVex))
        {
            fscanf(fpVex, "%d", &vexSet[vexLength]);
            vexLength++;
        }
        fclose(fpVex);
    }
    // 读取边信息
    VertexType arcSet[MAX_VERTEX][3];
    int arcSetLength = 0;
    FILE* fpArc = fopen("../data/DS08/arcSet.txt", "r");
    if (fpArc != NULL)
    {
        VertexType srcVertex, dstVertex, weight;
        while (!feof(fpArc))
        {

            fscanf(fpArc, "%d %d %d", &srcVertex, &dstVertex, &weight);
            arcSet[arcSetLength][0] = srcVertex;
            arcSet[arcSetLength][1] = dstVertex;
            arcSet[arcSetLength][2] = weight;
            arcSetLength++;
        }
        fclose(fpArc);
    }

转换、打印结果

ALGraph alG;
// 创建邻接矩阵
createALGraph(&alG, UDN, vexSet, vexLength, arcSet, arcSetLength);
// 输出邻接表
printALGraph(alG);
MGraph mG;
// 邻接表 --> 邻接矩阵
ALGraph2MGraph(alG, &mG);
// 打印邻接矩阵
printMGraph(mG);

3.邻接表到逆邻接表

问题

根据有向图的邻接表构造相应的逆邻接表

算法思想

• 邻接表和逆邻接表的定点信息是相同的，直接复制即可。
• 把出边信息转换为入边信息，则需要逐个访问邻接表各个顶点的出边表，把结点通过头插法插入相应入边表中。

代码

// 邻接表转换为逆邻接表
void convertAdjList(ALGraph& ALG, ALGraph& invALG)
{
    // 将基本信息复制
    invALG.vexnum = ALG.vexnum;
    invALG.arcnum = ALG.arcnum;
    invALG.kind = ALG.kind;
    // 初始化逆邻接表
    // 逆邻接表头结点置空，方便头插法；
    // 将邻接表中的顶点复制到逆邻接表中
    for (int i = 1; i <= invALG.vexnum; i++)
    {
        invALG.vertices[i].data = ALG.vertices[i].data;
        invALG.vertices[i].first = NULL;
    }
        
    // 将ALG中的顶点表复制给invALG逆邻接表的顶点表
    // 扫描每一行源节点开始的一行链表
    ArcNode* pArcNode = NULL;
    ArcNode* tmpArcNode = NULL;
    for (int i = 1; i <= invALG.vexnum; i++)
    {
        pArcNode = ALG.vertices[i].first;
        while (pArcNode != NULL)
        {
            // 注意内存分配
            tmpArcNode = (ArcNode*)malloc(sizeof(ArcNode));
            tmpArcNode->adjvex = i;
            // 头插法，插到源点顶点处
            tmpArcNode->next = invALG.vertices[pArcNode->adjvex].first;
            invALG.vertices[pArcNode->adjvex].first = tmpArcNode;

            pArcNode = pArcNode->next;
        }
    }
}

测试