图的邻接矩阵表示形式，DFS和BFS，最小生成树Prim和Kruscal，单源最短路径Dijkstra算法

时间：2021-03-22 12:35:13

图的邻接矩阵表示：

package com.AlgorithmDemo.Graphic;
/*
 * author:Tammy Pi
 * function:邻接矩阵的图
 */
public class AdMatrixGraph {

//节点个数
private int nodenum=0;
//边个数
private int cirnum=0;
    //邻接矩阵
private int[][] matrix;

//构造函数，初始化图
public AdMatrixGraph(int nodenum,int cirnum)
{
this.nodenum=nodenum;
this.cirnum=cirnum;
matrix=new int[nodenum][nodenum];

for(int i=0;i<nodenum;i++)
{
for(int j=0;j<nodenum;j++)
{
matrix[i][j]=0;
}
}
}

public int getNodenum() {
return nodenum;
}

public void setNodenum(int nodenum) {
this.nodenum = nodenum;
}

public int getCirnum() {
return cirnum;
}

public void setCirnum(int cirnum) {
this.cirnum = cirnum;
}

public int[][] getMatrix() {
return matrix;
}

public void setMatrix(int[][] matrix) {
this.matrix = matrix;
}

//无向图
public void add(int i,int j)
{
this.matrix[i][j]=1;
this.matrix[j][i]=1;
}
//无向图重载
public void add(int i,int j,int data)
{
this.matrix[i][j]=data;
this.matrix[j][i]=data;
}
}

算法中需用到的队列：

package com.AlgorithmDemo.Container;
import java.util.*;
/*
 * author:Tammy Pi
 * function:队列容器
 */
public class MyQueue {

private List<Integer> queue;

public MyQueue()
{
queue=new LinkedList<Integer>();
}
public void addElement(int elem)
{
queue.add(elem);
}
public boolean isEmtpy()
{
if(queue==null||queue.size()==0)
{
return true;
}
return false;
}
public int removeElement()
{
    returnqueue.remove(0);
}
public int getSize()
{
if(queue!=null)
{
return queue.size();
}
return 0;
}
//清空队列
public void clear()
{
queue.clear();
}

//用于测试的主函数
public static void main(String[] args)
{
int[] a=new int[]{2,3,1,5};
MyQueue queue=new MyQueue();
for(int i=0;i<a.length;i++)
{
queue.addElement(a[i]);
}
for(int i=0;i<a.length;i++)
{
System.out.print(queue.removeElement()+" ");
}
System.out.println("queue："+queue.getSize());
}
}

BFS和DFS算法：

package com.AlgorithmDemo.Graphic;
import java.util.*;
import com.AlgorithmDemo.Container.MyQueue;
/*
 * author:Tammy Pi
 * function:图的邻接矩阵表示，即DFS和BFS
 */
public class BFSVSDFS {

private AdMatrixGraph graph;
private int[] visited=null;
private MyQueue queue=null;
public BFSVSDFS(AdMatrixGraph graph)
{
this.graph=new AdMatrixGraph(graph.getNodenum(),graph.getCirnum());

visited=new int[this.graph.getNodenum()];
queue=new MyQueue();

this.graph.add(0,1);
this.graph.add(0,2);
this.graph.add(0,3);
this.graph.add(1,5);
this.graph.add(5,4);
this.graph.add(2,6);
this.graph.add(3,7);
}
//DFS
public void DFSTraverse(int i)
{
queue.addElement(i);

while(!queue.isEmtpy())
{
int node=queue.removeElement();
visited[i]=1;
System.out.print(i+" ");

for(int j=0;j<graph.getNodenum();j++)
{
if(graph.getMatrix()[node][j]==1&&visited[j]==0)
{
DFSTraverse(j);
}
}
}
}//DFSTraverse
public void DFS()
{
//初始化，设置所有节点均未访问过
for(int i=0;i<graph.getNodenum();i++)
{
visited[i]=0;
}
queue.clear();

//开始遍历
for(int i=0;i<graph.getNodenum();i++)
{
if(visited[i]==0)
{
DFSTraverse(i);
}
}
}//DFS

//BFS
public Integer getNearNode(int i)
{
for(int j=0;j<this.graph.getNodenum();j++)
{
if(this.graph.getMatrix()[j][i]==1&&visited[j]==0)
{
return j;
}
}
return null;
}
public void BFS()
{
//初始化，设置node未访问
for(int i=0;i<this.graph.getNodenum();i++)
{
visited[i]=0;
}
queue.clear();

//广度遍历
queue.addElement(0);
System.out.print("0 ");
visited[0]=1;

while(!queue.isEmtpy())
{
int node=queue.removeElement();
//遍历它的所有节点
for(Integer j=getNearNode(node);j!=null;j=getNearNode(node))
{
System.out.print(j+" ");
visited[j]=1;
queue.addElement(j);
}
}
}

//用于测试的主函数
public static void main(String[] args)
{
AdMatrixGraph graph=new AdMatrixGraph(8,7);
BFSVSDFS bfs=new BFSVSDFS(graph);
System.out.print("深度遍历的结果为：");
bfs.DFS();
System.out.println();
System.out.print("广度遍历的结果为：");
bfs.BFS();
}
}

最小生成树Prim算法：

package com.AlgorithmDemo.MinimumSpaninngTree;
import com.AlgorithmDemo.Graphic.AdMatrixGraph;
/*
 * author:Tammy Pi
 * function:最小生成树算法
 */
public class PrimAlgorithm {


private AdMatrixGraph graph;
private int[] s=null;
private int index=-1;

public void createTree(int nodenum,int cirnum)
{
graph=new AdMatrixGraph(nodenum,cirnum);
s=new int[graph.getNodenum()];

this.graph.add(0,1,1);
this.graph.add(0,3,1);
this.graph.add(0,2,3);
this.graph.add(3,2,1);
}

public boolean isContain(int j)
{
for(int k=0;k<=index;k++)
{
if(s[k]==j)
{
return true;
}
}
return false;
}
public int getMinValue(int node)
{
int minValue=Integer.MAX_VALUE;
for(int i=0;i<=index;i++)
{
if(this.graph.getMatrix()[i][node]!=0&&this.graph.getMatrix()[i][node]<minValue)
{
minValue=this.graph.getMatrix()[i][node];
}
}
return minValue;
}
public void prim()
{
//首先将0节点加入集合S中
s[++index]=0;
System.out.print("用Prim算法得到的最小生成树为："+0+" ");

while(!(index==graph.getNodenum()-1))
{
int minIndex=0;
int minValue=Integer.MAX_VALUE;
//计算与集合s中的点距离最小的点
for(int j=0;j<graph.getNodenum();j++)
{
if(!isContain(j))
{
if(getMinValue(j)<minValue)
{
minIndex=j;
minValue=getMinValue(j);
}
}
}
System.out.print(minIndex+" ");
s[++index]=minIndex;
}
System.out.println();
}

//用于测试的主函数
public static void main(String[] args)
{
PrimAlgorithm prim=new PrimAlgorithm();
prim.createTree(4,4);
prim.prim();
}
}

最小生成树Kruscal算法：

package com.AlgorithmDemo.MinimumSpaninngTree;
import com.AlgorithmDemo.Graphic.AdMatrixGraph;
/*
 * author:Tammy Pi
 * function:用Kruscal算法得到最小生成树
 */
public class KruscalAlgorithm {

private AdMatrixGraph graph;
private int[] s=null;
private int index=-1;
private int index1=-1;

public void createTree(int nodenum,int cirnum)
{
graph=new AdMatrixGraph(nodenum,cirnum);
s=new int[graph.getNodenum()];

this.graph.add(0,1,1);
this.graph.add(0,3,1);
this.graph.add(0,2,3);
this.graph.add(3,2,1);
}
    //在S集合中包含
public boolean isContain(int j)
{
for(int k=0;k<=index;k++)
{
if(s[k]==j)
{
return true;
}
}
return false;
}
//找到最短边的两端节点序号
public int[] getMinCir()
{
int[] minIndex=new int[2];
int minValue=Integer.MAX_VALUE;

for(int j=0;j<this.graph.getNodenum();j++)
{
for(int k=0;k<this.graph.getNodenum();k++)
{
//j和k不能相同
if(j==k)
{
continue;
}
//最小生成树不能包括环
if(isContain(j)&&isContain(k))
{
continue;
}
if(this.graph.getMatrix()[j][k]!=0&&this.graph.getMatrix()[j][k]<minValue)
{
minValue=this.graph.getMatrix()[j][k];
index1=-1;
if(!isContain(j))
{
minIndex[++index1]=j;
}
if(!isContain(k))
{
minIndex[++index1]=k;
}
}
}//for k
}//for j
return minIndex;
}
public void kruscal()
{
System.out.print("Kruscal算法得到的最小生成树为：");
while(!(index==this.graph.getNodenum()-1))
{
int[] minIndex=getMinCir();
for(int i=0;i<=index1;i++)
{
s[++index]=minIndex[i];
System.out.print(minIndex[i]+" ");
}
}
System.out.println();
}
//用于测试的主函数
public static void main(String[] args)
{
KruscalAlgorithm kruscal=new KruscalAlgorithm();
kruscal.createTree(4,4);
kruscal.kruscal(); 
}
}

单源最短路径算法：

package com.AlgorithmDemo.sigleSource.shortestPath;
import com.AlgorithmDemo.Graphic.AdMatrixGraph;
import java.util.*;
/*
 * author:Tammy Pi
 * function:单源最短路径Dijkstra
 */
public class DijkstraAlgorithm {

private AdMatrixGraph graph;
//用于存放S集合
private int[] s=null;
//当前节点
private int currentNode=0;
//目的节点
private int targetNode=0;
//用于记录
private int[] pre;
//用于记录各个节点与当前节点的距离
private int[] record;
private int index=-1;
private int index1=-1;

public void createTree(int nodenum,int cirnum)
{
graph=new AdMatrixGraph(nodenum,cirnum);
s=new int[graph.getNodenum()];
pre=new int[graph.getNodenum()];
record=new int[graph.getNodenum()];

int[][] kk=new int[this.graph.getNodenum()][this.graph.getNodenum()];
for(int i=0;i<kk.length;i++)
{
for(int j=0;j<kk.length;j++)
{
kk[i][j]=Integer.MAX_VALUE;
}
}
this.graph.setMatrix(kk);
this.graph.add(0,1,4);
this.graph.add(0,4,1);
this.graph.add(0,3,5);
this.graph.add(4,1,1);
this.graph.add(1,2,1);
this.graph.add(2,3,1);

//源节点为0，目标节点为2
this.currentNode=0;
this.targetNode=2;
s[++index]=0;
for(int i=0;i<this.graph.getNodenum();i++)
{
pre[i]=-1;
}
for(int i=0;i<this.graph.getNodenum();i++)
{
record[i]=Integer.MAX_VALUE;
}
record[0]=0;
}
public boolean isContain(int j)
{
for(int i=0;i<=index;i++)
{
if(s[i]==j)
{
return true;
}
}
return false;
}
//找到最近的点
public int getNearest()
{
int minIndex=-1;
int minValue=Integer.MAX_VALUE;
for(int i=0;i<this.graph.getNodenum();i++)
{
if(isContain(i))
{
continue;
}
if(record[i]<minValue)
{
minValue=record[i];
minIndex=i;
}
}
return minIndex;
}
//Dijkstra算法
public void dijkstra()
{
while(!(index==this.graph.getNodenum()-1))
{
for(int i=0;i<this.graph.getNodenum();i++)
{
if(i!=currentNode&&!isContain(i)&&this.graph.getMatrix()[currentNode][i]!=Integer.MAX_VALUE)
{
  if(record[currentNode]+this.graph.getMatrix()[currentNode][i]<record[i])
  {
record[i]=record[currentNode]+this.graph.getMatrix()[currentNode][i];
pre[i]=currentNode;
  }
}//if i
}//for i
currentNode=getNearest();
s[++index]=currentNode;
}//while s

//输出
System.out.println("Dijkstra算法求得单源最短路径：");
for(int i=1;i<this.graph.getNodenum();i++)
{
System.out.println(i+"距离0最短距离："+record[i]+"，它的前驱为："+pre[i]);
}
System.out.println();
}
public static void main(String[] args)
{
DijkstraAlgorithm dijkstra=new DijkstraAlgorithm();
dijkstra.createTree(5,6);
dijkstra.dijkstra();
}
}
标签：

相关文章