数据结构和算法（六）

1.7堆

堆（heap）也被称为优先队列（priority queue）。队列中允许的操作是先进先出（FIFO），在队尾插入元素，在队头取出元素。而堆也是一样，在堆底插入元素，在堆顶取出元素，但是堆中元素的排列不是按照到来的先后顺序，而是按照一定的优先顺序排列的。

1.8图

图G由两个集合V和E组成，记为G=(V,E)，其中， V是顶点(数据元素)的有穷非空集合，E是V中顶点偶对的有穷集合，这些顶点偶对称为边 。
（1）图的种类：
1.有向图

2.无向图

（2）权和网：
权：图中的边可标上具有某种含义的数值，该数值称为边上的权。
网：权可表示为从一个顶点到另一顶点的距离或耗费，这种边带权的图称网（网络）。
二、 图的存储表示
1.邻接矩阵（矩阵上的每个坐标代表当前两个顶点之间是否有边，有边值为1，无边为0）
2.邻接表（对于图G中的每个顶点vi，把所有邻接于vi的顶点链成一个单链表，这个单链表就称为顶点vi的邻接表）
（1）邻接矩阵：
例如：

对应的邻接矩阵为：

（2）邻接表：
例如：

对应的邻接表为：

（3）邻接表与邻接矩阵对比：

三、图的遍历

1.广度优先搜索算法
（1）连通图的深度优先搜索遍历： 从图中的某个顶点V出发，访问此节点，然后依次从V的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V路径想通的顶点都被访问到。

（2）图的广度优先搜索遍历图：
从图中的某个顶点V出发，并在访问此顶点之后依次访问V的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。