一. 图的概念

图（Graph），是一种复杂的非线性表结构，图的元素我们就叫做顶点（vertex），一个顶点可以与任意其他顶点建立连接关系，这种建立的关系叫做边（edge），顶点相连接的边的条数叫做度（degree） 。边有方向的图叫做有向图 ，边无方向的图叫无向图 。每条边都有一个权重（weight），可以通过这个权重来表示 一些可度量的值 ，这样的图叫做带权图（weighted graph） 。

image.png

当我们需要表示多对多的关系时，这里我们就用到了图。

1.1 图的举例说明

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

image.png

1.2 图的常用概念

1)顶点(vertex)
2)边(edge)
3)路径
4)无向图

image.png

5)有向图

image.png

6)带权图

image.png

1.3 图的表示方式

1.3.1 邻接矩阵

邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵是的row和col表示的是1....n个点。

image.png

1.3.2 邻接表

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

image.png

二. 图基本算法

image.png

参考:

1. http://www.dataguru.cn/article-5747-1.html
2. https://baijiahao.baidu.com/s?id=1687963417494491661&wfr=spider&for=pc
3. https://www.cnblogs.com/njuptzheng/p/13325222.html