首页 > 代码库 > 图

下面用java实现了图,这个图使用邻接矩阵来实现。然后图的遍历使用了:深度遍历,广度遍历。最小生成树使用普利姆算法以及克鲁斯卡尔算法

package net.itaem.graph;

public class Edge implements Comparable<Edge>{
    private int start;   //起点
    private int end;    //终点
    private int weight = Integer.MAX_VALUE / 2;   //权值,默认为无穷大
    
    public Edge(int start, int end, int weight){
    	this.start = start;
    	this.end = end;
    	this.weight = weight;
    }

	public int getStart() {
		return start;
	}

	public void setStart(int start) {
		this.start = start;
	}

	public int getEnd() {
		return end;
	}

	public void setEnd(int end) {
		this.end = end;
	}

	public int getWeight() {
		return weight;
	}

	public void setWeight(int weight) {
		this.weight = weight;
	}

	@Override
	public String toString() {
		return "Edge [start=" + start + ", end=" + end + ", weight=" + weight
				+ "]";
	}
        //实现了Comparable<Edge>接口,用于排序的时候使用
	@Override
	public int compareTo(Edge that) {
		if(that == this) return 0;
		
		
		return this.getWeight() - that.getWeight();
	}
    
}



package net.itaem.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * 使用邻接矩阵来实现图
 * */
public class Graph {

	private List<String> vexList;

	private List<Edge> edgeList;

	private int[][] edgeArray;

	private boolean[] visited;
	//创建一个图
	public Graph(int size){
		this.vexList = new ArrayList<String>();
		this.edgeList = new ArrayList<Edge>();
		this.edgeArray = new int[size][size];

		for(int i=0; i<size; i++){
			for(int j=0; j<size; j++){
				edgeArray[i][j] = Integer.MAX_VALUE / 2;
			}
		}
		createGraph();
	}

	public boolean isEdgeExists(int start, int end){

		if(edgeArray[start][end] != Integer.MAX_VALUE/2){
			return true;
		}else{
			return false;
		}
	}


	private void createGraph(){
		vexList.add("V0");
		vexList.add("V1");
		vexList.add("V2");
		vexList.add("V3");
		vexList.add("V4");
		vexList.add("V5");
		vexList.add("V6");
		vexList.add("V7");
		vexList.add("V8");


		//初始化4条边,因为是无向边,所以都是成对出现
		Edge edge1 = new Edge(0, 1, 10);
		Edge edge2 = new Edge(0, 5, 11);

		Edge edge3 = new Edge(1, 0, 10);
		Edge edge4 = new Edge(5, 0, 11);

		Edge edge5 = new Edge(1, 2, 18);
		Edge edge6 = new Edge(1, 6, 16);
		Edge edge7 = new Edge(1, 8, 12);

		Edge edge8 = new Edge(2, 1, 18);
		Edge edge9 = new Edge(6, 1, 16);
		Edge edge10 = new Edge(8, 1, 12);

		Edge edge11 = new Edge(2, 3, 22);
		Edge edge12 = new Edge(2, 8, 8);
		Edge edge13 = new Edge(3, 2, 22);
		Edge edge14 = new Edge(8, 2, 8);


		Edge edge15 = new Edge(3, 4, 20);
		Edge edge16 = new Edge(3, 7, 16);
		Edge edge17 = new Edge(3, 8, 21);

		Edge edge18 = new Edge(4, 3, 20);
		Edge edge19 = new Edge(7, 3, 16);
		Edge edge20 = new Edge(8, 3, 21);

		Edge edge21 = new Edge(4, 5, 26);
		Edge edge22 = new Edge(4, 7, 7);

		Edge edge23 = new Edge(5, 4, 26);
		Edge edge24 = new Edge(7, 4, 7);

		Edge edge25 = new Edge(5, 6, 17);
		Edge edge26 = new Edge(6, 5, 17);

		Edge edge27 = new Edge(6, 7, 19);
		Edge edge28 = new Edge(7, 6, 19);
 
		Edge edge29 = new Edge(1, 8, 12);
		Edge edge30 = new Edge(8, 1, 12);

		add(edge29);
		add(edge30);

		add(edge1);
		add(edge2);
		add(edge3);
		add(edge4);
		add(edge5);
		add(edge6);
		add(edge7);
		add(edge8);
		add(edge9);
		add(edge10);
		add(edge11);
		add(edge12);
		add(edge13);
		add(edge14);
		add(edge15);
		add(edge16);
		add(edge17);
		add(edge18);
		add(edge19);
		add(edge20);
		add(edge21);
		add(edge22);
		add(edge23);
		add(edge24);
		add(edge25);
		add(edge26);
		add(edge27);
		add(edge28);
	}

	public void add(Edge edge){
		for(int i=0; i<vexList.size(); i++){
			for(int j=0; j<vexList.size(); j++){
				//设置这个权值到数组中
				if(i != j && i == edge.getStart() && j == edge.getEnd() && edgeArray[i][j] == Integer.MAX_VALUE/2){
					edgeArray[i][j] = edge.getWeight();
				}else if(i == j){
					edgeArray[i][j] = 0;
				}
			}
		}

		edgeList.add(edge);
	}


	public String toString(){
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<vexList.size(); i++){
			for(int j=0; j<vexList.size(); j++){
				if(edgeArray[i][j] != Integer.MAX_VALUE/2)
					sb.append(edgeArray[i][j]+ " ");
				else
					sb.append("00" + " ");
			}
			sb.append("\n");
		}

		return sb.toString();
	}

	public static void main(String[] args) {
		Graph graph = new Graph(9);
		System.out.println(graph);
		System.out.println("DFS======================================");
		graph.DFS();
		System.out.println("======================================DFS");

		System.out.println();

		System.out.println("BFS======================================");
		graph.BFS();
		System.out.println("end======================================BFS");

		System.out.println("=======minSpanTreePrim==================");
		graph.minSpanTreePrim();
		System.out.println("=======minSpanTreePrim==================");


		System.out.println("=======miniSpanTreeKruskal==================");
		graph.miniSpanTreeKruskal();
		System.out.println("=======miniSpanTreeKruskal==================");



	}


	//深度优先遍历这个图
	public void DFS(){
		visited = new boolean[vexList.size()];  //标识每个节点是否被访问,这里全部重置
		for(int i=0; i<vexList.size(); i++){
			if(!visited[i]){
				DFS0(i);
			}
		}
	}

	public void DFS0(int index){

		System.out.println("vex "+ index +" value is " + vexList.get(index));   //输出这个节点,也可以更换成其它操作

		visited[index] = true;   //设置该节点已经被访问过了

		for(int j=0; j<vexList.size(); j++){
			if(isEdgeExists(index, j) && !visited[j]){
				DFS0(j);
			}
		}
	}


	//广度优先,遍历这个图
	public void BFS(){
		visited = new boolean[vexList.size()];  //标识每个节点是否被访问,这里全部重置

		LinkedList<Integer> queue = new LinkedList<Integer>();

		for(int i=0; i<vexList.size(); i++){
			//如果这个节点没有被访问过,就访问
			if(!visited[i]){
				visited[i] = true;

				System.out.println("vex " + i + " is " + vexList.get(i));     //输出这个节点,也可以更换成其它操作

				queue.addLast(i);   //将这个节点i加入队列

				while(!queue.isEmpty()){
					int index = queue.removeFirst();   //出队列,并且将这个下标记住

					for(int j=0; j<vexList.size(); j++){
						if(isEdgeExists(index, j) && !visited[j]){
							visited[j] = true;
							System.out.println("vex " + j + " is " + vexList.get(j));  //输出这个节点,也可以更换成其它操作
							queue.addLast(j);
						}
					}
				}
			}else{
				//System.out.println(i + " vex is visited");
			}
		}
	}


	/**
	 * 最小生成树,普利姆算法 
	 * 出发点:从其中一个顶点出发
	 * 前提条件:无
	 * 
	 * */
	public void minSpanTreePrim(){
		int min = 0, i = 0, j = 0, k = 0;   
		int[] adjvex = new int[vexList.size()];   //保存顶点相关下标
		int[] lowcost = new int[vexList.size()];   //保存定点之间的权值

		lowcost[0] = 0;   //初始化第一个权值为0,也就是V0加入生成树
		adjvex[0] = 0;    //初始化顶一个定点下标为0

		for(i=1; i<vexList.size(); i++){   //循环其它的定点
			lowcost[i] = edgeArray[0][i];   //取出V0连的边的全部权值

			adjvex[i] = 0;   //初始化都为V0下标
		}

		for(i=1; i<vexList.size(); i++){
			min = Integer.MAX_VALUE / 2;   //初始化权值最小为无穷大
			j = 1;
			k = 0;

			while(j < vexList.size()){
				if(lowcost[j] != 0 && lowcost[j] < min){   //如果权值不为0并且小于MIN,也就是该节点相连的边中最小权值
					min = lowcost[j];
					k = j;   //让最小的值的下标存入k
				}
				j++;
			}

			System.out.println("(" + adjvex[k] + "," + k + ")");   //输出边

			lowcost[k] = 0;   //将当前顶点的权值设置为0,表示此顶点已经完成任务

			for(j = 1; j<vexList.size(); j++){
				if(lowcost[j] != 0 && edgeArray[k][j] < lowcost[j]){
					lowcost[j] = edgeArray[k][j];

					adjvex[j] = k;
				}
			}
		}
	}

	/**
	 * 库鲁斯卡尔算法
	 * 出发点:从边出发
	 * 
	 * 前提:这些变都按照权值大小排序好
	 * 
	 * 从图的每一条边出发,然后查看这条边是否形成环,如果没有,加入到最小生成树
	 * 
	 * */
	public void miniSpanTreeKruskal(){
		int n = 0, m = 0, i = 0;

		int[] parent = new int[vexList.size()];   //定义一个数组用来判断是否形成环路,初始化的值都为0
        
		//获得排序好的所有边集合,也就是前提条件
		Collections.sort(edgeList);
		Edge[] edges = new Edge[edgeList.size()/2];
		int index = 0;
		for(int j=0; j < edgeList.size(); j++){
			if(j % 2 == 0){
				edges[index++] = edgeList.get(j);
			}
		}

		//循环每一条边
		for(i=0; i<edges.length; i++){
			
			n = find(parent, edges[i].getStart());   //找到这条边的起点
			m = find(parent, edges[i].getEnd());   //找到这条边的终点

            //如果没有形成环,加入到最小生成树
			if(n != m){   //如果不相等,说明没有构成环
				parent[n] = m;    //将此边的结尾顶点放入到下边起点的parent中,表示此顶点已经在生成树中
				System.out.println("(" + edges[i].getStart() + "," + edges[i].getEnd() + ")" + " weight " + edges[i].getWeight());
			}
		}

	}

	private int find(int[] parent, int f){  //查找连线节点的尾部下标
		while(parent[f] > 0)
			f = parent[f];

		return f;
	}
}



下面是是输出结果

0 10 00 00 00 11 00 00 00 
10 0 18 00 00 00 16 00 12 
00 18 0 22 00 00 00 00 8 
00 00 22 0 20 00 00 16 21 
00 00 00 20 0 26 00 7 00 
11 00 00 00 26 0 17 00 00 
00 16 00 00 00 17 0 19 00 
00 00 00 16 7 00 19 0 00 
00 12 8 21 00 00 00 00 0 

DFS======================================
vex 0 value is V0
vex 1 value is V1
vex 2 value is V2
vex 3 value is V3
vex 4 value is V4
vex 5 value is V5
vex 6 value is V6
vex 7 value is V7
vex 8 value is V8
======================================DFS

BFS======================================
vex 0 is V0
vex 1 is V1
vex 5 is V5
vex 2 is V2
vex 6 is V6
vex 8 is V8
vex 4 is V4
vex 3 is V3
vex 7 is V7
end======================================BFS
=======minSpanTreePrim==================
(0,1)
(0,5)
(1,8)
(8,2)
(1,6)
(6,7)
(7,4)
(7,3)
=======minSpanTreePrim==================
=======miniSpanTreeKruskal==================
(4,7) weight 7
(2,8) weight 8
(0,1) weight 10
(0,5) weight 11
(1,8) weight 12
(1,6) weight 16
(3,7) weight 16
(6,7) weight 19
=======miniSpanTreeKruskal==================