冒泡排序

快速排序

插入排序

希尔排序

选择排序

堆排序

归并排序

桶排序(计数排序)

• 自环:一条连接一个顶点和自身的边
• 平行边: 连接同一对顶点的两条边
• 路径: 由边顺序连接的一系列顶点
• 简单路径: 没有重复的顶点的路径
• 连通图: 从任意一个顶点都存在路径到达另一个任意点
• 树是一个无环连通图
• 连通分量：连通子图
• 有向环：起点和终点相同的有向路径
• 有向无环图(DAG)：不含有向环的有向图
• 强连通: 如果w和v是互相可达的，那么他们就是强连通的
• 有向图前序排列：在递归前将顶点加入队列
• 有向图后序排列：在递归后将顶点加入队列
• 有向图逆后序排列：在递归后将顶点加入栈
• 拓扑：给定一副有向图,将所有的顶点排序，使所有的有向边从排在前面的元素指向后面的元素

定义： 图的生成树是它的一颗含有其他所有顶点的无环连通子图。

• 用一条边连接任意两个顶点都会产生一个新的环

• 从树中删掉一条边会得到两颗独立的树

• 把图中的顶点分成两部分，称为切分

• 横切边：边的顶点分别属于切分的两个集合

在一副加权图中，给定任意的切分，权值最小的横切边一定属于最小生成树

初始状态下所有的边都设置成灰色，找到一种切分它的所有横切边都是灰色的，把他的最小横切边标记为黑色，直到标记了V-1条黑色的边为止。