根据性质2。4,得:
矩阵 中的元素全为非零元素,易得图1为连通图。 且第 行第 列的元素的大小表示的是 节点到 节点间连通的路径数。
同理,对图2所示的有向图,对应的无向图的节点,其所定义的邻接矩阵为:
,
根据性质2。 4,得:
可见矩阵 中的元素中存在零元素,即图2为非连通图。 同时,第 行第 列元素表示 节点和 节点间连通的路径数。
3。 2 邻接矩阵在最小生成树问题中的应用来*自-优=尔,论:文+网www.youerw.com
设图 为任意的简单图可以是完全的,也可以是不完全的。 图 有 个结点,且其边的集合为 。 求出图 的最小生成树的算法有两种,分别为克鲁斯卡尔算法和普利姆算法。 使用克鲁斯卡尔算法求出最小生成树的过程中,图的存贮结构采用边集数组,且权值相等的边在数组中排列的次序可以是任意的。 该方法对于边相对比较多的并不是很实用。 而若使用普利姆算法计算最小生成树,图的存贮结构采用邻接矩阵,对于边数较多的图也能较易算出。
现在具体介绍一下普利姆算法。 在该算法执行过程中我们使用桶 存放最小生成树的边,桶 存放最小生成树的结点,一个计数器记录桶 中边的数目,一个计数器记录桶 的结点的数目。 开始时,桶 桶 计数器都是空的。