数据结构与算法(三十)图的基本介绍

为什么要有图

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

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

图的常用概念

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

图的表示方式

  • 图的表示方式有两种:二维数组表示(邻接矩阵);链表表示(邻接表)。
    - 邻接矩阵
    邻接矩阵是表示图形中顶点之间相邻关系的矩阵,对于n个顶点的图而言,矩阵是的row和col表示的是1....n个点。
    image.png

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

image.png

图的代码实现

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();

    }






}

image.png

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://www.fengpt.cn/archives/数据结构与算法三十图