C++ STL中的栈与队列：核心原理与实战应用指南

在C++标准模板库（STL）中，stack（栈）和queue（队列）是两个重要的容器适配器，它们通过封装底层容器（默认使用deque）实现了特定的数据操作逻辑。本文将深入探讨它们的设计原理、常用操作及典型应用场景，帮助开发者快速掌握其核心用法。

一、栈（stack）：后进先出的数据管理
核心特性与初始化

栈遵循后进先出（LIFO）原则，仅允许在栈顶进行插入和删除操作。其底层通常基于deque或list容器实现。

include <stack>

std::stack<int> s;  // 默认基于deque的整型栈

常用操作及示例

方法         功能描述 示例代码

push(x) 将元素x压入栈顶 s.push(10);
pop() 移除栈顶元素（不返回值） s.pop();
top() 返回栈顶元素的引用（需非空检查） int val = s.top();
empty() 判断栈是否为空（返回布尔值） if (s.empty()) {...}
size() 返回栈中元素数量 int cnt = s.size();

操作示例：遍历栈并输出所有元素

std::stack<int> s;
s.push(1); s.push(2); s.push(3);
while (!s.empty()) {
    std::cout << s.top() << " ";  // 输出：3 2 1
    s.pop();

典型应用场景

括号匹配：通过栈结构检测表达式中的括号嵌套是否正确

深度优先搜索（DFS）：递归算法中隐式使用栈管理访问路径

撤销操作：文本编辑器中按顺序记录操作步骤

二、队列（queue）：先进先出的任务调度
核心特性与初始化

队列遵循先进先出（FIFO）原则，元素在队尾插入，队首删除。底层同样基于deque或list实现。

include <queue>

std::queue<std::string> q;  // 字符串队列

常用操作及示例

方法         功能描述 示例代码

push(x) 将元素x插入队尾 q.push("task1");
pop() 移除队首元素（不返回值） q.pop();
front() 返回队首元素的引用（需非空检查） auto task = q.front();
back() 返回队尾元素的引用 auto last = q.back();
empty() 判断队列是否空 if (q.empty()) {...}
size() 返回队列元素数量 int len = q.size();

操作示例：处理任务队列

std::queue<int> q;
q.push(10); q.push(20); q.push(30);
while (!q.empty()) {
    std::cout << q.front() << " ";  // 输出：10 20 30
    q.pop();

典型应用场景

广度优先搜索（BFS）：按层次遍历树或图结构

消息队列：异步处理系统中的任务缓冲

打印任务调度：保证文档按提交顺序打印

三、进阶扩展：优先队列（priority_queue）
优先队列是队列的变种，元素按优先级排序（默认最大堆）。常用于任务调度系统：
include

// 小顶堆示例
std::priority_queue<int, std::vector, std::greater> pq;
pq.push(3); pq.push(1); pq.push(4);
pq.top(); // 返回1（当前最小元素）

一、插入排序

1.直接插入排序与折半插入排序。

　　1.1步骤：
　　　(1)对于第i个元素，先用临时变量保存之，然后在1 ~ i-1的有序序列中找到其该插入的位置k。
　　　(2)将k到i-1的所有元素后移一位，导致k被腾出。
　　　(3)将临时变量保存的i号元素赋值到k位置。
　　*对于折半插入排序，因为i前必有序，找插入位置可使用折半查找。注意mid与临时变量相等时（即序列有重复元素），让low = mid + 1而非直接结束，最后将low ~ i-1或high+1 ~ i-1的元素往后移动一位腾出位置供插入。k=low。这样做是为了保证稳定性。考虑abcccdec，最后一个c为待插入前面的元素，mid=4与临时变量匹配就认为找到了k的话，在5的位置还有一个c就会被移动，就不稳定。
　　*对于直接插入排序，步骤(1)的找位置与步骤(2)同时进行。
　　*时间复杂度为O(n^2)。空间复杂度为O(1)。稳定。

2.希尔排序/缩小增量排序

　　2.1思想：
　　　以逐渐减小为1的增量（步长）划分子表，一个增量d可以把原序列化为d个子表，对每个子表插入排序即可。增量为1就是直接插入排序了。
　　*时间复杂度不明。空间复杂度为O(1)。不稳定。

二、交换排序

1.冒泡排序

　　*对于求冒泡的趟数的，把每一趟结束的序列写出来不要偷懒。最后千万别忘了得到一个排完序的序列之后实际上程序还要再跑一趟从而发现没有进行任何交换才会结束。
　　*时间复杂度为O(n^2)。空间复杂度为O(1)。稳定。

2.快速排序

　　*思想：移走首元素留下空位，比首元素（枢轴pivot）小的移到前面空位从而在后面产生空位，大的移到后面空位从而在前面产生空位，两者交替，最终空的就是存放首元素的位置。
　　*画二叉排序树的心算方法：把序列写出来，把首元素（枢轴pivot）写到序列下面，序列与其下的pivot充当一个结点。左手手指为low指针，右手笔为high指针，分别指向序列首尾。先low不动，high从当前位置的前一位开始判断是否比pivot小，不是则写入到该结点右分支的最左，high往左移动并继续判断，直到找到并写入到该结点左分支的最右或high与low相等则表明该结点成功生成子结点了。若结束原因非后者，则此次是保持high不变，low从其后一位开始移动直到low指向的大于pivot从而写入到high的位置或low与high相等。两者如此交替重复几轮终会导致low=high。此时两个子结点就生成完毕。然后对两个子结点的序列进行同样的操作。（详见王道p351第10题）
　　*时间复杂度：最好时树高logn，树的每一层low与high都对整个序列一个个的遍历，为n。故最好时间复杂度O(nlogn)。最坏树是单支树，O(n^2)。快速排序发生最好的情况的概率更大，故平均时间复杂度O(nlogn)。
　　*空间复杂度：即同时处于栈段的函数栈的个数，即树的树高，因此最好O(logn)最坏O(n)，平均O(logn)。
　　*定下一个序列的枢轴最终所在的位置需要比较的次数就是该序列长度-1。因为所有的比较无非就是枢轴元素与其他所有元素的比较。

三、选择排序

1.简单选择排序

　　*思想：每次从无序序列中选出最大/最小的元素交换到有序序列前/后一位。

2.堆排序

　　*堆即顺序存储的，根与其两个孩子有大小关系的完全二叉树。若堆有n个元素，则非叶结点的数量为⌊n/2⌋个。
　　*堆分为大根堆与小根堆。
　　步骤：
　　a.先将序列建堆。方法是序列前⌊n/2⌋个元素调用HeadAdjust函数。该函数针对传入其的根结点，暂存根结点并产生k与i双指针，其中k永远是i的双亲。在一个i每次乘2（指向其左孩子）的循环中，先比较左右孩子孰大孰小以确定i是否+1成为k的右孩子，在比较i与k孰大孰小决定是否让i移动到k的位置上，若无需移动则表明当前k结点为根的树符合堆的定义了，否则接下来k=i调整其子树成为堆。
　　b.建立n-1次的循环。这里与选择排序一致，因为堆顶一定是最大/小的元素，省去了选择排序遍历的麻烦。但每次将堆顶元素交换到后面都要调用HeadAdjust函数调整前面。
　　*建堆时间复杂度O(n)，堆排序时间复杂度O(nlogn)，总体O(nlogn)，空间复杂度O(1)。不稳定。
　　*堆的插入操作：新结点放序列末尾，然后向上调整。时间复杂度O(logn)。
　　*堆的删除操作：删除结点，以序列末尾元素代替。然后向下调整。时间复杂度O(logn)。
　　*题目若要求堆排序、堆插入或堆删除的比较次数，对每个结点，先比较其两个子结点的大小，选出有资格与该结点比较的子结点与该结点比较。子结点若不为叶结点则继续往下记录比较次数。
　　*题目若要求堆排序、堆插入或堆删除的交换次数，对每个结点，若其子结点移动到该结点的位置就算“交换”，即使实际代码中子结点并没有被该结点赋值。

四、归并排序

　　1.思想（以排成从小到大的序列为例）：
　　*全局建立一个辅助数组B，长度与序列长度相同。（因为首位弃用故长度为元素个数+1）
　　*函数Merge:传入待排序数组A，以及low,high,mid。左半部分数组为A[low~mid]，右半部分数组为A[mid+1~high]，两个子数组都有序。将所有这些元素通通移动到B中同下标的位置。然后设置三指针i,j,k。i为B中左半部分数组的移动索引，j为B中右半部分数组的移动索引，k为A的移动索引。循环比较B[i]与B[j]，谁小谁移到B[k]（相等则先把左子数列中的移到A保证稳定性），A[i]移走i++，A[j]移走j++，k不管谁移走都要加1。最终因为i与j的任何一个出界退出循环。最后再将没有移动完的B的子数组移动到A剩余位置。
　　*函数MergeSort:利用递归，递归结束条件是传入该层递归函数的low与high相等，否则产生变量mid=(low+high)/2，以low到mid调用他自己，再以mid+1到high调用他自己。最后调用Merge将low到high中的序列排有序。

2.排序趟数取决于树高，O(logn)，每趟O(n)，时间复杂度O(nlogn)，空间复杂度O(n)，稳定。

五、基数排序

　　1.思想：从关键字本身的信息出发，设关键字为r进制，位数为d位，个数为n个。设置r个队列，将最低位，放进相应队列（分配），再将各个队列的关键字保持先后顺序的拿出来存进链表（收集），再到下一位直至最高位。从高位出发到低位亦可行。
　　2.共d趟，每趟分配O(n)，收集O(r)，时间复杂度O(d(n+r))，空间复杂度O(r)。

一、线性表查找算法

1.顺序查找

　　•顺序查找无视待查表的有序与否。

2.折半查找

　　•折半查找只能用于顺序存储的线性表。
　　•表的各个元素在判定树中所在的树高就是其比较次数。对于失败情况所在的叶节点，其比较次数为其所在树高-1。判定树高度计算式与完全二叉树一致——里上外下。
　　•求ASL：画判定树，然后利用ASL定义计算。
　　•画判定树：别像个乌龟一样脑海中模拟一遍折半查找才画完树，用简便方法——逐个往树上添加结点，若是mid = (l + r)/2，要求使判定树中的每个子树的左子树结点数=右子树结点数，或左子树结点数+1=右子树结点数（因为当l与r之间有奇数个表项，mid算出来就是中间那个，其左右子树结点相等；当l与r之间有偶数个表项，mid的左子树就会比右子树少一个结点）。最后画完时，为树中原有的每个空链域添加一个叶结点表示失败情况。

3.分块查找/索引顺序查找

　　•求ASL：
　　　-通过定义求：每一个表项的查找次数 = 其所在块在索引表的位置 + 其在块中的位置。通过定义求和所有块的所有表项即可（很麻烦）。
　　　-简便方法：ASL = 索引表的ASL + 单个块的ASL。索引表的ASL和单个块的ASL由定义求出。

4.散列表（哈希表）

　　•求ASL：
　　•开放寻址解决冲突的散列表的相邻地址不一定存储同义词，是交错排列的。
　　•链地址法（拉链法）不可能造成聚集现象。（聚集——多个不同初地址关键字抢夺同一个地址进行插入）
　　•散列表的ASL或时间复杂度与装填因子直接相关，与不直接依赖于关键字数或散列表容量。

二、树形查找

1.二叉排序树（BST, Binary Search Tree）

　　1.1 查找：
　　　　——循环实现：使用游离指针T指向根结点，开始循环，当游离指针指向的结点为待找结点（找到）或游离指针指向NULL（没有该结点）时退出循环，否则让T指向该结点的左右孩子结点（待查找值小于T时让T指向T的左孩子，当待查找值大于T时让T指向T的右孩子）。
　　　　——递归实现：递归函数是递归结束函数的条件仍然是找到或当前传入的结点已经为NULL，此时返回T。递归函数是递归中间函数的条件相反，即传入的结点不为空，但又不与待找结点相同，那就分小于与大于，待找结点小于当前传入函数的结点时，返回递归调用左子树的结果，反之递归调用右子树的结果。
　　1.2 插入（递归实现）：递归函数是递归结束函数的条件是找到相同的或当前传入的结点为NULL，相同则返回错误，为NULL则修改该结点为malloc新建结点的返回值。递归函数是递归中间函数的条件相反，即传入的结点不为空，那就分小于，大于与等于，待找结点小于当前传入函数的结点时，返回递归调用左子树的结果，反之则递归调用右子树的结果。
　　1.3 构造：从头遍历关键字序列，对每一个序列调用插入操作。
　　1.4 删除：查找该结点在树中的位置。
　　　　——若该结点是叶节点，则直接删除。
　　　　——若该结点只有左子树或只有右子树，则直接让其子树的根节点代替它。
　　　　——若该结点既有左子树又有右子树，则需要让其直接前驱或直接后继复制给它。找直接前驱：中序遍历其左子树，最后遍历到的即其直接前驱。找直接后继：中序遍历其右子树，最先遍历到的即其直接后继。然后删除其直接前驱或直接后继的所处的结点（该结点肯定是叶节点或只有左子树/右子树）。
　　•中序遍历即可得到一个二叉排序树的有序序列。同一个序列的所有二叉排序树中序序列相同，且这些二叉树的中序序列就是该序列。
　　•卡特兰数 = n个结点构造的不同二叉排序树的个数 = 中序确定，不同先序序列的个数。计算式在王道书p301。

2.平衡二叉树（AVL树，取名为开发者名字首字母）

　　•平衡二叉树用于二叉排序树，使得查找时间为O(logn)，更快。
　　2.1 插入与删除：
　　　（1）直接插入，删除。
　　　（2）从插入/删除的点向上找最小不平衡树的根结点r。
　　　（3）找到该根结点r的高度最高的儿子结点x，结点x高度最高的儿子结点y。
　　　（4）分以下四种情况：
　　　　a.x,y都是左孩子——r相对x右（下）旋
　　　　b.x,y都是右孩子——r相对x左（下）旋
　　　　c.x左y右——x相对y左（下）旋，然后r相对y右（下）旋
　　　　a.x右y左——x相对y右（下）旋，然后r相对y左（下）旋
　　•ab情况是x成为最终根结点，cd情况是y成为最终根结点。
　　　（5）若是删除操作，则需要继续向上找有没有不平衡的结点。
　　•因为插入操作的插入操作本身及其后的四种平衡处理最终不会影响最小不平衡树的树高，而删除操作的删除操作本身及其后的四种平衡处理可能会使最小不平衡树的树高 - 1导致其祖先结点不平衡。
　　2.2 结点数分析
　　•平衡二叉树达到树高h的最少结点数：n(h) = n(h-2) + n(h-1) + 1，即树高为h所需的最少结点为将树高为h-1与树高为h-2的结点用一个根结点相连即可。
　　•平衡二叉树不超过树高h的最多结点数：满二叉树。
　　•平衡二叉树给定结点数的树高最低为里上外下，但可以更高。不同于完全二叉树给定结点数它就是一定是里上外下的树高。但是若从空树开始，插入序列是升序的，则产生的平衡二叉树的高度就是结点数对应的完全二叉树高度。
　　•平衡二叉树的一个结点的两个孩子平衡因子都为0，该结点平衡因子不一定为0。

3.红黑树（RBT）

　　3.1 原则：左根右，不红红，根叶黑，黑路同。
　　3.2 树形/时间复杂度分析：
　　结点黑高——结点到任意叶节点的路径上的黑结点数（不计该结点）。
　　树的黑高——根结点到任意叶节点的路径上的黑结点数（不计根结点）。
　　•树高（不算叶节点）最少为树黑高（全黑），最多为树黑高的两倍（黑红相间）——这是红黑树较平衡二叉树放宽松的地方。
　　•一个红黑树的黑高为bh，则该二叉树结点最少的情况为该树是高度为bh的满二叉树且全为黑结点，最多为该满二叉树两两黑结点之间添加红结点成为高度为2bh的满二叉树。
　　•n个结点可以生成的红黑树的最大高度为2log(n+1) （记住即可）（尝试解释：对于一颗全黑满树，挑一条路径，两两黑结点之间插入红结点以增加树高，最后得到的树就是达到该树高对结点量需求最少的树。此时树高为h，黑结点数为2^(h/2)-1，红结点数为h，该结点需求最少的树拥有2^(h/2)-1+h个结点。）
　　•AVL树与红黑树的查找，删除，插入的时间复杂度都为O(logn)。
　　3.3 插入：（直接插入+维护不红红条件）
　　a.插入结点。若插入结点将作为根结点，设为黑色，结束，否则设为红色（维护“黑路同”条件）。
　　b.看父结点是否是黑色，黑色表明不与“不红红”冲突，结束，否则进行接下来的维护操作。
　　c.看叔结点的颜色决定维护操作：
　　　c.1 叔结点为红色：叔父爷变色，将爷视为插入结点重复a步骤。
　　　c.2 叔结点为黑色或不存在：旋转+染色。旋转同AVL树，将其爷节点视为“最小不平衡子树根结点”r，将其父结点视为r的“最高子树”。染色时LL与RR旋，则父爷换色，LR与RL旋，则爷与插入结点换色。
　　•红黑树的任意子树不一定为红黑树，因为不一定满足根结点必黑的条件。
　　•红黑树的删除操作的旋转次数可能超过两次，插入操作最多两次旋转。

4.B树

　　4.1 树形/时间复杂度分析
　　给定关键字数n，树的阶数m。
　　•为了树尽量矮，规定每个非根结点至少有⌈m/2⌉个子树，至少包含⌈m/2⌉-1个关键字。根结点若不为叶节点至少有一个关键字即两个子树。
　　•树的高度最大时，根结点仅包含一个关键字，每个非根结点仅包含(⌈m/2⌉-1)个关键字，射出⌈m/2⌉条边（即充分伸高），关键字数为n = f(h) = 1+(⌈m/2⌉-1)（2+2⌈m/2⌉+2⌈m/2⌉^2+2⌈m/2⌉^3...+2⌈m/2⌉^(h-2))。那么可以求得不同h下所需要的最少关键字。题目给你关键字数numkey，仅需列出不同h需要的最少关键字数，当列出f(h0)<numkey而f(h0+1)>numkey时，numkey才够组成h0高度的B树，h0就是给定关键字下最高树高。
　　•树的高度最小时，每个结点包括根结点都有(m-1)个关键字，射出m条边（即充分长胖），关键字数n = f(h) = (m-1)(1+m+m^2+m^(h-1))，那么可以求得不同h下可容纳的最多关键字。题目给你关键字数numkey，仅需列出不同h支持的最多关键字数，当列出f(h0-1)<numkey而f(h0)>numkey时，h0才能容纳这么多的关键字，那么h0就是给定关键字下最低树高。
　　•实际做题时上述求最高最低树高的，现推太慢，太耗时间，现在花时间背公式考场少花时间。
　　•n个关键字的B数必定具有n-1个叶节点。因为n个关键字将(-∞,+∞)分为n+1个区间，落在这些区间上都是失败，落在分割点上都是成功的，失败结点即叶结点。
　　•408的叶节点指的是终端结点而非虚构NULL失败结点。

　　4.2 插入
　　将待插入关键字插入底部的终端结点，若插入后该终端结点的关键字超出m-1，即该结点目前拥有m个关键字。
　　若m为偶数，前m/2-1个留在结点，m/2号关键字插入到父结点，后面剩下的m/2个关键字新分配一个兄弟结点存储。
　　若m是奇数，则取中间的关键字插入到父结点，其左右各成一个结点。父结点若超了，则进行同样的操作。
　　ps:只要记住谁给父结点就行，m为偶数是刚好一半，m为奇数是刚好中间。

　　4.3删除
　　a.将待删除关键字直接删除。
　　b.被删关键字不在终端结点。用其直接前驱或后继代替它在该结点的位置即可。以c方式删除在终端结点中的直接前驱或后继。
　　c.被删关键字在终端结点。
　　　c.1 此时终端结点关键字数量满足最低要求⌈m/2⌉-1个，则无需任何操作。
　　　c.2 此时终端结点关键字数量低于最低要求⌈m/2⌉-1个，则需要看左右兄弟。若右兄弟够借，则父给它，兄给父。若左右兄弟都不够借，则父给它，它与一个兄弟合并。
　　d.最后若父结点是根结点且为空，抹去；不是根结点但关键字数低于限制，将该结点视为被删关键字的结点从b操作开始。

5.B+树

　　•广泛用于磁盘文件系统，磁盘的一个块即B+树的一个结点。所有记录指针都存在终端结点上，其余非终端结点存储的都是索引指针。这样使得一个磁盘块能够存更多的关键字索引，使B+树的阶达到最大。从而使B+树的高度最小，磁头在块之间转换的次数非常稳定，且最少。（B树也有概率很少，即待查关键字在树的前几行，但是由于B树每个关键字都附带一个很大的记录指针，树的阶明显小，树高明显更大，导致性能很多情况下是很差的。）

数据结构——图

一、图的性质

　　•图的路径的定义是边序列，也可是点边序列（正规定义）：以下默认路径是简单路径（点边序列中边不重合的路径）。
　　•一个图有n个结点，若边数大于n-1条，则一定有环（首尾结点相同的路径）（记住即可）。
　　•生成子图是一个包含原图所有结点的子图。
　　•无向图的连通：
　　　两结点连通，即两结点之间有路径。
　　　一个图是连通图，即任意两个结点有路径。
　　　连通分量 = 极大连通子图 = 包含尽可能多的结点与边的连通子图。
　　　无向图成为连通图所需边最少：构成一条线或一个生成树——n-1条。
　　　无向图成为连通图所需边最多：成为完全图——n(n-1)/2条。
　　•有向图的强连通：
　　　两结点强连通，即两结点可相互到达。
　　　一个图是强连通图，即任意两个结点可以相互到达。
　　　强连通分量 = 极大强连通子图 = 包含尽可能多的顶点与边的强连通子图。
　　　有向图成为强连通图所需边最少：构成一个环——n条。
　　　有向图成为强连通图所需边最多：成为完全图——n(n-1)条。
　　•对于连通图，有生成树，该生成树是包含其所有结点的极小连通子图（极小是边极少但仍保持连通）。非连通图有生成森林。
　　•连通分量只能少结点，生成树只能少边。而“极大”、“极小”是描述边的，因此极大连通子图指连通分量，包含全部顶点的极小连通子图指生成树。

二、图的存储

　　图的存储分为四种方法。
1.邻接矩阵存储
　　•矩阵元素为边，要么为1或0，要么为无穷（也可以为0）或一个数。
　　•矩阵元素（i,j)为1则表明结点i与结点j之间有边（无向图）或从结点i到结点j有弧（有向图）：
　　　因此一个顶点的入度（有向图）为j作为其自身而固定，i从1到|V|的元素中1或非0常数的个数——逐行求和。
　　　因此一个顶点的出度（有向图）为i作为其自身而固定，j从1到|V|的元素中1或非0常数的个数——逐列求和。
　　　因此一个顶点的度（有向/无向图）为上述相加——十字求和。
　　　总结：入行出列。
　　•存储的空间复杂度为O(n)。

2.邻接表存储及其改进存储方式
　　•一个图通过邻接表等所有涉及链表的存储方式进行存储的结果都不唯一——链表次序可不同（不用深究矩阵等顺序表为什么不能改变顺序）
　　•无向图的邻接表存储的边冗余了一倍——导致边链表结点的总数必定是偶数。
　　•任何需要遍历整个图的邻接表的操作（删除结点、建立表、有向图记录结点入度）的时间复杂度为O(|V|+2|E|)（无向图）或O(|V|+|E|)（有向图）即结点的个数，包括数组结点与链表节点。
　　•十字链表与邻接多重表是邻接表的变体。十字链表用于有向图，邻接多重表用于无向图。
　　　十字链表解决入度难寻的问题：从结点结构firstout域出发的边链表为其出度链表（一行）；从结点结构firstin域出发的链表为其入度链表（一列）。
　　　邻接多重表解决冗余问题：从结构结构的firstedge出发，每一个边结点都会告诉你下一个下一个边结点的位置，但你需要判断该往ilink走还是该往jlink走。

三、图的遍历

　　•两种方式——BFS、DFS。

1.BFS：Breadth-First-Search。外层函数使用循环从visted数组首结点开始调用BFS主体函数，循环条件是数组项为0（未访问）。BFS主体函数将传入该函数的结点入队，每次出队一个所有其未访问的邻接结点（需要visited数组支持）。入队时访问或出队时访问均可，访问后将结点对应visited项置1。
　　•采用邻接表进行BFS遍历，所有的操作无非就是对图的所有结点与所有边操作一次。时间复杂度为O(|V|+|E|)。
　　•采用邻接矩阵进行BFS遍历，所有的操作无非就是对图的所有结点入队的同时搜索其邻接结点。时间复杂度为O(|V|*|V|)。

2.DFS：Depth-First-Search。外层函数使用循环从visted数组首结点开始调用DFS主体函数，循环条件是数组项为0（未访问）。DFS主体函数先访问该结点，置该结点的visited项为1。然后对其每个visited为0的邻接结点递归调用该DFS主体函数。

　　•不需要visited数组的条件很苛刻。无向图不可能不需要。有向图只有树形才不需要。
　　•深度优先搜索可以判断一个图有没有环。这需要维护一个全局parent数组。考虑一个结点访问完后对其邻居判断是否已被访问，若未访问则访问。现在新增：若已访问，则看该邻接结点是否为其双亲结点（其直接遍历前驱），若不是，那么有环。
　　•BFS生成树的树高为图的两个结点距离的最大值。DFS生成树的树高至少为图的两个结点的最大值。

四、最小（代价）生成树算法

　　•适用：无向连通图
　　•应用：连通各点的道路最短修筑距离

1.prim算法：选一个结点加入树开始，维护各个结点加入树的最小代价数组lowCost与是否已经加入树的状态数组isJoin。对剩下每一个结点，调用两个循环。一个循环用于找到加入树代价最小的结点，然后将该结点加入树，将该结点对应的isJoin表项置1。第二个循环用于更新lowCost数组，具体操作是只要比较每个不在树中的结点到刚刚加入树的结点的距离是否小于现有值，小于就改。因此对于|V|-1个结点，每个结点消耗O(|V|+|V|)，总的时间复杂度就是O(|V|^2)。不依赖边。

2.kruskal算法：先将所有边抹除导致每个结点自成一个集合。每次选一条权值最小的边并将边关联的两个集合合并，且边的两个关联节点调用并查集的查操作证明不属于同一个集合，重复操作直到所有结点都在一个集合中。因此总计外层循环次数与边数|E|正相关，每个外层循环内部需调用并查集的查操作，其循环次数与树高log|E|正相关，故总的时间复杂度为O(|E|log|E|)。

　　•两个算法每次都不保证每次循环一定会选最短的未选边，prim要求新选结点在树之外，kruskal要求新选边的两边不同属一个集合。

五、最短路径算法

　　•适用：BFS算法适用无权图，Dijkstra算法适用正权图（多为有向图，但可以是无向），Floyd算法适用没有总权值为负的回路的图（多为有向图，但可以是无向）。
　　•应用：BFS与Dijkstra算法用于求单源最短路径；Floyd算法直接给出任意两点的最短路径。

1.BFS算法：只需修改BFS主体函数。函数一开始就初始化路径长度数组dist除了源为0其余为无穷，每个结点i出队后将其所有邻接结点j入队时将每个邻接结点j的路径长度设置为该出队结点i的路径长度+1（dist[j] = dist[i] + 1）。

2.Dijkstra算法：基于贪心算法。使用final数组表明各结点是否已找到最短路径=是否已经走过，使用dist数组存储各结点到源点的最短路径，使用path数组记录每个结点到源点路径的第一前驱。

　　a.首先初始化dist为各结点到源点的边的权值，没有边则为∞。若各结点与源点有边，path为源点所在数组下标，否则为-1。
　　b.然后，挑没走过的（final为0）且距离最短(dist最小)的路走，走完后所处的点到源点的最短路径就定了（不可能绕到其他点再回来会比此路径更短）。将目前所处的点的final置1。
　　c.最后看看从这个点出发到没有走过的邻接点（final为0）是否会更近，更近则更新dist数组与path数组中该临界点所在的项。
　　d.重复bc直到走完全部结点或final值都为1。

　　•时间复杂度分析：总共要走|V|-1个结点，每走到一个结点处，要使用循环遍历其射出的弧修改dist数组与path数组，循环次数取决于该结点的射出的弧数|E|（邻接表）或总结点数|V|（邻接矩阵）。接下来还要一个循环遍历dist数组找到没走过的最小项。因此时间复杂度为O((|V|-1)x(|V|+|E|))或O((|V|-1)x(|V|+|V|))，但化简后都是O(|V|x|V|)。

3.Floyd算法：基于动态规划。采用一个方阵A，逐步以各顶点作为中转迭代A。

　　a.首先初始化一个nxn的矩阵，每个矩阵元素A(i)(j)为结点i到结点j的距离。
　　b.以k号结点作为中转(k=0,1,2...n-1)，遍历矩阵，若结点i到结点k再到结点j的距离较原A(i)(j)小(A(i)(k)+A(k)(j) < A(i)(j))，则将A(i)(j)置为A(i)(k)+A(k)(j)。

　　•时间复杂度分析：显而易见，O(|V|x|V|x|V|)。

六、AOV网扩扑排序、AOE网关键路径算法

　　•适用：有向无环图。AOV网=有向无环图，AOE网还要求只有一个源点，只有一个汇点。

1.AOV网拓扑排序——标准法：假设已经准备好indegree数组存储每个结点的度
　　a.初始化一个栈或队列，将原所有度为0的结点如栈，初始化已经输出的结点数count为0，初始化print数组记录先后。
　　b.开始循环，循环条件为栈非空。每次循环出栈一个结点并将该结点存储进print数组最前面没被存储的位置。将该结点所有射出的弧指向的结点的度-1，遍历该结点所有射出的弧指向的结点，若发现度为0的结点，压入栈中。
　　c.最后发现count小于图的结点数，则说明有回路（回路导致没有结点度为0），输出失败信息，则输出成功信息。
　　•排序算法若给的是outdegree则得到是逆拓扑序列。
　　•若求一个AOV网的全部拓扑序列，则需要注意的是存储空间（队列或栈或别的）中有多个结点，那么出队的顺序是任意的。做题时牢牢根据算法，每个步骤写成“X出XXX...入”，或“X出”（没有入的）。每次出的时候脑海中把相应边抹除。参考王道课后题p244 16题，慢下心来。
　　•选择题问谁是给定图的拓扑序列直接从选项入手，列出所有扩扑序列需要耗费大量时间。从前至后，删除每个结点与其边，若有个结点删除时发现其前驱没有被删，就错。
　　•一个有向图有拓扑序列与该有向图没有环与该有向图可以作为AOV网三者等价。
　　•有向图有有序扩扑序列可以推出有向图的邻接矩阵为三角阵（因为有序拓扑序列任两个结点排在前面必定编号小，而扩扑序列只有排在前面的指向排在后面的弧，没有排在后面的指向排在前面的弧，则所有弧都是小编号结点指向大编号结点，则该图的邻接矩阵为三角阵）。有向图的邻接矩阵是个三角阵，可以推出该有向图必定无环，拓扑序列必定存在。

2.AOV网拓扑排序——DFS法：假设已经给出一个度为0的点
　　从该度为0的结点开始，调用DFS函数。函数主体先递归访问其所有未被访问的邻接，然后再将其自身添加进一个数组前面。如此，得到的数组的顺序就是先最后的工程，最后才是一开始先完成的工程。最后将数组倒置即为扩扑序列。
　　•若最后不倒置则得到的是逆扩扑序列。

3.AOE网关键路径
　　（结点代表的）事件的最早发生时间：当每个活动能做就做时所有前面发生的最晚结束的活动结束的时候。（不能再早了，不然就抢先了）。
　　（结点代表的）事件的最迟发生时间：当每个活动能拖就拖时所有后面发生的最早开始的活动开始的时候。（不能再晚了，不然就来不及了）。
　　（弧代表的）活动的最早开始事件=弧的源头结点的最早发生时间。
　　（弧代表的）活动的最晚开始事件=弧的指向结点的最晚发生时间-该活动耗时。
　　•关键路径上各个结点发生时间固定。最早发生时间=最晚发生时间。
　　•关键路径算法：
　　　1.先对图进行扩扑排序与逆拓扑排序。
　　　2.利用扩扑序列，从源点开始，求得每个结点的最早发生时间。
　　　3.利用逆拓扑序列，从汇点开始，求得每个结点的最晚发生时间。
　　　4.最早与最晚发生时间相等的结点构成关键路径（可能多条）。
　　•AOE网关键路径算法能判断图是否有回路全依赖扩扑排序的count。
　　•选择题求一个AOV网关键路径时用瞪眼法。