[数据结构与算法]图的基本实现和DJS算法（Java实现）

图

图是一种各个数据对象间存在多对多关系的数据结构

图的接口Interface

public interface IGraph {
	void createGraph();//创建图
	int getVexNum();//统计顶点数
	int getArcNum();//统计边数
	Object getVex(int v) throws Exception;//返回v位置对应的顶点
	int locateVex(Object vex);//查找vex在图中的位置
	int firstAdjVex(int v) throws Exception;//返回顶点v的第一个邻接点
	int nextAdjVex(int v,int w) throws Exception;//返回顶点v相对于邻接顶点w的下一个邻接顶点，若w为v的最后一个邻接顶点，返回-1
}

图的类型

图分为无向图，有向图，无向网，有向网四种，其中无向网，有向网在无向图，有向图的基础上，在各边上加上了权值，我们可以使用枚举类型enum定义图的类型

public enum GraphKind {
	UDG,//undirected graph 无向图
	DG,//directed graph 有向图
	UDN,//undirected network 无向网
	DN//directed network 有向网
}

图的表示

图的表示方法有邻接矩阵，邻接表，十字链表，邻接多重表等等，这里我们只介绍邻接矩阵和邻接表，因为这两种方法比较常见，而且代码实现起来也相对简单一些。

邻接矩阵

邻接矩阵的大小为N*N，N为图中顶点的个数，第i行第j列表示顶点Vi和Vj的边，若为0，则表示顶点Vi和Vj没有边相连，若为1则表示有边相连，若是不为1的其他数则表示顶点Vi和Vj相连边的权值
邻接矩阵的实现：

import java.util.*;
public class MGraph implements IGraph{
	public final static int INFINITY=Integer.MAX_VALUE;
	private GraphKind kind;
	private int vexNum,arcNum;
	private Object[] vexs;
	private int[][] arcs;
	public MGraph() {
		this(null,0,0,null,null);
	}
	public MGraph(GraphKind kind,int vexNum,int arcNum,Object[] vexs,int[][] arcs) {
		this.kind=kind;
		this.vexNum=vexNum;
		this.arcNum=arcNum;
		this.vexs=vexs;
		this.arcs=arcs;
	}
	@Override
	public void createGraph() {
		Scanner sc=new Scanner(System.in);
		System.out.println("请输入图的类型");
		GraphKind kind=GraphKind.valueOf(sc.next());
		switch(kind) {
		case UDG:
			createUDG();
			return ;
		case DG:
			createDG();
			return;
		case UDN:
			createUDN();
			return ;
		case DN:
			createDN();
			return ;
		}
	}
	
	public void createUDG() {
		Scanner sc =new Scanner(System.in);
		System.out.println("请输入图的顶点数和边数");
		vexNum=sc.nextInt();
		arcNum=sc.nextInt();
		vexs=new Object[vexNum];
		for(int i=0;i<vexNum;i++) {
			vexs[i]=sc.next();
		}
		arcs=new int[vexNum][vexNum];
		for(int i=0;i<vexNum;i++) {
			for(int j=0;j<vexNum;j++)
				arcs[i][j]=INFINITY;
		}
		System.out.println("请输入边的两个顶点");
		for(int i=0;i<arcNum;i++) {
			int u=locateVex(sc.next());
			int v=locateVex(sc.next());
			arcs[u][v]=arcs[v][u]=1;
		}
	}
	public void createDG() {
		Scanner sc =new Scanner(System.in);
		System.out.println("请输入图的顶点数和边数");
		vexNum=sc.nextInt();
		arcNum=sc.nextInt();
		vexs=new Object[vexNum];
		for(int i=0;i<vexNum;i++) {
			vexs[i]=sc.next();
		}
		arcs=new int[vexNum][vexNum];
		for(int i=0;i<vexNum;i++) {
			for(int j=0;j<vexNum;j++)
				arcs[i][j]=INFINITY;
		}
		System.out.println("请输入边的两个顶点及权值");
		for(int i=0;i<arcNum;i++) {
			int u=locateVex(sc.next());
			int v=locateVex(sc.next());
			arcs[u][v]=1;
		}
	}
	public void createUDN(){
		Scanner sc =new Scanner(System.in);
		System.out.println("请输入图的顶点数和边数");
		vexNum=sc.nextInt();
		arcNum=sc.nextInt();
		vexs=new Object[vexNum];
		for(int i=0;i<vexNum;i++) {
			vexs[i]=sc.next();
		}
		arcs=new int[vexNum][vexNum];
		for(int i=0;i<vexNum;i++) {
			for(int j=0;j<vexNum;j++)
				arcs[i][j]=INFINITY;
		}
		System.out.println("请输入边的两个顶点及权值");
		for(int i=0;i<arcNum;i++) {
			int u=locateVex(sc.next());
			int v=locateVex(sc.next());
			arcs[u][v]=arcs[v][u]=sc.nextInt();
		}
	}
	public void createDN() {
		Scanner sc =new Scanner(System.in);
		System.out.println("请输入图的顶点数和边数");
		vexNum=sc.nextInt();
		arcNum=sc.nextInt();
		vexs=new Object[vexNum];
		System.out.println("请输入图的各个顶点");
		for(int i=0;i<vexNum;i++) {
			vexs[i]=sc.next();
		}
		arcs=new int[vexNum][vexNum];
		for(int i=0;i<vexNum;i++) {
			for(int j=0;j<vexNum;j++)
				arcs[i][j]=INFINITY;
		}
		System.out.println("请输入边的两个顶点及权值");
		for(int i=0;i<arcNum;i++) {
			int u=locateVex(sc.next());
			int v=locateVex(sc.next());
			arcs[u][v]=sc.nextInt();
		}
	}
	@Override
	public int getVexNum() {
		return vexNum;
	}

	@Override
	public int getArcNum() {
		return arcNum;
	}

	@Override
	public Object getVex(int v) throws Exception{
		if(v<0||v>vexNum)
			throw new Exception("第"+v+"个顶点不存在");
		else
			return vexs[v];
	}

	@Override
	public int locateVex(Object vex) {
		for(int i=0;i<vexNum;i++)
			if(vexs[i].equals(vex))
				return i;
		return -1;
	}

	@Override
	public int firstAdjVex(int v) {
		for(int i=0;i<vexNum;i++)
			if(arcs[v][i]!=INFINITY)
				return i;
		return -1;	
	}

	@Override
	public int nextAdjVex(int v, int w)throws Exception {
		if(v<0||v>=vexNum) 
			throw new Exception("第"+v+"个顶点不存在");	
		if(w==vexNum-1)
			return -1;
		for(int i=w+1;i<vexNum;i++)
			if(arcs[v][i]!=INFINITY)
				return i;
		return -1;	
	}
	//这里的插入和删除边的函数仅以有向图/有向网为例，若要适用于全部的图可以使用if判断进行适当的修改即可
	public void deleteArc(MGraph G,int v,int w) throws Exception{
		if(v>=vexNum||w>=vexNum||v<0||w<0)
			throw new Exception("第"+v+"或"+w+"个顶点不存在");
		else
			G.arcs[v][w]=INFINITY;
	}
	public void insertArc(MGraph G,int v,int w) throws Exception{
		if(v>=vexNum||w>=vexNum||v<0||w<0)
			throw new Exception("第"+v+"或"+w+"个顶点不存在");
		else {
			Scanner sc=new Scanner(System.in);
			System.out.println("请输入想要添加的边的权值");
			int value=sc.nextInt();
			G.arcs[v][w]=value;
		}	
	}
	public void display() {
		System.out.println();
		for(int i=0;i<vexNum;i++){
			for(int j=0;j<vexNum;j++){
				if(arcs[i][j]==INFINITY)
					System.out.print("0 ");
				else
					System.out.print(arcs[i][j]+" ");
			}
			System.out.println();	
		}
	}
}

邻接表

邻接表表示图的话是使用了一个顶点数组和链表实现的
顶点类VNode

public class VNode {
	public Object data;
	public ArcNode firstArc;//第一个邻接顶点
	public VNode() {
		this(null,null);
	}
	public VNode(Object data) {
		this(data,null);
	}
	public VNode(Object data,ArcNode firstArc) {
		this.data=data;
		this.firstArc=firstArc;
	}
}

边类ArcNode

public class ArcNode {
	public int adjVex;//在vex数组中的位置
	public int value;//边的权值
	public ArcNode nextArc;//顶点vi的下一个邻接顶点
	public ArcNode() {
		this(-1,0,null);
	}
	public  ArcNode(int adjVex) {
		this(adjVex,0,null);
	}
	public  ArcNode(int adjVex,int value) {
		this(adjVex,value,null);
	}
	public  ArcNode(int adjVex,int value,ArcNode nextArc) {
		this.adjVex=adjVex;
		this.value=value;
		this.nextArc=nextArc;
	}
}

邻接表的实现

package graph;
import java.util.Scanner;
public class ALGraph implements IGraph{
	private GraphKind kind;
	private int vexNum,arcNum;
	private VNode[] vexs;
	public ALGraph() {
		this(null,0,0,null);
	}
	public ALGraph(GraphKind kind,int vexNum,int arcNum,VNode[] vexs) {
		this.kind=kind;
		this.vexNum=vexNum;
		this.arcNum=arcNum;
		this.vexs=vexs;
	}
	@Override
	public void createGraph() {
		Scanner sc=new Scanner(System.in);
		System.out.println("请输入图的类型");
		GraphKind kind=GraphKind.valueOf(sc.next());
		switch(kind) {
		case UDG:
			createUDG();
			return ;
		case DG:
			createDG();
			return;
		case UDN:
			createUDN();
			return ;
		case DN:
			createDN();
			return ;
		}
	}
	public void createUDG() {
		Scanner sc =new Scanner(System.in);
		System.out.println("请输入图的顶点数");
		vexNum=sc.nextInt();
		arcNum=sc.nextInt();
		vexs=new VNode[vexNum];
		System.out.println("请输入图的各个顶点");
		for(int i=0;i<vexNum;i++) {
			vexs[i]=new VNode(sc.next());
		}
		System.out.println("请输入各边的两个顶点在图中的位置:");
		for(int i=0;i<arcNum;i++) {
			int posv=sc.nextInt();
			int posu=sc.nextInt();
			int value=0;
			addArc(posv,posu,value);
			addArc(posu,posv,value);
		}
	}
	public void createDG() {
		Scanner sc =new Scanner(System.in);
		System.out.println("请输入图的顶点数");
		vexNum=sc.nextInt();
		arcNum=sc.nextInt();
		vexs=new VNode[vexNum];
		System.out.println("请输入图的各个顶点");
		for(int i=0;i<vexNum;i++) {
			vexs[i]=new VNode(sc.next());
		}
		System.out.println("请输入各边的两个顶点在图中的位置:");
		for(int i=0;i<arcNum;i++) {
			int posv=sc.nextInt();
			int posu=sc.nextInt();
			int value=0;
			addArc(posv,posu,value);
		}
	}
	public void createUDN(){
		Scanner sc =new Scanner(System.in);
		System.out.println("请输入图的顶点数");
		vexNum=sc.nextInt();
		arcNum=sc.nextInt();
		vexs=new VNode[vexNum];
		System.out.println("请输入图的各个顶点");
		for(int i=0;i<vexNum;i++) {
			vexs[i]=new VNode(sc.next());
		}
		System.out.println("请输入各边的两个顶点在图中的位置及边的权值:");
		for(int i=0;i<arcNum;i++) {
			int posv=sc.nextInt();
			int posu=sc.nextInt();
			int value=sc.nextInt();
			addArc(posv,posu,value);
			addArc(posu,posv,value);
		}
	}
	public void createDN() {
		Scanner sc =new Scanner(System.in);
		System.out.println("请输入图的顶点数，边数");
		vexNum=sc.nextInt();
		arcNum=sc.nextInt();
		vexs=new VNode[vexNum];
		System.out.println("请输入图的各个顶点");
		for(int i=0;i<vexNum;i++) {
			vexs[i]=new VNode(sc.next());
		}
		System.out.println("请输入各边的两个顶点在图中的位置及边的权值:");
		for(int i=0;i<arcNum;i++) {
			int posv=sc.nextInt();
			int posu=sc.nextInt();
			int value=sc.nextInt();
			addArc(posv,posu,value);
		}
	}
	public void addArc(int u,int v,int value) {
		ArcNode arc=new ArcNode(v,value);
		arc.nextArc=vexs[u].firstArc;
		vexs[u].firstArc=arc;
	}
	@Override
	public int getVexNum() {
		return vexNum;
	}
	@Override
	public int getArcNum() {
		return arcNum;
	}
	@Override
	public Object getVex(int v) {
		if(v<0||v>vexNum)
			return null;
		else
			return vexs[v].data;
	}
	@Override
	public int locateVex(Object vex) {
		for(int i=0;i<vexNum;i++)
			if(vexs[i].data.equals(vex))
				return i;
		return -1;
	}
	@Override
	public int firstAdjVex(int v) throws Exception{
		if(v<0||v>vexNum)
			throw new Exception("第"+v+"个顶点不存在");
		if(vexs[v].firstArc==null)
			return -1;
		else
			return vexs[v].firstArc.adjVex;
	}
	@Override
	public int nextAdjVex(int v, int w) throws Exception{
		if(v<0||v>vexNum)
			throw new Exception("第"+v+"个顶点不存在");
		ArcNode arc=vexs[v].firstArc;
		while(arc!=null) {
			if(arc.adjVex==w) {
				if(arc.nextArc!=null)
					return arc.nextArc.adjVex;
				else return -1;
			}
			arc=arc.nextArc;
		}
		return -1;
	}
	public void display() {
		System.out.println("图中所有顶点:");
		for(int i=0;i<vexNum;i++) 
			System.out.print(" "+vexs[i].data.toString());
		System.out.println();
		System.out.println("图中所有边:");
		for(int i=0;i<vexNum;i++){
			ArcNode arc=vexs[i].firstArc;
			while(arc!=null) {
				System.out.print(getVex(i).toString()+"---"+getVex(arc.adjVex).toString()+":"+arc.value+" ");
				arc=arc.nextArc;
			}
			System.out.println();	
		}
		System.out.println();	
	}
}

DJS算法：

在很多实际生产应用中，我们需要找到各个顶点之间的最短路径，就比如我们乘地铁通常APP会给我们推荐一些不同的方案，有用时最短，路程最短，花钱最少等等，其实都可以抽象为最短路径问题，我们可以将各个地铁站理解为顶点，只是说边上的权值换成了时间，路程，金钱等等。使用DJS算法可以找到某一个顶点到其他各个顶点的最短路径

算法思想：

为了更好的理解DJS算法，我们引入了集合V和顶点的全集S的概念，集合V中存放已经找到最短路径的顶点，最开始V中只有起点v0
1）首先找到起点和其他各个顶点的直接相连的边，并记录好边的权值，若无边相连可以理解为权值无限大，在这些边里找到权值最小的边的邻接顶点vi，v0到vi的最短路径即为 v0—>vi 将vi放入集合V中
2）从vi出发找到和其他各个顶点的直接相连的边，并记录好边的权值，如果v0到vj（与vi直接相连且在S-V中）的距离大于 v0到vi的最短路径的距离 和 vi到vj的距离 之和 ，则将v0到vj的最短路径换成 v0到vi的最短路径 再到vj，这里是v0—>vi—>vj，但是到后面这个路径可能会越来越复杂，不过思想是一样的
3）将vj加入集合V中，直到集合V与S相等，否则重复2）过程

代码实现

//邻接表的DJS算法实现
	int[] shortLen;
	public static final int INFINITY =Integer.MAX_VALUE;
	public int[][] shortDJS(ALGraph G,int v) {
		int[][] path;
		boolean[] pass;
		int vexNum=G.getVexNum();
		path=new int[vexNum][vexNum];
		shortLen=new int[vexNum];
		for(int i=0;i<vexNum;i++) {
			if(i==v) {
				continue;
			}
			shortLen[i]=INFINITY;
			path[i]=new int[vexNum];
			for(int j=0;j<vexNum;j++) {
				if(j==0)
					path[i][j]=v;
				else if(j==1)
					path[i][j]=i;
				else
					path[i][j]=-1;
			}
		}
		pass=new boolean[vexNum];
		for(int i=0;i<vexNum;i++) {
			pass[i]=false;
		}
		ArcNode arc=vexs[v].firstArc;
		if(arc!=null) {
			while(arc!=null) {
				shortLen[arc.adjVex]=arc.value;
				arc=arc.nextArc;
			}
			int pos=findMin(shortLen,pass,v);
			while(!pass[pos]){
				pass[pos]=true;
				arc=vexs[pos].firstArc;
				if(arc!=null) {
					while(arc!=null) {
						int adj=arc.adjVex;
						if(shortLen[pos]+arc.value<shortLen[adj]&&shortLen[pos]+arc.value>0){
							shortLen[adj]=shortLen[pos]+arc.value;
							for(int i=0;i<vexNum;i++) {
								if(path[pos][i]==-1) {
									path[adj][i]=adj;
									break;
								}	
								path[adj][i]=path[pos][i];
							}
						}
						arc=arc.nextArc;
					}
				}
				pos=findMin(shortLen,pass,v);
			}
		}
		return path;
	}
	public int findMin(int[] len,boolean[] flag,int v) {
		int min=v;
		len[v]=INFINITY;
		for(int i=0;i<len.length;i++) {
			if(len[i]<=len[min]&&flag[i]==false)
				min=i;
		}
		return min;
	}
	public void disShortPath(ALGraph G,int v) {
		int[][] shortPath=shortDJS(G,v);
		for(int i=0;i<G.getVexNum();i++) {
			if(i==v)
				continue;
			else
				System.out.print(G.getVex(v).toString()+"到"+G.getVex(i).toString()+"的最短路径:");
				for(int j=0;j<G.getVexNum();j++) {
					if(shortPath[i][j]!=-1)
						System.out.print(G.getVex(shortPath[i][j]).toString()+" ");
					else break;
				}
				System.out.println("最短距离:"+shortLen[i]);
		}
	}

邻接矩阵的DJS算法和邻接表的差不多，理解好邻接表的DJS算法再去写邻接矩阵的DJS算法实现应该会轻松一点，也可以当作一个练习来检验自己对于DJS算法的理解

如果本文中的代码存在bug的话请及时联系笔者，感谢！！