图的基本介绍

x33g5p2x  于2022-02-12 转载在 其他  
字(1.4k)|赞(0)|评价(0)|浏览(603)

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

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

图的表示方式

图的表示方式有两种:邻接矩阵(二维数组表示)、邻接表(链表表示)

创建图的代码

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

相关文章