北京邮电大学复杂网络论文.doc

精品文档基于图论和复杂网络知识的最小代价问题摘要：本文结合了图论知识和复杂网络知识来分析网络中的最小代价问题，运用了Dijkstra算法和Floyd算法求解网络的最短路径，运用Prim算法和Kruskal算法求解网络的最小生成树，并给出了具体的代码实现。关键词：图论；复杂网络；最小代价Minimum Cost Problem Based On Graph Theory and Complex NetworksAbstract: In this paper, the minimum cost problem of networks was analyzed by the knowledge of graph theory and complex networks. We use two algorithms, Dijkstra algorithm and Floyd algorithm, to find the shortest path of networks, also use two algorithms, Prim algorithm and Dijkstra algorithm, to find the minimum spanning tree of networks. The specific codes are given to implement it.Key words: graph theory; complex networks; minimum cost6欢迎下载6欢迎下载。1 概述及研究背景1.1 图论与网络网络研究已经成为当今自然科学和社会科学诸多研究领域研究的热点之一。广义地说，网络就是各种类型相互作用事物的整体1。可以说，整个自然界或人类社会，或两者的综合即整个世界，都是多层次、多类型、多姿态的复杂网络结构2。事实上，图论知识与网络有着天然的联系。在数学和自然科学领域，网络经常被抽象为许多节点和连接节点之间的边，其中节点用来代表真实系统中的个体或元素，而边则用来表示个体或元素之间的关系，通常是当两个节点之间具有某种特定的关系时连一条边，反之则不连边。有边相连的两个节点在网络中被看作是相邻的。例如，神经系统可以看作是大量神经细胞通过神经纤维相互连接形成的网络3；计算机网络可以看作是计算机通过通信介质（如光缆、双绞线、同轴电缆）相互连接形成的网络等等。1.2 研究背景 研究复杂网络的主要目标之一就是理解并掌握复杂网络上的传播行为，如信息传播问题。信息传播问题的实际意义或实际应用是多方面的，其中之一是以最小传播代价进行传播的问题，例如信件传送、管道铺设和路线设计等问题均需要求以最小的代价来解决问题，或是用最短路径完成任务。本文主要对此进行讨论。2 最短路径求解及算法实现 求解两点之间的最短路径是实际应用中的常见问题，也可以转换为图论和网络知识的应用问题。这类问题包括两个典型的问题： 从单个节点到其余各节点之间的最短路径。 各节点之间的最短路径。下面对以上两个问题进行简要讨论。2.1 网络最短距离 网络的平均最短距离定义为网络中任意一对节点之间的最短距离的平均值，数学表达式为：其中dij为节点i,j之间的最短路径长度。大多数真实网络具有较小的平均最短距离。在网络中，从一个节点到另一个节点所需要经过的最大步数叫做这个网络的直径。 动态规划中最短路径问题是一种最优化问题，是网络分析中的一个基本问题。它直接应用于解决生产实际的问题，如管道铺设、线路安排和厂区布置等。例如一个实际问题为：给出一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间找一条最短铁路线。以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边，得到图G。对G的每一边e赋以一个实数w(e)，即直通铁路的长度，称为e的权，得到赋权图G。G的子图的权是指子图各边的权和。问题即为求赋权图G中指定的两个顶点u0,v0间的最小权的铁路，这段铁路叫做u0,v0间的最短路径，它的权叫做u0,v0间的距离。现实中这类问题比较常见，这是简单的最短距离问题。2.2 某个节点到其余各节点的最短路径4 在有向图中，寻找从某个节点（称为源点）到其余各个节点或者每一对节点之间的最短带权路径的运算，称为最短路径问题，求解最短路径可以使用Dijkstra算法。 Dijkstra算法是解决关于带权图的最短路径问题的一种算法，它要一个个地找出从源节点出发到所有其他节点的最短路径。该算法的基本思想是按最短路径长度不减的次序求解各节点的解，即按由近到远的次序求解各节点的解。 不妨假设源节点为v0。事实上，其求解方法是由部分已知的距v0近的节点逐渐向远的节点推进求解的，具体求解方法如下（为便于描述，分别用数组元素pathv和distv表示从节点v0到节点v的最短路径及其对应长度）： 初始化：对v0以外的各节点vi，若存在，则将作为v0到vi的最短路径（当然这只是暂时的）存放到pathvi中，同时将其权值作为对应的路径长度存放到distvi中；否则，分别将空路径“()”和作为pathvi和distvi的值。 从未解节点中选择一个dist值最小的节点v，则当前的pathv和distv就是节点v的最终解（从而使v成为已解节点）。 由于某些节点经过v可能会使得从v0到该节点更近一些，因此应修改这些节点的路径及其长度值，即要修改其path和dist的值（显然，这些节点既可能是v的直接后继，也可能是v的间接后继，但我们只需修改其直接后继的path和dist值即可）。 重复、，直至所有节点求解完毕。Dijkstra算法的实现如下： void graph:dijkstra(int v0) /按照Dijkstra算法求解从v0到各节点的最短路径 int w,v; for(i=1;i=n;i+) /设置各节点的求解标志 solvedi=FALSE; solvedv0=TRUE; /设置v0为已解节点 for(i=1;i=n;i+) /初始化源点到各节点的最短路径及其长度 if(g.edge_weight(v0,i)!=) disti=g.edge_weight(v0,i); pathv0i=(v0,i); else disti=;pathi=(); for(i=1;in;i+) /控制n-1次循环 min=; /在未解节点中搜索最近的节点v for(j=1;j=n;j+) if(solvedj=FALSE & distjmin) min=distj;v=j; solvedv=TRUE; /设置搜索到的当前最短的未解节点为已解节点 for(w=g.firstadj(v);w!=0;w=g.nextadj(v,w) /修改v的后继的路径及其长度 if(distv+g.edge_weight(v,w)distw) distw=distv+g.edge_weight(v,w); /修改v的dist值 pathw=pathv+(v,w); /修改v的path值 2.3 每一对节点之间的最短路径4计算赋权图中各对顶点之间的最短路径，显然可以调用Dijkstra算法，具体方法是：每次以不同的节点作为源点，用Dijkstra算法求出从该源点到其余节点的最短路径，反复执行n次这样的操作，就可以得到从每一个节点到其他节点的最短路径。这种算法的时间复杂度为O(n3)。Floyd提出了另外一种更为直接的求解方法，称为Floyd算法。假设图G的邻接矩阵为A0，用来存放各边长度：其中：aii=0，i=1,2,n；aij=，i,j之间没有边，在程序中以各边都不可能达到的充分大的数代替；aij=wij，wij是i,j之间边的长度，i,j=1,2,n。对于无向图，A0是对称矩阵，aij=aji。Floyd算法的基本思想是：递推产生一个矩阵序列A0,A1,Ak,An，其中Ak(i,j)表示当从节点vi到vj的路径上所经过的所有节点的序号不大于k时的最短路径的长度。由这一定义可知，A0为图的邻接矩阵，而An(i,j)则表示从节点vi到vj的路径上可以经过图中任意节点时的最短路径长度。显然，An就是所要求的最终的最短路径长度，与此同步地求出相应的最短路径即实现了问题的求解。因此，下面先讨论这一矩阵序列的求解。为求解矩阵序列，可采用递推的方式，即通过依次由矩阵Ak-1求解出Ak来实现求解（k=1,2,n）。而由Ak-1求Ak，需要逐个求出其中的元素Ak(i,j)。分析如下：(1) 元素Ak(i,j)的求解由于在Ak-1中的Ak-1(i,j)表示在从节点vi到vj的路径上所经过的节点序号不大于k-1时的最短路径的长度，而Ak(i,j)则表示在从节点vi到vj的路径上所经过的节点序号不大于k时的最短路径的长度，因此Ak(i,j)的求解与Ak-1相关，根据经过节点k是否更近分为两种情况：经过节点k更近：即从节点vi到k再到vj更近，其中从节点vi到k以及k到vj的最短路径上的节点序号均不大于k-1，因而其最短路径长度值应分别是Ak-1中的Ak-1(i,k)和Ak-1(k,j)。因此在这种情况下，Ak(i,j)= Ak-1(i,k)+ Ak-1(k,j)。经过节点k反而更远：在这种情况下，Ak(i,j)= Ak-1(i,j)。由此可得由矩阵Ak-1求矩阵Ak中的元素Ak(i,j)的操作的伪指令如下： if(Ak-1(i,k)+Ak-1(k,j)Ak-1(i,j)Ak(i,j)=Ak-1(i,k)+Ak-1(k,j);else Ak(i,j)=Ak-1(i,j)(2) 矩阵Ak的求解由此可得到整个矩阵Ak的求解。由于在求得矩阵Ak后，矩阵Ak-1已经不再需要，因此，在编写代码时，各矩阵共用一个数组A就可以了。(3) Floyd算法让k依次取1到n求解Ak就实现了对整个矩阵序列的求解，由此得Floyd算法如下：输入：A是图G的邻接矩阵。输出：path和A分别是各点之间的最短路径及相应的长度。 void graph:floyd(adjmatrix& A,adjmatrix& path) /Floyd算法 for(i=1;i=n;i+) /初始化路径矩阵path for(j=1;j=n;j+) if(Aij!=) pathij=(i,j); else pathij=(); for(k=1;k=n;k+) /控制Ak的求解 for(i=1;i=n;i+) /求解Ak(i,j) for(j=1;j=n;j+) if(Aik+AkjAij) Aij=Aik+Akj; pathij=pathik+pathkj; 3 最小生成树求解及算法实现下面先从一个实例开始本部分的内容。假设在某地有一个煤气供应站点及n-1个生活小区，现在要给这些小区铺设煤气管道。请问应怎样铺设管道能使总造价最低（假设已知各小区之间是否可连接以及相应的造价）。可将这类问题转化为图的问题：将各小区和煤气供应站分别表示为图的一个节点，可连接的两点之间表示为一条边，连接的造价表示为边的权值。在这种表示下，原问题就变成了这样的问题：从图中选取若干条边将所有节点连接起来，并且所选取的这些边的权之和最小。显然，所选取的边不会构成回路（否则可去掉回路中的一条边使权值之和更小），因而构成了一棵树，称这样的树为生成树。由于这一生成树的权值之和最小，故称为最小生成树。关于最小生成树的求解，有两种较为典型的算法Prim算法和Kruskal算法。3.1 Prim算法 Prim算法通常要指定一个起点，其求解思想非常简单：首先将所指定的起点作为已选节点，然后反复在满足“一端已选，另一端未选”这一条件的边中选择一条最小边，直到所有节点成为已选节点为止（选择n-1条边）。 为实现Prim算法，需要考虑如下几个方面的实现。 已选节点的标识：可用数组来存储。 候选边的存储：由于本算法是通过反复在候选边中选取最小边来实现的，因此，首先要考虑其存储的实现。现在的问题是选用什么样的结构以及需要多大的空间来存储？如果将所有的候选边全部保存，则要存储的边最多的情况可能要接近图的边数的数量级，因而不太好确定存储容量。 分析：虽然在选取一条边时可能有多个候选边，但我们只需要其中最小的一条。因此，对每个未选节点来说，只需要保留一条最小的候选边就可以了，其他边则不需要，因而总共只需要保存n-1条边。为便于编程实现，可用一个有n个元素的数组来存储，其中，数组中的每个元素存储的是以对应的未选节点为端点的最小候选边，包括其两个节点及其权值。这样一来，相应的要解决以下操作。 (a) 满足条件的最小边的查找：变成了在候选边数组中查找一条权值最小的（要搜索n次）。 (b) 候选边数组的调整：当选出一个新边后，增加了一个新的已选节点。这样就要调整候选边：原有的一些候选边有可能不再是最小边了，另一些边则变成了候选边。对每一个未选节点来说，将新出现的相关的候选边与原有的相应的候选边比较，取更小的为该节点的新候选边。 基本完整的Prim算法实现如下：typedef struct /候选边存储结构int v; /未选节点对应的候选边的另一端点int w; /未选节点对应的候选边的权值 MinEdgeType;typedef MinEdgeType MinEdgeArraymax_num; /候选边集的存储结构void Init_MinEdges(graph& g,MinEdgeArray& MinEdges,int v0) /初始化候选边集int i;for(i=1;=n;i+) /初始化每个未选节点对应的候选边的相关信息if(have_edge(g,v0,i) /若g中存在边(v0,i)MinEdgesi.v=v0; /设置节点i到起点v0的候选边信息,内容包括:MinEdgesi.w=edge_weight(g,v0,i); /另一端点及相应的权值else MinEdgesi.w=; /否则表示不存在边(v0,i)int Get_MinEdge(graph& g,MinEdgeArray& MinEdges) /从候选边集中选出边最短的节点int MMin,j,k;MMin=; /设置当前最短边的权值for(j=1;j=n;j+) /逐个比较,搜索最小的边if(j是未选节点& MinEdgesj.wMMin)k=j; /记录当前具有最小边的未选节点MMin=MinEdgesj.w; /以及对应最短边的权值return k; /最后的k值记录的就是具有最小边的未选节点,作为函数值返回void change_MinEdges_with(graph& g,MinEdgeArray& MinEdges,int k)int j; /对新选出的候选节点k调整当前候选边集for(j=1;j=n;j+) /依次检查每个节点if(j是未选节点)if(have_edge(g,k,j) & edge_weight(g,k,j)MinEdgesj.w) /若节点j到k有更小的边MinEdgesj.w=edge_weight(g,k,j); /替换节点j原候选边的相关信息MinEdgesj.v=k;void Prim(graph& g,int v0) /Prim算法的主函数,假设v0是起点MinEdgeArray MinEdges;int i,j,k;selected_Vset=v0; /将起始节点v0作为已选点Init_MinEdges(g,MinEdges,v0); /初始化候选边集合for(i=1;in;i+) /控制n-1次最小边的选择k=Get_MinEdge(g,MinEdges); /调用函数选择对应最小候选边的未选节点selected_Vset=selected_Vset+k; /在已选点集中插入节点kchange_MinEdges_with(g,MinEdges,k); /调整当前候选边集3.2 Kruskal算法 Kruskal算法是另一种求解最小生成树的方法，其求解算法与Prim算法不同：反复在满足“和已选边不构成回路”这一条件的边中选出一条最小的边。 由前述算法思想可得Kruskal算法的简要描述：T=(V,);while(T中所含边数n-1)从E中选取当前最短边(u,v);从E中删除边(u,v);if(u,v)与T中边不构成回路）将边(u,v)加入T中；在这一求解中，需要解决如下几个问题。 候选边的存储，即如何组织候选边以降低在候选边中搜索的时间复杂度。如果简单地在存储结构（如邻接矩阵）中搜索n-1条边，则至少需要搜索(n-1)n2个元素，因而这一部分的时间复杂度是O(n3)；另外的办法是先对候选边数组按从小到大排序，由排序知识可知，时间复杂度最好可以达到O(eloge)。在这一排序的数组中搜索最小边就比较方便和节省时间；还可以有其他的方法，但总的来说，这一部分的时间性能不是太好。 另一个问题，同时也是一个难点，即如何判断所选择的边和已选的边不构成回路？对此有如下的考虑：逻辑上，将在求解过程中当前能够连成一个连通分量的所有节点看作是一个等价类。在编写程序实现时，通常是通过给同一等价类中的元素标注相同的值来实现，而且这一值一般以所在连通分量中的最小（大）的节点号来代替。这样，在编程时就需要实现以下几个问题的求解。 (a) 初始化：给每个节点标注初始值。一般是标注各自的节点号。 (b) 判断某条边是否和已选边构成回路：若该边的两个端点等价，即具有相同的标注值，说明已经在一