Java实现图论的基本使用

���这里主要写代码，定义等参考图论基础和表示 | 菜鸟教程

一、邻接矩阵代码实现

public class AdjacencyMatrix {    private int n;//节点数    private int m;//边数    private boolean directed;//是否为有向图    private int[][] data;//图数据    // 构造一个没有边的邻接矩阵    public AdjacencyMatrix(int n, boolean directed) {        // g初始化为n*n的布尔矩阵, 每一个data[i][j]均为0, 表示没有任何边，权值为0        // 为非零正整数时表示有边且边的权值为该值        assert n>=0;        this.n = n;        this.directed = directed;        this.m=0;        data=new int[n][n];    }    //判断v到w是否有边    private boolean hasEdge(int v,int w){        assert v>=0 && v=0 && w0;    }    //给v到w添加边和权值    private void addEdge(int v,int w,int weight){        assert v>=0 && v=0 && w= 0 && v  
二、邻接表代码实现
 
public class AdjacencyList {    private int n;//节点数    private int m;//边数    private boolean directed;//是否为有向图    //Vector是线程安全的可变数组    private Vector[] data;    public AdjacencyList(int n, boolean directed) {        this.n = n;        this.directed = directed;        data =  new Vector[n];        for (int i=0;i=0 && v=0 && w= 0 && start = 0 && end  ");        }    }}
 
五、广度优先遍历与最短路径
 
（Breadth First Search，广度优先搜索，又名宽度优先搜索），与深度优先算法在一个结点“***磕到底“的思维不同，广度优先算法关注的重点在于每一层的结点进行的下一层的访问。类似于二叉树或堆的层序遍历，BFS的核心就是要把当前在哪作为一个状态存储，并将这个状态交给队列进行入队操作
 
public class BFS {    AdjacencyMatrix matrix;    private int nodeNum;    private int start;//起点    private boolean[] visited;//记录dfs的过程中节点是否被访问    private int[] last;// 记录路径, last[i]表示查找的路径上i的上一个节点    private int[] order;// 记录路径中节点的次序。order[i]表示i节点在路径中的次序。    public BFS(AdjacencyMatrix matrix, int start) {        this.matrix = matrix;        this.start = start;        this.nodeNum = matrix.nodeNum();        assert start >= 0 && start  ");        }    }    // 查看从s点到w点的最短路径长度    // 若从s到w不可达，返回-1    public int length(int w){        assert w >= 0 && w