[数据结构与算法]图代码实现

方式一：邻阶矩阵实现

①无向不带权图

//该图为无向不带权图
public class Graph {
    private  int v;//矩阵的行列长
    private  boolean arr[][];//二维数组，如果为false代表与别的结点没有度
    
    public Graph(int v,boolean[][] arr){
        this.v=v;
        for(int i=0;i<v;i++){
            for(int j=0;j<v;j++){
                arr[i][j]=false;//初始化数组默认为0
            }
        }
    }
    
    public void add(int s,int t){//如果两个结点之间有度，则修改他们所在的位置为true
        arr[s][t]=true;
        arr[t][s]=true;
    }
}

②带权无向图

//该图为无向带权图
public class Graph {
    private  int v;//矩阵的行列长
    private  int arr[][];//二维数组，如果为0代表与别的结点没有度

    public Graph(int v,int[][] arr){
        this.v=v;
        for(int i=0;i<v;i++){
            for(int j=0;j<v;j++){
                arr[i][j]=0;//初始化数组默认为0
            }
        }
    }

    public void add(int s,int t,int value){//value为权值，如果两个结点之间有度，则修改他们所在的位置为权值
        arr[s][t]=value;
        arr[t][s]=value;
    }
}

③有向带权图

//该图为有向带权图
public class Graph {
    private  int v;//矩阵的行列长
    private  int arr[][];//二维数组，如果为0代表与别的结点没有度

    public Graph(int v,int[][] arr){
        this.v=v;
        for(int i=0;i<v;i++){
            for(int j=0;j<v;j++){
                arr[i][j]=0;//初始化数组默认为0
            }
        }
    }

    public void add(int s,int t,int value){//value为权值，s的出度是他t，即s指向t，则修改他们所在的位置为权值
        arr[s][t]=value；
    }
}

方式二：邻接表存储方式

//该图为无向图
public class Graph {
    private  int v;//数组长度
    private LinkedList<Integer> arr[];
    
    public Graph(int v){
        this.v=v;
        arr=new LinkedList[v];
        for(int i=0;i<v;i++){
            arr[i]=new LinkedList<>();//将数组中每个元素化为链表，存储它指向的结点
        }
    }
    
    public void ADD(int s,int t){//因为是无向图，所以存储两次
        arr[s].add(t);
        arr[t].add(s);
    }
}

详见《数据结构与算法之美》P216