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; } } }
测试
