什么是图
图是用来表示一些事物关系的表示方法，树是图的一种，许多问题都可以归纳成图的问题。
图由顶点（node）和边（edge）组成：
图的种类
有指向性的图叫做有向图，没有指向的图叫做无向图，上面的图片是无向图。
下面是有向图：
图的边可以带上权值，可以粗略的理解为边的长度，因为权值可以表示距离，也可以表示其他特殊含义。
带权值的图被叫做 带权图 。
无向图的基本概念
相邻 ：如果两个顶点有连接，则称他们相邻。
路径 ：相邻顶点的序列叫做路径，如下图，3和4之间的路径为
3-7-1-4 或者 3-9-5-4 ：
连通图 ：任意顶点之间都有路径的图叫做连通图。
圈 ：起点和终点一样的路径叫做圈。
树 ：没有圈的连通图叫做树，一棵树的边数恰好是顶点数-1。
森林 ：没有圈的 非 连通图叫做森林。
度 ：顶点连接边数的图叫做度，如上图，1的度是3，4的度是2。
有向图的基本概念
出度 ：由顶点向外指出的边的数量为该点的出度。
入度 ：指向顶点的变的数量为该点的入度。
图的表示
为了处理图这种结构，我们最常见的有两种图的表示方法：
邻接矩阵 和 邻接表 。
邻接矩阵
邻接矩阵用一个二维数组 G 表示。
在无向图中，如果 i 和 j 连接，我们就把 G[i][j] 和G[j][i] 设置成1或者对应的权值就行了。
比如我们连接3和1，他们之间的权值是5，数组如下图所示：
在无向图中，如果表示 i 指向 j ，我们就把 G[i][j] 设置成1或者对应的权值，就不需要设置 G[j][i] 了。
邻接表
用邻接矩阵会浪费大量内存，于是我们可以用邻接表。
邻接表的表示如下图：
邻接表的实现有很多方法，它比邻接矩阵节省内存，不过实现比矩阵复杂。
在邻接表中查询两点是否有边，我们需要遍历一遍顶点列表才行。
而矩阵不需要，直接用下标索引就行了。
所以邻接表的速度会比邻接矩阵慢一些。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ji-chu/88026.html