矩阵理论在数据结构中的应用.pdfVIP

用应的中构结据数在论理阵矩 矩阵理论在数据结构中的应用 徐 玮 王 芳 Xu WeiWang Fang （东华理工大学长江学院,江西 南昌 330013） （East China Institute of Technology， Jiangxi Nanchang330013） 摘 要:本文主要阐述矩阵在数据结构中的应用。随着计算机应用范围的不断扩大，数学方面的知识也越来越多地融 入到计算机应用中，两者互相渗入，互相融合，为彼此的应用开辟了广阔的前景。 关键词:矩阵;数据结构;关键路径;最小生成树 中图分类号：TP312 文献标识码：A 文章编号：1671-4792-(2007)11-0105-02 Abstract: Keywords: 0 引言 所谓关键路径，就是整个工程各路径中各活动持续时间 矩阵理论是一门研究矩阵在数学上的应用的科目。矩阵 之和最长的那些路径，即路径长度最长的路径。关键路径长 理论本来是线性代数的一个小分支，但其後由于陆续在图 度是整个工程完工至少需要的时间，关键路径上的活动是影 论、代数、组合数学和统计上得到应用，渐渐发展成为一门 响工程进度的关键活动。 独立的学科。矩阵理论既是学习经典数学的基础，又是一门 利用邻接矩阵寻找关键路径的基本步骤如下: 最有实用价值的数学理论。它不仅是数学的一个重要分支， (1)作已知有向无环图的邻接矩阵。 而且业已成为现代各科技领域处理大量有限维空间形式与数 (2)在源点s和汇点j之间根据“ Vi，Vj → Vj，Vk” 量关系的强有力的工具。矩阵理论具有十分丰富的内容，它 规则生成所有弧线性表，权和最大的那些弧线性表对应的路 是学习数学与其它学科 （例如数值分析、最优化理论、概率 径即为关键路径 （权和最小的线性表为最短路径）。 统计、运筹学、控制理论、力学、电学、信息科学、管理科 学与工程）的基础，也是科学与工程计算的有力工具，特别 是计算机的广泛应用，也为矩阵论的应用开辟了广阔的前 景。例如，系统工程、优化方法以及稳定性理论等，都与矩 阵论有着密切的联系，从而使矩阵理论近年来在内容上有相 当大的更新，非现有教科书所能概括，下面着重介绍矩阵在 数据结构中的应用。 1 矩阵在数据结构中求关键路径的应用 首先，在计算机领域中，数据结构一直都占有举足轻重 的地位。而在计算机数据结构中广泛地使用矩阵来描述结构 图一 G5有向无环示意图 和解决问题。 生成所有弧线性表 （弧定义为（出顶，入顶，权））： 例如在数据结构中解决关键路径的问题。已知一个带权 ①1，2，6→2，5，1→5，7，9→7，9，2 的有向无环图，其顶点表示事件，弧表示活动，权表示活动 ②1，2，6→2，5，1→5，8，7→8，9，4 持续的时间。图中只有一个入度为零的点（源点s）和一个 ③1，3，4→3，5，1→5，7，9→7，9，2 出度为零的点（汇点j）。将有向无环图看成是一个工程，对 ④1，3，4→3，5，1→5，8，7→8，9，4 有向无环图 （AOE网）有待研究的问题是: ⑤1，4，5→4，6，2→6，8，4→8，9，4 ①完成整个工程至少需要多少时间; 上述五条弧线性表的权和依次是18，18，16，16，15， ②哪些活动是影响工程进度的关键。 因此，①和②条弧线性表对应的路径是关键路径。 59 科技广场 2007.11 图四 G4无向连通图 图五 G4下三角连