大体分为无向图和有向图
我们鈳以给边赋予各种各样的属性。比较具有代表性的有权值( cost )边上带有权值的图叫做带权图。在不同问题中权值可以代表距离、时间以及價格等不同的属性。

两个顶点之间如果有边连接,那么就视为两个顶点相邻相邻顶点的序列称为路径。起点和终点重合的路径叫做圈任意两点之间都有路径连接的图叫做连通图。顶点连接的边数叫做这个顶点的度

没有圈的连通图叫做树( tree ),没有圈的非连通图叫做森林。- -棵树嘚边数恰好是顶点数-1反之，边数等于顶点数- 1的连通图就是一棵树
如果在树上选择-一个顶点作为根( root),就可以把根提到最上面，而离根越远嘚顶点越往下安排其位置这样的树叫做有根树。
不过对于无根树,有时选择适当的顶点作为根使之变成有根数，可以使问题得到简化

沒有圈的有向图叫做DAG ( Directed Acyclic Graph)。例如让我们用顶点表示整数，n能整除m时从n向m连一条边的图 这就构成-个DAG。 像下图-样在DAG中我们可以给顶点标记一個先后顺序。
对于每个顶点我们给它一个编号 第1号顶点叫做v。那么存在从顶点v到顶点y的边时就有i<j成立这样的编号方式叫做拓扑序。
如果把图中的顶点按照拓扑序从左到右排列那么所有的边都是从左指向右的。
因此通过这样的编号方式，有些DAG问题就可以使用DP来解决了求解拓扑序的算法叫做拓扑排序。

为了能在程序中对图进行处理,需要把顶点和边用具体的数据结构存储下来在图的表示方法中，比较具有代表性的有邻接矩阵和邻接表需要注意的是,两种表示方法都有各自的优缺点，根据问题的不同使用不同的存储方式可能会影响算法的时间复杂度。

邻接矩阵使用 |V| x |V| 的二维数组来表示图g[i][j]表示的是顶点i和顶点j的关系。

• 无向图中只需知道“顶点i和顶点j之间是否有边连着”这样的信息，因此如果顶点i和顶点 j之间有边相连那么g[i[j]和g[j][i]就设为1,否则设为0。这样就可以表示一个无向图了
  
• 有向图中，只需要知道“是否有从顶点i发出指向顶点j的边”这样的信息因此如果顶点i有一条指向顶点的边，那么g [i] [j]就设为1否则设为0。这样就可以表示一个有向图了有向图与无向图不同，并不需要满足 g[i] [j] = g[j] [i]

用邻接矩阵表示稀疏图会浪费大量内存空间。
而在邻接表中是通过把“从顶点0出发有到顶点2, 4, 5的邊”这样的信息保存在链表中来表示图的。这样只需要O(|V|+IE|)的内存空间

稀疏图使用邻接表处理较好。能大大降低（相比于使用邻接矩阵处理）空间复杂度