数据结构与算法图的基本概念

1.图的定义
图G由顶点集V和边集E组成，记为G=(V,E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系集合

2.图的一些基本概念和术语
有向图
无向图
简单图：不存在重复遍，和到自身的边
多重图：简单图相反
完全图：任意两个顶点之间都存在边
子图
连通、连通图和连通分量：任意两个顶点都是连通的
强连通图、强连通分量：任意两个顶点之间都有路径
生成树：包含途中全部顶点的一个极小连通子图
生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成深林
顶点的度，入读和出度：
度：定义为以该顶点为一个端点的边的数目
边的权和网：边上具有某种含义的数值
稠密图、稀疏图
路径、路径长度和回路
简单路径、简单回路
距离：两个顶点之间的最短路径
有向树：一个顶点的入度为0，其余顶点的入度均为1的有向图