数据结构之图（概念）

定义

一个图边集可以是空集，不过顶点集不能是

应用

有有向图和无向图两种

无向图和有向图

简单图和多重图

我们在数据结构课程中只研究简单图奥

顶点的度，入度和出度

无向图
假设e为无向图的边的数量
图的度=2e,一条边共享2个度
有向图异曲同工

顶点顶点间关系的描述

点和点之间的距离，是两个点之间的最短距离

连通图和强连通图

非连通图的最多边的情况

子图

生成子图：包含原图的所有节点，可以不包含所有边
有向图同理

连通分量和强连通分量

在连通的情况下包含尽可能多的边和顶点

生成树

边尽可能保持的少还要连通
边肯定为n-1条因为只要多一条边图就会有回路

生成森林

把图的连通分量单独拿出来
然后搞成生成树就是生成森林喽

边的权/带权图

几种特殊的图

总结