云代码会员 - 云代码空间
——
用邻接矩阵存放图中顶点的关系，实现无向图的邻接矩阵存储。
1）图的建立，删除（添加，删除边/顶点）
2）广度和深度优先遍历
3）prim最小生成树
1，成员变量，构造函数，以及数组扩展
实现策略：维护一个顶点的数组，以及一个二维的数组来表示顶点之间的关系，维护2个基本变量记录顶点和边的数量。
重点是：1）可以动态扩展顶点数组，并保持数组的连续性，这意味着删除顶点时后面的顶点要前移，那么顶点的编号也变了，关系矩阵也要改变。 2）关系矩阵也动态维护，随时保持和顶点数组一样大。顶点数组的长度为VNodes.length，实际存放了顶点的位置只到了size()处，对应的，关系矩阵的大小为int[VNodes.length][VNodes.length]，实际有效地区域也只在左上角的int[size()][size()]范围内。
/*总是将关系矩阵保持和顶点数组大小对应，顶点数组不一定放满，关系矩阵也只
* 在左上角放满，顶点数组放满的大小为size（），关系矩阵也只到size（）*/
private VNode[] VNodes;
private int[][] M;
private int nodeCount;
private int edgeCount;
public MatUnDirectedGraph()
{
VNodes = new VNode[5];
M = new int[5][5];
nodeCount = 0;
edgeCount = 0;
}
public void expand()
{
VNode[] larger = new VNode[VNodes.length * 2];//顶点数组扩大
int[][] M_larger = new int[larger.length][larger.length];//关系矩阵也要扩展
for(int i = 0;i < VNodes.length;i++)
{
larger[i] = VNodes[i];
for(int j = 0;j < VNodes.length;j++)
M_larger[i][j] = M[i][j];
}
VNodes = larger;
M = M_larger;
}
2，建图，删图相关方法分析
用邻接矩阵存储表示顶点之间的关系果然比邻接表在代码实现上简单很多
1）添加边，只需要在关系矩阵M的两个位置上赋值即可，而在邻接表实现中，要在2个顶点的边链表的最后都添加上一个边
2）删除边，1）的逆过程，将那2个位置的值置为0即可，而在邻接表的实现中，也是要到边链表中去删（还要记录被删边得前缀）
3）添加顶点，直接在顶点数组中添加一个，注意如果满的话，要扩展，在扩展方法中，已经实现了同时扩展关系矩阵（将矩阵变大了，左上角有效区域还是不变）。在邻接表中这个稍微简单点，因为邻接表直接扩展数组即可，关系不用动。
4）删除顶点，无论哪种方式，删除顶点都是最麻烦的，在邻接表的实现中，删除顶点要先删除所有跟顶点关联的边，然后后面的顶点前移以保证顶点数组连续，移动会导致原来的顶点的边链表的信息变化（边的端点），所以在移动前我们先将所有边链表中的边得信息调整好，再来移动数组使它保持连续。
在邻接矩阵中，删除了一个顶点也要将顶点数组前移来保持顶点数组连续，结果会导致关系矩阵也要变（假设删除的顶点下标是position，那么左上角M[position][position]大小范围内的矩阵不需要变，从这个边界到M[size][size]范围的矩阵值要向内紧缩---也是因为顶点移动导致顶点下标变了，具体怎么去向内收缩，见代码及注释）
添加和删除边：
public void addEdge(int start,int end,int len){ //在两个指定下标的节点之间添加一条边
M[start][end] = len;
M[end][start] = len;
edgeCount++;
}
//在图中2个顶点之间删除一条边
public void removeEdge(int start,int end){ //删除两个指定下标顶点之间的边
M[start][end] = 0;
M[end][start] = 0;
edgeCount--;
}
添加顶点：
public void addVNode(Object element){ //添加顶点
VNode node = new VNode(element);
if(size() == VNodes.length)
expand(); //扩展方法时同时扩展了关系矩阵
VNodes[nodeCount++] = node;
}
上面三个方法都很简单，最复杂的仍然是删除顶点：弄清楚矩阵是怎么向左上角紧缩的
public Object removeVNode(int position){ //删除顶点
VNode result = VNodes[position];
//先调整关系矩阵
for(int i = 0;i < size();i++)
for(int j = 0;j < size();j++) //将关系矩阵向内紧缩（顶点将要移动）
{
if(i > position && j > position)
M[i-1][j-1] = M[i][j];
else if(i > position)
M[i-1][j] = M[i][j];
else if(j > position)
M[i][j-1] = M[i][j];
}
for(int i = 0;i < size();i++) //紧缩以后，最后一个顶点已经没有意义了（移到倒数第二个了）
{
M[size()-1][i] = 0;
M[i][size()-1] = 0;
}
//再调整顶点数组
for(int i = position;i < size()-1;i++)//保证数组连续性
VNodes[i] = VNodes[i+1];
VNodes[size()-1] = null;
nodeCount--;
return result;
}
3，广度优先遍历和深度优先遍历
拿广度优先遍历来说，顶点A每次从遍历队列出来的时候要将其未被访问的关联顶点添加到遍历队列，这就需要求得A在顶点数组里的位置，然后在关系矩阵里找跟它关联且没有被访问的顶点。
深度优先一样。
仅贴出广度优先，深度优先的实现只需要把遍历队列改成遍历栈即可：
//广度优先遍历图
public Iterator GraphBFS(int position){ //可以遍历多个联通分量的BFS
LinkedQueue queue = new LinkedQueue();
BFSorder(position,queue);
for(int i = 0;i < size();i++) //注意是size，不是VNodes.length,下面的BFSorder也是
if(VNodes[i].getVisited() == false)
BFSorder(i,queue);
return queue.iterator();
}
public Iterator SingleBFS(int position){ //只遍历position所在连通域的BFS
LinkedQueue queue = new LinkedQueue();
BFSorder(position,queue);
return queue.iterator();
}
private void BFSorder(int position,LinkedQueue queue){//按照广度规则从position开始将position所在连通分量顶点进队
LinkedQueue tempqueue = new LinkedQueue();
tempqueue.enqueue(VNodes[position]);
VNodes[position].setVisited(true);
while(!tempqueue.isEmpty())
{
VNode node = (VNode) tempqueue.dequeue();
queue.enqueue(node);
int index = 0;
for(int i = 0;i < size();i++)
if(VNodes[i] == node)
index = i;//node在数组里的下标
for(int i = 0;i < size();i++)
if(M[index][i] != 0 && VNodes[i].getVisited() == false)
{
tempqueue.enqueue(VNodes[i]);
VNodes[i].setVisited(true);
}
}
}
4，prim最小生成树
用邻接表写过之后，prim的思想也就很熟悉了，用邻接矩阵写也比较顺利，很容易就写成功了。这里可以直接在关系矩阵M里去找最小值，简单一点，不像邻接表实现需要那么多的支持方法。
直接贴出代码：
1 //prim最小生成树
2 public Edge[] getEdges(int position){
3 Edge[] Edges = new Edge[size()-1];
4 VNodes[position].setVisited(true);
5 for(int i = 0;i < Edges.length;i++)
6 Edges[i] = getMinEdge(VNodes);
7 return Edges;
8 }
9
10 private Edge getMinEdge(VNode[] VNodes){ //从当前分割的两个顶点集合之间找最小边
11
12 //直接在关系矩阵中找就可以了(逻辑简单点，也可以从顶点数组去循环查找)
13 Edge min = null;
14 for(int i = 0;i < size();i++)
15 for(int j = 0;j < size();j++)
16 if(VNodes[i].getVisited() && !VNodes[j].getVisited() && M[i][j] != 0)
17 {
18 if(min == null)
19 min = new Edge(i,j,M[i][j]);
20 else
21 if(M[i][j] < min.getLen())
22 min = new Edge(i,j,M[i][j]);
23 //VNodes[j].setVisited(true);
24 }
25 VNodes[min.getEnd()].setVisited(true);
26 return min;
27 }
28
5，完整清单及测试
MatUnDirectedGraph
package Graph;
import java.util.Iterator;
import java.util.Stack;
import Queue.LinkedQueue;
import Stack.LinkedStack;
//邻接矩阵实现一个无向图，顶点仍是放在数组中
public class MatUnDirectedGraph {
/*总是将关系矩阵保持和顶点数组大小对应，顶点数组不一定放满，关系矩阵也只
* 在左上角放满，顶点数组放满的大小为size（），关系矩阵也只到size（）*/
private VNode[] VNodes;
private int[][] M;
private int nodeCount;
private int edgeCount;
public MatUnDirectedGraph()
{
VNodes = new VNode[5];
M = new int[5][5];
nodeCount = 0;
edgeCount = 0;
}
public void expand()
{
VNode[] larger = new VNode[VNodes.length * 2];//顶点数组扩大
int[][] M_larger = new int[larger.length][larger.length];//关系矩阵也要扩展
for(int i = 0;i < VNodes.length;i++)
{
larger[i] = VNodes[i];
for(int j = 0;j < VNodes.length;j++)
M_larger[i][j] = M[i][j];
}
VNodes = larger;
M = M_larger;
}
public int size(){
return nodeCount;
}
public boolean isEmpty(){
return size() == 0;
}
//在图中的2个顶点之间添加一条边
public void addEdge(int start,int end,int len){ //在两个指定下标的节点之间添加一条边
M[start][end] = len;
M[end][start] = len;
edgeCount++;
}
public boolean hasEdge(int start,int end){ //判断2个顶点之间是否存在边
if(M[start][end] != 0)
return true;
return false;
}
//在图中2个顶点之间删除一条边
public void removeEdge(int start,int end){ //删除两个指定下标顶点之间的边
M[start][end] = 0;
M[end][start] = 0;
edgeCount--;
}
//向图中添加一个顶点
public void addVNode(Object element){ //添加顶点
VNode node = new VNode(element);
if(size() == VNodes.length)
expand(); //扩展方法时同时扩展了关系矩阵
VNodes[nodeCount++] = node;
}
//从图中删除一个顶点
public Object removeVNode(int position){ //删除顶点
VNode result = VNodes[position];
//先调整关系矩阵
for(int i = 0;i < size();i++)
for(int j = 0;j < size();j++) //将关系矩阵向内紧缩（顶点将要移动）
{
if(i > position && j > position)
M[i-1][j-1] = M[i][j];
else if(i > position)
M[i-1][j] = M[i][j];
else if(j > position)
M[i][j-1] = M[i][j];
}
for(int i = 0;i < size();i++) //紧缩以后，最后一个顶点已经没有意义了（移到倒数第二个了）
{
M[size()-1][i] = 0;
M[i][size()-1] = 0;
}
//再调整顶点数组
for(int i = position;i < size()-1;i++)//保证数组连续性
VNodes[i] = VNodes[i+1];
VNodes[size()-1] = null;
nodeCount--;
return result;
}
//广度优先遍历图
public Iterator GraphBFS(int position){ //可以遍历多个联通分量的BFS
LinkedQueue queue = new LinkedQueue();
BFSorder(position,queue);
for(int i = 0;i < size();i++) //注意是size，不是VNodes.length,下面的BFSorder也是
if(VNodes[i].getVisited() == false)
BFSorder(i,queue);
return queue.iterator();
}
public Iterator SingleBFS(int position){ //只遍历position所在连通域的BFS
LinkedQueue queue = new LinkedQueue();
BFSorder(position,queue);
return queue.iterator();
}
private void BFSorder(int position,LinkedQueue queue){//按照广度规则从position开始将position所在连通分量顶点进队
LinkedQueue tempqueue = new LinkedQueue();
tempqueue.enqueue(VNodes[position]);
VNodes[position].setVisited(true);
while(!tempqueue.isEmpty())
{
VNode node = (VNode) tempqueue.dequeue();
queue.enqueue(node);
int index = 0;
for(int i = 0;i < size();i++)
if(VNodes[i] == node)
index = i;//node在数组里的下标
for(int i = 0;i < size();i++)
if(M[index][i] != 0 && VNodes[i].getVisited() == false)
{
tempqueue.enqueue(VNodes[i]);
VNodes[i].setVisited(true);
}
}
}
//深度优先遍历图
public Iterator GraphDFS(int position){ //可以遍历多个连通分量的DFS
LinkedQueue queue = new LinkedQueue();
DFSorder(position,queue);
for(int i = 0;i < size();i++)
if(VNodes[i].getVisited() == false)
DFSorder(i,queue);
return queue.iterator();
}
public Iterator SingleDFS(int position){ //只遍历position所在连通域的DFS
LinkedQueue queue = new LinkedQueue();
DFSorder(position,queue);
return queue.iterator();
}
//按照深度优先规则将position所在连通域顶点进队
public void DFSorder(int position,LinkedQueue queue){
Stack tempstack = new Stack();
tempstack.push(VNodes[position]);
VNodes[position].setVisited(true);
while(!tempstack.isEmpty())
{
VNode node = (VNode) tempstack.pop();
queue.enqueue(node);
int index = 0; //node在数组里的下标
for(int i = 0;i < size();i++)
if(VNodes[i] == node)
index = i;
for(int i = 0;i < size();i++)
if(M[index][i] != 0 && VNodes[i].getVisited() == false)
{
tempstack.push(VNodes[i]);
VNodes[i].setVisited(true);
}
}
}
public void clearVisited(){ //清除访问记录
for(int i = 0;i < size();i++)
VNodes[i].setVisited(false);
}
//prim最小生成树
public Edge[] getEdges(int position){
Edge[] Edges = new Edge[size()-1];
VNodes[position].setVisited(true);
for(int i = 0;i < Edges.length;i++)
Edges[i] = getMinEdge(VNodes);
return Edges;
}
private Edge getMinEdge(VNode[] VNodes){ //从当前分割的两个顶点集合之间找最小边
//直接在关系矩阵中找就可以了(逻辑简单点，也可以从顶点数组去循环查找)
Edge min = null;
for(int i = 0;i < size();i++)
for(int j = 0;j < size();j++)
if(VNodes[i].getVisited() && !VNodes[j].getVisited() && M[i][j] != 0)
{
if(min == null)
min = new Edge(i,j,M[i][j]);
else
if(M[i][j] < min.getLen())
min = new Edge(i,j,M[i][j]);
//VNodes[j].setVisited(true);
}
VNodes[min.getEnd()].setVisited(true);
return min;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
MatUnDirectedGraph g = new MatUnDirectedGraph();
for(int i = 1;i < 7;i++)
g.addVNode("V" + i);
g.addEdge(0, 1, 6);
g.addEdge(0, 2, 1);
g.addEdge(0, 3, 5);
g.addEdge(1, 2, 5);
g.addEdge(1, 4, 5);
g.addEdge(2, 3, 5);
g.addEdge(2, 4, 6);
g.addEdge(2, 5, 4);
g.addEdge(3, 5, 2);
g.addEdge(4, 5, 6);//严蔚敏数据结构中的那个图
System.out.println("关系矩阵为： ");
for(int i = 0;i < g.size();i++)
{
for(int j = 0;j < g.size();j++)
System.out.print(g.M[i][j] + " ");
System.out.println();
}
Edge[] edges = g.getEdges(0);
System.out.println("\n输出最小生成树的边: \n");
for(int i = 0;i < edges.length;i++)
{
int start = edges[i].getStart();
int end = edges[i].getEnd();
System.out.println("边： " + g.VNodes[start].getVNode() +"---" + g.VNodes[end].getVNode()
+ " 长度：" + edges[i].getLen());
}
/*
for(int i = 0;i < 15;i++)
g.addVNode(i);
g.addEdge(0, 2,1);
g.addEdge(0, 3,1);
g.addEdge(1, 2,1);
g.addEdge(1, 5,1);
g.addEdge(1, 4,1);
g.addEdge(2, 5,1);
g.addEdge(3, 7,1);
g.addEdge(3, 9,1);
g.addEdge(4, 9,1);
g.addEdge(5, 9,1);
g.addEdge(6, 8,1);
g.addEdge(6, 9,1);
g.addEdge(7, 8,1);
g.addEdge(10, 13, 1);
g.addEdge(10, 12, 1);
g.addEdge(13, 12, 1);
//g.removeVNode(10);
//g.removeVNode(11);
//g.removeVNode(12);
//g.removeVNode(13);
//g.removeVNode(14);
System.out.println("图大小为： " + g.size());
System.out.println("\n关系矩阵为： ");
for(int i = 0;i < g.size();i++)
{
for(int j = 0;j < g.size();j++)
System.out.print(g.M[i][j] + " ");
System.out.println();
}
Iterator it = g.SingleBFS(0);
System.out.println("\n广度优先遍历为： ");
while(it.hasNext())
{
VNode node = (VNode) it.next();
System.out.print(node.getVNode() + " ");
}
g.clearVisited();
it = g.SingleDFS(0);
System.out.println("\n深度优先遍历为： ");
while(it.hasNext())
{
VNode node = (VNode) it.next();
System.out.print(node.getVNode() + " ");
}
g.clearVisited();
it = g.GraphBFS(0);
System.out.println("\n\n整个图的广度优先遍历为： ");
while(it.hasNext())
{
VNode node = (VNode) it.next();
System.out.print(node.getVNode() + " ");
}
g.clearVisited();
it = g.GraphDFS(0);
System.out.println("\n整个图的深度优先遍历为： ");
while(it.hasNext())
{
VNode node = (VNode) it.next();
System.out.print(node.getVNode() + " ");
}
*/
}
}
只贴出最小生成树的结果：
仍然构造上节中的最小生成树---
关系矩阵为：
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