这世界上最痛苦的事情就是，老师摆了，但是学生摆不了。

0 绪论

所谓数据结构，就是数据+关系

我们定义一个抽象数据结构ADT，也就是定义一个三元组：

• D 数据
• S 关系
• P 操作

纠错可以用assert.h中函数来判断。

我们的目的是高效但空间小；算法和结构的选择取决于规模和具体问题。这一点会在以后看到。

其中有趣的是时间复杂度分析和空间复杂度。

1 线性表

1.1 没什么营养的介绍

线性表的结构很简单，和Peano公理定义的自然数一样。

• 数据就是数据
• 关系就是前驱和后继。这是一种线性的关系。

链表的定义具有很大的人为性。也就是说，由于我们一般不在表头存储数据，所以链表的定义长度取决于其内包含的数据节点数量。不过，就考试而言，考查这种知识的行为是愚蠢的。

具体实现有三种，一种是用下标访问的数组；一种是利用结构体指针的链式存储；最后一种是利用结构体，并将数组下标当作指针的静态链表。

顺序表有诸多缺点，比如每次删除就要整个移位。可以用静态链表解决；另外，链式存储的访问只能一个一个来，显得过于麻烦。

对于链式存储，有双向、循环等方式实现方便的遍历。但使用的核心必须要熟知指针的切换。

链表的主要Bug终归还是指针的Bug，尤其是NULL的理解和使用，以及终结情况的选取。

1.2 链表、以C++类为例

由C++没有专门设立链表类，但是有一个十分相似的向量vector

在此之前，我们先介绍一下C++STL:

STL 是“Standard Template Library”的缩写，中文译为“标准模板库”。STL 是 C++ 标准库的一部分，不用单独安装。

C++标准模板库的核心包括以下三个组件：

为了使用向量，我们需要#include<vector>

直接打开这个库看看。。。它的内容不多，但是库是真的多。具体操作看菜鸟-向量

或者在网上搜索即可。

但是，向量是作为一个动态的数组，分配了一块连续的地址空间，访问效率高但插入删除效率低。此外，还有一个数据结构为列表list：

list(列表)和vector(向量)的区别：

1. 向量为一个动态的数组（单向），列表是由双向链表组成的（双向）
2. vector为存储的对象分配一块连续的地址空间，随机访问效率很高。但是插入和删除需要移动数据，故效率较低
3. list存储空间是不连续的，随机访问需要遍历整个链表，因此效率比vector低。但是在list插入元素，尤其是首尾插入，效率很高，只要改变元素的指针。
4. vector中迭代器iterator使用后就释放，而list的迭代器在使用后还可以继续使用。
5. list比vector占用的内存多。

区别来源：CSDN

具体操作看菜鸟-列表

1.3 OJ例题

。。。没有什么好说的，最难的题在于输入输出以及特殊情况，和链表结构没什么关系。

但链表最重要的是插入删除时指针的调整。

1.4 应用

一个很有意思的排序—基数排序可以基于链表设计。

Radix sort

2 栈

2.1 没什么营养的介绍

栈可以理解成操作受限的线性表。

让线性表只能从一端进出，就成了栈。

当然也可以用连续空间动态分配+栈顶指针栈底指针确定范围。

而链式存储则一般用头节点作为栈顶，并加入一个节点作为栈底。

一般来说，用数组作为存储方式可能更加简介，而且会更加方便。

这里又有一些小细节，比如栈顶指针。它指向刚来的元素位置，还是空位置。

2.2 C++栈

见菜鸟-栈

2.3 OJ例题

2.3.1 逆波兰表达式

这里需要说一下逆波兰表达式，这是栈运用的一个极好的例子，虽然对树来说也挺不错的。

计算核心是比较运算符号的优先级。栈顶符号优先级低则当前符号压入栈；否则就弹栈，直到出现一个比当前符号优先级低的。

还有一点需要注意的是，右括号需要单独考虑。或者说，有着最高的优先级。但由于右括号不会入栈，所以不如单独考虑。

#include<cstdio>

char res[30000];
char buff[30000];

int index = 0;
int pri(char);
char pop();
void push(char);
char top(); 

int main()
{
	buff[index] = '#';//top指向当前，不指向下一个空位置 
	int i = 0;
	char c;
	
	while((c=getchar()) != '\n')
	{
		if(pri(c) == 0)//符号直接压入 
		{
			res[i] = c;
			i++;
		}else{
			if(c=='(')//若为左括号，则直接入栈 
			{
				push(c); 
			}else if(c == ')')//若为右括号，则弹出直到左括号
			{
				while (top() != '(')
                {
                    res[i++] = pop(); 
                }
                pop();//删掉左括号 
			}else{//最后是运算符的情况： 
				while (top() != '#' && pri(c) <= pri(top()))   //栈顶优先级大于等于当前运算符，则输出；而且栈非空 
                {
                    res[i++]= pop();
                }
                push(c);
			} 
		}
	}
	
	while((c = pop()) != '#')
	{
		res[i++] = c;
	}
	
	printf("%s",res);
	return 0;
}

int pri(char c)
{
	switch(c)
	{
		case '(':
			return 1;
		case '+':
			return 2;
		case '-':
			return 2;
		case '*':
			return 5;
		case '/':
			return 5;
		case '#':
			return -1;
		default:
			return 0;
	}
}

char pop()
{
	char ch = buff[index];
	if(ch == '#')
	{
		return ch;
	}else{
		buff[index] = 0;
		index--; 
		return ch;
	}
}

char top()
{
	return buff[index];
}

void push(char cin)
{
	buff[++index] = cin;
}

2.3.2 递归调用

尾递归参见点击

汉诺塔是一个不错的例子。

void hanoi(int n, char from, char assist, char to)

如果只有一个，那么就$a\to c$

否则，我们考虑hanoi(n-1,a,c,b)，将$n-1$个盘子移到b，然后将第$n$个盘子移到c。

最后只需要hanoi(n-1,b,a,c)，借用a柱，将$n-1$个盘子移到c柱子。

3 队列

3.1 没什么营养的介绍

和栈相反，队列是一种FIFO的数据结构。不过也可以看作是阉割版链表。

3.2 C++

它给出了三种实现：

• 队列Queue
• 双端队列Deque
• 优先队列priority_queue

队列用链表实现很麻烦，虽然十分贴合其本质，但是用数组实现的循环列表却更加节省空间，且方便。

循环链表一个重要的地方就是模算术以及判满判空。

3.3 应用

队列的一个重要应用是离散事件模拟。不过一个更重要的事情是BFS的遍历需要它。

不过从另一个角度来说，BFS中使用的队列遍历不过是队列遍历的一个应用。

队列遍历还有很多应用场景。比如划分子集问题，或者说日程安排问题。

• 比赛项目：A={1, 2, 3, 4, 5, 6, 7, 8, 9}
• 运动员人数：5
• 运动员参加项目：R={(1,2,3),(4,5,6),(7,8,9),(1,4,7),(2,5,8),(3,6,9)}

可构建冲突矩阵：

大致算法过程如下：

入队列：

• M:123456789

选1开始划分，遍历M：

• M:23456789
• G:1
• res:1

选出和1不冲突的项目：

• M:2347
• G:5689
• res:1

选出和5不冲突的项目，若冲突，则返回原队列M：

• M:234768
• G:9
• res:15

选出一个159，以2作为下一个，开始遍历：

• M:34768
• G:2
• res:159/2

选出一个159，以2作为下一个，开始遍历：

• M:38
• G:476
• res:159/2

选择4，继续，发现均冲突：

• M:3876
• G:
• res:159/24

选择3，开始选下一组解：

• M:876
• G:3

• res:159/24/3

• M:6
• G:87

• res:159/24/3

• M:67
• G:

• res:159/24/38

• M:7
• G:6
• res:159/24/38/6

事实上，你会发现，最后四个数字，无论是37，68还是38，67都是可以接受的。

这时候得看题目有没有什么顺序要求。否则多解是很可能的。

排队问题直接开摆，学个屁。

4 数组

4.1 简单认识

这里，数组作为一个只是用来存储的单元，如果不考虑删增其内部信息，那么顺式存储完全够用了。

但我们还需要考虑各行各列的实际指代，说到这里，我鄙视所有用a[3][3]这类行列一样大小的多维数组声明讲解的教材。

#include<stdio.h>
int Tarray[2][3][4] = {
    {
        {1,2,3,4},
        {11,12,13,14},
        {21,22,23,24},
    },
    {
        {101,102,103,104},
        {111,112,113,114},
        {121,122,123,124},
    }
};

int main()
{
    int i=0;
    while(i<24)
    {
        printf("%2d:%4d\n",i,*(**Tarray+i));
        ++i; 
    }
    return 0;
}

上述代码输出结果如下：

0:   1
1:   2
2:   3
3:   4
4:  11
5:  12
6:  13
7:  14
8:  21
9:  22
10:  23
11:  24
12: 101
13: 102
14: 103
15: 104
16: 111
17: 112
18: 113
19: 114
20: 121
21: 122
22: 123
23: 124

这说明了，在数组声明中，优先考虑前面的下标。

比如int array[a][b][c][d][e]，它表示这个数组首先有a个单元，对每个单元，其中含有b个子单元，每个子单元中又存在c个子子单元…如此。

到这里就需要考虑它在内存中的实际存储。在C语言中，它是将后面的下标存放完，再存放前一个下标。结合上题输出和初始化理解即可。

4.2 区区指针

从上例的输出中，我们可以清晰地看出，Tarray就是一个指针。但是这个指针指向的内容很值得讨论，这涉及到C语言中的复杂声明，尽管这种复杂声明不是正常人会写出来的，但是谨防万一，还是需要了解一番。

int Tarray[2][3][4] = {
    {
        {1,2,3,4},
        {11,12,13,14},
        {21,22,23,24},
    },
    {
        {101,102,103,104},
        {111,112,113,114},
        {121,122,123,124},
    }
};

int main()
{
    printf("%p %p %p %p\n",Tarray, Tarray[0], Tarray[0][0], Tarray[0][0][0]);
    printf("%p %p %p %p\n",Tarray,*Tarray,**Tarray,***Tarray);
    return 0;
}
#output
0000000000403040 0000000000403040 0000000000403040 0000000000000001
0000000000403040 0000000000403040 0000000000403040 0000000000000001

我们可以看到，除了最后一项直接按地址格式输出了第一个元素外，其余的地址都是相同的。

但实际上，Tarray[0][0]是指向{1,2,3,4}中的，它指向的对象是一个长度为4，元素为int类型的数组。而Tarray[0]是指向

{
    {1,2,3,4},
    {11,12,13,14},
    {21,22,23,24},
},

的，输出也只是输出其中首个元素{1,2,3,4}的首地址罢了。所以多维数组的本质就是一个数组指针。我们可以直接从堆中申请内存证明这一切。

代码来源

int main()
{
    int(*p)[2];
    p = (int (*)[2])malloc(sizeof(int) * 6);
    for (int i = 0; i < 3 ; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            p[i][j] = i + j;
        }
    }
    
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            printf("%d\n", p[i][j]);
        }
    }
    free(p);
    return 0;
}

这里也可以谈一下int(*p)[2];和int*p[2];的区别。也许你不一定需要会这种（。。）写法，但是还是需要了解一下。

在C语法分析器中，前者会先处理括号中的指针，从而得到这是一个指针，它指向一个长度为2的整型数组；而后者是一个长度为2的数组，数组中每一个元素都是指向整型的指针。

这是因为[]的优先级高于*。

进一步考虑这两种声明方式的区别:

• int(*p)[2];代表了一个指向数组的指针，那么我声明n个这样的指针，就相当于声明了一个n*2的整型数组。
• int*p[2];代表了一个包含两个指针的数组，其中每个指针都可以指向一个int类型的数组，相当于声明了一个确定行数的二维数组，它的行数是2。

再次回顾之前的代码：

int(*p)[2];

声明一个指向数组的指针；

p = (int (*)[2])malloc(sizeof(int) * 6);

给这个指针6个int的空间，就可以取三行了。

for (int i = 0; i < 3 ; i++){
    for(int j = 0; j < 2; j++){
        p[i][j] = i + j;
    }
}

以上，就勉勉强强完成了对数组的解释。

5 特殊数组–矩阵的存储

矩阵是十分重要的，一般我们用二维数组来表示矩阵。这里我们不讨论矩阵的高效乘法，只讨论部分特殊矩阵的存储。

5.1 对角矩阵

将$n^2$压缩成$\frac{n(n+1)}{2}$，对于上三角矩阵也可以这么做。

没有什么需要记的。唯一需要沟通好的一点是，以行序为主序还是列序。

本质上，类似于此的，有规律的多0矩阵都可以按照约定的方式来存储。

这种约定并不是普适的，所以一定要沟通好。

5.2 稀疏矩阵

对于一类不怎么有规律的多0矩阵。我们称为稀疏矩阵好了。大概衡量程度是0.05：

所以除了存储元素外，还需要存储它的位置。

一个很直观的方式就是开一个结构体数组，其方式很直观，不赘叙。

这里我们考虑一下转置的事情，大致就是，行列值互换再加一个重排就行。(防止可能的运算，必须要考虑顺序。)

这里需要对每一列遍历，所以实际上十分慢，大概到$O(n^3)$了，如果非零元没那么少的话。

接下来我们尝试加快转置的速度。(虽然感觉方向有一点歪)

第二种快速转置算法：

核心思想是预处理，只需要预先求得原矩阵中每一列的第一个非零元位置，那么转置扫描时，就可以直接把原数组每一列放到新数组的制定范围内。(牢记，行列都是结构体，我们操作的是结构体指针。)

我们加入两个辅助数组即可：

• num[col]：记录矩阵转置前各列（即转置矩阵各行）非零元素个数；
• cpot[col]：记录各列非零元素在转置三元组表中开始存放位置。

其实本质上，最后用到的只有cpot数组。(这个名字页很奇怪)

这样的话，本质上当矩阵足够稀疏，只需要$O(m+n)$。稍微大一点，就是正常的时间复杂度，这可以接受。

随着快速转置算法的学习，我们发现，这个cpot可以快速告诉我们每一行矩阵的起始位置，这用起来就很方便，所以有了第二中稍微聪明一点的方式：

行逻辑连接的顺序表

这样就可以很方便的写出矩阵相乘，需要注意行列必须合法，以及0元的排除。而且使用了行逻辑存储，就很方便。

当然，看了这么久，我们发现，数组一到变换存储结构就十分麻烦，时间复杂度蹭蹭往上涨。。不如我们简单一点，采用链表来存储。

另一种更大胆一点的链表存储方式是：十字链表

这也是个麻烦的构造。加两个指针就可以了。至于行列数，可以再构建一个结构体+malloc，不过得先输入一个行列数。

其插入和单链表的插入基本一致。但插入了行后，还需要考虑列的连接。

说实话，二维数组不香吗？

6 广义表

和树差不多。

广义表的核心在于两种定义方式，作为一种递归定义的结构体：

6.1 Head or Tail?

这里十分有必要说一下Head和Tail两种操作：

• Head 取广义表的表头，所谓表头就是，非空广义表的第一个元素；
• Tail是取表尾，所谓表尾，就是除去第一个元素后，剩下的元素所构成的列表。

这是递归运算的核心。

6.2 广义表的关系

这里有两种构建方法。

typedef enum{ATOM,LIST} Tag;

typedef struct GLNode{
    Tag tag;
    union{
        int atom;
        struct {
            struct GLNode *hp, *tp;//一个指向表头，一个指向下一个表。
        }ptr;
    };
}

typedef enum{ATOM,LIST} Tag;

typedef struct GLNode{
    Tag tag;
    union{
        int atom;
        struct GLNode *hp;//一个指向表头
    };
    struct GLNode *tp;//一个指向下一个表。
}

这两种方式会连接起不同的结构。

前者以原子为终点，后者则是以NULL指针为中点。

下面给出广义表删除的递归算法，以第一种为例。（感谢室友提供的输入输出函数）

#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef struct GLNode{
	int tag;
	union{
		char atom;
		struct{
			struct GLNode *hp,*tp;
		}ptr;
	};
}*Glist;
void serve(string &str,string &hstr);
void CreateGlist(Glist &L,string s);
void PrintGlist(Glist &L,int htcheck);
Glist Del(Glist,char);

int main()
{
	Glist G,GP;
	string input;
	char todele;
	cin>>input;
	cin>>todele;
	CreateGlist(G,input);
	G = Del(G, todele);
	if(G!= NULL && G->ptr.hp)
		PrintGlist(G,1);
	else
		cout<<-1;
}
void CreateGlist(Glist &L,string s)
{
	Glist p,q;
	if (!s.compare("()"))
		L = NULL;
	else
	{
		L = (Glist)malloc(sizeof(GLNode));
		if (s.length() == 1)
		{
			L->tag = 0;
			L->atom = s[0];
		}
		else
		{
			L->tag = 1;
			p = L;
			string sub,hsub;
			sub = s.substr(1,s.length() - 2);
			do{
				serve(sub,hsub);
				CreateGlist(p->ptr.hp,hsub);
				q = p;
				if (sub.length() != 0)
				{
					p = (Glist)malloc(sizeof(GLNode));
					p->tag = 1;
					q->ptr.tp = p;
				}
			}while(sub.length() != 0);
			q->ptr.tp = NULL;
		}
	}
	return;
}
void serve(string &str,string &hstr)
{
	int n = str.length(), i = 0, k = 0;
	string ch;
	do{
		ch = str.substr(i,1);
		if (ch == "(")	++k;
		else if (ch == ")")	 --k;
		++i; 
	}while(i < n && (ch != "," || k != 0));
	if (i < n)
	{
		hstr = str.substr(0,i-1);
		str = str.substr(i,n-i);
	}
	else
	{
		hstr = str;
		str = "";
	}
}

Glist Del(Glist L, char c)
{
	if(L == NULL) return NULL;
	
	switch(L->tag)
	{
		case 0:
			if(L->atom == c) return NULL;
			else return L;
			break;
		case 1:
			Glist p = Del(L->ptr.tp, c);
			L->ptr.tp = p;
			L->ptr.hp = Del(L->ptr.hp, c);
			if(L->ptr.hp == NULL) return p;
			break;
	}
	return L;
}

void PrintGlist(Glist &L,int htcheck)	//htcheck用来判断此时输出的是头结点还是尾结点，若为尾结点则不需要输出构造尾结点时多了的一层（） 
{										//htcheck == 1代表此时是头结点，htcheck == 0代表此时是尾结点 
	if (!L)
		return;
	if (L->tag == 0)
	{
		cout<<L->atom;
		return;
	}
	else
	{
		if (htcheck)
			cout<<"(";
		PrintGlist(L->ptr.hp,1);
		if (L->ptr.tp != NULL)
		{
			cout<<",";
			PrintGlist(L->ptr.tp,0);
		}
	}
	if (htcheck)
		cout<<")";
	return;
}

7 定义：一棵树是什么

7.1 定义

树就是有一个根节点root的图，然后把根节点去掉后，就可以划分成不同的树。如此递归。

可以用树状图或者套圈圈来直观表示。

7.2 行业黑话

• 度，结点的度就是子树数量；树的度就是对其内节点取一个上确界。
• 叶子节点，度为0；
• 分支节点，度不为0；
• 孩子，双亲，兄弟，堂兄弟。
• 层次，规定根为第一层
• 深度，最大层次。
• 满m次树，每一层都是满的
• 完全m次数， 和满m次树的层序一致。
  • 左枝>右枝；且叶子只在最后两层。

7.3 性质

• 树中节点数等于所有结点度数+1
• 具有n个节点的m次数最小高度为$1+\lfloor\log_{m}{n}\rfloor$
• $n_0=n_2+1$
• 编号后有

8 二叉树是什么树

m=2的树。

8.1 性质

• $n_0=n_2+1$
• 编号后有：
  • 除根外，$\lfloor i/2\rfloor$为其双亲节点。
  • $2i>n$，则该节点无左孩子，否则2i必然其左孩子
  • 2i+1为右

8.2 实际存储

• 顺式存储：就是地址作编号；
• 链式存储：
  • 二叉链表：找父节点麻烦；
  • 三叉链表；
  • 双亲链表：找父节点舒服；
  • 线索链表：遍历方便，且利用了空闲的叶子指针域。

8.3 二叉树的遍历

• 先序：先访问根，DLR；直观看起来是第一次到便访问。
• 中序：中间访问根，LDR；值得注意的是，除二叉树外，其他树难以定义中序；直观看是第二次到才访问。
• 后序：最后访问根，直观来看是一个剪枝的过程。

这些访问都是递归去做，所以十分方便。但是非递归的话，就必须要人为引入一个栈作为中间存储。

9 多少棵树才算森林

事实上，森林是多于0棵树的不交并。另一方面，在不计根节点的情况下，树和森林是等价的。

9.1 树的存储

由于不知道m的具体值，m个指针太过于浪费；

所以采用很多奇怪的方式，比如索引分层+指针指向子女；

又或者孩子兄弟表示法，也是一种二叉链表，换一种解释就可以在形式上等同于二叉树。

这里可以看出，根的右子树必然是欠缺的。森林向树的转化就是靠这一步。

9.2 树和森林的转换

树->森林:根与右子树分离，转正即可。

森林->树：

• 先转换成二叉树，然后用右子树连接。

9.3 树的遍历

先根，和等价二叉树一致

后根，和等价二叉树中根一致。

9.4 森林的遍历

先序，递归

中序，从左到右

10 Huffman树

挑俩小的合并，递归。

11 图的基本概念

11.1 定义

• 图 G = (V,E)
  • V是顶点集
  • E是边集

根据边，可以将图划分成有向图和无向图；带权图和无权图。

11.2 握手定理

• 对每个点，其边的数量为度，记作$deg(v)$：
  • 对于无向图有：$2\mid E\mid = \sum_{v\in V}deg(v)$
  • 对于有向图有：$\mid E\mid = \sum_{v\in V}deg^+(v) = \sum_{v\in V}deg^-(v)$

推论：无向图的奇度数点只能有偶数个。

11.3 连通性

连通则有通路，通路path定义如下：

• 对图$G = (V,E)$，存在: \(\{x_i\}\in V，i=0,1,...,n，(x_k,x_{k+1})\in E, k=0,1,...n-1\)

若$x_n=x_0$，则称为回路。

若通路中不存在重复的边，那就说明这条路径是简单路径。

通过路径的定义，就可以定义图的连通性：

12 图的存储结构

12.1 矩阵

矩阵的存储很直观，i->j有条边就max[i][j] = 1很合理。

无向图是一个对称矩阵、有向图则未必。顶点的入度和出度也十分好计算。

还可以用来存权值，无边的两点之间存储对应数据类型的最大值即可。

12.2 邻接表

对于每个顶点，用链表存储它所有的邻接点即可。

typedef struct node{
	int data;
	struct node*  next;
}Node;

typedef Node* graph;

入度计算方便，权值很好增加，无向图只需要增加两次即可。

12.3 十字链表

十字链表克服了邻接表出度计算难的方法。

分别存储顶点和边。

struct vertex{
    int node;
    struct edge* in;
    struct edge* out;
}

struct edge{
    int begin;
    int end;
    struct edge* tail;//指向头节点（弧尾）相同的边
    struct edge* head;//指向尾节点（弧头）相同的边
}

顶点有三个域：

• 数据，存储顶点名称；
• in：存储第一个指向该顶点的边，随后可遍历其head指针得到入度；
• out：存储该顶点指出的边，随后可遍历其tail指针得到出度。

12.4 邻接多重表

和十字链表差不多吧，就是存储无向图的。

12.5 边数组

存储边，弧尾弧头权值。很简单。

12.6 总评

一般来说，稠密图用矩阵；稀疏图用邻接表。这些都是十分方便且实用的存储结构。

后面三种理论上只需要了解即可，使用范围并不广泛。

13 图的问题与算法

13.1 有向无环图问题

13.1.1 拓扑排序

针对AOV（Activity on Vertex Network）图，是一种有向无环图，可以在其上定义一个偏序关系：

• $(v_i,v_j)\in E, v_i\le v_j$

我们给出一个偏序的排序，称为拓扑排序，算法过程很简单。

只需要考虑点中一个出度为0的点，输出，并删去所有的邻边。递归。

将顶点分成两个部分，可以是数组，也可以是其他做记录的数据结构。每次搜寻就是将一个部分的元素搬运到另一个部分。

用逆邻接表+优先队列可以将复杂度限制到$O(\mid E\mid + \mid V\mid)$

一般来说，图算法的复杂度只谈论最坏情况，很少谈论平均情况。因为我们很难去讨论如何“平均”地生成一个图。

13.1.2 关键路径

考虑AOE图（Activity on Edge Network）。

所谓关键路径，就是必须按时做，没有容限的事情集合。

为了更好的理解，定义四个时间点：

• 事件能够发生的最早时间
• 事情必须发生的最晚时间
• 任务最早开工的时间
• 任务最晚开工的时间

一次拓扑排序就得到最早；一次逆拓扑排序，得到最晚。

13.2 最短路径问题

13.2.1 无权最短路径

那么长度就是路径数，直接BFS即可，一个递归调用即可。

这里许多教材和博客上来就是队列遍历，其实还有更自然的想法：

• 顶点带一个标记域，或者单独声明一个标记数组
  • 这样每次都需要遍历数组得到是否已遍历，需要$O(\mid V^2\mid )$
• 按照类似于拓扑排序的划分，并用队列优化实现，也就是网络上标准的BFS。
  • $O(\mid E\mid + \mid V\mid)$

13.2.2 有权最短路径(无负权)

Dijkstra

类似于BFS，将顶点分成两类，一类是已经找到最短路径的，一类是没找到的。

每次从没找到更新一个进入找到的，并且更新没找到的顶点路径长度，直到找完。

该算法若通过查找数组来找到没找到集合中的最小值，则总计花费$O(\mid E\mid + \mid V\mid^2)$

若是稠密图，则该算法非常优秀，若是稀疏图，则需要对数据结构进行优化。比如优先队列、二叉堆等。

Floyd

该算法对于矩阵表示法有优势，而且会产生所有顶点对之间的最短路径。

不过算法开销在$O(\mid V\mid ^3)$

核心想法是：

• 对于顶点间路径：$i\to j$；
• 考虑中间顶点$k$，遍历$i\to k$与$k\to j$的和；
• 并与现有数据作比较。

13.3 最小生成树

Prim

从点开始，不断选择最小边。

Kruskal

一直选择最小边。但不要成环。

13.4 DFS与双（重）连通性

未完待续。。。等到我理解DFS最小生成树。