数据结构与算法（三十）图的基本介绍

为什么要有图

• 前面我们学了线性表和树
• 线性表局限于一个直接前驱和一个直接后继的关系
• 树也只能有一个直接前驱也就是父节点
• 当我们需要表示多对多的关系时， 这里我们就用到了图

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

图的常用概念

• 顶点(vertex)
• 边(edge)
• 路径：比如从 D -> C 的路径
• 无向图：顶点之间的连接没有方向
• 有向图：顶点之间的连接有方向，比如A-B,
  只能是 A-> B 不能是 B->A .
• 带权图：这种边带权值的图也叫网.
• 

图的表示方式

• 图的表示方式有两种：二维数组表示（邻接矩阵）；链表表示（邻接表）。
  - 邻接矩阵
  邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵是的row和col表示的是1....n个点。
  

• 邻接表
  邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在,会造成空间的一定损失.
  邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成

图的代码实现

public class Graph {


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


    public Graph(int n){
        edges=new int[n][n];
        vertexList=new ArrayList<>(n);
        numOfEdges=0;
    }


    /**
     * 返回节点的个数
     * @return
     */
    public int getNumOfVertex(){
        return vertexList.size();
    }


    /**
     * 显示图对应的矩阵
     */
    public  void showGraph(){
        for (int [] link: edges){
            System.out.println(Arrays.toString(link));
        }
    }



    /**
     *  得到边的数量
     * @return
     */
    public int getNumOfEdges(){
        return numOfEdges;
    }


    /**
     * 根据下标得到对应的数据
     * @param index
     * @return
     */
    public String getValueByIndex(int index){
        return vertexList.get(index);
    }


    /**
     * 得到 路径权值
     * @param v1
     * @param v2
     * @return
     */
    public int getWeight(int v1,int v2){
        return edges[v1][v2];
    }





    /**
     * 加入节点
     * @param vertex
     */
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }



    /**
     *  添加边
     * @param v1
     * @param v2
     * @param weight  0 表示不可到达   1表示可以到达
     */
    public void insertEdge(int v1,int v2,int weight){
        edges[v1][v2]=weight;
        edges[v2][v1]=weight;
        numOfEdges++;
    }


    public static void main(String[] args) {
        int n = 5;  //结点的个数
        String Vertexs[] = {"A", "B", "C", "D", "E"};

        //创建图对象
        Graph graph = new Graph(n);
        //循环的添加顶点
        for(String vertex: Vertexs) {
            graph.insertVertex(vertex);
        }

        //添加边
        //A-B A-C B-C B-D B-E
		graph.insertEdge(0, 1, 1); // A-B
		graph.insertEdge(0, 2, 1); //
		graph.insertEdge(1, 2, 1); //
		graph.insertEdge(1, 3, 1); //
		graph.insertEdge(1, 4, 1); //

        graph.showGraph();

    }






}