java数据结构和算法——图的创建

一、示例要求

代码实现如下图结构

二、代码实现示例

1、创建图的类

package com.rf.springboot01.dataStructure.graph;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @description: 定义一个图 类
 * @author: xiaozhi
 * @create: 2020-10-27 21:58
 */
public class Graph {
    private ArrayList vertexList;//存储顶点集合
    private int[][] edges;//存储图所对应的邻接矩阵
    private int numEdges;//表示边的数量

    //构造方法 n表示有多少个顶点
    public Graph(int n){
        //初始化
        vertexList=new ArrayList(n);
        edges =new int[n][n];
        numEdges=0;
    }

    /**
    * @Description:  新增节点方法
    * @Param: vertex 节点
    * @Author: xz
    * @Date: 2020/10/27 22:02
    */
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }

    /** 
    * @Description:  新增边的方法
    * @Param: v1 表示点对应的的下标，即第几个顶点 ，比如 A — B， 点A的下标为0，点B的下标为1
    *         v2,表示第二个顶点对应的下标
    * @Author: xz  
    * @return: void
    * @Date: 2020/10/27 22:02
    */ 
    public void insertEdge(int v1 ,int v2 ,int weight) {
            edges[v1][v2] =weight;
            edges[v2][v1]=weight;
            numEdges++;
    }
    
    /** 
    * @Description: 返回结点个数的方法
    * @Author: xz
    * @Date: 2020/10/27 22:25
    */
    public int getNumVertex(){
        return vertexList.size();
    }
    
    /** 
    * @Description: 返回边的数量方法
    * @Author: xz
    * @Date: 2020/10/27 22:26
    */
    public int getNumEdge(){
        return numEdges;
    }

    /** 
    * @Description: 返回节点i(下标)对应的数据  0->"A" 1->"B" 2->"C"
    * @Author: xz
    * @Date: 2020/10/27 22:31
    */
    public String getValueByIndex(int i){
        return vertexList.get(i);
    }

    /**
    * @Description: 返回v1和v2的权值
    * v1 表示点对应的的下标
    * v2 表示第二个顶点对应的下标
    * @Author: xz
    * @Date: 2020/10/27 22:34
    */
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }
    
    /** 
    * @Description: 显示图对应的矩阵
    * @Author: xz
    * @Date: 2020/10/27 22:44
    */
    public void showGraph(){
        for(int[] link : edges) {
            System.err.println(Arrays.toString(link));
        }
    }

}

2、创建图的测试类

package com.rf.springboot01.dataStructure.graph;

/**
 * @description: 创建图的测试类
 * @author: xiaozhi
 * @create: 2020-10-27 22:48
 */
public class GraphTest {
    public static void main(String[] args) {
        int n =5;//节点个数
        String vertexs[] ={"A","B","C","D","E"};//定义5个节点
        //1、创建图对象
        Graph graph = new Graph(n);
        //2、循环添加顶点
        for(String vertex : vertexs){
            graph.insertVertex(vertex);
        }
        //3、添加边 A-B A-C B-C B-D B-E
        graph.insertEdge(0, 1, 1);//A-B
        graph.insertEdge(0, 2, 1); //A-C
		graph.insertEdge(1, 2, 1); //B-C
	    graph.insertEdge(1, 3, 1); //B-D
		graph.insertEdge(1, 4, 1); //B-E
        //显示邻结矩阵
        graph.showGraph();
    }
}

3、运行测试类，运行结果如下：