数据结构学习小记2（图1）

一、今日的学习的是图这一部分，图这一部分是个人感觉最难的，所以最先开始复习，并且分几块复习。

图（Graph）G是由两个集合V和E组成，记为G=(V,E).

V是顶点的的有穷非空集合，V(G)表示图的顶点集（顶点的单词为vertex）.

E是边的有穷非空集，E(G)表示图的边集合，若边集为有向边的集合，则称该图为有向图；若边集为无向边的集合，则称该图为无向图。（边的单词为：edge）。

二、一些基本术语

（1）子图：假设有两个图，G=（V，E）和G1=（V1，E1），如果V1 集合属于V，E1集合属于E，则称G1为G的子图。

（2）对于无向图，若具有n(n-1)/2条边，则称为无向完全图；对于有向图，若具有n(n-1)条弧则称为有向完全图。

（3）有很少条边或弧的图称为稀疏图，反之称为稠密图。对于稀疏图，邻接表的表示法更适合；对于稠密图，邻接矩阵的表示法更适合

（4）权和网：在实际应用中，每条边可以表上具有某种含义的数值，该数值称为该边上的权，这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网。

（5）邻接点：对于无向图G，如果图的边（v，v1）∈E，则称顶点v和v1互为邻接点，即这两点相邻接。边（v，v1）依附于顶点v,v1,或者说v,v1相关联。

（6）度：顶点v的度就是指和v相关联的边的数目，记为TD(v).

（7）对于有向图，顶点v的度分为出度和入度。出度是以顶点v为尾的弧的数目，记为OD(v),入度是以顶点v为头的弧的数目，记为ID(v)。

一般地，如果一个顶点的度记为TD(vi),那么一个有n个顶点，e条边的图，满足如下关系

e=1/2∑ TD（vi）

（7）在无向图G中，从顶点v到v1的路径是一个顶点序列，如果G为有向图，则路径也是有向的。路径长度是一条路径上经过的弧或者边的数目。

（8）第一个顶点和最后一个顶点相同的路径称为回路或环。

（9）序列中顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路或简单环。

（10）如果从顶点v到顶点v1有路径，则称v和v1是连通的。如果对于图中任意两个顶点都是连通的，则称G为连通图。连通分量就是指无向图中的极大连通子图。

（11）对于有向图，如果对于每一对v1,v2∈V,v1≠ v2,从v1到v2和v2到v1都存在路径（即任意两点存在双向路径），则称G为强连通图。有向图的强连通分量就是指有向图中的极大强连通子图。

（参考自教材严蔚敏版《数据结构》）