用邻接矩阵存放图中顶点的
关系,实现无向图的邻接矩阵
存储。
1)图的
建立,删除(添加,删除边/顶点)
2)广度和深度优先遍历
3)prim最小生成树
1,成员变量,
构造函数,以及数组扩展
实现
策略:维护一个顶点的数组,以及一个二维的数组来表示顶点之间的关系,维护2个
基本变量记录顶点和边的数量。
重点是:1)
可以动态扩展顶点数组,并保持数组的连续性,这意味着删除顶点时后面的顶点要前移,那么顶点的编号也变了,关系矩阵也要改变。 2)关系矩阵也动态维护,随时保持和顶点数组一样大。
顶点数组的长度为VNodes.length,实际存放了顶点的位置只到了size()处,对应的,关系矩阵的大小为int[VNodes.length][VNodes.length],实际有效地区域也只在左上角的int[size()][size()]范围内。
2,建图,删图相关
方法
分析
用邻接矩阵存储表示顶点之间的关系果然比邻接表在代码实现上简单很多
1)添加边,只需要在关系矩阵M的两个位置上赋值即可,而在邻接表实现中,要在2个顶点的边链表的最后都添加上一个边
2)删除边,1)的逆
过程,将那2个位置的值置为0即可,而在邻接表的实现中,也是要到边链表中去删(还要记录被删边得前缀)
3)添加顶点,直接在顶点数组中添加一个,
注意如果满的话,要扩展,在扩展方法中,已经实现了同时扩展关系矩阵(将矩阵变大了,左上角有效区域还是不变)。在邻接表中这个稍微简单点,因为邻接表直接扩展数组即可,关系
不用动。
4)删除顶点,无论哪种方式,删除顶点都是最麻烦的,在邻接表的实现中,删除顶点要先删除所有跟顶点关联的边,然后后面的顶点前移以
保证顶点数组连续,移动会导致原来的顶点的边链表的信息变化(边的端点),所以在移动前
我们先将所有边链表中的边得信息
调整好,再来移动数组使它保持连续。
在邻接矩阵中,删除了一个顶点也要将顶点数组前移来保持顶点数组连续,结果会导致关系矩阵也要变(假设删除的顶点下标是position,那么左上角M[position][position]大小范围内的矩阵不需要变,从这个边界到M[size][size]范围的矩阵值要向内紧缩---也是因为顶点移动导致顶点下标变了,具体怎么去向内收缩,见代码及注释)
添加和删除边:
添加顶点:
上面三个方法都很简单,最复杂的仍然是删除顶点:弄清楚矩阵是怎么向左上角紧缩的
3,广度优先遍历和深度优先遍历
拿广度优先遍历来说,顶点A每次从遍历队列出来的时候要将其未被
访问的关联顶点添加到遍历队列,这就需要求得A在顶点数组里的位置,然后在关系矩阵里找跟它关联且没有被访问的顶点。
深度优先一样。
仅贴出广度优先,深度优先的实现只需要把遍历队列改成遍历栈即可:
4,prim最小生成树
用邻接表写过之后,prim的思想也就很熟悉了,用邻接矩阵写也比较顺利,很
容易就写
成功了。这里可以直接在关系矩阵M里去找最小值,简单一点,不像邻接表实现需要那么多的支持方法。
直接贴出代码:
5,完整清单及测试
只贴出最小生成树的结果:
仍然构造上节中的最小生成树---
关系矩阵为:
0 6 1 5 0 0
6 0 5 0 5 0
1 5 0 5 6 4
5 0 5 0 0 2
0 5 6 0 0 6
0 0 4 2 6 0
输出最小生成树的边:
边: V1---V3 长度:1
边: V3---V6 长度:4
边: V6---V4 长度:2
边: V3---V2 长度:5
边: V2---V5 长度:5