本文作為《啊哈！演算法》里面的內容，作者整理了部分知識供大家參考，如有侵權聯系洗掉，
一大波數正在靠近——排序
最快最簡單的排序——桶排序
簡單介紹一下下圖的主人公小哼
小哼的班上只有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 <stdio.h>
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 <stdio.h>
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 <stdio.h>
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 <stdio.h>
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 <stdio.h>
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 <stdio.h>
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 <stdio.h>
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 <stdio.h>
#include <string.h>
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 <stdio.h>
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 <stdio.h>
#include <stdlib.h>
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 = a;
p->next = NULL;
->結構體指標運算子，用來訪問結構內部成員的，因為p是個指標，所以不能使用.號訪問內部成員，
設定頭指標并設定新創建結點的*next指向空，頭指標的作用是方便以后從頭遍歷整個鏈表，
if(head == NULL) {
head = p; // 頭指標指向這個結點
}
else {
q->next = p; // 上一個結點的后續指標指向當前結點
}
如果這是第一個創建的結點，則將頭指標指向這個結點
如果不是第一個創建的結點，則將上一個結點的后續指標指向當前結點
最后將指標q也指向當前結點，因為臨時指標p將會指向新創建的結點
q = p; // 指標q指向當前結點
#include <stdio.h>
#include <stdlib.h>
// 創建一個結構體表示鏈表的結點型別
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 = 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 = 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 <stdio.h>
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 <iostream>
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 <stdio.h>
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結點是樹的樹根（即根結點），一棵樹只有一個根結點，父親結點稱為父結點，兒子結點稱為子結點，如果一個結點沒有子結點，那么稱為葉結點；沒有父結點，那么稱為根結點，如果一個結點既不是根結點也不是葉結點，則稱為內部結點，結點的深度是指從根到這個結點的層數（根為第一層），
二叉樹
二叉樹是一種特殊的樹，二叉樹的特點是每個結點最多有兩個兒子，左邊的叫做左兒子，右邊的叫做右兒子（即每個結點最多右兩棵子樹），更加嚴格的遞回定義：二叉樹要么為空，要么右根結點、左子樹和右子樹組成，而左子樹和右子樹分別是一棵二叉樹，
二叉樹中特殊的兩種二叉樹：滿二叉樹和完全二叉樹，
滿二叉樹：二叉樹中每個內部結點都有兩個兒子（滿二叉樹所有的葉結點都有相同的深度），嚴格定義：一棵深度為n且有
2
n
?
1
2^n-1
2n?1個結點的二叉樹，
完全二叉樹：一棵二叉樹除了最右邊位置上有一個或幾個葉結點缺少外，其他都是豐滿的，嚴格定義：若設二叉樹的高度為n，出第n層外，其他各層（1~n-1）的結點數都達到最大個數，第n層從右向左連續缺若干結點（即如果一個結點有右子結點，那么它一定也有左子結點，
上圖我們發現如果完全二叉樹的一個父結點編號為k，那么左兒子編號為2k，右兒子編號為2k+1，如果知道兒子（左兒子或右兒子）的編號是x，那么它的父結點編號就是x/2（取整數），
堆——神奇的優先佇列
堆是一種特殊的完全二叉樹，如下圖
上圖的二叉樹的父結點都比子結點要小，這樣的完全二叉樹稱為最小堆，反之，稱為最大堆，
假如有14個數，分別是99、5、36、7、22、17、46、12、2、19、25、28、1和92，請找出這14個數中最小的數，
for(i = 1; i <= 14; i++) {
if(a[i] < min)
min = a[i];
}
我們想洗掉其中最小的數，并增加一個新數23，再求這14個數中最小的一個數，
我們把14個數按最小堆的要求放入一棵完全二叉樹，如下圖，
我們設存盤這個堆的陣列為h，最小數就是h[1]，我們將堆頂的數洗掉，將增加的數23放到堆頂，然后我們進行調整，
我們將23與2和5進行比較，選擇較小的與之交換
發現還是不符合最小堆的特性，繼續向下調整
最終效果
我們發現我們比較了3次，就恢復了最小堆的特性，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/302233.html
標籤：其他