图论课程论文
设计（论文）题目：Prim算法在通信网络架设中的应用
学院名称：通信与信息工程学院
学生姓名：
专业：
学号：
填表时间：2014年12月
摘要
通信网络系统架设属于典型的图论优化问题，针对通信网络系统的特点，抽象问题，简化模型，以通信网络系统架设费用那个最小为优化目标，应用Prim 算法进行通信网络系统架设模型研究。首先简述了五个城市之间架设通信网络系统问题，然后应用数学建模知识对隐含在该问题中的图论模型进行了抽象研究，进而构造问题的数学模型，最后应用Prim算法设计了该通信网络系统架设实现流程及相应代码的编写。程序执行结果表明:准确构建了问题的数学模型及应用Prim算法正确求解了该数学模型；并且权值因子的可变性使得该程序具有较强的通用性，易于在实际中使用。
【关键字】：数学建模无向连通图最小生成树Prim算法
引言
随着数学科学和计算机技术的发展，数学建模知识在各领域中发挥着重要作用，抽象实际问题、建立正确的数学模型已成为解决实际应用问题的关键[1]。通过数学建模，就可以对实际问题进行抽象、简化，确定变量和参数，并应用某些“规律”建立起变量、参数间的确定的数学模型；一个理想的数学模型，它应满足两个条件；一是模型的可靠性，即在允许的误差范围内，能正确反映所考虑系统相关特性的内在联系，反映客观实际；二是模型的可解性，即它易于数学处理和计算[2]。
本文主要研究的是架设通信网络系统的费用最小问题，应用数学建模知识，建立相应的数学模型，其中求最小生成树可以通过Prim算法和Kruskal算法，根据本文所要解决问题的特点，主要采用Prim算法[3]。依据算法的基本思想加入了不同的权值，解决不同情况下网络架设的费用最小问题，并编写了相关程序，该程序具有较强的通用性，易于在实际中使用。
一、相关知识介绍
1.树
树包含n（n>=0）个节点。当n=0时表示为空树。其定义如下：
T=(D,R)其中，D为树中节点的有限集合，关系R满足一下条件：
①有且仅有一个节点k0属于D，它对于关系R来说没有前趋节点，结点k0称作树的根结点。
②除根结点k0之外，D中的每个结点仅有一个前趋结点，但可以有过个后继结点。
③D中可以有多个终端结点。即除根结点无父结点，其余各结点都有一个父结点和n（n>=0）个子结点。
2.邻接矩阵
图的矩阵表示，本文中只用到了邻接矩阵，故在这只提出邻接矩阵的定义，及其图在邻接矩阵中的表示。
设图 A = (V, E)是一个有n 个顶点的图, 图的邻接矩阵是一个二维数组A.edge[n][n]，用来存放顶点的信息和边或弧的信息。是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵：
①无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。
②无向图的邻接矩阵中第i行第j列表示i结点到j结点的度即权值，可以表示为某一具体应用的数据。也表示i结点是否与j结点连通。
3.最小生成树
在一给定的无向图G=(V, E)中(u,v) 代表连接顶点u与顶点v的边(即),而w(u,v)代表此边的权重,若存在T为E的子集（即)且为无循环图，使得的w(T)最小则此T为G的最小生成树。
二、提出问题与问题抽象
1.提出问题
假设在五个城市架设通信网络系统，任意两个城市之间都可直接架设通信网络，最终目标是以最小总费用在五个城市架设通信网络系统。表1为各城市之间的距离，单位为公里。各城市之间架设网络每公里费用为10000元。其中五个城市分别用A、B、C、D、E表示。
表1：五城市之间距离关系
2.问题的数学抽象
因为任意两个城市之间都可直接架设通信网络，并且网络连接无方向性，所以五个城市之间的连接图如图1可以认为是一个无向连通赋权图G(V,E,W)，其中，V表示顶点集，E表示边集,W表示各边权值，本问题代表为公里数。这样问题就转化为一个图论问题，变为了一个在无向连通赋权图G中求解一棵最小代价生成树问题，该树满足以下条件：
①树中任意两点之间至多只有一条边
②树中边数等于树的顶点数减一
③树中任意去掉一条边，即得一个不连通图
④树中各边权值之和是该连通赋权图中所有可能树中各边权值之和最小的。
图1：五城市之间连通图
3.建立问题求解模型
对连通赋权图G（V,E,W）,一般来说，生成树不止一个，因此，最小代价生成树不一定是唯一的。我们的目的是找出一棵关于图G的最小代价生成树。设T(V,E)为G的一棵生成树，其各边加权之和：
W(T)=∑W(e i)
称为树T的权，找G中树权值最小的生成树T*,T*为G的最小代价生成树。
4.数学模型的算法设计
基于具有五个顶点的无向连通赋权图G的每个生成树刚好具有四条边，所以问题是用某种方法选择四条边使它们形成G的最小生成树。此处用到了Prim 算法[4]。
4.1构造最小生成树的Prim算法
假设G（V,E,W）为问题中五城市的连通图，顶点集V(A,B,C,D,E)，E为图中所有带权边的集合。设置两个新的集合U和EDGE,其中集合U用于存放G的最小生成树中的顶点，集合EDGE存放G的最小生成树中的边。假设构造最小生成树时，从顶点A出发，令集合U的初值为U｛A｝,集合EDGE的初值为空[5]。
Prim算法的基本思想：从所有u∈U,v∈V-U的边中，选取具有最小权值的边（u,v）,将顶点v加入集合U中，将边(u,v)加入集合EDGE中，如此不断重复，直到U=V时，最小生成树构造完毕，这时集合EDGE中包含了最小生成树的所有四条边。
三、算法具体实现
1.Prim算法实现步骤
假设V是图中顶点的集合，E是图中边的集合，EDGE为最小生成树的边的集合，则Prim算法通过以下步骤可以得到最小生成树：
a：初始化：U=｛U0｝,EDGE=｛｝。此步骤设立一个只有顶点U0的结点集U 和一个空的边集EDGE作为最小生成树的初始形态。
b：在所有u∈U,v∈V-U的边(u,v)∈E中，找一条权最小的边(u0,vi),将此边加
进集合EDGE=｛(u0,vi)｝中，并将此边的非U中的顶点vi加入U中，U=｛u0，vi｝。
c：如果U=V,则算法结束；否则重复步骤2。可以算出当U=V时，步骤2共执行了四次，EDGE中也增加了四条边，这四条边就是所求出的最小生成树的边。
2.算法编码实现
代码的编写主要通过visual studio 2013编辑器来编写，用到的编程语言为C++。具体细节如下：
①首先定义一个5*5的二维数组来存储邻接矩阵值，数组名为value[5][5];定义一个结构体来存储最小生成树中边的信息，结构体定义如下：
typedef struct TREE
{
int from;
int to;
int weight;
}Tree;
其中结构体中有三个整形的成员变量，from代表最小生成树中某条边的起点，to代表最小生成树中某条边的终点，weight代表最小生成树中某条边的权重。首先初始化一个结构体数组Tree TE[5]，TE[5]用于存储最小生成树中边的信息。
②首先假设A为起点，以A为起点，B、C、D、E为终点的边假设为最小权边，将其分别存储在TE[1],TE[2],TE[3],TE[4]。
③找出TE[]数组中权值最小的边，然后将其与TE[1]交换数据。
④然后假设最小权边的终点为起点，重新比较各边的权重，跟新TE[]数组中的信息。
⑤重复步骤③与④，直到找出四条最小权边。
具体代码如下：
void CGraphShow::MiniTree_prim()
{
for (int i = 0; i < MAX; i++)
{
for (int j = 0; j < MAX; j++)
{
value[i][j] = ((CCTRLDlg*)AfxGetApp()->m_pMainWnd)->value[i][j];
}
}
int i, j, k, m, min, t, w;
for (i = 1; i < m_ctrldlg.m_editvalue; i++)
{
TE[i].from = 0;
TE[i].to = i;
TE[i].weight = value[0][i];
}
for (j = 1; j < m_ctrldlg.m_editvalue; j++)
{
m = j;
min = MAX_V ALUE;
for (k = j; k < m_ctrldlg.m_editvalue; k++)
{
if (TE[k].weight < min)
{
min = TE[k].weight;
m = k;
}
}
Tree temp;
temp = TE[j];
TE[j] = TE[m];
TE[m] = temp;
k = TE[j].to;
for (i = j + 1; i < m_ctrldlg.m_editvalue; i++)
{
t = TE[i].to;
w = value[k][t];
if (w < TE[i].weight)
{
TE[i].weight = w;
TE[i].from = k;
}
}
}
}
3.运行结果
①构建邻接矩阵见图2
图2：邻接矩阵图
②画出五个城市之间连接图，见图3
图3：连通图
③生成最小生成树，见图4
图4：最小生成树
4．结论
通过程序求出的仿真图形我们可以求出最小生成树，所以在五座城市之间架设通信线路费用最少为：Y=(10+12+13+12)*10000=470000元。
四、结论
本文综合应用数学建模和图论知识，针对通信网络系统架设的特点及优化目标，建立了问题的数学模型，并应用Prim算法求解该数学模型，最后编写相应代码。程序执行结果表明了建立的数学模型的正确性和Prim算法解决架设通信网络系统费用最小问题的有效性；同时也证明了该应用程序具有较强的通用性，可以调整输入的权值以匹配不同的网络架设情况，从而使程序易于在实际中使用。
参考文献
[1] 朱建青. 数学建模[M]. 解放军出版社,, 1996.
[2] 殷剑宏, 吴开亚. 图论及其算法[M]. 中国科学技术大学出版杜, 2003.
[3] 徐俊明. 图论及其应用[M]. 中国科学技术大学出版社, 2000.
[4] 宋增民. 图论与网络最优化[M]. 东南大学出版杜, 1990.
[5] 张清华. 图论及其应用[M]. 清华大学出版社, 2012.
上海电力学院 数据结构（JAVA）课程设计 题目:____最小生成树_______ 学生姓名：_****___________ 学号：_____*******_______ 院系：计算机科学与技术学院 专业年级： ______*****___级 20**年 *月**日
目录 1.设计题目 (1) 2.需求分析 (1) 1）运行环境 (1) 2）输入的形式和输入值的范围 (1) 3）输出的形式描述 (1) 4）功能描述 (1) 5）测试数据 (1) 3.概要设计 (1) 1）抽象数据类型定义描述 (1) .2）功能模块设计 (1) 3）模块层次调用关系图 (2) 4.详细设计。实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。 (2) 5.调试分析。包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会。 (6) 6.用户使用说明。详细列出每一步的操作说明。 (7) 7. 测试结果 (7) 8.附录：程序设计源代码 (9)
一、设计题目 1).问题描述 若要在 n 个城市之间建设通信网络，只需要架设n-1 条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。 2). 基本要求 以邻接多重表存储无向带权图，利用克鲁斯卡尔算法或普瑞姆算法求网的最小生成树。 二、需求分析 1）运行环境 软件在JDK运行，硬件支持windows系统 2）输入的形式和输入值的范围 自动生成顶点数据在10~20之间；各个顶点之间权值在25~50之间；通过程序改动亦可生成已知顶点权值之间的最小生成树，需将随机生成代码改为edge edge[]={new edge(0,1,16),new（0,2,18）......}； 将已知顶点、权值通过其函数输入再生成其所对应最小生成树。 3）输出的形式描述 输出随机生成顶点个数以及各个顶点之间权值；然后输出本次生成顶点之间构成的最小生成树。
5.3.6 图论在通信网中的应用 网络可靠性是评价网络是否稳定工作的一个非常重要的指标。而网络可靠性的衡量取决于网络的两个重要的指标——结合度和连通度。下面主要就结合度和连通度的定义及其计算作简要描述，并以一个例子加以说明。 1. 网络的结合度和连通度的定义 1）结合度： 网络G 的结合度又称为边连通度，记为()L G ，其大小等于使网络成为不连通图所需去掉链路（边）的最少条数。它反映网络节点间的内聚程度，是网络可靠性的一个基本度量指标。例如, 通过观察易知,图5.29所示的网络的结合度()3L G =。 ? ? ?? ?? ?? 图5.29 2）连通度：网络G 的连通度又称为点连通度，记为()K G ，其大小等于使网络成为不连通图所需去掉的节点的最少个数。例如，图5.29所示的网络的连通度()2K G =。从某种意义上讲，点连通度是比边连通度更重要的网络可靠性度量指标，这是因为在网络中去掉某个节点 就意味着与之关联的所有链路将失去意义。 2. 网络结合度和连通度的算法 1）算法基本思想 通常，要求给定网络(,)G V E =的结合度，需要首先确定任意不同两点的链路割集。设i v 和j v 是的两个不同节点，所谓G 的一个i j v v -链路割集是指这样的链路集合：若去掉其中所有链路，网络G 将被分割成两个分支，一个包含节点i v ，另一个包含节点j v 。假设 ij L 是G 中所有i j v v -链路割集中链路的最小数，则ij L 就是切断i v 和j v 之间所有路由所需 从G 中删去的最小链路数，故网络G 的结合度()L G 可按下式计算： ,,()m in i j i j ij v v V v v L G L ∈≠= 与确定结合度的方法类似，求给定网络(,)G V E =的连通度，则需要首先确定任两个不同节点间的节点割集。设i v 和j v 是的两个不同节点，G 的一个i j v v -节点割集是指这样
快速生成树的配置（已经测试过） 实验名称：快速生成树配置。 实验目的：理解快速生成树配置及原理。 背景描述：现有两台交换机互连组成内部局域网，为了提高网络的可靠性，网络管理员用2 条链路将交换机互连，现要在交换机上做适当配置，使网络避免环路。 技术原理：生成树协议是利用SPA算法（生成树算法），在存在交换环路的网络中生成一个没有环路的树形网络。运用该算法将交换网络冗余的备份链路逻辑上断开，当主要链路出现故障时，能够自动 的切换到备份链路，保护数据的正常转发。 生成树协议目前常见的版本有STP（生成树协议IEEE802.1d）、RSTP(快速生成树协议IEE E802.1w)、MSTP（多生成树协议IEEE802.1s）。 实现功能：使网络在有冗余链路的情况下避免环路的产生，避免广播风暴等。 实验设备：S2126（2台）；PC机（2台）；直连线（4根） 实验拓扑： 按照拓扑图连接网络时注意，两台交换机都配置完快速生成树协议后，再将两台交换机连接起来。 如果先连接再配置会造成广播风暴，影响交换机的正常工作。
实验步骤： 步骤1：交换机A的基本配置。 SwitchA(config)#vlan 10 SwitchA(config-vlan)#name sales SwitchA(config-vlan)#exit SwitchA(config)#interface fastEthernet 0/3 SwitchA(config-if)#switchport access vlan 10 SwitchA(config-if)#end SwitchA#sh vlan id 10 VLAN Name Status Ports ---- -------------------------------- --------- --------- 10 sales active Fa0/3 SwitchA# 步骤2：在交换机A上配置快速生成树。 SwitchA(config)# spanning mode pvst SwitchA(config)#interface range fastethernet 0/1 SwitchA(config-if)#swit mode trunk SwitchA(config)#interface range fastethernet 0/2 SwitchA(config-if)#swit mode trunk SwitchA(config-if)#exit 步骤3：交换机B的基本配置。
题目：最小生成树在城市交通建设中的应用 姓名： 学号： 指导老师： 专业：机械工程 2014年3月16
目录 摘要..................................................................................... 错误！未定义书签。 1 绪论 (1) 2 有关最小生成树的概念 (2) 3 prim算法介绍 (3) 4 系统设计及其应用 (5) 一、系统设计 (5) 二、最小生成树应用 (8) 5 总结 (11) 参考文献 (12) 附件： (13)
最小生成树在城市交通建设中的应用 摘要：连通图广泛应用于交通建设，求连通图的最小生成树是最主要的应用。比如要在n个城市间建立通信联络网，要考虑的是如何保证n点连通的前提下最节省经费，就应用到了最小生成树。 求图的最小生成树有两种算法，一种是Prim（普里姆）算法，另一种是Kruskal（克鲁斯卡尔）算法。 本文通过将城市各地点转换成连通图，再将连通图转换成邻接矩阵。在Microsoft Visual C++上，通过输入结点和权值，用普里姆算法获得权值最小边来得到最小生成树，从而在保证各个地点之间能连通的情况下节省所需费用。 本文从分析课题的题目背景、题目意义、题目要求等出发，分别从需求分析、总体设计、详细设计、测试等各个方面详细介绍了系统的设计与实现过程，最后对系统的完成情况进行了总结。 关键字：PRIM算法、最小生成树、邻接矩阵、交通建设
Abstract Connected graph is widely applied in traffic construction, connected graph of minimum spanning tree is the main application.Such as to establish a communication network between the n city, want to consider is how to ensure n points connected under the premise of the most save money, apply to the minimum spanning tree. O figure there are two kinds of minimum spanning tree algorithm, one kind is Prim (she) algorithm, the other is a Kruskal algorithm (Kruskal). In this article, through the city around point into a connected graph, then connected graph is transformed into adjacency matrix.On Microsoft Visual c + +, through the input nodes and the weights, gain weight minimum edge using she algorithm to get minimum spanning tree, which in the case of guarantee every location between connected to save costs. Based on the analysis topic subject background, significance, subject requirements, etc, from requirements analysis, general design, detailed design, testing, and other aspects detailed introduces the system design and implementation process, finally the completion of the system are summarized. Key words: PRIM algorithm, minimum spanning tree, adjacency matrix, traffic construction
河北科技大学 课程设计报告 学生姓名：白云学号：Z110702301 专业班级：计算机113班 课程名称：数据结构课程设计 学年学期： 2 01 3—2 014学年第2学期指导教师：郑广 2014年6月
课程设计成绩评定表
目录 一、需求分析说明 (1) 1.1最小生成树总体功能要求 (1) 1.2基本功能 (1) 1.3 模块分析 (1) 二、概要设计说明 (1) 2.1设计思路 (1) 2.2模块调用图 (2) 2.3数据结构设计 (2) 2.3.1.抽象数据类型 (2) 2.3.2方法描述 (2) 三、详细设计说明 (3) 3.1主函数模块 (3) 3.2邻接表输出子模块 (3) 3.3邻接矩阵输出子模块 (3) 3.4创建邻接矩阵子模块 (3) 3.5创建邻接表子模块 (3) 3.6 Prim子模块 (3) 3.7 Kruscal子模块 (4) 四、调试分析 (4) 4.1实际完成情况说明 (4) 4.2 出现的问题及解决方案 (4) 4.3程序中可以改进的地方 (4) 六、课程设计总结 (7) 七、测试数据 (7) 八、参考书目 (7)
一、需求分析说明 1.1最小生成树总体功能要求 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 1.2基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 1.3 模块分析 主模块：用于生成界面和调用各个子模块。 Kruscal模块：以kruscal算法实现最小生成树。 Prim模块：以prim算法实现最小生成树。 邻接表模块：用邻接表方式存储图。 邻接表输出模块：输出邻接表。 邻接矩阵模块：用邻接矩阵方式存储图。 邻接矩阵模块：输出邻接矩阵。 二、概要设计说明 2.1设计思路 问题的解决分别采用普利姆算法以及克鲁斯卡尔算法。 1) 普利姆算法就是先选择根，把它放入一个集合U中，剩余的顶点放在集合V中。然后选择该顶点与V中顶点之间权值最小的一条边，以此类推，如果达到最后一个则返回上一个顶点。 2) 克鲁斯卡尔算法就是写出所有的顶点，选择权最小的边，然后写出第二小的，以此类推，最终要有一个判断是否生成环，不生成则得到克鲁斯卡尔的最小生成树。
算法设计与分析课程设计报告 学院计算机科学与技术 专业计算机科学与技术 年级2011 姓名XXX 学号 2013年5 月19 日
题目：最小生成树问题的算法实现及复杂度分析 摘要：该程序操作简单，具有一定的应用性。数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。而最小生成树算法是算法设计与分析中的重要算法，最小生成树也是最短路径算法。最短路径的问题在现实生活中应用非常广泛，如邮递员送信、公路造价等问题。本设计以Visual Studio 2010作为开发平台，C/C++语言作为编程语言，以邻接矩阵作为存储结构，编程实现了最小生成树算法。构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM 经典算法的算法思想，最后用这种经典算法实现了最小生成树的生成。 引言：假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n（n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。一棵生成树的代价就是树上各边的代价之和。而实现这个运算的经典算法就是普利姆算法。
实验四、生成树协议 STP的应用实验 【相关知识】 1．生成树协议 STP简介 在局域网中，为了提高网络连接可靠性，经常提供冗余链路。所谓冗余链路就像公路、铁路一 样，条条道路通北京，这条不通走那条。例如在大型企业网中，多半在核心层配置备份交换机（网 桥），则与汇聚层交换机形成环路，这样做使得企业网具备了冗余链路的安全优势。但原先的交换机 并不知道如何处理环路，而是将转发的数据帧在环路里循环转发，使得网络中出现广播风暴，最终 导致网络瘫痪。 为了解决冗余链路引起的问题， IEEE802 通过了 IEEE 802.1d协议， 即生成树协议 （Spanning Tree Protocol，STP）。IEEE 802.1d协议通过在交换机上运行一套复杂的算法，使冗余端口置于“阻塞状 ，从而使网络中的计算机通信时只有一条链路生效，而当这个链路出现故障时，STP 将会重新计 态” 算出网络的最优链路，将“阻塞状态”的端口重新打开，从而确保网络连接的稳定可靠。 生成树协议和其它协议一样，是随着网络的不断发展而不断更新换代的。在生成树协议发展的 过程中，老的缺陷不断被克服，新的特性不断被开发出来。按照功能特点的改进情况，习惯上生成 树协议的发展过程被分为三代： 第一代生成树协议：STP/RSTP 第二代生成树协议：PVST/PVST+ 第三代生成树协议：MISTP/MSTP 2．IEEE 801.1D生成树协议简介 生成树协议（Spanning Tree Protocol，STP）最初是由美国数字设备公司（DEC）开发的，后经 IEEE 修改并最终制定了 IEEE 802.1d标准。 STP 协议的主要思想是当网络中存在备份链路时，只允许主链路激活，如果主链路失效，备份 链路才会被打开。大家知道，自然界中生长的树是不会出现环路的，如果网络也能够像树一样生长 就不会出现环路。STP 协议的本质就是利用图论中的生成树算法，对网络的物理结构不加改变，而 在逻辑上切断环路，封闭某个网桥，提取连通图，形成一个生成树，以解决环路所造成的严重后果。 为了理解生成树协议，必先了解以下概念： （1）桥协议数据单元（Bridge Protocol Data Unit，BPDU）：交换机通过交换 BPDU来获得建立 最佳树型拓扑结构所需的信息。生成树协议运行时， 交换机使用共同的组播地址 “01-80-C2-00-00-00”来发送 BPDU； （2）每个交换机有唯一的桥标识符（Brideg ID），由桥优先级和 MAC 地址组成； （3）每个交换机的端口有唯一的端口标识符（Port ID），由端口优先级和端口号组成； （4）对生成树的配置时，对每个交换机配置一个相对的优先级，对每个交换机的每个端口也配 置一个相对的优先级，该值越小优先级越高； （5）具有最高优先级的交换机被称为根桥（Root Bridge），如果所有设备都具有相同的优先级， 则具有最低 MAC 地址的设备将成为根桥； （6）网络中每个交换机端口都有一个根路径开销（Root Path Cost），根路径开销是某交换机到 根桥所经过的路径开销（与链路带宽有关）的总和； （7）根端口是各个交换机通往根桥的根路径开销最低的端口，若有多个端口具有相同的根路径 开销，则端口标识符小的端口为根端口； （8）在每个 LAN 中都有一个交换机被称为指定交换机（Designated Bridge），它是该 LAN 中与 根桥连接而且根路径开销最低的交换机； （9）指定交换机和 LAN 连接的端口被称为指定端口（Designated Port）。如果指定桥中有两个 以上的端口连在这个 LAN 上，则具有最高优先级的端口被选为指定端口。根桥上的端口都可以成为
数据结构课程设计报告题目：最小生成树问题 院（系）：计算机工程学院 学生姓名: 班级：学号: 起迄日期: 指导教师: 2011—2012年度第 2 学期 一、需求分析 1.问题描述：
在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 2.基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 3.输入输出 以文本形式输出最小生成树，同时输出它们的权值。通过人机对话方式即用户通过自行选择命令来输入数据和生成相应的数据结果。 二、概要设计 1.设计思路： 因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和 prim算法两种方法来生成最小生成树。根据要求，需采用多种存储结构，所以我选择采用了邻接表和邻接矩阵两种存储结构。 2.数据结构设计： 图状结构： ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R={VR} VR={
初始条件：图G存在。 操作结果：销毁图G。 LocateVex( G, u ) 初始条件：图G存在，u和G中顶点有相同特征。 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返 回其它信息。 GetVex( G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的值。 PutVex( &G, v, value ) 初始条件：图G存在，v是G中某个顶点。 操作结果：对v赋值value。 FirstAdjVex( G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点， 则返回“空”。 NextAdjVex( G, v, w ) 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。 操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的 最后一个邻接点，则返回“空”。 InsertVex( &G, v ) 初始条件：图G存在，v和图中顶点有相同特征。 操作结果：在图G中增添新顶点v。 DeleteVex( &G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：删除G中顶点v及其相关的弧。 InsertArc( &G, v, w )
图和子图 图 图 G = (V, E)， 其中 V = {νv v v ,......,,21} V ---顶点集， ν---顶点数 E = {e e e 12,,......,ε} E ---边集， ε---边数 例。 左图中， V={a, b,......,f}, E={p,q, ae, af,......,ce, cf} 注意， 左图仅仅是图G 的几何实现（代表）， 它们有无穷多个。真正的 图G 是上面所给出式子，它与顶点的位置、边的形状等无关。不过今后对两者将经常不加以区别。 称 边 ad 与顶点 a (及d) 相关联。也称 顶点 b(及 f) 与边 bf 相关联。 称顶点a 与e 相邻。称有公共端点的一些边彼此相邻，例如p 与af 。 环（loop ，selfloop ）：如边 l 。 棱（link ）：如边ae 。 重边：如边p 及边q 。 简单图：（simple graph ）无环，无重边 平凡图：仅有一个顶点的图（可有多条环）。 一条边的端点：它的两个顶点。 记号：νε()(),()().G V G G E G ==。 习题 1.1.1 若G 为简单图，则 εν≤?? ?? ?2 。 1.1.2 n ( ≥ 4 )个人中，若每4人中一定有一人认识其他3人，则一定有一 人认识其他n-1人。 同构 在下图中， 图G 恒等于图H , 记为 G = H ? V （G)=V(H), E(G)=E(H)。 图G 同构于图F ? V(G)与V(F), E(G)与E(F)之间各存在一一对应关系，且这二对应关系保持关联关系。 记为 G ?F 。 注 往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。 d e f G = (V, E) y z w c G =(V , E ) w c y z H =(V ?, E ?) ?a ? c ? y ? e ?z ? F=(V ??, E ??)
编号： 审定成绩： 重庆邮电大学研究生堂下考试答卷 2013-2014学年第1 学期论文题目：最小生成树在旅游路线选择中的应用 学院名称： 学生姓名： 专业： 学号： 指导教师： 重庆邮电大学教务处制
摘要 随着生活节奏的加快，人民生活水平的提高，人们越来越热衷于四处旅游，同时，大家也不愿意将大部分的时间花费在路途上，人们旅游目的在于放松、赏景、游玩，旅游公司就不得不根据游客要求做出相应的旅游路线安排。很多旅游景点之间都相隔一定的距离，那么如何在众多旅游景点路线中选择最近的一条呢？因此，如何做到即保证游览各个景点又确保路途最近地从众多可行路线中选出最优路线成为了解决此问题的关键。 图论最小生成树理论常用于交通线路选择中，本文将其运用于旅游交通优化与线路组织上，即在赋权图中找出一颗最优树，以满足以最短路径最小连接各旅游目的城市和最小的建设成本。我们所学《图论及其算法》教材中介绍了其中的三种算法Prim 算法、Kruskal 算法和破圈法。本文涉及的抽象图形结构较为简单，使用各类算法的差别在此并无明显体现，一般来说，Kruskal 算法应用较为普遍，因此本文采用Kruskal 算法实现最优路径求取。 文中通过一个例子应用，将最小生成树的Kruskal 算法实际化，通过算法步骤分析，以及在VC++6.0中程序的运行，最终求出的最小生成树与实际相符，该算法思想成立，并具有一般性，能够增删节点、修改权值，也可运用到其他问题的解决中。 关键词：旅游路线问题 Kruskal算法最优路线最小生成树
一、引言 旅游交通是为旅游者由客源地到旅游目的地的往返，以及在旅游目的地各处旅游活动而提供的交通设施及服务，其便利程度，是衡量旅游业发达程度的重要标志。与一般交通不同，旅游交通过程本身也是旅游体验过程，对于游客来说，立足于最小的时间与经济成本获得最多的旅游体验，对于旅游组织者来说，则立足于最小的建设成本与最大的社会、经济、生态效益。道路是交通的载体，具有高度通达性、完善的旅游服务功能和景观化、生态化、人性化的道路是区域旅游交通完善的重要标志，基于此，有学者提出“风景道”、“旅游交通干道”等规划建设理念与原则。其中，旅游交通系统的优化很大程度取决于合理的道路布局，而如何使道路通达性与建设成本之间获得平衡，达到性价比最优，成为道路系统优化的重要指标。因此，其实质上可以简化为最短距离连接各旅游目的地最优解问题[1]。 旅游路线组织是旅游地理学研究的重要内容，其研究主要以游客的行为空间模式为导向，旅游路线是旅游产品的组成部分，作为产品就必须满足游客的需求，因此游客的行为模式就成为旅游路线设计的重要依据。 二、背景知识 1、图和树 图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。树是无圈连通无向图，如果树T的节点数为n，那么树的边数为n-1。 2、生成树 连通图G 上的一个子图，该子图连通，无回路且包含图G 的所有节点，称为连通图的极小连通子图。一个连通图可以有多棵不同的生成树。 3、最小生成树 对一个带权连通图，也有多可不同的生成树。由于该图是带权图，各边的权值不一定相等，因此这些生成树的各边权值之和也不一定相同，其中权值最小的生成树被称为该带权连通图的最小生成树[4]。 三、最小生成树的求解方法 构造最小生成树可以有多种算法。我们所学《图论及其算法》教材中介绍了其中的三种算法Prim 算法、Kruskal 算法和破圈法，本文分别用这三种算法来实现最小生成树的构造。
中北大学 数据结构与算法课程设计 说明书 学院、系：软件学院 专业：软件工程 班级： 学生姓名：学号： 设计题目：最小生成树问题 起迄日期: 2015年1月12日- 2015年1月29日指导教师:王秀娟 2015 年1月 29 日
1需求分析 1.1已知一个无向连通网表示n个城市以及城市间可能设置的通信网络线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。我们要选择一棵生成树，使总的耗费最小。 1.2该无向连通图的建立需要使用两种存储结构，即邻接表和邻接矩阵。 1.3实现最小生成树需要使用两种算法。即普里姆算法和克鲁斯卡尔。 1.4程序通过人机交互实现数据的输入和输出。 2选题要求 设计内容： 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用（邻接表和邻接矩阵）两种，采用课本上的两种求解算法。 设计要求： (1) 符合课题要求，实现相应功能； (2) 要求界面友好美观，操作方便易行； (3) 注意程序的实用性、安全性。 3程序设计方法及主要函数介绍 ADT Graph{ 数据对象V;V是具有相同特性的数据元素的集合，成为顶点集。 数据关系R： R = {VR} VR = {（v,w）|v,w为V集合中的元素，（v,w）表示v和w之间存在的路径} 基本操作P; CreateMGraph(MGraph *G) 初始条件：V是图的顶点集，VR是图的边的集合。 操作结果：按V和VR的定义构造图G，用邻接矩阵存储。 CreateALGraph(ALGraph *G)
小 型 微 型 计 算 机 系 统 Journal of Chinese Computer Systems
2008 年 月 第 期 Vol.28 No. 2008
?
图论在网络拓扑发现算法中的应用
路连兵 1+，胡吉明 2，姜 岩 1
1，2
，2
(河海大学 计算机及信息工程学院,江苏 南京
210098)
E-mail ：famioo@https://www.doczj.com/doc/8c14190738.html,
摘
要：网络拓扑发现技术已经广泛地应用在各种项目软件中。然而，随着网络结构复杂度升级，这给拓扑发现带来了
挑战。所以我们越来越需要一种高效，准确的网络拓扑算法自动发现网络拓扑结构。目前的拓扑算法主要集中在：(1)路 由层的发现。这个层面的发现算法在技术上比较简单，只需要寻找路由与路由之间，或路由端口与子网之间的连接关系， 利用路由器的自身特性，很容易实现。(2)链路层的发现。直到目前为止，已有的厂商工具很难准确发现网络拓扑，已发 表的理论文献知识也只是理论上阐述，实际应用难度比较大。本论文，提出一种基于图论的骨架树数据存储结构算法，可 以高效推断网络的拓扑关系。 关键词：骨架树;子网;地址转发表;图论；信任节点
Topology Discovery in Networks Based on Graph Theory*
LU Lian-Bing1+, HU Ji-Ming2，Jiang Yan1,2
1,2
(School of Computer Science and Information, Hohai University, Nanjing Jiangsu 210098, China)
Abstract: Topology discovery systems are starting to be introduced in the form of easily and widely deployed software. However, Today's IP network is complex and dynamic. Keeping track of topology information efficiently is a difficult task. So, we need effective algorithms for automatically discovering physical network topology. Earlier work has typically focused on: (1) Layer-3 (network layer) topology, which can only router-to-router interconnections and router interface-to-subnet relationships. This work is relatively easy and has lots of systems can do it. (2)Layer-2(link layer), till now, no tools can discovery the network topology exactly because of bad algorithm. In this paper, Skeleton-tree based on Graph theory is proposed to infer the connections between network nodes. Key words: Skeleton-tree; subnets; Address Forwarding Table; Graph Theory；Trust Node
作者简介: 路连兵(1979－),男,江苏泗洪人,硕士。 主要研究网络自拓扑,软件项目管理,Perl 研究;胡吉明(1967－),男,硕导,副教授,主要研究 领域为计算机应用技术,网络安全,数据挖掘，Z 语言; 姜岩(1979-),男,硕士研究生,主要研究方向,网络应用,中间件
最小生成树算法分析 一、生成树的概念 若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次bfs或dfs后便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs亦可系统地访问所有顶点。在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的生成树。 对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点出发，调用一次bfs或dfs后一般不能系统地访问所有顶点，而只能得到以出发点为根的连通分支（或强连通分支）的生成树。要访问其它顶点需要从没有访问过的顶点中找一个顶点作为起始点，再次调用bfs 或dfs，这样得到的是生成森林。 由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。 可以证明：具有n个顶点的带权连通图，其对应的生成树有n-1条边。 二、求图的最小生成树算法 严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V， E’），且边集E’能将图中所有顶点连通又不形成回路，则称子图G’是图G的一棵生成树。 对于加权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。 求图的最小生成树具有很高的实际应用价值，比如下面的这个例题。
例1、城市公交网 [问题描述] 有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。 [输入] n（城市数，1<=n<=100） e（边数） 以下e行，每行3个数i,j,w ij，表示在城市i,j之间修建高速公路的造价。 [输出] n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。 [举例] 下面的图（A）表示一个5个城市的地图，图（B）、（C）是对图（A）分别进行深度优先遍历和广度优先遍历得到的一棵生成树，其权和分别为20和33，前者比后者好一些，但并不是最小生成树，最小生成树的权和为19。 [问题分析] 出发点：具有n个顶点的带权连通图，其对应的生成树有n-1条边。那么选哪n-1条边呢？设图G的度为n，G=（V，E），我们介绍两种基于贪心的算法，Prim算法和Kruskal算法。 1、用Prim算法求最小生成树的思想如下： ①设置一个顶点的集合S和一个边的集合TE，S和TE的初始状态均为空集； ②选定图中的一个顶点K，从K开始生成最小生成树，将K加入到集合S； ③重复下列操作，直到选取了n-1条边： 选取一条权值最小的边（X，Y），其中X∈S，not (Y∈S)； 将顶点Y加入集合S，边（X，Y）加入集合TE； ④得到最小生成树T =（S，TE）
目录 前言 (1) 1. 邻接矩阵发展简史 (3) 2．基本概念及记号 (4) 3. 无向图的邻接矩阵 (6) 3.1 无向图的邻接矩阵定义及表示 (6) 3.2 无向图的邻接矩阵的性质 (8) 4. 有向图的邻接矩阵 (9) 4.1 有向图的邻接矩阵的定义及表示 (9) 4.2 有向图的邻接矩阵的性质 (10) 5. 邻接矩阵的重要定理及应用 (11) 6. 邻接矩阵的应用 (13) 6.1 邻接矩阵生成图的遍历序列 (13) 6.2用邻接矩阵生成图的广度优先遍历序列 (15) 6.3 矩阵构造最小生成树 (16) 6.4 用邻接矩阵寻找关键路径 (19) 参考文献 (21) 致谢 (22)
平顶山学院本科毕业论文（设计） 前言 图论最早起源于一些数学游戏的难题研究，如欧拉所解决的哥尼斯堡七桥问题，以及在民间广泛流传的一些游戏难题．这些古老的难题，当时吸引了很多学者的注意．在这些问题研究的基础上又继续提出了著名的四色猜想和汉米尔顿（环游世界）数学难题． 1847年，图论应用于分析电路网络，这是它最早应用于工程科学，以后随着科学的发展，图论在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，发挥出越来越大的作用．在人们的社会实践中，图论已成为解决自然科学、工程技术、社会科学、生物技术以及经济、军事等领域中许多问题的有力工具之一，因此越来越受到数学家和实际工作者的喜爱．我们所学的这一章只是介绍一些基本概念、原理以及一些典型的应用实例，目的是在今后对工程技术有关学科的学习研究时，可以把图论的基本知识、方法作为工具[]1． “图论”是数学的一个分支,它以图为研究对象.图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系. 图论是一门极有兴趣的学问，其广阔的应用领域涵盖了人类学、计算机科学、化学、环境保护、电信领域等等.严格地讲，图论是组合数学的一个分支，例如，它交叉运用了拓扑学、群论和数论.图论就是研究一些事物及它们之间关系的学科，现实世界中的许多事物能用图来表示其拓扑结构，把实际问题的研究转化为图的研究，利用图论的相关结论 对这些问题作分析或判断[]1. 图论是近二十年来发展十分迅速、应用比较广泛的一个新兴的数学分支，在许多领域，诸如物理学、化学、运筹学、信息论、控制论、计算机等方面甚至在生产生活中都有广泛的应用.因此受到全世界越来越广泛的重视。图论的内容十分丰富，涉及面也比较广. 研究节点和边组成的图形的数学理论和方法，为运筹学的一个分支。图论的基本元素是节点和边（也称线、弧、枝），用节点表示所研究的对象，用 1
实验九图的最小生成树算法的实现 实验预备知识： 1．理解图最小生成树的意义和相应算法。 2．掌握带权图的存储结构。 一、实验目的 1．使学生熟悉最小生成树的算法实现。 2．掌握带权图的存储结构和处理方法。 二、实验环境 ⒈硬件：每个学生需配备计算机一台。操作系统：DOS或Windows； ⒉软件：DOS或Windows操作系统+Turbo C； 三、实验要求 1．能够独立完成带权图的存储和最小生成树的生成 四、实验内容 1．在自己的U盘的“姓名+学号”文件夹中创建“实验9”文件夹，本次实验的所有程序和数据都要求存储到本文件夹中。 2．现在某电信公司要对如下图的几个城市之间进行光纤连接布线，请用合适的存储结构将下图存储到计算机中方便进行处理。 3．现在公司想以最小的代价将所有城市连通，方便所有城市间通信，请用普里姆算法和克鲁斯卡尔算法实现本图的最小生成树
#include
第1章 1、传输系统的硬件包括哪些？ 线路接口设备、传输媒介、交叉连接设备等。 2、在垂直结构上，可以将通信网分为哪三层？ 应用层、业务网和传送网。 3、从水平分层观点来看，网络结构是基于用户接入网络实际的物理连接来划分的，如何划分？可以分为用户驻地网、接入网和核心网，或者分为局域网、城域网和广域网等。 4、利用网络的基本结构形式可以构成任意类型的非基本拓扑结构。实际常用的非基本结构形式有哪些？（1）复合网；（2）格形网；（3）树形网； 1、简述现代通信网的定义、构成要素和每一要素的基本功能。 （1）通信网是由一定数量的节点(包括终端节点、交换节点)和连接这些节点的传输系统有 机地组织在一起的，按约定的信令或协议完成任意用户间信息交换的通信体系。 （2）实际的通信网是由软件和硬件按特定方式构成的一个通信系统，每一次通信都需要软 硬件设施的协调配合来完成。从硬件构成来看：通信网由终端设备、交换设备和传输 系统构成，它们完成通信网的基本功能：接入、交换和传输。软件设施则包括信令、 协议、控制、管理、计费等，它们主要完成通信网的控制、管理、运营和维护，实现 通信网的智能化。 2、为什么要在通信网中引入分层结构？ （1）可以更清晰地描述现代通信的网络结构； （2）使网络规范与具体实施方法无关，从而简化了网络的规划和设计； （3）使各层的功能相对独立。 3、分别按以下标准对通信网进行分类：（1）通信服务的范围；（2）通信的活动方式。 （1）按通信服务的范围进行分类：本地通信网、长途通信网和国际通信网或局域网(LAN)、 城域网(MAN)和广域网(WAN)等。 （2）按通信的活动方式进行分类：固定通信网和移动通信网等。 4、通信网组网的基本结构形式有哪四种？假如网络节点数为N ，请写出每种结构的链路数。 （1）全连通网；）（1-2 1N N H = （2）星形网；1-N H = （3）环形网;N H = 5、一般通信网的质量要求可以通过哪几个方面进行衡量？影响接通的任意性和快速性的因素有哪些？ （1）对于一般通信网的质量要求可以通过以下几个方面来衡量:接通的任意性与快速性;信息传输的透明性与传输质量的一致性;网络的可靠性与经济合理性. （2）影响接通的任意性和快速性的因素有：通信网的拓扑结构;通信网的网络资源;通信网的可靠性.