day 8 图

当我们需要用到多对多的关系时 就需要图

图中的节点也可以称为顶点

两个顶点之间的链接称之为边

当图中的边没有指认方向时 称为无向图

当图的边有了权值 就称为带权图

路径是指两个顶点之前所以可以互相到达的路线

import com.sun.org.apache.regexp.internal.RE;

import java.util.ArrayList;

public class mapTest {
    public static void main(String[] args) {
        String []x = {"A","B","C","D","E"};
        //构建一个节点数为5的图
        map map = new map(5);
        //向图中添加节点
        for (String i :x){
            map.add(i);
        }
        //链接边 0(A), 1(B), 2(C), 3(D), 4(E)
        //A链接C,B
        map.linkside(0,1,1);
        map.linkside(0,2,1);
        //b链接c,d,e (也链接a 但a-c过了所以无需再连)
        map.linkside(1,2,1);
        map.linkside(1,3,1);
        map.linkside(1,4,1);
        //查看连接后的矩阵图
        map.showMatrix();

    }
}
class map{
    //用来存放节点
    private ArrayList vertex;
    //用二维数组矩阵来储存显示图
    private int [][]matrix;
    //用来记录边的数量
    private int side;
    //构造图 传入节点的数量
    public map(int i){
        vertex = new ArrayList(i);
        matrix = new int[i][i];
        side = 0;
    }
    //添加节点
    public void add(String value){
        vertex.add(value);
    }
    //在矩阵中连接边 链接边A - B 权值为 C
    public void linkside(int a,int b,int c){
        matrix[a][b] = c;
        matrix[b][a] = c;
        side++;
    }
    //获取边的数量
    public int getSide(){
        return side;
    }
    //获取节点的数量
    public int getVertex(){
        return vertex.size();
    }
    //显示矩阵图
    public void showMatrix(){
        for (int[] show:matrix){
            for (int show1:show){
                System.out.print(show1+"t");
            }
            System.out.println();
        }
    }
    //根据节点索引 获取节点的值 {A ,B ,C ,D, E} 0 = A    1 = B ....
    public String getVertexValue(int i){
        return vertex.get(i);
    }
    //获取两个节点之间的权值
    public int getVartexqz(int a,int b){
        return matrix[a][b];
    }
}