算法速成（十四）图之非线性数据结构

算法速成（十四）图之非线性数据结构2014-04-28 csdn博客特种兵—AK47今天来分享一下图，这是一种比较复杂的非线性数据结构，之所以复杂是因为他们的数据元素之间的关系是任意的，而不像树那样

被几个性质定理框住了，元素之间的关系还是比较明显的，图的使用范围很广的，比如网络爬虫，求最短路径等等，不过大家也不要胆怯，

越是复杂的东西越能体现我们码农的核心竞争力。

既然要学习图，得要遵守一下图的游戏规则。

一：概念

图是由“顶点”的集合和“边”的集合组成。记作：G=（V,E）；

<1> 无向图

就是“图”中的边没有方向，那么（V1,V2）这条边自然跟（V2，V1）是等价的，无向图的表示一般用”圆括号“。

<2> 有向图

“图“中的边有方向，自然<V1,V2>这条边跟 <V2,V1>不是等价的，有向图的表示一般用"尖括号"表示。

<3> 邻接点

一条边上的两个顶点叫做邻接点，比如（V1，V2），（V1，V3），（V1，V5），只是在有向图中有一个“入边，出边“的

概念，比如V3的入边为V5，V3的出边为V2，V1，V4。

<4> 顶点的度

这个跟“树”中的度的意思一样。不过有向图中也分为“入度”和“出度”两种，这个相信大家懂的。

<5> 完全图

每两个顶点都存在一条边，这是一种完美的表现，自然可以求出边的数量。

无向图：edges=n（n-1）/2;

有向图：edges=n（n-1）; //因为有向图是有边的，所以必须在原来的基础上"X2"。