数据结构全攻略--概念篇之图

    上篇博客讨论了几种特殊的二叉树结构之间的关系，接下来继续讨论非线性结构的图，这部分的概念比较多，在继续往下看前，先来看看图中的基本概念。

一、基本概念

1、图和树

   也许你会疑问图和树之间有什么关系吗，来我们看看下面这张有关图的图。

   上图中的图（a）很像树结构，其实它是图，所以树是一种特殊的图。树将节点有规律的组合到了一块，所以从某种意义上说树是一种特殊的图结构，图（a）也将是接下来要讨论的生成树。

2、生成树

    从图中任意一顶点出发遍历图，所经历的边的集合可看做是一个图的生成树，按照深度和广度的不同会得到不同的生成树，得到的生成树也是该图的一个子图。

最小生成树

    由于生成树不唯一，从不同的顶点出发可以得到不同的生成树。对连通网来说，边是带权值的，构造出具有最小权值的生成树就是最小生成树。构造最小生成树有多重算法，下面介绍两种最常用的。

2.1 普利姆算法

    构造过程：以一个顶点集合U={μ}作初态，不断寻找与U中顶点相邻且代价最小的边的另一个顶点，扩充U集合直至U中顶点包括所有的顶点为止。

2.2  克鲁斯卡尔算法

       构造过程：在图E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而进行选择下一条代价最小的边。

3、图的其它概念

    图中有很多概念，其中最让人头疼的是连通分量，连通分量是针对于无向图来说的，另一种是是强连通分量，它针对于有向图来说的，这两种都是指代的极大连通子图。

    对于连通分量来说，它指的是一个图中的极大连通子图，一个无向图可以分成几个极大地连通子图，极大相当于数学中的极大值，尽可能多的在子图中增加相连接的节点，示例如上图。

3.1 图的存储结构

    图的存储结构有两种，分别是邻接矩阵和邻接链表。邻接矩阵中元素分为0或1，0代表两个顶点之间没有边，1代表两顶点之间有边。邻接链表存储方式，类似于以前说的二叉树的邻接链表存储方式，一个结点指针域指向邻接结点。

3.2 有向图

    有向图有很重要的两种网，两种网是在工程领域中定义工程项目实施的一个模型，类似于PERT图。

3.2.2 拓扑排序

         AOV网：分为顶点和有向边，其中顶点表示活动，有向边表示顶点之间的优先关系，重要的是顶点，表示了活动。

    拓扑排序：依次找出只有输出没有输入的顶点，把得到的顶点排成一个线性结构。

3.2.3 关键路径

        AOE网：和AOV网相反，有向边是主体，表示了活动，其中边上的权值表示了活动的持续时间，顶点表示了事件。

   关键路径：从源点到汇点，长度最长的路径成为关键路径，要求路径上活动的持续时间最长。

二、结语

    至此，有关非线性结构的图的概念进行了一边回顾，其中很不多概念和以前树的概念相似，而且客观来说树是一种特殊的图，所以树的一些概念同样适用于图，另外在图中有两种特殊的网用在工程领域分别是AOV和AOE，两种网的概念很容易理解。

2楼kanglix1an昨天 23:01

学习啦

1楼u011487732昨天 22:25

人家业绩300W的表示很淡定。。。http://www.haobitou.com/new/300W.html#2