目录
一、基本概念
二、构造函数
三、构造稠密图和稀疏图
四、辅助函数：将文本转化成图：
五、计算连通分量： （深度优先遍历）
六、计算从n->m的路径（深度优先遍历及改进）
七、最短路径（广度优先遍历及改进）
八、测试函数：
1.图的定义：
图：由节点和节点之间的连接组成，如下图所示（红色圆代表节点，黑线代表连接）：
图可以分为：
（1）有向图和无向图：指的是连接是否有方向，由一个节点指向另一个节点
（2）有权图和无权图：指的是连接是否带有值，用户可以自定义
本次博客的内容只介绍无权图，有权图在之后还会补充
2.图的表示：
图的表示方法有两种，一般为：
（1）稀疏图（SparseGraph）：使用邻接矩阵表示
->使用二维数组，数组的内容表示连接状态，比如：1表示连接，0表示中断
如下图中，arr[0][1]=0表示：0和1断开；arr[0][3]=1表示：0和3连接
（2）稠密图（DenseGraph）：使用邻接表表示
->使用二维数组，每一行数组存储的数组表示与其连接的节点序号
如下图中，arr[0]={3,5,8},表示0和3,5,8之间是连接的
3.图的应用：
（1）计算连通分量，如图有3个连通分量：（深度优先遍历）
（2）计算路径（深度优先遍历）
（3）计算最短路径（广度优先遍历）
1.声明一个Graph的类：（方便后面复用）
package IMUHERO; public interface Graph { int nodeSize(); //节点的个数 int edgeSize(); //边的个数 boolean hasEdge(int v, int w); //判断两个节点是否有边 void addEdge(int v,int w); //为两个节点添加边 Iterable<Integer>adj(int v); //相邻边迭代器（辅助函数） void show(); //展示图的方法（辅助函数） }这里稠密图和稀疏图的定义：（边：edg，节点：node）
1.edg/node->1（值接近1），使用稠密图
2.edg/node->0（值接近0），使用稀疏图
图（1）稀疏图 图（2）稠密图
1.构造一个稠密图：
package IMUHERO; import java.util.Vector; public class DenseGraph implements Graph{ private boolean [][]graph; private int n; //节点node private int e; //边edge private boolean isDirected; //方便在：有向/无向之间切换 DenseGraph(int size,boolean isDirected){ assert size>=0;//保证输入无误 n=size; graph=new boolean[n][n]; e=0; this.isDirected=isDirected; //false表示未连通，true表示已连通 for (int i=0;i<n;i++){ for (int j=0;j<n;j++){ graph[i][j]=false; } } } public int nodeSize(){ return n; } public int edgeSize(){ return e; } //如果是有向图，默认传入数据按照：v->w 来组织 public void addEdge(int v,int w){ assert (v>=0&&v<n&&w>=0&&w<n); if (!hasEdge(v,w)) { graph[v][w] = true; //是否有向？如果是无向图则需要添加两条边，graph[w][v]和graph[v][w] if (!isDirected){ graph[w][v]=true; } e++;//外层if 判断是否已经有连接，以防边的数量统计有误 } } public boolean hasEdge(int v, int w){ assert (v>=0&&v<n&&w>=0&&w<n); return graph[v][w]; } //以表的形式展示稠密图： public void show(){ for (int i=0;i<n;i++){ System.out.print(i+": "); for (int j=0;j<n;j++){ System.out.print(graph[i][j]+" "); } System.out.println(); } } public Iterable<Integer> adj(int v) { assert v >= 0 && v < n; Vector<Integer> adjV = new Vector<Integer>(); for(int i = 0 ; i < n ; i ++ ) if( graph[v][i] ) adjV.add(i); return adjV; } }2.构造一个稀疏图：
package IMUHERO; import java.util.Vector; public class SparseGraph implements Graph{ Vector<Integer>[]graph;//二维动态数组的初始化 int n;//节点node int e;//边edge boolean isDirected; SparseGraph(int size, boolean isDirected){ assert size>=0; n=size; graph=(Vector<Integer>[]) new Vector[n]; e=0; this.isDirected=isDirected; for (int i=0;i<n;i++){ graph[i]=new Vector<Integer>(); } } public int nodeSize(){ return n; } public int edgeSize(){ return e; } public void addEdge(int v,int w){ assert (v>0&&v<n&&w>0&&w<n); graph[v].add(w); if (v!=w&&!isDirected){ graph[w].add(v); } e++; } public boolean hasEdge(int v, int w){ assert (v>0&&v<n&&w>0&&w<n); for (int i:graph[v]){ if (i==w)return true; } return false; } public void show(){ for (int i=0;i<n;i++){ System.out.print("Vertex"+i+":"); for (int v:graph[i]) System.out.print(v+" "); System.out.println(); } } public Iterable<Integer>adj(int v){ assert v>=0&&v<n; return graph[v]; } }3.相邻节点遍历器adj的使用测试：
public static void main(String[] args) { DenseGraph DG = new DenseGraph(5,false); SparseGraph SG = new SparseGraph(5,false); DG.addEdge(4,1); SG.addEdge(4,1); for (int i=0;i<4;i++){ DG.addEdge(i,i+1); SG.addEdge(i,i+1); } System.out.println("稠密图："); for (int i=0;i<5;i++){ Iterable<Integer> it = DG.adj(i); System.out.print(i+": "); for (int a:it){ System.out.print(a+" "); } System.out.println(); } System.out.println("稀疏图"); for (int j=0;j<5;j++){ Iterable<Integer> it = SG.adj(j); System.out.print(j+": "); for (int a:it){ System.out.print(a+" "); } System.out.println(); } }结果为：（可以看到，稠密图是具有顺序性的，而稀疏图是根据添加边的顺序直接生成的，不具有顺序性）
稠密图： 0: 1 1: 0 2 4 2: 1 3 3: 2 4 4: 1 3 稀疏图 0: 1 1: 4 0 2 2: 1 3 3: 2 4 4: 1 3（readGraph）（此条可忽略）
基本功能是：输入一个文本，readGraph可以自动阅读文本，并生成对应的图
package IMUHERO; import java.io.BufferedInputStream; import java.io.File; import java.io.FileInputStream; import java.io.IOException; import java.util.InputMismatchException; import java.util.Locale; import java.util.NoSuchElementException; import java.util.Scanner; public class readGraph { Scanner scanner; public readGraph(Graph graph,String fileName){ readFile(fileName); try{ int V = scanner.nextInt(); if (V < 0) throw new IllegalArgumentException("number of vertices in a Graph must be nonnegative"); assert V == graph.nodeSize(); int E = scanner.nextInt(); if (E < 0) throw new IllegalArgumentException("number of edges in a Graph must be nonnegative"); for (int i = 0; i < E; i++) { int v = scanner.nextInt(); int w = scanner.nextInt(); assert v >= 0 && v < V; assert w >= 0 && w < V; graph.addEdge(v, w); } }catch (InputMismatchException e) { String token = scanner.next(); throw new InputMismatchException("attempts to read an 'int' value from input stream, but the next token is \"" + token + "\""); } catch (NoSuchElementException e) { throw new NoSuchElementException("attemps to read an 'int' value from input stream, but there are no more tokens available"); } } public void readFile(String fileName){ assert fileName!=null; try { File file = new File(fileName); if (file.exists()) { FileInputStream fi = new FileInputStream(file); scanner=new Scanner(new BufferedInputStream(fi)); scanner.useLocale(Locale.ENGLISH); } } catch (IOException ioe){ throw new IllegalArgumentException("Could not oped"+fileName); } } }文本是.txt文件
testG1.TXT:
13 13 0 5 4 3 0 1 9 12 6 4 5 4 0 2 11 12 9 10 0 6 7 8 9 11 5 3testG2.TXT:
6 8 0 1 0 2 0 5 1 2 1 3 1 4 3 4 3 5//调用关系基本为： //showPath() -> findPath() -> hasPath() -> Path()进行初始化 -> dfs()深度遍历
package IMUHERO; import java.util.Stack; import java.util.Vector; public class Path { Graph G;//使用接口，可以的同时应用在稠密图和稀疏图中 private boolean visited[];//记录是否被遍历过 private int from[]; private int start;//表示路径的起始点 public Path(Graph graph, int s){ assert s >= 0 && s < G.nodeSize(); this.G=graph; this.visited=new boolean[G.nodeSize()]; this.from=new int[G.nodeSize()]; this.start=s; for (int i=0;i<G.nodeSize();i++){ visited[i]=false;//初始时，默认全部都没有遍历过 from[i]=-1; } dfs(start); } private void dfs(int n){ assert n>=0&&n<G.nodeSize(); visited[n]=true; //遍历n所连接的所有节点，如果没有被visited，则进行dfs for (int a:G.adj(n)){ if (!visited[a]){ from[a]=n; dfs(a); } } //这个遍历方法体现了迭代器的好处，可以不了解底层，对稠密图和稀疏图使用同一种方法进行遍历 } //查看是否有路径 public boolean hasPath(int w){ assert w>0&&w<=G.nodeSize(); return visited[w]; } //查找从s到w的路径，将路径存入Vector中 public Vector<Integer> findPath(int w){ assert hasPath(w); //确保有路径才能去寻路 Vector<Integer>retPath=new Vector<>(); Stack<Integer>stack=new Stack<>(); int p=w; //用一个替换，不要直接用w，会改变他的初始值 //终止条件这样设计的原因是：只有起始节点保持from为初始值 -1； while (p!=-1) { stack.push(p); p=from[p]; } while (!stack.isEmpty()) { retPath.add(stack.pop()); } return retPath; } public void showPath(int w){ Vector<Integer>show=new Vector<>(); show=findPath(w); for (int i=0;i<show.size();i++){ System.out.print(show.get(i)); if (i<show.size()-1){ System.out.print("->"); } } } //调用关系基本为： //showPath() -> findPath() -> hasPath() -> Path()进行初始化 -> dfs()深度遍历 }使用队列辅助：
特别注意：visited[ i ]=true是在入队时就加入，而不是在取出时才加入
package IMUHERO; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; import java.util.Vector; public class ShortestPath { Graph G;//使用接口，可以的同时应用在稠密图和稀疏图中 private boolean visited[];//记录是否被遍历过 private int from[]; private int start;//表示路径的起始点 private int []ord;//用来记录当前节点所在的层数，比如：1->6->7,1->2,1就是第一层，6、2是第二层，7是第三层 public ShortestPath(Graph graph, int s){ assert s >= 0 && s < G.nodeSize(); this.G=graph; this.visited=new boolean[G.nodeSize()]; this.from=new int[G.nodeSize()]; this.ord=new int [G.nodeSize()]; this.start=s; for (int i=0;i<G.nodeSize();i++){ visited[i]=false;//初始时，默认全部都没有遍历过 from[i]=-1; ord[i]=-1; } Queue<Integer> q = new LinkedList<Integer>(); q.add(s); visited[s]=true; ord[s]=1; while (!q.isEmpty()){ int begin=q.remove();//表示起始点，先移除 for (int a:G.adj(begin)){ if (visited[a]!=true){ q.add(a); visited[a]=true; from[a]=begin;//a的上一个连接元素是begin ord[a]=ord[begin]+1;//层数+1 } } } } //查找从s到w的路径，将路径存入Vector中 public Vector<Integer> findPath(int w){ assert hasPath(w);//确保有路径才能去寻路 Vector<Integer>retPath=new Vector<>(); Stack<Integer>stack=new Stack<>(); int p=w;//用一个替换，最好不要直接用w，会改变他的初始值 while (p!=-1) { stack.push(p); p=from[p]; } while (!stack.isEmpty()) { retPath.add(stack.pop()); } return retPath; } public boolean hasPath(int w){ assert w>0&&w<=G.nodeSize(); return visited[w]; } public void showPath(int w){ Vector<Integer>show=new Vector<>(); show=findPath(w); for (int i=0;i<show.size();i++){ System.out.print(show.get(i)); if (i<show.size()-1){ System.out.print("->"); } } } public int shortestL(int w){ assert w>=0&&w<G.nodeSize(); return ord[w]; } }result：
使用稠密图打印图1 0: false true true false false true true false false false false false false 1: true false false false false false false false false false false false false 2: true false false false false false false false false false false false false 3: false false false false true true false false false false false false false 4: false false false true false true true false false false false false false 5: true false false true true false false false false false false false false 6: true false false false true false false false false false false false false 7: false false false false false false false false true false false false false 8: false false false false false false false true false false false false false 9: false false false false false false false false false false true true true 10: false false false false false false false false false true false false false 11: false false false false false false false false false true false false true 12: false false false false false false false false false true false true false 使用稀疏图打印图1 Vertex0:5 1 2 6 Vertex1:0 Vertex2:0 Vertex3:4 5 Vertex4:3 6 5 Vertex5:0 4 3 Vertex6:4 0 Vertex7:8 Vertex8:7 Vertex9:12 10 11 Vertex10:9 Vertex11:12 9 Vertex12:9 11 使用稠密图打印图2 0: false true true false false true 1: true false true true true false 2: true true false false false false 3: false true false false true true 4: false true false true false false 5: true false false true false false 使用稀疏图打印图2 Vertex0:1 2 5 Vertex1:0 2 3 4 Vertex2:0 1 Vertex3:1 4 5 Vertex4:1 3 Vertex5:0 3 文本1中表示的图的连通量是：3 0和5是否连通? true 文本2中表示的图的连通量是：1 0和3是否连通? true 图1中：0->5的路径为： 0->5->3->4 图2中：0->5的路径为： 0->1->3->4 图1中：0->4的最短路径为： 0->5->4 最短路径长度为：3 图2中：0->4的最短路径为： 0->1->4 最短路径长度为：3
