图论

算法

无向图

图是又一组顶点和一组能够将两个顶点相连的边组成。
特殊的图
自环：一条连接一个顶点和其自身的边。
连接同一对顶点的两条边称为平行边。
多重图：含有平行边的图。
简单图：没有平行边或自环的图。
树是无环连通图，互不相连的树组成的集合称为森林。
有一幅含有V个结点的图G满足下列5个条件之一时，它就是一棵树：

• G有V-1条边且不含有环
• G有V-1条边且是连通的
• G是连通的，但删除任意一条边都会使它不再连通
• G是无环图，但添加任意一条边都会产生一条环
• G中任意一对顶点之间仅存在一条简单路径

图的密度：已经连接的顶点对占所有可能被连接的顶点对的比例。
二分图：能够将所有节点分为两部分的图

图的表示方式

要求：必须为可能在应用中碰到的各种类型的图预留出足够的空间
Graph的实例方法的实现一定要快-它们是开发处理图的各种用例的基础
邻接矩阵：所需的空间太大（排除了平行边，邻接矩阵无法表达）
边的数组：不能实现第二个条件，实现和v相邻的所有顶点需要遍历所有边
邻接表数组。
邻接表的数据结构：它将每个定点的所有相邻顶点都保存在该顶点对应元素所指向的一张链表中。

• 使用的空间和V+E成正比
• 添加一条边所需要的时间为常数
• 遍历顶点V的所有相邻顶点所需要的时间和v的度数成正比

支持平行边和自环

深度优先搜索

走迷宫

Tremaux搜索：
选择一条没有标记过的通道，在你走过的路上铺一条绳子
标记所有你第一次路过的路口和通道
当来到一个标记过的路口时会退到上个路口
当回到的路口已没有可走的通道时继续回退

访问其中一个顶点时：将它标记为已访问，递归地访问它的所有没被标记过的邻居顶点。这种方法成为深度优先搜索（DFS），使用一个boolean数组记录和起点连通的所有顶点，递归方法会标记给定的顶点并调用自己来访问该顶点的相邻顶点列表中所有没有被标记过的顶点，如果图是连通的，每个邻接链表中的元素都会被检查到。
深度优先搜索标记与起点连通的所有顶点所需的时间和顶点的度数之和成正比。

单向通道

无向图的深度优先搜索中，碰到边要么进行递归调用，要么跳过这条边，第二次从另一个相反方向遇到一条边的时候会忽略它，因为它的另一端肯定已经被访问了。

深度优先搜索中，每条边都会被访问两次，且在第二次时总会发现这个顶点已经被标记过。

广度优先搜索

得到的路径不仅取决于图的结构，还取决于图的表示和递归调用的性质。
使用一个队列保存所有已经被标记过但其邻接表还未被检查过的顶点，先将起点加入队列，然后重复一下步骤知道队列为空。
取队列中的下一个顶点v来标记它
将与v相邻的所有未被标记过的顶点加入队列。

连通分量

深度优先搜索的下一个直接应用就是找出一幅图的所有连通分量。

最小生成树

加权图是一种为每条边关联一个权值或是成本的图模型。
图的生成树是它的一棵含有其所有顶点的无环连通子图，一幅加权无向图是它的一棵权值最小的生成树。
边的权重不一定表示距离
边的权重可能是0或者负数
所有边的权重都各不相同。

图的一种切分是将图的所有顶点分为两个非空且不重复的两个集合。哼切边是一条连接两个属于不同几何的顶点的边。
切分定理：在一幅加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图的最小生成树。

贪心算法

最小生成树的贪心算法：将含有V个顶点的任意加权连通图中属于最小生成树的边标记为黑色：初始状态下所有边均为灰色，找到一种切分，它产生的横切边均不为黑色，将它权重最小的横切边标记为黑色。反复，直到标记了V-1条黑色边为止。