# 图

图是一种网状结构，图分为有向图和无向图。边有方向的称为有向图，边无方向的称为无向图。通常使用G=<V,E>来表示一个图，V表示顶点，E表示边。

图有两种表示方法：邻接表和邻接矩阵。邻接矩阵就是用二维数组来表示，这种情况很容易造成空间浪费，所以进行空间优化后可以选择使用邻接表的方式来表示。

邻接表是数组嵌套链表，会比邻接矩阵节省不少空间，但是对于无向图来说，仍然会浪费一半的空间。

# 概念

弧：在有向图中，通常将边称为弧，含箭头的一端成为弧头，另一端称为弧尾，记作 $<vi,vj>$ ，它表示从顶点vi到顶点vj有一条边。边就是弧。

顶点的度：与它关联的边的数量。

子图：一张图的一部分。

连通图与非连通图：连通图是指图内任意两个节点间，都有一条路径能连接它们。否则，就是非连通图。如果图中有孤立的岛，则说明是非连通图。

加权图与非加权图：加权图含有权重，非加权图的节点和边上有没有权重。

非循环图和循环图：非循环图是指图中不存在循环路径（起点和终点是同一个顶点），反之循环图则是包含循环路径。有向图和无向图都可能包含循环。

树与图的关系：树是一个无向连通图，其中任何两个顶点只通过一条路径连接。换句话说，一个任何没有简单环路的连通图都是一棵树。