欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构与算法六:图

程序员文章站 2024-03-12 15:54:56
...

1. 图基本介绍

1.1 为什么要有图

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

1.2 图的举例说明

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

2. 图的常用概念

数据结构与算法六:图
数据结构与算法六:图

3. 图的表示方式

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

3.1 邻接矩阵

邻接矩阵是表示图形中顶点之间相邻关系的矩阵,对于n个顶点的图而言,矩阵是的row和col表示的是1…n个点。
数据结构与算法六:图

3.2 邻接表

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

4. 图的快速入门案例

要求: 代码实现如下图结构.
数据结构与算法六:图

/**
 * 图
 *
 * @author Wnlife
 * @create 2020-01-26 20:18
 */
public class Graph {

    /**
     * 存储顶点的集合
     */
    private ArrayList<String> vertexList;
    /**
     * 存储图对应的邻接矩阵
     */
    private int[][] edges;
    /**
     * 表示边的数目
     */
    private int 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);
        graph.insertEdge(0,2,1);
        graph.insertEdge(1,2,1);
        graph.insertEdge(1,3,1);
        graph.insertEdge(1,4,1);
        //打印图
        graph.showGraph();


    }

    /**
     * 构造函数,初始化图
     *
     * @param n 顶点的个数
     */
    public Graph(int n) {
        edges = new int[n][n];
        vertexList = new ArrayList<>(n);
        numOfEdges = 0;
    }

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

    /**
     * 显示图对应的矩阵
     */
    public void showGraph(){
        Arrays.stream(edges).forEach((v)->{
            System.out.println(Arrays.toString(v));
        });
    }

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

    /**
     * 返回结点i(下标)对应的数据 0->"A" 1->"B" 2->"C"
     * @param i 下标
     * @return 数据
     */
    public String getValueByIndex(int i){
        return vertexList.get(i);
    }

    /**
     * 返回两个节点的权值
     * @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 表示权重
     */
    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }
}
相关标签: 算法和数据结构