算法|《啊哈！算法》的笔记 c语言|数据结构

本文作为《啊哈！算法》里面的内容，作者整理了部分知识供大家参考，如有侵权联系删除。
一大波数正在靠近——排序最快最简单的排序——桶排序
简单介绍一下下图的主人公小哼

文章图片

小哼的班上只有5个同学，这5个同学分别考了5分、3分、5分、2分和8分（满分为10分），按从大到小排序，排序后是 8 5 5 3 2。

文章图片

我们只需申请一个大小为11的数组 int a[11]，现在我们有编号从a[0]到a[10]，我们将a[0]~a[10]初始为0，表示这些分数没人得到。如：a[0]=0表示目前没人0分。

文章图片

根据小哼班里的成绩可得到最终结果如下图：

文章图片

因此我们只需将出现过的分数打印处理就可以了。

文章图片

简化版桶排序：有11个桶，编号从0~10，每出现一个数，就在对应编号的桶中放一个小旗子，最后数出每个桶中有几个小旗子。如下图：
代码实现：

#include int main() { int a[11], i, j, t; for(i = 0; i <= 10; i++) {a[i] = 0; // 初始化为0 } for(i = 1; i <= 5; i++) {scanf("%d", &t); // 读入5个数到变量 a[t]++; // 计数 } for(i = 10; i >=0; i--) {for(j = 1; j <= a[i]; j++) {printf("%d", i); } } getchar(); getchar(); // 暂停程序 return 0; }

该算法的时间复杂度是 O ( M + N ) O(M+N) O(M+N).
邻居好说话——冒泡排序
简化版的桶排序的缺点：浪费空间！
冒泡排序的基本思想：每次比较两个相邻的元素，如果它们顺序错误就把它们交换过来。
如 12 35 99 18 76 这5个数按从大到小排序，即越小的越靠后。首先比较第1位和第2位的大小，发现 12 比 35 小，交换这两个数的位置，交换后的顺序是 35 12 99 18 76，经过4次比较，得到 35 99 18 76 12。
我们刚刚将5个数中最小的一个归位了，每个将一个数归位我们称其位“一趟”。

文章图片

总结：如果有n个数进行排序，只需将 n-1 个数归位（即n-1趟），每次都需从第1位开始进行比较，将较小的一个数放后面，比较完后向后挪一位继续比较下面两个相邻数的大小。
代码实现

#include int main() { int a[100], i, j, t, n; scanf("%d", &a[i]); for (i = 1; i <= n; i++) {scanf("%d", &a[i]); } for (i = 1; i <= n - i; j++) {for (j = 1; j <= n - i; j++) {if (a[j] < a[j + 1]) {t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } } } for (i = 1; i <= n; i++) {printf("%d", a[i]); } getchar(); getchar(); return 0; }

冒泡排序核心是双重嵌套循环，时间复杂度是 O ( N 2 ) O(N^2) O(N2)。
最常用的排序——快速排序
我们对 6 1 2 7 9 3 4 5 10 8 这10个数进行排序，首先在这个序列中找一个数作基准数（用来做参照的数）。我们让6作基准数，将这个序列中所以大于基准数放6的右边，小于基准数的放6的左边。
方法：先从右往左找一个小于6的数，再从左往右找一个大于6的数然后交换。所以我们使用两个变量i 和j，分别指向序列最左边和最右边。我们为这两个变量取个名字“哨兵i"和”哨兵j“，刚开始让哨兵i指向序列最左边（i=1），指向数字6，让哨兵j指向序列最右边（j=10），指向数字8.

文章图片

首先哨兵j开始出动，哨兵j向左移动（j–）直到找到一个小于6的数才停下来，接下来哨兵i向右移动（i++），直到找到一个大于6的数才停下来，最后哨兵j停在数字5，哨兵i停在数字7。

文章图片

交换哨兵i和哨兵j所指向的元素的值

文章图片

第一次交换结束，哨兵j继续向左移动，到数字4停下，哨兵i继续向右移动，到9停下，再次进行交换

文章图片

第二次交换结束，哨兵j继续向左移动，到3停下哨兵i继续向右移动，哨兵i走到数字3与哨兵j相遇了

文章图片

此时探测结束，我们将基准数6和3进行交换

文章图片

整个算法的处理过程图

文章图片

快速排序相比于冒泡排序，每次交换是跳跃式的，基于二分的思想。每次排序的时候设置一个基准点，将小于等于基准点的数放基准点左边，将大于等于基准点的数放基准点右边。
最坏的情况是相邻的两数进行交换，此时快速排序的时间复杂度是 O ( N 2 ) O(N^2) O(N2)（最差时间复杂度），平均时间复杂度是 O ( N l o g N ) O(Nlog_N) O(NlogN?)

#include int a[101], n; void quicksort(int left, int right) { int i, j, t, temp; if (left > right) {return; } temp = a[left]; i = left; j = right; while (i != j) {while (a[j] >= temp && i < j) {j--; } while (a[i] <= temp && i < j) {i++; } if (i < j) {t = a[i]; a[i] = a[j]; a[j] = t; } a[left] = a[i]; a[i] = temp; quicksort(left, i - 1); quicksort(i + 1, right); } } int main() { int i, j, t; scanf("%d", &n); for (i = 1; i <= n; i++) {scanf("%d", &a[i]); } quicksort(1, n); for (i = 1; i <= n; i++) {printf("%d", a[i]); } getchar(); getchar(); return 0; }

小哼买书
【算法|《啊哈！算法》的笔记】小哼的学校要建一个图书角，老师派小哼去找同学做调查，每本书有唯一的ISBN号，小哼需要完成去重和排序的工作。

文章图片

输入2行，第1行表示有多少个同学参加调查（1 ~ 100），第2行表示图书的ISBN号（1 ~ 1000）。
输出2行，第1行表示需要买多少书，第2行表示从小到大已排序好的图书的ISBN号。
方法一：去重后排序

#include int main() { int a[1001], n, i, t; for (i = 1; i <= 1000; i++) {a[i] = 0; // 初始化 } scanf("%d", &n); // 读入n for (i = 1; i <= n; i++) {scanf("%d", &t); a[t] = 1; // 标记 } for (i = 1; i <= 1000; i++) {if (a[i] == 1) {printf("%d", i); } } getchar(); getchar(); return 0; }

桶排序的时间复杂度： O ( N + M ) O(N+M) O(N+M)
方法二：排序后去重

#include int main() { int a[1001], n, i, t; for (i = 1; i <= n; i++) {scanf("%d", &a[i]); } for (i = 1; i <= n - 1; i++) {for (j = 1; j <= n - i; j++) {if (a[j] > a[j + 1]) {t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; } } } printf("%d", a[i]); for (i = 2; i <= n; i++) {if (a[i] != a[i - 1]) {printf("%d", a[i]); } } getchar(); getchar(); return 0; }

时间复杂度： O ( N 2 ) O(N^2) O(N2)
栈、队列、链表解密QQ号——队列
小哼向新同桌小哈询问QQ号，小哈给小哼一串加密过的数字6 3 1 7 5 8 9 2 4，解密规则是：首先将第1个数删除，接着将第2个数放到这串数的末尾，直到剩下最后一个数，将最后一个数也删除，按刚才删除的顺序，把这些删除的数连在一起就是小哈的QQ号了。

文章图片

如何在数组中删除一个数？
最简单的方法：将后面的数都往前移动一位。

文章图片

我们引入两个整型变量head和tail，head用来记录队列的队首（第一位），tail用来记录队列的队尾（最后一位）的下一个位置。我们这里规定队首和队尾重合时，队列为空。
我们将这9个数全部放入队列，head=1; tail=10; 在队首删除一个数的操作是head++

文章图片

在队尾增加一个数x的操作是q[tail]=x; tail++

文章图片

整个解密过程图

文章图片

#include int main() { int q[102] = { 0, 6, 3, 1, 7, 5, 8, 9, 2,4 }, head, tail; int i; head = 1; tail = 10; while (head < tail) { // 队列不为空 printf("%d", q[head]); // 打印队首并出队 head++; q[tail] = q[head]; // 将队首贴加到队尾 tail++; head++; // 再将队首出队 } getchar(); getchar(); return 0; }

队列：一种特殊的线性结构，只允许在队列的首部（head）进行删除操作，称为出队，队列的尾部（tail）进行插入操作，称为入队，当队列中没有元素是（head=tail）队列为空队列。
队列是我们今后学习广度优先搜索以及队列优化的Bellman-Ford 最短路算法的核心数据结构，我们将队列的三个基本元素（一个数组，两个变量）封装为一个结构体类型。

struct queue { int data[100]; // 队列的主体 int head; // 队首 int tail; // 队尾 };

文章图片

定义结构体变量：

struct queue q;

访问结构体变量的内部成员

q.head = 1; q.tail = 1; scanf("%d", &q.data[q.tail]);

结构体实现的队列操作

#include struct queue { int data[100]; // 队列的主体 int head; // 队首 int tail; // 队尾 }; int main() { struct queue q; int i; q.head = 1; q.tail = 1; for (i = 1; i <= 9; i++) {scanf("%d", &q.data[q.tail]); } while (head < tail) { // 队列不为空 printf("%d", q[head]); // 打印队首并出队 head++; q[tail] = q[head]; // 将队首贴加到队尾 tail++; head++; // 再将队首出队 } getchar(); getchar(); return 0; }

解密回文——栈
后进后出的数据结构——栈
栈限定为只能在一端进行插入和删除操作，如：有一个小桶直径只能放一个小球，我们依次放入2、1、3号小球，如果你想要拿出2号小球，必须先将3号小球拿出，再拿出1号小球，最后才能将2号小球拿出。
栈的实现：一个一维数组和一个指向栈顶的变量top，我们通过top来对栈进行插入和删除操作。
如：xyzyx 是一个回文字符串，所谓回文字符是正读反读均相同的字符序列。

文章图片

读取这行字符串，求出这个字符串的长度

char a[101]; int len; gets(a); len = strlen(a);

如果一个字符串是回文字符，那么它必须是中间对称的，所以我们求中点

mid = len / 2 - 1;

我们先将mid之前的字符全部入栈，char s[101]; ，初始化栈 top=0；。入栈的操作是top++；s[top]=x; (入栈的字符暂存字符变量x中），可简写s[++top]=x; 。

for(i = 0; i <= mid; i++) { s[++top] = x; }

代码实现

#include #include int main() { char a[101], s[101]; int i, len, mid, next, top; gets(a); // 读入一行字符 len = strlen(a); // 求字符串长度 mid = len / 2 - 1; // 求字符串中点 top = 0; // 栈的初始化 for (i = 0; i <= mid; i++) {s[++top] = a[i]; } if (len % 2 == 0) { // 判断字符串长度是奇数还是偶数 next = mid + 1; } else {next = mid + 2; } for (i = next; i <= len - 1; i++) {if (a[i] != s[top]) {break; } top--; } if (top == 0) { // top为0，表示栈内所以字符都被一一匹配 printf("YES"); } else {printf("NO"); } getchar(); getchar(); return 0; }

链表
如果需要在8前面插入一个6，无需像数组一样将8及后面的数都依次往后移一位，只需像下图一样

文章图片

C语言中可以使用指针和动态分配内存函数 malloc来实现。

int *p; // 定义一个整型指针变量

指针作用：存储一个地址，存储一个内存空间的地址

p = &a; // &取地址符，整型指针p指向了整型变量a

通过指针p来输出变量a的值

#include int main() { int a = 10; int *p; p = &a; printf("%d", *p); // *在printf里做间接运算符，取得指针p所指向的内存中的值 getchar(); getchar(); }

运行结果

10

动态存储方法
malloc函数：从内存中申请分配指定字节大小的内存空间

malloc(4);

sizeof(int)获取int类型所占用的字节数

malloc(sizeof(int));

存储这个空间的首地址

int *p; p = (int *)malloc(sizeof(int));

malloc函数的返回类型是void类型，void表示未确定类型的指针。在C和C++中，void*类型可以强制转换为任何其他类型的指针。
指针就是用来存储内存地址的，为什么要分不同类型的指针呢？因为变量存储的是一个内存空间的首地址（第一个字节的地址），但这个空间占用了多少个字节，用来存储什么类型的数，则是由指针的类型来标明的，这样系统才知道去多少个连续内存作为一个数据。

#include #include int main() { int *p; // 定义一个指针p p = (int *)malloc(sizeof(int)); // 指针p获取动态分配的内存空间地址 *p = 10; printf("%d", *p); // 输出指针p所指向的内存中的值 }

运行结果

10

数组模拟链表

文章图片

每个结点都由两个部分组成，左边部分用来存储具体的数值，可以用一个整型变量；右边部分存储下一个结点的地址，可以用指针实现（称为后继指针）。
定义一个结构体来存储这个结点

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

文章图片

我们定义一个叫做 node 的结构体类型，第一个成员整型data，用来存储具体的数值；第二个成员是一个指针，用来存储下一个节点的地址。
如何建立链表？
我们需要一个头指针 head 指向链表的最开始，当链表还没建立时头指针 head 为空（指向空指针）。

struct node *head; head = NULL; // 头指针初始为空

创建一个结点，并用临时指针p指向这个结点

struct node *p; p = (struct node *)malloc(sizeof(struct node));

设置新创建的这个结点的左半部分和右半部分

scanf("%d", &a); p->data = https://www.it610.com/article/a; p->next = NULL;

文章图片

->结构体指针运算符，用来访问结构内部成员的，因为p是个指针，所以不能使用.号访问内部成员。
设置头指针并设置新创建结点的*next指向空，头指针的作用是方便以后从头遍历整个链表。

if(head == NULL) { head = p; // 头指针指向这个结点 } else { q->next = p; // 上一个结点的后续指针指向当前结点 }

如果这是第一个创建的结点，则将头指针指向这个结点

文章图片

如果不是第一个创建的结点，则将上一个结点的后续指针指向当前结点

文章图片

最后将指针q也指向当前结点，因为临时指针p将会指向新创建的结点

q = p; // 指针q指向当前结点

#include #include // 创建一个结构体表示链表的结点类型 struct node { int data; struct node *next; }; int main() { struct node *head, *p, *q, *t; int i, n, a; scanf("%d", &n); head = NULL; // 头指针初始为空 for(i = 1; i <= n; i++) {scanf("%d", &a); p = (struct node *)malloc(sizeof(struct node)); p->data = https://www.it610.com/article/a; // 将数据存储到当前结点的data域中 p->next = NULL; // 设置当前结点的后续指针指向空，也就是当前结点的下一个结点为空 if(head == NULL) head = p; // 如果是第一个创建的结点，则将头指针指向这个结点 else q->next = p; // 如果不是第一个创建的结点，则将上一个结点的后续指针指向当前结点 q = p; // 指针q也指向当前结点 } t = head; while(t != NULL) {printf("%d", t->data); t = t->next; // 继续下一个结点 } getchar(); getchar(); return 0; }

注意：记得用释放动态申请的空间

文章图片

scanf("%d", &a); // 读入待插入的数 while(t != NULL) { if(t->next->data > a) {p = (struct node*)malloc(sizeof(struct node)); // 动态空间 p->data = https://www.it610.com/article/a; p->next = t->next; // 新增结点的后续指针指向当前结点的后续指针所指向的结点 t->next = p; // 当前结点的后续指针指向新增结点 break; // 插入完后退出 } t = t->next; // 继续下个结点 }

模拟链表
利用data数组来存储序列中的每个数，利用right来存储序列中每个数右边的数在数组data中的位置。

文章图片

如：right[0]表示当前序列中9号元素的右边没有元素
现要在8前面插入一个6，只需将6直接存放在数组末尾（data[10]=6），接下来将right[3]=10表示新序列3号元素右边的元素存放在data[10]中，再将right[10]=4，表示新序列中10号元素右边的元素存放在data[4]中，这样就完成了8前面插入一个6。

文章图片

#include int main() { int data[101], right[101]; int i, n, t, len; // 读入数字 scanf("%d", &n); for(i = 1; i <=n; i++) scanf("%d", &data[i]); len = n; // 初始化数组right for(i = 1; i <= n; i++) {if(i != n) right[i] = i + 1; else right[i] = 0; } // 数组data末尾增加一个数 len++; scanf("%d", &data[len]); // 链表头部开始遍历 t = 1; while(t != 0) {if(data[right][t] > data[len]) // 如果当前结点的下个结点的值大于待插入数，将数插入中间 {right[len] = right[t]; // 新插入数的下一个结点编号等于当前结点的下一个结点编号 right[t] = len; // 当前结点的下一个节点编号就是新插入数的编号 break; // 插入完成结束循环 } t = right[t]; } // 输出链表的数 t = 1; while(t != 0) {printf("%d", data[t]); t = right[t]; } getchar(); getchar(); return 0; }

枚举！很暴力坑爹的奥数
枚举算法（穷举算法）：有序地去尝试每一种可能
小哼在数学课上遇到一道奥数题：

文章图片
，填入相同的数字使得等式成立。

for (int i = 1; i <= 9; i++) {if ((i * 10 + 3) * 6528 == (30 + i) * 8256) printf("%d", i); }

数的全排列
123 的全排列是 123、132、213、312、312、321。

#include int main() {for(int a = 1; a <= 3; a++) {for(int b = 1; b <= 3; b++) {for(int c = 1; c <= 3; c++) {if(a != b && a != c && b != c) {printf("%d%d%d\n", a, b, c); } } } } }

运行结果

文章图片

万能的搜索不撞南墙不回头——深度优先搜索
有编号为1、2、3的3张扑克牌和编号为1、2、3的3个盒子，现需将这3张扑克牌分别放到3个盒子里，且每个盒子只能放一张扑克牌，那么有多少种不同放法？

文章图片

小哼走到盒子面前，每到一个新盒子按照1、2、3号扑克牌的顺序来放，于是小哼将1号放入1号盒子。

文章图片

现手上剩下2号和3号扑克牌，于是小哼将2号扑克牌放入了2号盒子中。

文章图片

小哼走到3号盒子面前时，手中只有3号扑克牌了，于是只能往3号盒子里放3号扑克牌。

文章图片

这是产生了一种排序1 2 3，于是小哼需取回放在3号盒子里的扑克牌，看看能否产生新的排序。当取回3号盒子的扑克牌时，发现手中只有3号扑克牌，于是小哼得往回退一步，收回2号扑克牌后，小哼手中有2号和3号扑克牌了。按规定小哼需往2号盒子放3号扑克牌，放好后来到3号盒子面前放入仅剩的2号扑克牌，这是产生了新的排序1 3 2。

#include int a[10], book[10], n; void dfs(int step) { // step 表示现在站在第几个盒子面前 int i; if(step == n + 1) { // 站在n+1盒子前表示n个盒子已经放好扑克牌 for(i = 1; i <= n; i++) { // 输出排列 printf("%d", a[i]); } printf("\n"); return; } for(i = 1; i <= n; i++) {if(book[i] == 0) { // 判断扑克牌是否在手中 a[step] = i; // 将i号扑克牌放入第step个盒子 book[i] = 1; // i号扑克牌已经不在手中 dfs(step + 1); // 函数调用 book[i] = 0; // 收回扑克牌 } } return; } int main() {scanf("%d", &n); dfs(1); // 站在1号盒子面前 getchar(); getchar(); return 0; }

总结：深度优先搜索的关键在于解决 “ 当下该如何做”。
深度优先搜索的基本模型

void dfs(int step) { 判断边界尝试每种可能 for(i = 1; i <= n; i++) {继续下一步 dfs(step + 1); } 返回 }

层层递进——广度优先搜索
广度优先搜索（Breadth First Search，BFS），也称宽度优先搜索。

文章图片

我们使用一个二维数组来存储一个迷宫，最开始小哼在迷宫（1，1）处，可以往下或往右走。
深度优先搜索：先让小哼往右走，然后一直尝试下去，直至走不通的时候再返回。
我们通过 ”一层一层“扩展的方法来找到终点，扩展时每发现一个点就将这个点加入队列直到到达终点。
小哼站在（1，1）只能通过（1，2）和（2，1）两点往下走，当小哼走到（1，2）时它接下来能到达（2，2）；当小哼走到（2，1）时它接下来能到达（2，2）和（3，1），两个都可以到达（2，2）这个点。

文章图片

于是当小哼在（2，2）或（3，1）时又可以往哪里走，通过（2，2）可以到（3，2）和（2，3）两点，通过（3，1）可以到（3，2）和（4，1）两点。于是继续重复直到到达终点。

文章图片

我们用一个结构体来实现队列来模拟这个过程。

struct note { int x; // 横坐标 int y; // 纵坐标 int s; // 步数 }; struct note que[2501]; int head, tail; int a[51][51] = { 0}; int book[51][51] = { 0}; head = 1; tail = 1; // 将（1，1）加入队列，标记（1，1）走过 que[tail].x = 1; que[tail].y = 1; que[tail].s = 0; tail++; book[1][1] = 1;

文章图片

往右走到达（1，2）

tx = que[head].x; ty = que[head].y + 1;

判断（1，2）是否越界

if(tx < 1 || tx > n || ty < 1 || ty > m) continue;

判断（1，2）是否为障碍物或已经在路径中

if(a[tx][ty] == 0 && book[tx][ty] == 0) {}

满足条件（1，2）入队，标记该店已走过

book[tx][ty] = 1; que[tail].x = tx; que[tail].y = ty; que[tail].s = que[head].s + 1; tail++;

文章图片

按右、下、左、上顺序尝试，将（2，1）加入队列

文章图片

扩展完后将（1，1）出队

head++;

出队后，head指向（1，2）这个点，通过这个点可到达（2，2），于是将（2，2）加入队列

文章图片

（1，2）出队后，head指向（2，1），通过（2，1）可到达（2，2）和（3，1），于是将（3，1）入队。

文章图片

于是继续重复，直至走到终点，算法结束。
图的遍历深度和广度优先究竟指啥
深度和广度是针对图的遍历而言的。

文章图片

图：一些小圆点（顶点）和连接小圆点的直线（边）组成。
如：上图是由（1、2、3、4、5）和5条边（1-2、1-3、1-5、2-4、3-5）组成
我们从1号顶点开始遍历这个图，遍历就是把图的每个顶点都访问一次。
使用深度优先会得到如下的结果

文章图片

深度优先搜索思想：首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点；当没有未访问过的顶点时，则回到上一个顶点，继续访问别的顶点，直到所以的顶点都被访问过。即沿着图的某一条分支遍历直到末端，然后回溯，再沿另一条继续遍历，直到所以顶点都被访问过。
广度优先搜索来遍历这个图

文章图片

广度优先搜索遍历图的过程：首先以一个未被访问过的顶点作为起始顶点，如：以1号顶点为起点，将1号顶点放入队列中，然后将1号顶点相邻的未访问过的顶点（2号、3号、5号）依次放入队列。

文章图片

再将2号顶点相邻的未访问过的顶点4放入队列中，此时遍历结束。

文章图片

广度优先遍历的思想：首先以一个未被访问过的顶点作为起始顶点，访问其所有顶点，然后对每个相邻的顶点，访问它们相邻的未被访问的顶点，直到所有顶点都被访问过，遍历结束。
最短路径只有五行的算法——Floyd-Warshall

文章图片

小哼准备去城市旅游，为节省经费和方便计划旅程，小哼希望在出发之前知道两个城市之间的最短路程。

文章图片

我们用二维数组来存储， ∞ \infty ∞代表无法到达。

文章图片

当只允许经过1号顶点时，我们需要判断e[i][1]+e[1][j]是否小于e[i][j]。
注意：e[i][[j]代表从i号顶点到j号顶点之间的路程。

for(i = 1; i <= n; i++) { for(j = 1; j <= n; j++) {if(e[i][j] > e[i][1] + e[1][j]) e[i][j] = e[i][1] + e[1][j]; } }

当只允许经过1号顶点时，任意两点之间的最短路径更新为：

文章图片

只经过1和2号顶点的情况下任意两点之间的最短路

// 1号顶点 for(i = 1; i <= n; i++) { for(j = 1; j <= n; j++) {if(e[i][j] > e[i][1] + e[1][j]) e[i][j] = e[i][1] + e[1][j]; } } // 2号顶点 for(i = 1; i <= n; i++) { for(j = 1; j <= n; j++) {if(e[i][j] > e[i][2] + e[2][j]) e[i][j] = e[i][2] + e[2][j]; } }

当允许经过1、2号顶点时，任意两点之间的最短路程更新为：

文章图片

接着经过1、2、3号顶点进行中转，任意两点之间的最短路程更新为：

文章图片

允许所有顶点作为中转，任意两点最终的最短路程为：

文章图片

核心代码

for(k = 1; k <= n; k++) for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) if(e[i][j] > e[i][k] + e[k][j]) e[i][j] = e[i][k] + e[k][j];

注意：Floyd-Warshall算法不能解决带有“负权回路”（“负权环”）的图，因为它没有最短路径，如下图

文章图片

Dijkstra算法——通过边实现松弛
指定一个点（源点）到其他各个顶点的最短路径（单源最短路径）

文章图片

二维数组存储顶点之间边的关系

文章图片

一维数组存储1号顶点到其他顶点的路程

文章图片

此时dis数组中的值称为最短路程的“估计值”，当求1号顶点到其他各个顶点的最短路程，那就先找离1号顶点最近的顶点2号顶点，于是dis[2]的值从“估计值”变为了“确定值”，即1号顶点到2号顶点的最短路程就是dis[2]的值。
选择了2号顶点后，发现有2-3和2-4这两条边，通过2-3这条边时判断dis[3]和dis[2]+dis[2][3]的大小，因为12>10所有dis[3]要更新为10。这个过程叫做“松弛”，即Dijkstra算法的主要思想：通过“边”来松弛1号顶点到其他各个顶点的路程。通过2-4，dis[4]的值松弛为4。

文章图片

最终效果

文章图片

这个算法的基本思想：每次找到离源点（1号顶点）最近的一个顶点，然后以该顶点进行扩展，最终得到源点到其余所有点的最短路径。
Bellman-Ford——解决负权边
我们使用dis数组记录源点到其它各个顶点的最短路径，通过判断1号顶点到v[i]号顶点的距离是否小于1号顶点到u[i]号顶点加上u[i]-v[i]这条边的值（权值w[i]）来实现松弛。

for(k = 1; k <= n - 1; k++) for(i = 1; i <= m; i++) if(dis[v[i]] > dis[u[i]] + w[i]) dis[v[i]] = dis[u[i]] + w[i]

1号顶点到其它各个顶点的最短路径

文章图片

用dis数组存储

文章图片

判断dis[3]是否大于dis[2]+2，发现松弛失败，继续判断dis[2]是否大于dis[1]+(-3),发现松弛成功，继续处理，松弛一遍后效果如下

文章图片

第2轮松弛

文章图片

小哼提出了如下的问题

文章图片

思考：最多只能包含n-1条边吗？为什么最短路径中没有回路？
我们知道回路分为正权回路（回路权值之和为正）和负权回路，当包含正权回路是，去掉这个回路，可以得到更短的路径；当包含负权回路时，肯定没有最短路径，因此最短路径肯定是个不包含回路的简单路径。
Bellman-Ford的队列优化
每次仅对最短路程发生变化了的点的相邻边执行松弛操作。

文章图片

我们用dis数组存储1号顶点到其它各个顶点的最短路径，初始值dis[1]=0，其它为 ∞ \infty ∞。1号顶点入队，用数组que及队列头head和尾tail来实现队列。

文章图片

判断dis[2]和dis[1]+(1$\to$2)的大小，然后将2号顶点入队且dis[2]的值更新为2。

文章图片

对1号顶点剩余边进行处理

文章图片

1号顶点处理完毕后，将1号顶点出队（head++），再对新队首2号顶点进行处理时，上如dis[5]的值更新为9，但5号顶点已经在队列中了，因此不能入队。

文章图片

最终效果

文章图片

最短路径算法对比分析

文章图片

神奇的树开启“树”之旅

文章图片

上图是一个树，我们将其变换一下

文章图片

树和图的区别？
树不包含回路的连通无向图。

文章图片

可以看出左边是个树，右边是个图。因为左边没有回路，而右边有回路。
树的特性:

一棵树中的任意两个结点有且仅有唯一的一条路径连通。
一棵树如果有n个结点，那么它一定恰好有n-1条边
在一棵树中加一条边将会构成一个回路

树的用途：如目录结构

文章图片

文章图片

我们将树中的每个点称为结点，上图1、3结点是树的树根（即根结点），一棵树只有一个根结点。父亲结点称为父结点，儿子结点称为子结点，如果一个结点没有子结点，那么称为叶结点；没有父结点，那么称为根结点。如果一个结点既不是根结点也不是叶结点，则称为内部结点。结点的深度是指从根到这个结点的层数（根为第一层）。