基于邻接矩阵的近似Prim算法解决无向图特定问题
2015-06-14杨秀香李云飞
王 敏，杨秀香，李云飞
(渭南师范学院a.网络安全与信息化学院;b.数理学院，陕西 渭南714099)
用计算机解决一个具体问题，大致需要经过下列几个步骤:首先要从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序，进行测试、调试直至得到最终解答.寻求数学模型的实质是分析问题，从中提取操作对象，然后用数学语言描述它们之间的关系［1］.算法必须采用与之相适应的数据结构，才能有效地计算所求解的问题［2］.
数据的逻辑结构通常有集合、线性、树和图四类.数据在计算机中有顺序和链式两种存储结构.算法的设计取决于数据选定的逻辑结构，而算法的实现依赖于采用的存储结构［1］.本文将研究消除无向连通图中构成环路的冗余边的算法.
1 图的概念
图的逻辑结构可形式化定义为:Graph=(V，R).其中:V={x|x∈dataobject}，R={VR}，VR={＜x，y＞|P(x，y)∧ (x，y∈V)}.V是顶点的有穷非空集合，VR是顶点间关系的集合，P(x，y)代表顶点x和y具有某种谓词关系［1］.在本文所讨论的范围内，谓词P(x，y)可表示为顶点x和y之间存在一条相关边.
2 问题描述
待求解问题描述为:对于任意一个无向连通图G=(V，{E})，G中可能含有环，要求编写算法实现删除G中的某些冗余边，使得G中不含环.
算法要求:编写出的算法所删除的边数必须最少.
3 数据结构分析
在图的逻辑结构中，任意两个顶点之间的关系不存在先后顺序，因而不能采用一维数组的线性结构来存储;另一方面，如果采用链式存储结构，由于图中各顶点的度不同，最小度数和最大度数可能相差较大，若按顶点的最大度数设计链表的指针域，则会造成存储单元的浪费.反之，若根据各顶点的度分别设计不同的链表结点，则又增加了操作复杂性.因此，图的存储结构需要特殊设计.
3.1 存储结构分析与设计
常用的图的存储结构有邻接矩阵、邻接表、十字链表和邻接多重表，具体选用哪种取决于图的特点和所定义的运算.
邻接矩阵是图的顺序存贮，该结构容易判断图中两个顶点是否相关，易于实现求图中各顶点的度的算法.该存储结构的缺点是不适用于存储顶点多而边较少的图.
邻接表是图的链式存储［3］.顶点的顺序存储便于实现访问任意顶点的相关边的算法，因而求图中各顶点的度的算法也易于实现.存储有向图时，某个顶点指向的单链表中，各边结点都是以该顶点为弧尾的弧，因而求顶点的出度算法易于实现，而求顶点入度的算法则需要遍历全部单链表中的边结点，此时仍需要借助逆邻接表存储结构来实现.由此可见，邻接表存储结构在不考虑空间浪费的情况下更适用于存储无向图.
十字链表存储结构专为存储有向图设计，不适用于存储无向图，此时无需同时设计有向图的邻接表和逆邻接表，但较多的指针域仍然容易造成涉及频繁修改弧之类的算法操作的复杂度提升.
在邻接多重表中，边结点结构类似有向图的十字链表存储结构，唯一的边结点消除了无向图的边结点冗余存储，但相应增加的指针域也使得涉及对边结点单链表进行遍历之类的算法操作复杂度增大.
综上对比分析，本文所讨论的无向连通图，其存储结构宜选择较为简单常用的邻接矩阵存储方式.
3.1.1 邻接矩阵存储结构定义
邻接矩阵表示法也称数组表示法，它用一个一维数组存储数据元素(顶点)的信息，一个二维数组(称为邻接矩阵)存储数据元素间关系(边或弧)的信息［4］.
具有n个顶点的图G的邻接矩阵A为n×n的方阵，其形式化定义如下:
其中:VR为顶点间关系的集合;有直接边的两个顶点vi和vj在矩阵中对应的行列交叉点处取值为1.
3.1.2 邻接矩阵的压缩存储
由于无向图G的邻接矩阵为对称方阵，要将一条边记录为已被访问或删除，需要在该边依附的两个邻接点所在的行同时进行操作.这显然存在重复操作，因此，可考虑只存储G的邻接矩阵的下三角(i≥j)，将n2个元压缩存储到n(n+1)/2个元的空间中.
假设以一维数组SA［n(n+1)/2］作为G的邻接矩阵存储结构，则SA［k］和矩阵元A［i，j］之间存在如下对应关系:
这样，对于任意给定的一组下标(i，j)，均可在 SA 中找到矩阵元 A［i，j］.反之，对所有的 k=0，1，2，…，n(n+1)/2－1，都能确定 SA［k］中的元在矩阵中的位置(i，j)［1］.
3.1.3 邻接矩阵存储结构的C语言描述
图的压缩存储的邻接矩阵存储结构可用C语言描述如下:
#define MAX_VER 50 //最大顶点个数
typedef structArcNode{
intadj;//取值为1或0
InfoType info;//边上的其他信息
}ArcNode;
typedef struct{
VerType vexs［MAX_VER］; //顶点向量
ArcNode arcs［MAX_VER(MAX_VER+1)/2］;//压缩存储的邻接矩阵
intvexnum，arcnum; //当前顶点数和边数
}MatrixGraph;
3.2 算法分析与设计
3.2.1 算法设计思路
通过类似Prim算法求解图的生成树，在求解过程中记录下已选中的各边，并在求得G的生成树后，将G中未被记录的边(即不属于生成树中的边)删除.
3.2.2 思路分析
Prim算法可称之为“加点法”.初始状态G的生成树GT的顶点集VT中只含起点，边集TE为空.随后，从G的顶点集VG中选择同VT中的顶点相关，但不属于VT的点加入VT，同时将邻接点的相关边也加进TE.重复该过程直到VT=VG时算法结束.
Prim算法求解的是带权图的最小生成树，因此在选取符合条件的边时，是按照边的权值非递减顺序进行的.本文介绍的待求解问题中并未说明图G是否为带权图，且需要进行的操作只是删除某些冗余边，而又未指明待删边的权值相关性，因此，可将其视为针对非带权无向连通图的一个特定算法.这样，在采用Prim算法的思路选取边时，根据邻接矩阵存储结构的特点，只需顺序选择VT中顶点的第一条未标记的相关边即可.
这种近似Prim算法在顺序选择VT中顶点的各条未标记的相关边时，如何选择VT中作为起点的顶点是需要首先考虑的问题.如果按照顶点序号次序进行选择，则在算法实现上增加了搜索确定起始顶点的时间耗费.因此，可采用广度优先搜索遍历的思路来实现.广度优先搜索遍历即从G中某个起始顶点出发，访问该顶点，然后依次访问该顶点的所有未被访问的邻接点，再根据各邻接点被访问的先后次序，分别从这些邻接点出发依次访问它们的邻接点，直到图中所有已被访问顶点的邻接点都被访问到为止［1］.
3.2.3 算法的C语言描述
设无向连通图G采用前述MatrixGraph存储结构，且G中有n个顶点v1～vn，分别存储在vexs［0..n－1］单元，其arcs数组的数组元均已初始化.为保证图中各顶点在遍历过程中仅被访问一次，可以通过设置一个全局的访问标志数组 visited［n］来实现，其初始值均为 0，一旦顶点 vi被访问，则置 visited［i］为 1［1，5］.不失一般性，假设从顶点vi(vexs［i］，i=0～n－1)出发构造G的生成树.由于G为非带权图，因此不必附设辅助数组closedge(用以记录邻接点分别在VT和VG－VT的具有最小权值的边).在得到GT后，将属于EG但不属于TE的边从EG中删除.算法的C语言描述如下:
intvisited［MAX_VER］;//访问标志数组
voidBreadthFirstSearch(MatrixGraph*G，int i)
{InitQueue(Q);
visited［i］=1;
EnQueue(Q，i);
while(!EmptyQueue(Q))
{DeleteQueue(Q，k);
for(j=0;j＜G－＞vexnum;j++)
if(!visited［j］＆＆G－＞arcs［k(k+1)/2+j］.adj==1)
{G－＞arcs［k(k+1)/2+j］.info=1;//记录被访问边
visited(j)=1;
EnQueue(Q，j);}//End－of－if
}//End－of－while
}//End［1］
void DeleteRedundentEdge(MatrixGraph*G)
{BreadthFirstSearch(G，0);
for(i=0;i＜G－＞vexnum;i++)
for(j=0;j＜i;j++)
{k=i(i+1)/2+j;
if(G－＞arcs［k］.adj==1＆＆G－＞arcs［k］.info==0)
G－＞arcs［k］.adj=0;//删除未被记录的边
}//End－of－for
}//End
4 算法性能评价
本文介绍的消除无向连通图中冗余边的算法通过函数DeleteRedundentEdge()最终实现，该函数的函数体中包括两条基本语句:一是对函数BreadthFirstSearch()的调用，二是一条双重for循环语句.函数BreadthFirstSearch()完成对G的广度优先搜索遍历，遍历结束得到G的广度优先搜索生成树.双重for循环完成删除不属于生成树中的边，即构成回路的冗余边.该算法采用了邻接矩阵存储结构，查找每个顶点的邻接点所需时间为O(n(n+1)/2)=O(n2)，其中n为图中的顶点数.双重for循环语句的循环体执行次数为O(n(n－1)/2)=O(n2).将顶点数n看作问题的规模，则随着问题的规模n逐渐增大，算法的时间复杂度约为T(n)=O(n2).
该算法除了函数本身和图G所占空间外，引入了一个一维数组visited［MAX_VER］的辅助空间，从而算法的空间复杂度为线性阶，即S(n)=O(n).
［1］严蔚敏，吴伟民.数据结构(C语言版)［M］.北京:清华大学出版社，2002.
［2］王卫东.数据结构学习指导［M］.西安:西安电子科技大学出版社，2004.
［3］江涛.数据结构［M］.北京:中央广播电视大学出版社，1995.
［4］王昆仑，李红.数据结构与算法［M］.北京:中国铁道出版社，2007.
［5］耿国华.数据结构—C语言描述［M］.西安:西安电子科技大学出版社，2005.
