数据结构-图

图也是一种非线性结构，图中任意两个节点间都可能有直接关系。

相关定义如下：

无向图：图的结点之间连接线是没有箭头的，不分方向。

有向图：图的结点之间连接线是箭头，区分A到B,和B到A是两条线。

完全图：无向完全图中，节点两两之间都有连线，n个结点的连线数为n-1)+n-2+…+1 n*(-1)/2:有向完全图中，节点两两之间都有互通的两个箭头，n个节点的连线数为 n*(n-1）

度、出度和入度：顶点的度是关联与该顶点的边的数目。在有向图中，顶点的度为出 度和入度之和。出度是以该顶点为起点的有向边的数目。入度是以该顶点为终点的有 向边的数目。

路径：存在一条通路，可以从一个顶点到达另一个顶点，有向图的路径也是有方向的。

连通图和连通分量：针对无向图。若从顶点v到顶点u之间是有路径的，则说明v和u之间是连通的，若无向图中任意两个顶点之间都是连通的，则称为连通图。无向图G的极 大连通子图称为其连通分量。

强连通图和强连通分量：，针对有向图。，若有向图任意两个顶点间都互相存在路径，即 存在v到，也存在u到的路径，则称为强连通图。有向图中的极大莲通子图称为其强 连通分量。

网：边带权值的图称为网。

图的存储

邻接矩阵：假设一个图中有n个节点，则使用n阶矩阵来存储这个图中各节点的关 系，规则是若节点i到节点j有连线，则矩阵Ri,j=1,否则为0。因此，如果是一个无 向图，肯定是沿对角线对称的，只需要存储上三角或者下三角就可以了，而有向 图则不一定对称。示例如下图所示：

、

邻接链表：用到了两个数据结构，先用一个一维数组将图中所有顶点存储起来 而后，对此一维数组的每个顶点元素，使用链表挂上和其有连线关系的结点的编 号和权值，示例如下图所示：

图的遍历

图的遍历是指从图的任意节点出发，沿着某条搜索路径对图中所有节点进行访问且只访问一次，分为以下两种方式：

深度优先遍历：从任一顶点出发，遍历到底，直至返回，再选取任一其他节点出发，重复这个过程直至遍历完整个图；

广度优先遍历：先访问完一个顶点的所有邻接顶点，而后再依次访问其邻接顶点的所有邻接顶点，类似于层次遍历。

图的最小生成树

假设有n个节点，那么这个图的最小生成树有n-1条边（不会形成环路，是树非图），这n-1条边会将所有顶点都连接成一个树，并且这些边的权值之和最小，因此称为最小生成树。

普里姆算法：从任意顶点出发，找出与其邻接的边权值最小的，此时此边的另外一个顶点自动加入树集合中，而后再从这这个树集合的所有顶点中找出与其邻接的边权值最小的，同样此边的另外一个顶点加入树集合中，依次递归，直至图中所有顶点都加入树集合中，此时此树就是该图的最小生成树。

克鲁斯卡尔算法（推荐）：这个算法是从边出发的，因为本质是选取权值最小的n-1条边，因此，就将边按权值大小排序，依次选取权值最小的边，直至囊括所有节点，要注意，每次选边后要检查不能形成环路。

图的拓扑序列

AV网（以顶点表示活动的网）：在有向图中，以顶点表示活动，用有向边表示活 动之间的优先关系。

AV网用来表示大的工程项目执行计划，因此不能出现有向环，若存在，则意味着 某项活动必须以自身任务的完成为先决条件，因此，若要检测一个工程是否可行， 首先应检查对应的AV网是否存在回路。检测的方法是对有向图构造其顶点的拓扑 有序序列。

构造方法：将有向图的有向边作为活动开始的顺序，若图中一个节点入度为，则 应该最先执行此活动，而后删除掉此节点和其关联的有向边，再去找图中其他没 有入度的结点，执行活动，依次进行，示例如下：