图

图是一种数据结构,其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。
结点也可以称为顶点。图可以分为有向图和无向图

• 无向图：边仅仅连接两个顶点，没有其他含义。
• 有向图：边不仅连接两个顶点，且具有方向。

图的表示方式

图的表示方式有两种：邻接矩阵（二维数组表示）、邻接表（链表表示）

创建图的代码

public class Graph {

    /*存储顶点的集合*/
    private ArrayList<String> vertexList;
    /*存储图对应的邻接矩阵*/
    private int[][] edges;
    /*边的数目*/
    private int numOfEdges;

    public static void main(String[] args) {
        String[] vertexs = {"A","B","C","D","E"};
        /*创建图对象*/
        Graph graph = new Graph(vertexs.length);
        /*添加顶点*/
        for (String vertex:vertexs) {
            graph.insertVertex(vertex);
        }
        /*添加边*/
        graph.insertEdges(0,1,1);
        graph.insertEdges(0,2,1);
        graph.insertEdges(1,2,1);
        graph.insertEdges(1,3,1);
        graph.insertEdges(1,4,1);
        graph.show();
    }

    public Graph(int n){
        /*初始化矩阵和集合*/
        edges = new int[n][n];
        vertexList = new ArrayList<>(n);
        numOfEdges = 0;
    }

    /*出入顶点*/
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }

    /**
     *  插入边
     * @param v1 顶点在邻接矩阵中的下标
     * @param v2 顶点在邻接矩阵中的下标
     * @param weight 权值
     */
    public void insertEdges(int v1,int v2,int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }
    /*得到顶点的数目*/
    public int getNumOfVertex(){
        return vertexList.size();
    }
    /*得到边的数目*/
    public int getNumOfEdges(){
        return numOfEdges;
    }
    /*根据下标index得到对应的数据*/
    public String getValueByIndex(int index){
        return vertexList.get(index);
    }
    /*返回v1v2的权值*/
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }
    /*显示图的邻接矩阵*/
    public void show(){
        for (int[] arr : edges) {
            System.out.println(Arrays.toString(arr));
        }
    }
}

打印图的邻接矩阵

[0, 1, 1, 0, 0]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[0, 1, 0, 0, 0]
[0, 1, 0, 0, 0]

Process finished with exit code 0