数据结构

some concepts

• 数据：所有能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。

• 数据元素：数据（集合）中的一个“个体”，数据及结构中讨论的基本单位

• 数据项：数据的不可分割的最小单位。一个数据元素可由若干个数据项组成。

• 数据类型：在一种程序设计语言中，变量所具有的数据种类。整型、浮点型、字符型等等

• 逻辑结构：数据之间的相互关系。

• 集合 结构中的数据元素除了同属于一种类型外，别无其它关系。

• 线性结构 数据元素之间一对一的关系

• 树形结构 数据元素之间一对多的关系

• 图状结构或网状结构 结构中的数据元素之间存在多对多的关系

• 物理结构/存储结构：数据在计算机中的表示。物理结构是描述数据具体在内存中的存储（如：顺序结构、链式结构、索引结构、哈希结构）等

• 在数据结构中,从逻辑上可以将其分为线性结构和非线性结构

• 数据结构的基本操作的设置的最重要的准则是,实现应用程序与存储结构的独立。实现应用程序是“逻辑结构”，存储的是“物理结构”。逻辑结构主要是对该结构操作的设定，物理结构是描述数据具体在内存中的存储（如：顺序结构、链式结构、索引结构、希哈结构）等。

• 顺序存储结构中，线性表的逻辑顺序和物理顺序总是一致的。但在链式存储结构中，线性表的逻辑顺序和物理顺序一般是不同的。

• 算法五个特性： 有穷性、确定性、可行性、输入、输出

• 算法设计要求：正确性、可读性、健壮性、高效率与低存储量需求。(好的算法)
  算法的描述有伪程序、流程图、N-S结构图等。E-R图是实体联系模型，不是程序的描述方式。

• 设计算法在执行时间时需要考虑：算法选用的规模、问题的规模

• 时间复杂度：算法的执行时间与原操作执行次数之和成正比。时间复杂度有小到大：O(1)、O(logn)、O(n)、O(nlogn)、O(n2)、O(n3)。幂次时间复杂度有小到大O(2n)、O(n!)、O(nn)
  *空间复杂度：若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间

list

线性表是一种典型的线性结构。头结点无前驱有一个后继，尾节点无后继有一个前驱。链表只能顺序查找，定位一个元素的时间为O(N)，删除一个元素的时间为O(1)

• 线性表的顺序存储结构：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。是一种随机存取的存储结构。顺序存储指内存地址是一块的，随机存取指访问时可以按下标随机访问，存储和存取是不一样的。如果是存储，则是指按顺序的，如果是存取，则是可以随机的，可以利用元素下标进行。数组比线性表速度更快的是：原地逆序、返回中间节点、选择随机节点。
  便于线性表的构造和任意元素的访问
  插入：插入新结点，之后结点后移。平均时间复杂度:O(n)
  删除：删除节点，之后结点前移。平均时间复杂度:O(n)

• 线性链表：用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址。data域是数据域，用来存放结点的值。next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。不需要事先估计存储空间大小。
  单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。同时，由于最后一个结点无后继，故结点的指针域为空，即NULL。头插法建表(逆序)、尾插法建表(顺序)。增加头结点的目的是算法实现上的方便，但增大了内存开销。
  查找：只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。
  插入：先找到表的第i-1的存储位置，然后插入。新结点先连后继，再连前驱。
  删除：首先找到ai-1的存储位置p。然后令p–>next指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间.r=p->next;p->next=r->next;delete r。
  判断一个单向链表中是否存在环的最佳方法是快慢指针。

• 静态链表：用一维数组来实现线性链表，这种用一维数组表示的线性链表，称为静态链表。静态：体现在表的容量是一定的。（数组的大小）；链表：插入与删除同前面所述的动态链表方法相同。静态链表中指针表示的是下一元素在数组中的位置。
  静态链表是用数组实现的，是顺序的存储结构，在物理地址上是连续的，而且需要预先分配大小。动态链表是用申请内存函数（C是malloc,C++是new）动态申请内存的，所以在链表的长度上没有限制。动态链表因为是动态申请内存的，所以每个节点的物理地址不连续，要通过指针来顺序访问。静态链表在插入、删除时也是通过修改指针域来实现的，与动态链表没有什么分别

• 循环链表：是一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。
  在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或p—>next是否为空，而是判断它们是否等于某一指定指针，如头指针或尾指针等。
  双向链表:在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链。双链表一般由头指针唯一确定的，将头结点和尾结点链接起来构成循环链表，并称之为双向链表。设指针p指向某一结点，则双向链表结构的对称性可用下式描述：p—>prior—>next=p=p—>next—>prior。从两个方向搜索双链表，比从一个方向搜索双链表的方差要小。
  插入：先搞定插入节点的前驱和后继，再搞定后结点的前驱，最后搞定前结点的后继。
  在有序双向链表中定位删除一个元素的平均时间复杂度为O(n)
  可以直接删除当前指针所指向的节点。而不需要像单向链表中，删除一个元素必须找到其前驱。因此在插入数据时，单向链表和双向链表操作复杂度相同，而删除数据时，双向链表的性能优于单向链表

• eg:
  确定链的起环 和 起环点
  输出倒数第K个节点
  两个无环链表的公共节点

栈和队列

栈

栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。先进后出。top= -1时为空栈，top=0只能说明栈中只有一个元素，并且元素进栈时top应该自增

顺序存储栈：顺序存储结构
链栈：链式存储结构。插入和删除操作仅限制在链头位置上进行。栈顶指针就是链表的头指针。通常不会出现栈满的情况。 不需要判断栈满但需要判断栈空。
两个栈共用静态存储空间,对头使用也存在空间溢出问题。栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是top[1]+1=top[2]。
基本操作：删除栈顶元素、判断栈是否为空以及将栈置为空栈等
对于n各元素的入栈问题，可能的出栈顺序有C(2n,n)/(n+1)个。
堆栈溢出一般是循环的递归调用、大数据结构的局部变量导致的应用.

• 进制转换
• 括号匹配的检验
• 行编辑程序
• 迷宫求解：若当前位置“可通”，则纳入路径，继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。
• 表达式求解：前缀、中缀、后缀。
  操作数之间的相对次序不变;
  运算符的相对次序不同;
  中缀式丢失了括弧信息，致使运算的次序不确定
  前缀式的运算规则为:连续出现的两个操作数和在它们之前且紧靠它们的运算符构成一个最小表达式
  后缀式的运算规则为:运算符在式中出现的顺序恰为表达式的运算顺序;每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式。
• 实现递归：多个函数嵌套调用的规则是：后调用先返回。
  不是所有的递归程序都需要栈来保护现场，比方说求阶乘的，是单向递归，直接用循环去替代从1乘到n就是结果了，另外一些需要栈保存的也可以用队列等来替代。不是所有的递归转化为非递归都要用到栈。转化为非递归主要有两种方法：对于尾递归或单向递归，可以用循环结构算法代替

队列

队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。先进先出。

• 顺序队列：顺序存储结构。当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头前一个位置，而尾指针始终指向队尾元素的实际位置

• 循环队列。在循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（MaxSize-1）时，其加1操作的结果是指向向量的下界0。除非向量空间真的被队列元素全部占用，否则不会上溢。因此，除一些简单的应用外，真正实用的顺序队列是循环队列。故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”

• 链队列：链式存储结构。限制仅在表头删除和表尾插入的单链表。显然仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。

• tips:
  设尾指针的循环链表表示队列,则入队和出队算法的时间复杂度均为O(1)。用循环链表表示队列，必定有链表的头结点，入队操作在链表尾插入，直接插入在尾指针指向的节点后面，时间复杂度是常数级的；出队操作在链表表头进行，也就是删除表头指向的节点，时间复杂度也是常数级的。
  队空条件：rear==front，但是一般需要引入新的标记来说明栈满还是栈空，比如每个位置布尔值
  队满条件：(rear+1) % QueueSize==front，其中QueueSize为循环队列的最大长度
  计算队列长度：（rear-front+QueueSize）% QueueSize
  入队：（rear+1）% QueueSize
  出队：（front+1）% QueueSize
  假设以数组A[N]为容量存放循环队列的元素,其头指针是front,当前队列有X个元素,则队列的尾指针值为(front+X mod N)

• eg:
  从尾到头打印链表
  栈和队列的互相表示
  滑动窗口的最值
  台阶问题

串

串(String)是零个或多个字符组成的有限序列。长度为零的串称为空串(Empty String)，它不包含任何字符。通常将仅由一个或多个空格组成的串称为空白串(Blank String) 注意：空串和空白串的不同，例如“ ”和“”分别表示长度为1的空白串和长度为0的空串。

• 串的表示和实现：
  定长顺序存储表示。静态存储分配的顺序表。
  堆分配存储表示。存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表
  串的链式存储结构。
  串匹配：将主串称为目标串，子串称之为模式串。蛮力法匹配。KMP算法匹配。Boyer-Moore算法匹配。
• eg：
  空格替换
  字符串另类匹配
  左旋字符串

数组和广义表

数组和广义表可看成是一种特殊的线性表，其特殊在于: 表中的元素本身也是一种线性表。内存连续。根据下标在O(1)时间读/写任何元素。
二维数组，多维数组，广义表、树、图都属于非线性结构

数组

数组的顺序存储：行优先顺序；列优先顺序。数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。

关联数组(Associative Array)，又称映射（Map）、字典（ Dictionary）是一个抽象的数据结构，它包含着类似于(键，值)的有序对。 不是线性表。

矩阵的压缩：

对称矩阵、三角矩阵：直接存储矩阵的上三角或者下三角元素。注意区分i>=j和i

• eg:
  重复数字的去除
  最大子段和

广义表

广义表（Lists，又称列表）是线性表的推广。广义表是n(n≥0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。若广义表LS（n>=1)非空，则a1是LS的表头，其余元素组成的表(a2,…an)称为LS的表尾。广义表的元素可以是广义表，也可以是原子，广义表的元素也可以为空。表尾是指除去表头后剩下的元素组成的表，表头可以为表或单元素值。所以表尾不可以是单个元素值。

• eg:
  A=（）——A是一个空表，其长度为零。
  B=（e）——表B只有一个原子e，B的长度为1。
  C=（a,(b,c,d))——表C的长度为2，两个元素分别为原子a和子表(b,c,d)。
  D=（A，B，C）——表D的长度为3，三个元素都是广义 表。显然，将子表的值代入后，则有D=(( ),(e),(a,(b,c,d)))。
  E=（a,E）——这是一个递归的表，它的长度为2，E相当于一个无限的广义表E=(a,(a,(a,(a,…)))).
• tips:
  1 广义表的元素可以是子表，而子表的元素还可以是子表。由此，广义表是一个多层次的结构，可以用图形象地表示
  2 广义表可为其它表所共享。例如在上述例4中，广义表A，B，C为D的子表，则在D中可以不必列出子表的值，而是通过子表的名称来引用。
  3
  广义表的递归性:
  广义表是0个或多个单因素或子表组成的有限序列，广义表可以是自身的子表，广义表的长度n>=0，所以可以为空表。广义表的同级元素(直属于同一个表中的各元素)具有线性关系
  广义表的表头为空，并不代表该广义表为空表。广义表()和(())不同。前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表)，对其可进行分解，得到的表头和表尾均是空表()
  已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是head(tail(head(tail(LS)))。根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。也就是说，广义表的head操作，取出的元素是什么，那么结果就是什么。但是tail操作取出的元素外必须加一个表——“（）“。tail(LS)＝((d,e,f))；head(tail(LS))=(d,e,f)；tail(head(tail(LS)))=(e,f)；head(tail(head(tail(LS))))=e。
  二维以上的数组其实是一种特殊的广义表
  在（非空）广义表中：
  1、表头head可以是原子或者一个表
  2、表尾tail一定是一个表
  3.广义表难以用顺序存储结构
  4.广义表可以是一个多层次的结构

树和二叉树

一种非线性结构。树是递归结构，在树的定义中又用到了树的概念。

基本术语：

树结点：包含一个数据元素及若干指向子树的分支；
孩子结点：结点的子树的根称为该结点的孩子；
双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；
兄弟结点：同一双亲的孩子结点；
堂兄结点：同一层上结点；
结点层次：根结点的层定义为1；根的孩子为第二层结点，依此类推；
树的高（深）度：树中最大的结点层
结点的度：结点子树的个数
树的度： 树中最大的结点度。
叶子结点：也叫终端结点，是度为0的结点；
分枝结点：度不为0的结点（非终端结点）；
森林：互不相交的树集合；
有序树：子树有序的树，如：家族树；
无序树：不考虑子树的顺序；
二叉树
二叉树可以为空。二叉树结点的子树要区分左子树和右子树，即使只有一棵子树也要进行区分，说明它是左子树，还是右子树。这是二叉树与树的最主要的差别。注意区分：二叉树、二叉查找树/二叉排序树/二叉搜索树、二叉平衡(查找)树

二叉平衡树肯定是一颗二叉排序树。堆不是一颗二叉平衡树。

二叉树与树是不同的，二叉树不等价于分支树最多为二的有序树。当一个结点只包含一个子节点时，对于有序树并无左右孩子之分，而对于二叉树来说依然有左右孩子之分，所以二叉树与树是两种不同的结构。

性质：

在二叉树的第 i 层上至多有2i-1个结点。
深度为 k 的二叉树上至多含 2k-1 个结点（k≥1）
对任何一棵二叉树，若它含有n0个叶子结点、n2个度为 2 的结点，则必存在关系式：n0= n2+1。
具有 n 个结点的完全二叉树的深度为⎣log2 n⎦+1 。
n个结点的二叉树中，完全二叉树具有最小的路径长度。
如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i（1<=i<=n),有：
如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲的编号是 i/2(整除）。
如果2i>n，无左孩子；否则，其左孩子是结点2i。
如果2i＋1>n，则结点i无右孩子；否则，其右孩子是结点2i＋1。
二叉树的存储结构

顺序存储结构：仅仅适用于满或完全二叉树，结点之间的层次关系由性质5确定。
二叉链表法：每个节点存储左子树和右子树。三叉链表：左子树、右子树、父节点，总的指针是n+2
在有n个结点的二叉链表中，值为非空的链域的个数为n-1。在有N个结点的二叉链表中必定有2N个链域。除根结点外，其余N-1个结点都有一个父结点。所以，一共有N-1个非空链域，其余2N-(N-1)=N+1个为空链域。
二叉链存储法也叫孩子兄弟法，左指针指向左孩子，右指针指向右兄弟。而中序遍历的顺序是左孩子，根，右孩子。这种遍历顺序与存储结构不同，因此需要堆栈保存中间结果。而中序遍历检索二叉树时，由于其存储结构跟遍历顺序相符，因此不需要用堆栈。
遍历二叉树和线索二叉树
遍历二叉树：使得每一个结点均被访问一次，而且仅被访问一次。非递归的遍历实现要利用栈。

先序遍历DLR：根节点->左子树->右子树
中序遍历LDR：左子树->根节点->右子树。必须要有中序遍历才能得到一棵二叉树的正确顺序
后续遍历LRD：左子树->右子树->根节点。需要栈的支持。
层次遍历：用一维数组存储二叉树时,总是以层次遍历的顺序存储结点。层次遍历应该借助队列。
线索二叉树：对二叉树所有结点做某种处理可在遍历过程中实现；检索（查找）二叉树某个结点，可通过遍历实现；如果能将二叉树线索化，就可以简化遍历算法，提高遍历速度，目的是加快查找结点的前驱或后继的速度。

如何线索化？以中序遍历为例，若能将中序序列中每个结点前趋、后继信息保存起来，以后再遍历二叉树时就可以根据所保存的结点前趋、后继信息对二叉树进行遍历。对于二叉树的线索化，实质上就是遍历一次二叉树，只是在遍历的过程中，检查当前结点左，右指针域是否为空，若为空，将它们改为指向前驱结点或后继结点的线索。前驱就是在这一点之前走过的点，不是下一将要去往的点。

加上结点前趋后继信息（结索）的二叉树称为线索二叉树。n个结点的线索二叉树上每个结点有2个指针域（指向左孩子和右孩子），总共有2n个指针域；一个n个结点的树有n-1条边，那么空指针域= 2n - (n-1) = n + 1，即线索数为n+1。指针域tag为0，存放孩子指针，为1，存放前驱/后继节点指针。

线索树下结点x的前驱与后继查找：设结点x相应的左（右）标志是线索标志，则lchild(rchild)就是前驱(后继），否则：

LDR–前驱：左子树中最靠右边的结点；后继：右子树中最靠左边的结点
LRD–前驱：右子树的根，若无右子树，为左子树跟。后继：x是根，后继是空；x是双亲的右孩子、x是双亲的左孩子，但双亲无右孩子，双亲是后继；x是双亲的左孩子，双亲有右孩子，双亲右子树中最左的叶子是后继
DLR–对称于LRD线索树—将LRD中所有左右互换，前驱与后继互换，得到DLR的方法。
为简化线索链表的遍历算法，仿照线性链表，为线索链表加上一头结点，约定：
头结点的lchild域：存放线索链表的根结点指针；
头结点的rchild域: 中序序列最后一个结点的指针；
中序序列第一结点lchild域指向头结点;
中序序列最后一个结点的rchild域指向头结点;
中序遍历的线索二叉树以及线索二叉树链表示意图

一棵左右子树均不空的二叉树在前序线索化后,其中空的链域的个数是1。前序和后续线索化后空链域个数都是1，中序是2。二叉树在线索化后，仍不能有效求解的问题是前序求前序先驱，后序求后序后继。

中序遍历的顺序为：左、根、右，所以对于每一非空的线索，左子树结点的后继为根结点，右子树结点的前驱为根结点，再递归的执行上面的过程，可得非空线索均指向其祖先结点。在中序线索二叉树中,每一非空的线索均指向其祖先结点。

在二叉树上加上结点前趋、后继线索后，可利用线索对二叉树进行遍历,此时，不需栈，也不需递归。基本步骤：

p=T->lchild; p指向线索链表的根结点；
若线索链表非空，循环：
循环，顺着p左孩子指针找到最左下结点；访问之；
若p所指结点的右孩子域为线索，p的右孩子结点即为后继结点循环： p=p->rchild； 并访问p所指结点；（在此循环中，顺着后继线索访问二叉树中的结点）
一旦线索“中断”，p所指结点的右孩子域为右孩子指针，p=p->rchild，使 p指向右孩子结点；
树和森林
树的存储结构：

双亲表示法
孩子表示法
利用图表示树
孩子兄弟表示法（二叉树表示法）：链表中每个结点的两指针域分别指向其第一个孩子结点和下一个兄弟结点
将树转化成二叉树：右子树一定为空

加线：在兄弟之间加一连线
抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系
旋转：以树的根结点为轴心，将整树顺时针转45°
森林转换成二叉树：

将各棵树分别转换成二叉树
将每棵树的根结点用线相连
以第一棵树根结点为二叉树的根
树与转换后的二叉树的关系：转换后的二叉树的先序对应树的先序遍历；转换后的二叉树的中序对应树的后序遍历

哈弗曼树/霍夫曼树

一些概念

路径：从一个祖先结点到子孙结点之间的分支构成这两个结点间的路径；
路径长度：路径上的分支数目称为路径长度；
树的路径长度：从根到每个结点的路径长度之和。
结点的权：根据应用的需要可以给树的结点赋权值；
结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积；
树的带权路径长度=树中所有叶子结点的带权路径之和；通常记作 WPL=∑wi×li
哈夫曼树：假设有n个权值(w1, w2, … , wn)，构造有n个叶子结点的二叉树，每个叶子结点有一个 wi作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。最优二叉树。
前缀码的定义：在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀。霍夫曼编码就是前缀码，可用于快速判断霍夫曼编码是否正确。霍夫曼树是满二叉树，若有n个节点，则共有(n+1)/2个码子

给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为霍夫曼树(Huffman Tree)。霍夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

假设哈夫曼树是二叉的话，则度为0的结点个数为N，度为2的结点个数为N-1，则结点总数为2N-1。哈夫曼树的结点个数必为奇数。

哈夫曼树不一定是完全二叉树，但一定是最优二叉树。

若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为[(n-1)/(m-1)]。边的数目等于度。

图

遍历与回溯

图搜索->形成搜索树

穷举法。
贪心法。多步决策，每步选择使得构成一个问题的可能解，同时满足目标函数。
回溯法。根据题意，选取度量标准，然后将可能的选择方法按度量标准所要求顺序排好，每次处理一个量，得到该意义下的最优解的分解处理。
图
无向图

回路或环：第一个顶点和最后一个顶点相同的路径。
简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路
连通：顶点v至v’ 之间有路径存在
连通图：无向图图 G 的任意两点之间都是连通的，则称G是连通图。
连通分量：极大连通子图，子图中包含的顶点个数极大
所有顶点度的和必须为偶数
有向图：

回路或环：第一个顶点和最后一个顶点相同的路径。
简单回路或简单环：除第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路。
连通：顶点v至v’之间有路径存在
强连通图：有向图G的任意两点之间都是连通的，则称G是强连通图。各个顶点间均可达。
强连通分量：极大连通子图
有向图顶点的度是顶点的入度与出度之和。邻接矩阵中第V行中的1的个数是V的出度

生成树：极小连通子图。包含图的所有n个结点，但只含图的n-1条边。在生成树中添加一条边之后，必定会形成回路或环。

完全图：有 n(n-1)/2 条边的无向图。其中n是结点个数。必定是连通图。
有向完全图：有n(n-1)条边的有向图。其中n是结点个数。每两个顶点之间都有两条方向相反的边连接的图。
一个无向图 G=(V,E) 是连通的，那么边的数目大于等于顶点的数目减一：|E|>=|V|-1，而反之不成立。如果 G=(V,E) 是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目：|E|>=|V|，而反之不成立。没有回路的无向图是连通的当且仅当它是树，即等价于：|E|=|V|-1。
图的存储形式
邻接矩阵和加权邻接矩阵
无权有向图：出度: i行之和；入度: j列之和。
无权无向图：i结点的度: i行或i列之和。
加权邻接矩阵：相连为w，不相连为∞
邻接表
用顶点数组表、边（弧）表表示该有向图或无向图
顶点数组表：用数组存放所有的顶点。数组大小为图顶点数n
边表（边结点表）：每条边用一个结点进行表示。同一个结点的所有的边形成它的边结点单链表。
n个顶点的无向图的邻接表最多有n(n-1)个边表结点。有n个顶点的无向图最多有n(n-1)/2条边，此时为完全无向图，而在邻接表中每条边存储两次，所以有n(n-1)个结点
图的遍历
深度优先搜索利用栈，广度优先搜索利用队列

求一条从顶点i到顶点s的简单路径–深搜。求两个顶点之间的一条长度最短的路径–广搜。当各边上的权值均相等时,BFS算法可用来解决单源最短路径问题。

生成树和最小生成树
每次遍历一个连通图将图的边分成遍历所经过的边和没有经过的边两部分，将遍历经过的边同图的顶点构成一个子图，该子图称为生成树。因此有DFS生成树和BFS生成树。

生成树是连通图的极小子图，有n个顶点的连通图的生成树必定有n-1条边,在生成树中任意增加一条边，必定产生回路。若砍去它的一条边，就会把生成树变成非连通子图

最小生成树：生成树中边的权值(代价)之和最小的树。最小生成树问题是构造连通网的最小代价生成树。

Kruskal算法：令最小生成树集合T初始状态为空，在有n个顶点的图中选取代价最小的边并从图中删去。若该边加到T中有回路则丢弃，否则留在T中；依此类推，直至T中有n-1条边为止。

Prim算法、Kruskal算法和Dijkstra算法均属于贪心算法。

Dijkstra算法解决的是带权重的有向图上单源最短路径问题，该算法要求所有边的权重都为非负值。
Dijkstra算法解决了从某个原点到其余各顶点的最短路径问题，由循环嵌套可知该算法的时间复杂度为O(NN)。若要求任一顶点到其余所有顶点的最短路径，一个比较简单的方法是对每个顶点当做源点运行一次该算法，等于在原有算法的基础上，再来一次循环，此时整个算法的复杂度就变成了O(NN*N)。
Bellman-Ford算法解决的是一般情况下的单源最短路径问题，在这里，边的权重可以为负值。该算法返回一个布尔值，以表明是否存在一个从源节点可以到达的权重为负值的环路。如果存在这样一个环路，算法将告诉我们不存在解决方案。如果没有这种环路存在，算法将给出最短路径和它们的权重。
双连通图和关节点
若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。

若连通图中的某个顶点和其相关联的边被删去之后，该连通图被分割成两个或两个以上的连通分量，则称此顶点为关节点。

没有关节点的连通图为双连通图

若生成树的根结点，有两个或两个以上的分支，则此顶点(生成树的根)必为关节点；
对生成树上的任意一个非叶“顶点”，若其某棵子树中的所有“顶点”没有和其祖先相通的回边，则该“顶点”必为关节点。
有向无环图及其应用
拓扑排序。在用邻接表表示图时,对有n个顶点和e条弧的有向图而言时间复杂度为O(n+e)。一个有向图能被拓扑排序的充要条件就是它是一个有向无环图。拓扑序列唯一不能唯一确定有向图。

AOV网(Activity On Vertex)：用顶点表示活动，边表示活动的优先关系的有向图称为AOV网。AOV网中不允许有回路，这意味着某项活动以自己为先决条件。

拓扑有序序列：把AOV网络中各顶点按照它们相互之间的优先关系排列一个线性序列的过程。若vi是vj前驱，则vi一定在vj之前；对于没有优先关系的点，顺序任意。

拓扑排序：对AOV网络中顶点构造拓扑有序序列的过程。方法：

在有向图中选一个没有前驱的顶点且输出之
从图中删除该顶点和所有以它为尾的弧
重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止(此时说明图中有环）
采用深度优先搜索或拓扑排序算法可以判断出一个有向图中是否有环(回路).深度优先搜索只要在其中记录下搜索的节点数n，当n大于图中节点数时退出，并可以得出有回路。若有回路，则拓扑排序访问不到图中所有的节点，所以也可以得出回路。广度优先搜索过程中如果访问到一个已经访问过的节点，可能是多个节点指向这个节点，不一定是存在环。

算法描述：

把邻接表中入度为0的顶点依此进栈
若栈不空，则
栈顶元素vj退栈并输出；
在邻接表中查找vj的直接后继vk，把vk的入度减1；若vk的入度为0则进栈
若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕。
AOE网：带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。在工程上常用来表示工程进度计划。

一些定义：

事件的最早发生时间（ve(j)）：从源点到j结点的最长的路径。意味着事件最早能够发生的时间。
事件的最迟发生时间（vl(j)）：不影响工程的如期完工，事件j必须发生的时间。
活动ai由弧

！