图论网络资料模型与案例分析.ppt

《图论网络资料模型与案例分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、图论（网络）模型与案例分析2012年7月12日第1讲：图的基本概念、图的存储表示第2讲：图的连通性、图的遍历、图的最小生成树第3讲：最短路径问题、匹配问题、一笔画问题第4讲：活动网络（AOV、AOE）、流网络（网络流）第5讲：历年全国大学生数学建模竞赛试题与案例分析内容提要第1讲图的基本概念、画法及计算机存取ABCDABCDE有向图G1无向图G2结点或顶点：有向边（弧）、弧尾或初始结点、弧头或终止结点ABAB有向图：G1=（V1，{A1}）V1={A,B,C,D}A1={,,,}结点或顶点：无向边或边AB无

2、向图：G2=（V2，{A2}）V2={A,B,C,D,E}A2={(A,B),(A,C),(B,D),(B,E),(C,E),(D,E)}ABA.图的基本概念子图ABCD无向图G2AACDACABCD有向图G1的子图ABCDEABDEAABCDABCDE无向图G2的子图有向图G1图生成子图图的其它术语完全图：有n(n-1)/2条边的无向图。其中n是结点个数。有向完全图：有n(n-1)条边的有向图。其中n是结点个数。竞赛图：完全图的定向图。边的权值，边有权的图称之为网络。邻接点：无向图结点的度有向图结点的出度和入度ABCDEHM无向图G1有向图G2

3、ABCDB.图的绘制：—LatexCadC.图的计算机存取邻接矩阵和加权邻接矩阵√邻接表十字链表邻接多重表邻接矩阵ABCD无权值的有向图的邻接矩阵设有向图具有n个结点，则用n行n列的布尔矩阵A表示该有向图；并且A[i,j]=1,如果i至j有一条有向边；A[i,j]=0如果i至j没有一条有向边注意：A[i,i]=0。出度:i行之和。入度:j列之和。表示成右图矩阵0110000000011000在物理实现时的考虑：分别用0、1、2、3分别标识结点A、B、C、D。而将真正的数据场之值放入一个一维数组之中。01230123DABC0123邻接矩阵无权值的

4、无向图的邻接矩阵设无向图具有n个结点，则用n行n列的布尔矩阵A表示该无向图；并且A[i,j]=1,如果i至j有一条无向边；A[i,j]=0如果i至j没有一条无向边注意：A[i,i]=0。i结点的度i行或i列之和。上三角矩阵或下三角矩阵。表示成右图矩阵0110010011100010100101110ABCDE在物理实现时的考虑，和前一页的无向图类似。加权邻接矩阵有向图的加权邻接矩阵设有向图具有n个结点，则用n行n列的矩阵A表示该有向图；并且A[i,j]=a,如果i至j有一条有向边且它的权值为a。A[i,j]=‘空或其它标志；如果i至j没有一条有向

5、边。ABCD表示成右图矩阵abbbaaaaabbb优点：判断任意两点之间是否有边方便，仅耗费O(1)时间。缺点：即使<

6、点：存储量＝结点数＋边数缺点：确定i-->j是否有边，最坏需耗费O(n)时间。无向图同一条边表示两次边表空间浪费一倍。有向图中寻找进入某结点的边，非常困难。dataadj结点表中的结点的表示：用数组data:结点的数据场，保存结点的数据值。adj:结点的指针场，给出自该结点出发的的第一条边的边结点的地址。datafirstarc结点表中的结点的表示：用单链表data:结点的数据场，保存结点的数据值。firstarc:结点的指针场，给出自该结点出发的的第一条边的边结点的地址。nextvex:结点的指针场，给出该结点的下一结点的地址。nextvexc

7、ostdestlink边结点表中的结点的表示：cost:边结点的数据场，保存边的权值等。dest:边结点的指针场，给出本条边依附的另一结点（非出发结点）的地址。link:结点的指针场，给出自该结点出发的的下一条边的边结点的地址。邻接表实例：ABCD无向图G2ABCDE向图G1ABCD12030123nullnullnullnulldataadjdestlinkAB1201234nulldataadj03041423CDE41nullnullnullnull6条边却用了12个边结点!!!改进：建立邻接多重表寻找进入结点的边非常困难!!!改进：建立逆

8、邻接表或十字链表destlink邻接表逆邻接表实例：ABCD有向图G1AB230123null002CDnullnullnull注意：在