# 資料結構與演算法 習題解答 第5~7章
### 高立圖書：512326
#### 即時更新請見：https://hackmd.io/@sjshyu/DS_Exercises_Ch5-7
---
## 第五章 樹
### 1. 針對程式 5-1 一般化串列鏈結節點的宣告，設計樹的輸入，寫出必要的程序，使能完成樹的一般化鏈結串列的建構。
:::spoiler
```cpp=
Add (struct TreeNode *p, struct TreeNode *subtree)
{ struct TreeNode *s;
s->tag = 1;
s->link = p->link;
p->link = s;
s->node = subtree;
}
```
:::
---
### 2. 在 5.2.2 節中，我們用圖 5-7 描繪了左子右兄弟表示法的節點構造，請寫出此節點的程式宣告。
:::spoiler
```cpp=
# include <stdio.h>
struct node
{ struct node *leftmostchild;
int data;
struct node *rightsibling;
};
struct node *root;
int main()
{ return 0;
}
```
:::
---
### 3. 在5.2.3節中我們討論了分支度為 $2$ 的樹表示法，請寫出此節點的程式宣告。
:::spoiler
```cpp=
# include <stdio.h>
struct node
{ struct node *Left;
int data;
struct node *Right;
};
struct node *root;
int main()
{ return 0;
}
```
:::
---
### 4. 一個分支度為 $k$，高度為 $h$ 的二元樹，其最大節點數為多少？證明你的答案。
:::spoiler
$\sum\limits_{i=1}^{h}{k^{i-1}} = 1+k^1+k^2+...+k^{h-1} = \frac{k^h-1}{k-1}$
:::
---
### 5. 參考程式 5-6-1，實作出非遞迴版本的程式，執行二元樹前序走訪。
:::spoiler
```cpp=
# include <stdio.h>
# include <stdlib.h>
//BinaryTreeNode
struct node
{ struct node *LeftChild;
int data;
struct node *RightChild;
};
struct node *NewNode(int x)
{ struct node *Node = (struct Node *)malloc(sizeof(struct node));
Node->data = x;
Node->LeftChild = NULL;
Node->RightChild = NULL;
return Node;
}
struct node *Insert(struct node *Node,int x)
{ if (Node == NULL) return NewNode(x);
if (x < Node->data) Node->LeftChild = Insert(Node->LeftChild, x);
else Node->RightChild = Insert(Node->RightChild, x);
return Node;
}
struct node *root;
//Stack
struct node **Stack;
int top = -1;
void push(struct node *element)
{ if (top >= 1000) return;
else Stack[++top] = element;
}
struct node *pop()
{ if (top == -1) return NULL;
else return Stack[top--];
}
int StackEmpty()
{ return top == -1;
}
//preorder
void preorder()
{ struct node *p = root;
while (!StackEmpty()||p)
{ while (p)
{ printf("%d\n", p->data);
push(p);
p = p->LeftChild;
}
if (!StackEmpty())
{ p = pop();
p = p->RightChild;
}
}
}
int main()
{ Stack = (struct Node **)malloc(1000 * sizeof(struct node*));//Insert 100 random number(0~32767)
for (int i = 0; i < 100; i++)
{ int number = rand();
root = Insert(root,number);
}
preorder();
}
```
:::
---
### 6. 參考程式 5-6-2 和習題 5，實作出非遞迴版本的程式，執行二元樹後序走訪。
:::spoiler
```cpp=
struct BTreeNode
{ struct BTreeNode *leftchild;
char data;
bool traversed = false;
struct BtreeNode *rightchild;
};
void postorder_Stack()
{ struct StackNode *top;
struct BTreeNode *node = root;
push_node(node);
do
{ while (node != NULL)
{ push_node(node);
node = node->leftchild;
}
if (top != NULL)
{ node = pop_node();
if (node->rightchild != NULL && node->traversed == false)
{ push_node(node);
node->traversed == true;
node = node->rightchild;
}
else
{ cout << node->data;
node = NULL;
}
}
} while (top != NULL);
}
```
:::
---
### 7. 參考程式 5-7 實作出階層走訪 (level-order travesal) 的程式，走訪一二元樹。
:::spoiler
```cpp=
# include <stdio.h>
# include <stdlib.h>
//BinaryTreeNode
struct node
{ struct node *LeftChild;
int data;
struct node *RightChild;
};
struct node *NewNode(int x)
{ struct node *Node = (struct node *)malloc(sizeof(struct node));
Node->data = x;
Node->LeftChild = NULL;
Node->RightChild = NULL;
return Node;
}
struct node *Insert(struct node *Node, int x)
{ if (Node == NULL) return NewNode(x);
if (x < Node->data)
Node->LeftChild = Insert(Node->LeftChild, x);
else
Node->RightChild = Insert(Node->RightChild, x);
return Node;
}
struct node *root;
//Queue
struct node **Queue;
int front = -1, rear = -1;
void AddQueue(struct node *element)
{ if (front >= 1000) return;
else Queue[++rear] = element;
}
struct node *DeleteQueue()
{ if (rear == front)return NULL;
else return Queue[++front];
}
int QueueEmpty()
{ return front == rear;
}
//levelOrder
void LevelOrder()
{ AddQueue(root);
struct node *p = NULL;
while (!QueueEmpty())
{ p = DeleteQueue();
printf("%d\n", p->data);
if (p->LeftChild )
AddQueue(p->LeftChild);
if (p->RightChild)
AddQueue(p->RightChild);
}
}
int main()
{ Queue = (struct Node **)malloc(1000 * sizeof(struct node*));
//Insert 100 random number(0~32767)
for (int i = 0; i < 100; i++)
{ int number = rand();
root = Insert(root,number);
}
LevelOrder();
}
```
:::
---
### 8. 寫出能計算出二元樹 $T$ 中葉節點數目的程序，分析它的計算時間為何？
:::spoiler
利用階層走訪，當分支數為 $0$ 時 $Count$++，走訪完後傳回 $Count$ 即為葉節點個數。
```cpp=
int Count_leaveNode()
{ struct StackNode *top;
struct BTreeNode *node = root;
push_node(node);
int Count = 0;
while (top != NULL)
{ node = pop_node();
cout << node->data;
int count = 0;
if(node->rightchild != NULL)
{ push_node(node->rightchild);
count++;
}
if (node-> leftchild != NULL)
{ push_node(node->leftchild);
count++;
}
if (count == 0)
Count++;
}
return Count;
}
```
時間複雜度為 $O(n)$，其中 $n$ 為節點個數。
:::
---
### 9. 寫出一演算法將輸入的二元樹 $T$，以 SwapTree($T$)交換每一個節點的左右子點。請看圖 5-57 的例子。
:::spoiler
```cpp=
struct BTNode *SwapTree(struct BTNode *node)
{ if (node)
{ node->leftchild = SwapTree(node->rightchild);
node->rightchild = SwapTree(node->leftchild);
return node;
}
return NULL;
}
```
想想下面想法是否可行？
```cpp=
SwapTree (Tree T)
{ for ( T 上每一個點)
{ node = T->leftchild;
T->leftchild = T->rightchild;
T->rightchild = node;
}
}
```
:::
---
### 10. 試想若程式 5-11 中的程序 Next，所傳入的參數指標正是 root，請問 Next是否可正常運作？
:::spoiler
當程式執行 Next(root) 時
(1)會將 temp 指向 root->rightchild (root->rightchild = 自己)，即 node 與 temp 皆指向 root。
(2)判斷 temp->rightthread，因為 root->rightthread = $0$，故會找temp->leftchild，即 root->leftchild。
由 (1) 和 (2) 可知執行 Next (root) 時候，可以正常運作，並且能找到該樹中序表
示中的第一個節點。
:::
---
### 11. 請參考程式 5-13，寫出程序—使可插入節點 new 成為引線二元樹的節點 $p$ 的左子節點。
:::spoiler
```cpp=
//建立 node h; 將 ch 存入 h; 插入 h 作為 s 的左兒子
void Threaded::InsertLeft (ThreadedNode *s, char ch)
{ ThreadedNode *h = new ThreadNode(ch);
h->LeftChild = s->LeftChild;
h->LeftThread = s->LeftThread;
h->RightChild = s;
h->RightThread = TRUE; //右兒子為引線
s->LeftChild = h; //把 h 加到 s
s->LeftThread = FALSE;
if (!h->LeftThread)
{ ThreadedNode *temp = InorderPred(h);
Temp->RightChild = h;
}
}
```
:::
---
### 12. 考慮使用後序引線而非前序引線來連接一二元樹時，哪一個走訪法可以不使用堆疊就能夠完成？對於這些不使用堆疊就能夠完成的走訪法，寫出演算法來，並且分析其空間的複雜度。
:::spoiler
沒有任何走訪可以不使用堆疊就能完成。
以下圖高度為 $3$ 的後序引線二元樹為例：
1. 中序走訪：第一個走訪節點為 $D$，下一個節點應為 $B$，但此時就無法透過節點 $D$ 的左引線或右引線到達節點 $B$，故可知中序走訪無法不使用堆疊完成。
2. 前序走訪：第一個走訪節點為 $A$，下一個節點應為 $B$，可由節點 $A$ 的左指標到達，而在下一個節點應為 $D$，可由節點 $B$ 的左指標到達，再下一個節點應為 $E$，可由節點 $D$ 的右引線到達，再下一個節點應為 $C$ ，但此時就無法透過節點 $E$ 的左引線或右引線到達節點 $C$，故可知前序走訪無法不使用堆疊完成。
3. 後序走訪：第一個走訪節點為 $D$，下一個節點應為 $E$，可由節點 $D$ 的右引線到達，而下一個節點應為 $B$，可由節點 $E$ 的右引線到達，再下一個節點應為 $C$，但此時就無法透過節點 $B$ 的左指標或右指標到達節點 $C$，故可知後序走訪無法不使用堆疊完成。
以下圖高度為 $4$ 的後序引線二元樹為例：
1. 中序走訪：第一個走訪節點為 $H$，下一個節點應為 $D$，但此時就無法透過節點 $H$ 的左引線或右引線到達節點 $D$，故可知中序走訪無法不使用堆疊完成。
2. 前序走訪：第一個走訪節點為 $A$，下一個節點應為 $B$，可由節點 $A$ 的左指標到達，而在下一個節點應為 $D$，可由節點 $B$ 的左指標到達，再下一個節點應為 $H$，可由節點 $D$ 的左指標到達，再下一個節點應為 $I$ ，可由節點 $H$ 的右引線到達，再下一個節點應為 $E$，但此時就無法透過節點 $I$ 的左引線或右引線到達節點 $E$，故可知前序走訪無法不使用堆疊完成。
3. 後序走訪：第一個走訪節點為 $H$，下一個節點應為 $I$，可由節點 $H$ 的右引線到達，而下一個節點應為 $D$，可由節點 $I$ 的右引線到達，再下一個節點應為 $E$，但此時就無法透過節點 $D$ 的左指標或右指標到達節點 $E$，故可知後序走訪無法不使用堆疊完成。
要能舉出沒有任何走訪可以不使用堆疊就能完成走訪的例子需在後序引線二元樹的高度大於 $2$ 時才能舉出，
下圖為高度為 $2$ 時有走訪法能成功走完的例子：
此後序引線二元樹高度為 $2$，但因只有兩個節點，所以不管是中序、前序和後序走訪都能成功走訪完，故無法舉出沒有任何走訪可以不使用堆疊就能完成走訪的例子。
此後序引線二元樹高度為 $2$，且為完滿二元樹，但此樹在前序和後序走訪時能成功利用後序引線走訪完整棵樹，唯獨在中序走訪無法成功，故無法舉出沒有任何走訪可以不使用堆疊就能完成走訪的例子。
:::
---
### 13. 寫一演算法以在最小堆積中作插入動作。這個演算法的複雜度應為 $O(logn)$，請證明。
:::spoiler
```cpp=
void InsertHeap(int x)
{ if (n == maxsize) HeapFull();
else
{ n++;
i = n;
while ((i > 1) && (x < heap[i/2]))
{ heap[i] = heap[i/2];
i /= 2;
}
heap[i] = x;
}
}
```
新增節點的位置若在 $k$ 處，則新增資料可能的位置，會在 $k$ 往上走至樹根的任何節點上，亦即最差情況程式迴圈會執行 ⎡$log(k+1)$⎤ 次，這也是此完備二元樹的深度。因此程序 InsertHeap 在插入第 $n$ 個資料時，需要的時間複雜度為 $O(logn)$。
:::
---
### 14. 寫一演算法在最小堆積中刪除最小元素。此演算法的複雜度為 $O(logn)$，並證明這一點。
:::spoiler
```cpp=
int DeleteHeap()
{ int x, i, j;
if (n == 0) HeapEmpty();
else
{ x = heap[1];
heap[1] = heap[n];
n--;
i = 1;
while (i <= n / 2)
{ if (heap[2 * i] < heap[2 * i + 1]) j = 2 * i;
else j = 2 * i + 1;
if (heap[i] < heap[j]) break;
swap(&heap[i], &heap[j]);
i = j;
}
return x;
}
}
```
每次刪除最小元素 heap[$1$] 後，將最後一個元素 heap[$n$] 取代 heap[$1$]，並將堆積修正回最小堆積，故最差狀況會是取代後的 heap[$1$] 比對堆積的深度 $logn$ 次後才得到最小堆積，因此複雜度為 $O(logn)$。
:::
---
### 15. 證明一樹林的前序走訪與其對應二元樹的前序走訪，結果相同。
:::spoiler
假設 $(T_1, T_2, ..., T_n)$ 視為一樹林且 $PO(T_1, T_2, ..., T_n)$ 為樹林的前序走訪，將森林的樹個別做前序走訪並依序合併寫作 $PO(T_1), PO(T_2), ..., PO(T_n)$，可將$T_1$ 視為是根以及左子樹，$T_2, T_3, ..., T_n$ 視為右子樹，顯然的，$T_1$ 在其他樹的元素前先做了前序走訪，重複這個假設，我們可以得到 $T_1, T_2, ..., T_n$ 的前序走訪會與樹林的前序走訪有相同的順序。
:::
---
### 16. 證明一樹林的階層走訪與其對應二元樹的階層走訪，並不一定獲得相同的結果。
:::spoiler
由上圖中樹林的階層順序為 $ABCDEFGHI$ 與二元樹的階層順序為 $ABCDGEHFI$ 不同。以圖5-51 樹林與圖5-53樹林對應的二元樹為例：
樹林的階層走訪為： $ABCDEFGHI$
樹林對應的二元樹之階層走訪為： $ABCDGEHFI$
:::
---
### 17. 以樹林後序走訪法，寫一個非遞迴程序走訪一樹林的對應二元樹。並計算你的程序之時間與空間複雜度。
:::spoiler
```cpp=
void Forest :: postorder()
{ stack<ForestNode*> s;
ForestNode *node = root;
ForestNode *prev = NULL;
while (node != NULL || !s.empty())
{ while (node != NULL)
{ s.push(node);
node = node->leftchild;
}
node = s.top();
if (node->rightchild == NULL || node->rightchild == prev)
{ cout<< node->data<< endl;
s.pop();
prev = node;
node = NULL;
}
else
{ node = node->rightchild;
}
}
}
```
時間複雜度 $O(n)$，$n$ 為樹林中節點的個數。
空間複雜度 $O(n)$，$n$ 為樹林中節點的個數。
:::
---
### 18. 二元樹中的中序和後序順序，可否決定唯一的二元樹？說明或證明之。
:::spoiler
基礎：只有一個節點的樹，其後序與中序相同，因此二元樹是唯一的。
假設：假設 $n$ 為一個大於一的正整數，當樹的節點數少於 $n$ 時，由後序與中序可以得到唯一的二元樹。
推論：使 $T$ 為一個有 $n$ 個節點的樹，使它的後序與中序分別為 $p_1, p_2, ..., p_n$ 和 $i_1, i_2, ...i_n$，後序的最後一個元素為樹根，也就是 $p_n$，找到 $p_n$ 在中序中的位置，稱之為 $i_k$ ，因此，$(i_1, i_2, ..., i_{k-1})$ 與 $(p_1, p_2, ..., p_{k-1})$ 為 T 的左子樹，$(i_{k+1}, i_{k+2}, ..., i_n)$ 與 $(p_k, p_{k+1}, ..., p_{n-1})$ 為 $T$ 的右子樹。
$T$ 的左子樹與右子樹的節點數都少於 $n$，符合假設，也就代表其左子樹與右子樹的後序與中序可以得到唯一的二元樹，因為樹根為唯一的，且左右子樹也為唯一，因此 $T$ 也為唯一的二元樹。
:::
---
### 19. 二元樹中的中序和前序順序，可否決定唯一的二元樹？說明或證明之。
:::spoiler
基礎：只有一個節點的樹，其前序與中序相同，因此二元樹是唯一的。
假設：假設 $n$ 為一個大於一的正整數，當樹的節點數少於 $n$ 時，由前序與中序可以得到唯一的二元樹。
推論：使 $T$ 為一個有 $n$ 個節點的樹，使它的前序與中序分別為 $p_1, p_2, ..., p_n$ 和 $i_1, i_2, ...i_n$ ，前序的第一個元素為樹根，也就是 $p_1$，找到 $p_1$ 在中序中的位置，稱之為 $i_k$ ，因此，$(i_1, i_2, ..., i_{k-1})$ 與 $(p_2, p_3, ..., p_{k})$ 為 $T$ 的左子樹，$(i_{k+1}, i_{k+2}, ..., i_n)$ 與 $(p_{k+1}, p_{k+2}, ..., p_{n})$ 為 $T$ 的右子樹。
$T$ 的左子樹與右子樹的節點數都少於 $n$，符合假設，也就代表其左子樹與右子樹的前序與中序可以得到唯一的二元樹，因為樹根為唯一的，且左右子樹也為唯一，因此 $T$ 也為唯一的二元樹。
:::
---
### 20. 二元樹中的中序和階層順序，可否決定唯一的二元樹？說明或證明之。
:::spoiler
基礎：只有一個節點的樹，其階層順序與中序相同，因此二元樹是唯一的。
假設：假設 $n$ 為一個大於一的正整數，當樹的節點數少於 $n$ 時，由階層順序與中序可以得到唯一的二元樹。
推論：使 $T$ 為一個有 $n$ 個節點的樹，使它的階層順序與中序分別為 $l_1, l_2, ..., l_n$ 和 $i_1, i_2, …, i_n$，階層順序的第一個元素為樹根，也就是 $l_1$，找到 $l_1$ 在中序中的位置，稱之為 $i_k$，因此，$(i_1, i_2, ..., i_{k-1})$ 與其對應的階層順序元素為 $T$ 的左子樹，$(i_{k+1}, i_{k+2}, ..., i_n)$與其對應的階層順序元素為 $T$ 的右子樹。
$T$ 的左子樹與右子樹的節點數都少於 $n$，符合假設，也就代表其左子樹與右子樹的中序與階層順序可以得到唯一的二元樹，因為樹根為唯一的，且左右子樹也為唯一因此 $T$ 也為唯一的二元樹。
:::
---
### 21. 寫一個演算法，以所提供的前序和中序順序，建立出對應的二元樹。
:::spoiler
```cpp=
struct BTreeNode *BTree_InfixPrefix(String infix, String prefix)
{ int k;
struct BTreeNode *node;
if (infix.Length == 0) return NULL;
node = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
node->data = prefix[1];
k = find(prefix[1], infix);
node->leftchild = BTree_InfixPrefix (infix[1, k - 1], prefix[2, k - 1]);
node->rightchild = BTree_InfixPrefix (infix[k + 1, infix.Length - k], prefix[k + 1, prefix.Length - k]);
return node;
}
```
:::
---
### 22. 請証明 $N(h) = F_{h+2}−1，h ≥ 0$。（提示：$F_{0} = 0, F_1=1, F_n=F_{n-1}+F_{n-2}$；數學歸納法）
:::spoiler
基礎：高度為 $0$ 時，為一空樹，最少 $0$ 個節點即可，$F_{0+2}−1 = F_2−1 = 1−1 = 0$，原式成立。
(若原題條件為 $h≥1$，則
基礎：高度為 $1$ 時，為含唯一節點(樹根)的樹，最少正是 $1$ 個節點，$F_{1+2}−1 = F_3−1 = 2−1 = 1$，原式成立。)
假設：高度小於等於 $h−1$ 時該式成立。
推論：考慮高度等於 $h$，最少節點數 $N(h)$ 必定發生在「樹根」之左右子樹高度相差 $1$ 時；不失一般性，令左子樹高度為 $h−1$；右子樹高度為 $h−2$。所以左子樹最少節點個數為 $F_{(h−1)+2}−1 = F_{h+1}−1$；右子樹最少節點個數為 $F_{(h−2)+2}−1 = F_h−1$。
整棵樹需要最少的節點數為 $N(h) = F_{h+1}−1 + F_h−1 + 1 = F_{h+2}−1$。
基於數學歸納法原理可知原式得証。
:::
---
### 23. 實作程式 5-25 新增資料至 AVL 樹中。
:::spoiler
```cpp=
struct AVLTreeNode *NewAVLNode(int x)
{ struct AVLTreeNode *node = new struct AVLTreeNode;
node->data = x;
node->height = 1; //新增的節點必為樹葉
node->leftchild = NULL;
node->rightchild = NULL;
return node;
} //新增節點空間妥善地存放傳入資料；因其必為樹葉，設定其高度為 1
int getBalance(struct AVLTreeNode *p)
{ if (p == NULL) return 0;
return height(p->leftchild) - height(p->rightchild);
} // 計算指標 p 所指向節點的平衡因子
struct AVLTreeNode *InsertAVLTree(struct AVLTreeNode *node, int x)
{ if (node == NULL) return NewAVLNode(x);
if (x<node->data)
node->leftchild = InsertAVLTree(node->leftchild, x);
else
node->rightchild = InsertAVLTree(node->rightchild, x);
node->height = MAX(height(node->leftchild),
height(node->rightchild)) + 1; //更新 node 節點的高度
int balance = getBalance(node);
if (balance > 1 && x < node->leftchild->data) //LL 型
return rightRotate(node);
if (balance < -1 && x > node->rightchild->data) //RR 型
return leftRotate(node);
if (balance > 1 && x > node->leftchild->data) //LR 型
{ node->leftchild = leftRotate(node->leftchild);
return rightRotate(node);
}
if (balance < -1 && x < node->rightchild->data) //RL 型
{ node->rightchild = rightRotate(node->rightchild);
return leftRotate(node);
}
return node; //return the (unchanged) node pointer
}
```
:::
---
### 24. 實作程式 5-26 自 AVL 樹中刪除資料；並請舉例說明程序 DeleteAVLTree 可能執行一次以上的旋轉以保持樹的平衡。
:::spoiler
```cpp=
struct AVLTreeNode *InorderAVLSucc(struct AVLTreeNode *node)
{ struct AVLTreeNode * p;
for (p = node->rightchild; p->leftchild != NULL; p = p->leftchild);
return p;
} // 在 AVL 樹中尋找 node 節點資料的中序直接後繼元素
struct AVLTreeNode *DeleteAVLTree(struct AVLTreeNode *node, int x)
{ struct AVLTreeNode *temp;
if (node == NULL) return node;
if (x < node->data)
node->leftchild = DeleteAVLTree(node->leftchild, x);
else if (x > node->data)
node->rightchild = DeleteAVLTree(node->rightchild, x);
else // x found in node
{ if ((node->leftchild == NULL) || (node->rightchild == NULL))
{ temp = node->leftchild ? node->leftchild : node->rightchild;
if (temp == NULL)
{ temp = node;
node = NULL;
}
else *node = *temp;
free(temp);
}
else
{ temp = InorderAVLSucc(node->rightchild);
node->data = temp->data;
node->rightchild = DeleteAVLTree(node->rightchild, temp->data);
}
}
if (node == NULL) return node;
node->height = MAX(height(node->leftchild), height(node->rightchild)) + 1;
int balance = getBalance(node);
if (balance > 1 && getBalance(node->leftchild) >= 0) //LL
return rightRotate(node);
if (balance > 1 && getBalance(node->leftchild) < 0) //LR
{ node->leftchild = leftRotate(node->leftchild);
return rightRotate(node);
}
if (balance < -1 && getBalance(node->rightchild) <= 0) //RR
return leftRotate(node);
if (balance < -1 && getBalance(node->rightchild) > 0) //RL
{ node->rightchild = rightRotate(node->rightchild);
return leftRotate(node);
}
return node;
}
```
以下為一次 LR 旋轉的例子：
```cpp=
20 //刪除節點30
/ \
15 25
/ \ \
10 17 30
/
16
==> 20 //對節點15做左旋轉
/ \
15 25
/ \
10 17
/
16
==> 20 //對節點20做右旋轉
/ \
17 25
/
15
/ \
10 16
==> 17 //完成->共計2次旋轉
/ \
15 20
/ \ \
10 16 25
```
:::
---
---
## 第六章 圖形
---
### 1. 證明當我們對一個無向連通圖形 $G$ 執行深先搜尋 DFS（演算法 6-1）時，$T$ 中的所有邊會形成一棵樹。
 首先證明 $G$ 是 connected，若 $G$ 不是 connected，令 $x$ 為 dfs 程序結束後，尚未被標示為 true 的點，既然 $G$ 為 connected，那麼一定存在至少一點連接標示為 true 的某一點和 $x$ 內的某一點，這是矛盾的!(當一點被走訪，所有與其連接的點皆會被標示為 true)所以 $G$ 是 connected。
 接下來我們得證明 $G$ 中沒有 cycle，一開始 $G = ψ$，每當一條 edge$(u,v)$ 要加入 $G$ 時，我們一定是找 visited[$v$] = false 者，然後設 visited[$v$] = true，假設$(u,v)$ 即為令 $G$ 造成 cycle 的 edge，表示當初 visited[$u$] 和 visited[$v$] 皆為 ture，既然兩者皆為 true，我們不可能考慮 $(u,v)$ 的加入，所以 $G$ 不會有 cycle。
---
### 2. 證明如果 $T$ 是無向連通圖形 $G$ 的一棵延展樹，則我們加入一個邊 $e$，$e$ 不屬於 $E_T$，但存在於 $E$，會在 $T$ 上產生一個迴圈。
$G = (V, E), v, v_1, v_2, …, v_n ∈ V$
延展樹 $T = (V, E_T), E_T ⊆ E$
因為 $T$ 中存在一路徑 $e’= u, x_1, x_2, …, x_n,v$，若 $T$ 於任兩點 $u,v ∈ V$ 中加入一邊 $e = (u, v) ∉ E_T$,則會存在一條路徑 $u, x_1, x_2, …, x_n, v, u$ 由 $e’$ 到 $u$ 再經由 $v$ 回到 $u$，使得 $T$ 存在一個迴圈
---
### 3. 假設 $G$ 是一個無向連通圖形。證明 $G$ 裡的邊沒有重複出現在 $G$ 的兩個雙向連通成分 (biconnected component) 裡。
假設 $G$ 裡的邊 $(u, v)$ 重複出現在 2 個雙向連通成分 $C_1$ 和 $C_2$ 中，那麼 $C_1$ 的點可經由 $(u, v)$ 雙向地往返 $C_2$ 的點，反之亦然；於是可將 $C_1$ 和 $C_2$ 組成更大的雙向連通成分—這與「雙向連通成分已是最大子圖」的限制產生矛盾！故 $G$ 裡的邊不會重複出現在 2 個或以上的連通成分。
---
### 4. 證明在一個 $n$ 個頂點的完整圖形上，延展樹的數目最少有 $n^{n−2}$ 個。（提示：Prüfer sequence）
可用長度為 $n-2$ 的 Prüfer sequence 與含 $n$ 個點的樹的命名(不同命名方式的樹即為一棵不同的延展樹)一一對應，而前者即有 $n^{n-2}$ 個。(詳見：https://en.wikipedia.org/wiki/Pr%C3%BCfer_sequence)
亦可利用 Kirchhoff's Matrix-Tree Theorem:
---
### 5. 把 Kruskal 最小成本延展樹的演算法寫成完整的程式。
```cpp=
#include <iostream>
using namespace std;
const int MAXN = 10005;
int n, m, ans;
int fa[MAXN];
struct edge
{ int from, to, weight;
};
struct edge e[MAXN];
int find(int x)
{ if (fa[x] == x) return x;
return fa[x] = find(fa[x]);
}
void merge(int x, int y)
{ fa[find(x)] = find(y);
}
void kruskal()
{ for (int i = 0; i < m - 1; i++)
{ for (int j = 0; j < m - i - 1; j++)
{ if(e[j].weight > e[j + 1].weight)
{ edge temp = e[j];
e[j] = e[j + 1];
e[j + 1] = temp;
}
}
}
for (int i = 0; i < n; i++) fa[i] = i;
for (int i = 0; i < m; i++)
{ int u = e[i].from, v = e[i].to, w = e[i].weight;
if (find(u) == find(v)) continue;
merge(u, v);
ans += w;
}
}
int main()
{ cin >> n >> m;
for (int i = 0; i < m; i++)
{ cin >> e[i].from >> e[i].to >> e[i].weight;
}
kruskal();
cout << ans << endl;
return 0;
}
```
---
### 6. 證明 Prim 演算法可以為所有連通無向圖形建立起最小成本延展樹。
反證法:
假設 $G_0$ 為 prim 所生成的樹，並假設 $G_{min}$ 存在，讓 $cost(G_{min})$ < $cost(G_0)$，則在 $G_{min}$ 中存在 $<u,v>$ 不屬於 $G_0$
將 $<u,v>$ 加入 $G_0$ 中可得一個環，且 $<u,v>$ 不是該環的最長邊；此時產生矛盾 $(<u,v>\in G_{min})$！
因為假設不成立，故命題得證。
---
### 7. 證明 Sollin 演算法可以為所有無向連通圖形建立起最小成本延展樹。
1. 令 $G$ 為一個無向連通圖形。
2. 初始化一個空的最小成本延展樹 $T$。
3. 對於 $G$ 中的每一個節點，建立一個獨立的樹，並將這些樹的根節點加入到一個佇列 $Q$ 中。
4. 重複以下步驟直到 $Q$ 中只剩下一棵樹：
a. 從 $Q$ 中取出一棵樹，假設為 $T_i$。
b. 對於 $T_i$ 中的每一個節點，找出一條連接 $T_i$ 和 $G-T_i$ 中的節點的最小權重邊，假設為 $ei$。
c. 如果 $e_i$ 的兩端點不在同一棵樹中，則將 $e_i$ 加入到 $T$ 中，並將兩棵樹合併為一棵樹。
d. 將合併後的樹的根節點加入到 $Q$ 中。
5. 返回最小成本延展樹 $T$。
根據上述步驟，可以證明 Sollin 演算法可以為所有無向連通圖形建立起最小成本延展樹。因為每次都選擇了每棵樹能夠達到的最小權重邊，並合併了不同的樹，直到只剩下一棵樹為止，所以最終得到的樹一定是最小成本延展樹。此外，由於每棵樹都是獨立的，因此可以處理所有的連通分量，也就是所有的無向連通圖形。
---
### 8. $T$ 是一棵根點為 $v$ 的樹，且 $T$ 上的邊是無方向性的；其上的邊都有非負長度。設計一個演算法來計算從 $v$ 到所有其他點的最短距離。此演算法的複雜度應該是 $O(n)$，其中 $n$ 是圖上的頂點個數。
令 $length[i][j]$ 存放 $(i,j)$ 的權重/距離值，且 $dist[i]$ 存放自 $v$ 到 $i$ 點的最短距離。吾人可用類似深先搜尋的方式，走訪出自 $v$ 到 $i$ 點的最短距離：
```cpp=
void ShortestPath(int node, int weight)
{ dist[node] = weight;
for all the children x of the node
ShortestPath(x, weight + length(node, x));
}
```
主程式呼叫：
```cpp
ShortestPath(v, 0);
```
即可得出 $dist[i], i\in V$。
---
### 9. 利用最短路徑（演算法 6-8、6-9）的概念，設計一個找出最小成本延展樹
### 的演算法，其最糟狀況所花去時間為 $O(n^2)$。
```cpp=
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;
#define MAXN 100000 // 最大節點數
typedef pair<int, int> pii; // pair 的別名
vector<pii> adj[MAXN]; // adjacency list
int dist[MAXN]; // 記錄每個頂點到樹的距離
bool visited[MAXN]; // 記錄每個頂點是否已被加入樹中
void dijkstra(int start)
{ // 初始化距離和訪問狀態
fill(dist, dist + MAXN, INT_MAX);
fill(visited, visited + MAXN, false);
// 建立優先級隊列
priority_queue<pii, vector<pii>, greater<pii>> pq;
// 起點到自己的距離為0
dist[start] = 0;
// 加入起點到優先級隊列中
pq.push(make_pair(0, start));
while (!pq.empty())
{ // 取出優先級隊列中距離最近的頂點
int u = pq.top().second;
pq.pop();
// 如果已經被加入樹中，就跳過
if (visited[u])
{ continue;
}
// 加入樹中
visited[u] = true;
// 更新與 u 相鄰的頂點的距離
for (int i = 0; i < adj[u].size(); i++)
{ int v = adj[u][i].first; // 相鄰頂點
int w = adj[u][i].second; // u 到 v 的權重
// 如果 v 沒有被加入樹中，且通過 u 到達 v 的距離更短，就更新距離
if (!visited[v] && dist[u] + w < dist[v])
{ dist[v] = dist[u] + w;
pq.push(make_pair(dist[v], v)); // 加入優先級隊列中
}
}
}
}
int main()
{ int n, m; // 節點數和邊數
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
// 建立雙向邊
adj[u].push_back(make_pair(v, w));
adj[v].push_back(make_pair(u, w));
}
// 從 1 號節點開始找最小成本延展樹
dijkstra(1);
// 輸出每個頂點到樹的距離
for (int i = 1; i <= n; i++) {
cout << "dist[" << i << "] = " << dist[i] << endl;
}
return 0;
}
```
---
### 10. 利用圖 6-53 的有向圖形，解釋為什麼所提的最短路徑演算法不能正常執行？由 $0$ 到 $5$ 的最短路徑為何？
(1)
圖形中不能有負號，否則可能會導致找到的下一個值愈變愈小，換句話說就是走的路增加，但是距離總合卻減少。
(2)
迴圈到第 3 步驟時，開始有問題產生，此時 $0$ -> $1$ 的最短距離依演算法確定為 $2$，但實際上距離為 $1$。
從 $0$ 到 $5$ 的最短路徑由演算法應該是 $0$ -> $1$ -> $3$ -> $5$ (長為 $11$)，但實際上 $0$ -> $2$ -> $1$ -> $3$ -> $5$ (長為 $10$)才是最短距離。因為 $0$ -> $1$ 的最短距離無法自演算法確定； 遂正確距離 $0$ -> $2$ -> $1$ -> $3$ -> $5$ (長為 $10$)不會被找出。
---
### 11. 實作任意兩點間最短路徑的程式。
```cpp=
# include <iostream>
using namespace std;
int main()
{ int n, w[100][100], A[100][100], a, b;
cin >> n;
for (int i = 0; i < n; i++)
{ for (int j = 0; j < n; j++) cin >> w[i][j];
}
for (int i = 0; i < n; i++)
{ for (int j = 0; j < n; j++) A[i][j] = w[i][j];
}
for (int k = 0; k < n; k++)
{ for (int i = 0; i < n; i++)
{ for (int j = 0; j < n; j++)
if (A[i][k] + A[k][j] < A[i][j] && i != j)
A[i][j] = A[k][j] + A[i][k];
}
}
cin >> a >> b;
cout << A[a][b];
}
```
---
### 12. 演算法 6-13 是 Stephen Barnard 所寫，用在一個沒有任何奇數分支度頂點的連通無向圖形，可以找出該圖的尤拉迴路。 <br>   (a) 證明當 $G$ 以相鄰複合串列表示，且路徑以鏈結串列表示時，這個Eu1erCircuit 程序可以在 $O(n+e)$ 的時間內完成。 <br>   (b) 利用數學歸納法證明：這個演算法可以為任何有尤拉迴路的圖形找出其尤拉迴路，而用來呼叫 Eu1erCircuit 程序的起始值可以是圖中任何一個點。 <br>   (c\) 判斷應該要做些什麼，才能知道 $G$ 是否有尤拉迴路？
```cpp=
/*演算法 6-13 找尤拉迴路（用在沒有任何奇數分支度頂點的連通無向圖形）：*/
Path EulerCircuit(vertex v)
{ Path path = ∅;
for ((all w adjacent to v) && ((v, w) not yet used))
{ mark edge (v, w) as used;
path = {(v, w)} ∪ EulreCircuit(w) ∪ path;
}
return path;
}
```
(a)
這個程序使用了遞迴來遍歷圖的所有邊，將它們組合成一個歐拉迴路。因為每條邊只被標記一次，所以在每次遞迴中，都會至少標記一條邊。因此，程序的時間複雜度取決於總共需要標記多少邊。
從一個頂點 $v$ 開始，我們可以利用相鄰複合串列表依次遍歷 $G$ 中的每個邊。當我們到達一個新的頂點 $w$ 時，我們可以將 $(v, w)$ 標記為已使用，並遞迴地尋找以 $w$ 為起點的歐拉迴路。由於每條邊最多被標記一次，所以總共需要遍歷的邊數是 $O(e)$。
當我們遍歷完所有的邊後，我們可以按照遞迴的順序將它們組合成一個歐拉迴路。因為每條邊最多被標記一次，所以歐拉迴路的長度也是 $O(e)$。
因此，整個程序的時間複雜度是 $O(n+e)$。
(b)
Basis Step：當圖形只有一個頂點時，它的尤拉迴路就是它自己。因此Basis Step成立。
Introduction Step：假設對於任何有尤拉迴路的圖形，演算法都可以找出其尤拉迴路，而用來呼叫程序的起始值可以是圖中任何一個點。現在考慮一個有尤拉迴路的圖形 $G$，我們要證明演算法也可以找出它的尤拉迴路。
我們假設 $G$ 的尤拉迴路為 $v_1, v_2, ..., v_k$。根據尤拉迴路的定義，從任何一個頂點出發，我們可以依次經過所有的邊，最終回到起點。因此，從 $vi$ 出發，我們可以找到一條經過所有未被使用的邊的路徑 $P$，使得 $P$ 的終點是 $v_j$。
現在考慮圖形 $G'$，其中我們標記了所有在 $P$ 上的邊和從 $P$ 的終點開始遍歷時遍歷過的邊。根據標記的邊和未被使用的邊的定義，$G'$ 中每個連通分量都是有尤拉迴路的。此外，由於 $P$ 上的邊都被標記了，因此 $G'$ 中所有的邊都被標記了。因此，$G'$ 的所有連通分量都是完整的，即每條邊都在某一個環中。
現在我們選擇 $G'$ 中任意一個連通分量 $C$，並從其中選擇一個點作為起點。根據演算法，我們可以找到 $C$ 的一條尤拉迴路。將這個尤拉迴路添加到 $P$ 中，我們得到一個新的路徑 $P'$，它從 $v_i$ 出發，經過所有未被使用的邊和從 $P$ 的終點開始遍歷時遍歷過的邊，最終回到 $v_j$。重複這個步驟，直到所有的邊都被使用，我們就得到了一個經過所有邊的路徑，它的起點和終點都是相同的，即為尤拉迴路。
由於 $G'$ 中所有的連通分量都是有尤拉迴路的，因此在執行演算法時，我們一定會選擇每個連通分量的尤拉迴路。因此，演算法可以找到 $G$ 的尤拉迴路。
因此，根據數學歸納法原理，這個演算法可以為任何有尤拉迴路的圖形找出其尤拉迴路，而用來呼叫程序的起始值可以是圖中任何一個點。
(c\)
計算每個節點的度數（即與節點相連的邊的數量），如果所有節點的度數都是偶數，那麼 $G$ 有尤拉迴路。如果有兩個節點的度數是奇數，那麼 $G$ 沒有尤拉迴路。
---
### 13. 給定一個 $n$ 個頂點的完全連通圖形，證明任意兩點間可能擁有的最多路徑數目是 $O((n−1)!)$。
令 $G = (V, E)$ 為完備圖 (complete graph)，$n = |V|$。既是任意兩點，不失一般性，令為點 1 和 2—考量其間的路徑個數。包含邊數為 1 的路徑只有一個（即 (1, 2)）；而包含兩條邊者（起點 1 終點 2 已固定；點 1 不能連到點 2）有 $n-2$ 個可能（每個可能皆可有邊連到點2）；包含三條邊者，有 $(n-2)(n-3)$ 個可能；依此類推，包含 $n-1$ 條邊者，有 $(n-2)!$ 個可能。整理如下表：
| 邊數 | $1$ | $2$ | $3$ | $...$ | $n-3$ | $n-2$ | $n-1$ |
|-----|---|---|---|-----|-----|-----|-----|
| 可能路徑數 | $1$ | $n-2$ | $(n-2)(n-3)$ | ... | $(n-2)(n-3)...3$ | $(n-2)(n-3)...2$ | $(n-2)(n-3)...1$ |
| 整理 | $\frac{(n-2)!}{(n-2)!}$ | $\frac{(n-2)!}{(n-3)!}$ | $\frac{(n-2)!}{(n-4)!}$ | ... | $\frac{(n-2)!}{2!}$ | $\frac{(n-2)!}{1!}$ | $\frac{(n-2)!}{0!}$ |
所有路徑個數為：
$(n-2)! + \frac{(n-2)!}{1!} + \frac{(n-2)!}{2!} + … + \frac{(n-2)!}{(n-3)!} + 1
= (n-2)! + (n-2)! [1 + \frac{1}{2!} + \frac{1}{3!} + … + \frac{1}{(n-2)!}]$
當 $n$ 趨近於無限大時，$[1 + 1/2! + 1/3!+ … + 1/n!] = e – 1$，而 $e = 2.718$。
於是所有路徑個數為 $c (n-2)!$ $(<(n-1)!\text{）}$，其中 $c$ 為常數，故任意兩點間可能擁有的最多路徑數目是 $O((n-1)!)$
---
### 14. 一個「二分圖形」(bipartite graph)，$G = (V, E)$ 是指一個無向圖形，其頂點可以被分為兩個不相交的集合 $A$ 以及 $B (= V−A)$，而有以下特性： <br>   (1) $A$ 集合中的任意兩點在 $G$ 上都不相鄰。 <br>   (2) $B$ 集合中的任意兩點在 $G$ 上都不相鄰。 <br> 圖 6-7 的 $G_3$ 就是一個二分圖形，其中一個可能的分法是 $G_A = \{A, E, F, G\}$，$G_B = \{B, C, D\}$。 證明 $G$ 是一個二分圖形若且唯若 $G$ 中沒有奇數長度的迴圈。
已知 $G = (V_1 ∪ V_2, E)$ 為一二分圖形；若 $C$ 為 $G$ 中長度為 $n-1$ 的一個奇數長度迴圈 ($n$ 為偶數)， 即 $C = v_1-v_2-v_3- … -v_{n-1}-v_1$。因為二分圖形中，同一群組必無路徑相通；所以 $v$ 令 $v_1∈V_1，v_2∈V_2，v_3∈V_1，v_4∈V_2 ， … ，v_{n-1}∈V_1，v_1∈V_1$ 則可得 $v_{n-1}∈V_1$ 且 $v_1∈V_1$ 與假設 $C$ 為迴圈矛盾，故不存在 奇數迴圈。
同理，若 $C$ 中不存在奇數迴圈，則迴圈中相鄰的點會被分在不同群組，為二 分圖形的條件
---
### 15. 設計一個演算法判斷圖形 $G$ 是否為二分圖形，如果 $G$ 是二分圖形則你的演算法應該要傳回該圖的兩個二分集合。證明如果以相鄰串列表示圓形，這個演算法可以在 $O(n+e)$ 的時間內完成，其中 $n$ 是頂點數， $e$ 是邊數。
input:
(1) 以任意一點為起點，令此點為 $0$
(2) 將此點所有連接之點設為 $1$
(3) 檢查為 $1$ 的點所連接之點，若為 $1$ 則非雙分圖；否則令為 $0$
(4) 檢查為 $0$ 的點所連接之點，若為 $0$ 則非雙分圖；否則令為 $1$
(5) 重複(3)(4)若所有點都檢查過且都符合條件，則為雙分圖
建立一個矩陣 A 存放相鄰串列
建立一個矩陣 label 存放群組組別 ($0$ 或 $1$)
```cpp=
input: G = (V, E)
output: G 是否為二分圖形
select x ∊ E
X = {x}; Y = V - X
label[x] = 0;
while ( X ∪ Y ≠ V )
{ for ( each x ∊ X )
for ( each y ∊ Y where (x, y) ∊ E and label[y] is undefined)
{ label[y] = 1;
Y = Y ∪ {y};
}
if (no such y) break;
for (each y∊Y)
for (each z ∊ (V - Y - X) where (y, z) ∊ E and label[z] is undefined)
{ label[z] = 0;
X = X ∪ {z};
}
if (no such z) break;
}
return (X ∪ Y == V) ? 1 : 0; // 1:G is bipartite; 0:G is NOT
```
相鄰串列表的建立過程需要對每條邊進行一次操作，將邊的端點加入相鄰串中，因此建立相鄰串列表的時間複雜度是 $O(e)$。
接下來，我們使用上面的演算法來判斷圖形是否為二分圖形。該演算法需要進行一次深度優先搜索，對於每個節點，最多需要訪問其一次。
因此，該演算法的時間複雜度是 $O(n+e)$。
---
### 16. 證明每一棵樹都是二分圖形。
令樹為 $T = (V, E)，|V| = n，|E| = n-1$。考量集合 $S_1$ 和 $S_2$ —將樹中奇（偶）數階層的點存放至 $S_1 (S_2)$，此時 $S_1∪S_2 = V$；並保留 $E$ 中所有邊。先觀察奇數階層的點 $a$ 和 $b (a, b∈S_1)$，若它們處於同一階層（互為兄弟）自然不會有邊連接；若它們在不同階層，也不存在連接 $a$ 和 $b$ 的邊 $(a, b)$（否則造成迴圏— $a$ 透過樹根與 $b$ 有路徑相連，若存在 $(a, b)$ 則形成樹上的迴圏—違反樹的性質）。偶數階層的點亦有相同性質。並且所有邊皆自 $S_1$ 連向 $S_2$，於是 $G = (S_1∪S_2, E)$ 是二分圖形。
根據 15 題，每一棵樹皆無基數長度的迴圈，故每一棵樹都是二分圖形。
---
### 17. 給定一個無向連通圖形 $G$，所有邊長皆為 $1$，設計一個函式利用廣先搜尋找出 $G$ 的延展樹。
```cpp=
struct spNode // Adjacent list for spanning tree T
{ int u;
int v;
};
struct spList
{ struct spNode *link;
};
struct spList T[n];
struct edgeNode // Adjacent list for input graph G
{ int u;
int v;
struct edgeNode *next;
};
struct vertexList
{ struct edgeNode *edge;
};
struct vertexList G[n];
void addAsFirst(struct spNode *first, struct spNode *q)
{ q->next = first->next;
first->next = q;
}
struct spNode *newSPNode(edgeNode *p)
{ struct spNode *q = new struct spNode;
q->u = p->u; q->v = p->v;
return q;
}
void BFSSP(int u) // 以 u 為起點做 BFS
{ int v, i, visited[SIZE];
struct spNode *q;
for (i = 0; i < n; i++) visited[i] = 0;
visited[u] = 1;
T[u].link = NULL;
Add_Queue(u);
while (Queue 仍有頂點資料)
{ v = Delete_Queue();
for (p = G[v].edge; p; p = p->next) // 所有與 v 相鄰的頂點 w)
{ if (visited[p->v] == 0)
{ visited(p->v) = 1;
q = newSPNode(p);
addAsFirst(T[u].link, q);
Add_Queue(p->v);
}
}
}
// T[u].edge 所指串列即為 “以 u 為起點做 BFS 後延展樹邊” 的集合;
}
```
---
### 18. 「圖直徑」(diameter of a graph) 是指任意兩點間最大距離。給定一個
### 無向連通圖形 $G$，所有邊長皆為 $1$，設計一個函式利用找出 $G$ 的直徑。
```cpp=
struct spNode // Adjacent list for spanning tree T
{ int u, v;
int level;
int from;
int maxDistance;
};
struct spList
{ int radius;
struct spNode * link;
};
struct spList T[n];
struct edgeNode // Adjacent list for input graph G
{ int u, v;
struct edgeNode *next;
};
struct vertexList
{ struct edgeNode *edge;
};
struct vertexList G[n];
int maxDist[n][n];
int from[n][n];
void addAsFirst(struct spNode *first, struct spNode *q)
{ q->next = first->next;
first->next = q;
}
struct spNode *newSPNodeLevel(edgeNode *p, int level)
{ struct spNode *q = new struct spNode;
q->u = p->u; q->v = p->v;
q->level = level + 1;
return q;
}
int maxDistBFSSP(int u) // 以 u 為起點做 BFS
{ int v, i, j, visited[SIZE], level, maxDist;
struct spNode *q;
for (i = 0; i < n; i++)
{ visited[i] = 0;
for (j = 0; j < n; j++) D[][] = ;
}
visited[u] = 1;
T[u].radius = 0;
T[u].link = NULL; level = maxDist = 0;
Add_Queue(u, level);
while (Queue 仍有頂點資料)
{ (v, level, maxDist) = Delete_Queue();
for (p = G[v].edge; p; p = p->next) // 所有與 v 相鄰的頂點 w)
{ if (visited[p->v] == 0) // 自 u bfs 首次經過 p->v
{ visited(p->v) = 1;
q = newSPNodeLevel(p, level); // 串在 T[u].link
addAsFirst(T[u].link, q);
Add_Queue(p->v, q->level);
if (q->level>T[u].radius) T[u].radius = q->level;
maxDist[p->u][p->v] = q->level;
}
else // 自 u bfs 再次來到 p->v
{ if (maxDist[p->u][p->v] < maxDist[u][p->u] + 1)
{ maxDist[p->u][p->u] = maxDist[u][p->u] + 1;
from[p->u][p->u] = p->u;
}
}
}
}
return T[u].radius;
}
int findSPMaxDiameter()
{ int i, j, r, maxDiam = -1, maxVertA, maxVertB ;
for (i = 0; i < n; i++) maxDistBFSSP(i);
for (i = 0; i < n; i++)
{ for (j = 0; j < n; ++)
{ if (maxDist[i][j] > maxDiam)
{ maxDiam = maxDist[i][j];
maxVertA = i;
maxVertB = j;
}
}
}
return maxDiam; // maxDist[maxVertA][maxVertB] = maxDiam
}
```
---
### 19. 一棵樹的「半徑」(radius) 是指從根節點到其中某個葉 (leaf) 的最長長
### 度。給定一個無向連通圖形 $G$，所有邊長皆為 $1$，設計一個函式找出 $G$ 中有
### 最小半徑的延展樹。
```cpp=
struct spNode // Adjacent list for spanning tree T
{ int u, v;
int level;
};
strut spList
{ int radius;
struct spNode *link;
};
struct spList T[n];
struct edgeNode // Adjacent list for input graph G
{ int u, v;
struct edgeNode *next;
};
struct vertexList
{ struct edgeNode *edge;
};
struct vertexList G[n];
void addAsFirst(struct spNode *first, struct spNode *q)
{ q->next = first->next;
first->next = q;
}
struct spNode *newSPNodeLevel(edgeNode *p, int level)
{ struct spNode *q = new struct spNode;
q->u = p->u; q->v = p->v;
q->level = level+1;
return q;
}
int radiusBFSSP(int u) // 以 u 為起點做 BFS
{ int v, i, visited[SIZE], level;
struct spNode *q;
for (i = 0; i < n; i++) visited[i] = 0;
visited[u] = 1;
T[u].radius = 0;
T[u].link = NULL;
Add_Queue(u, 0);
while (Queue 仍有頂點資料)
{ (v, level) = Delete_Queue();
for (p = G[v].edge; p; p = p->next) // 所有與 v 相鄰的頂點 w)
{ if (visited[p- > v] == 0)
{ visited(p- > v) = 1;
q = newSPNodeLevel(p, level);
addAsFirst(T[u].link, q);
Add_Queue(p- > v, q->level);
if (q->level > T[u].radius) T[u].radius = q->level;
}
}
}
return T[u].radius;
}
int findSPMinRadius()
{ int i, r, minSPRadius = MAXINT, minSPRoot;
for (i=0; i < n; i++)
{ if ((r = radiusBFSSP(i)) < minSPRadius)
{ minSPRoot = i;
minSPRadius = r;
}
}
return minSPRoot; // minSPRadius 即為 T[minSPRoot].radius
}
```
---
### 20. 給定一個無向連通圖形 $G$，所有邊長皆為 $1$，設計一個函式找出 $G$ 中有
### 最大直徑的延展樹。
```cpp=
struct spNode // Adjacent list for spanning tree T
{ int u, v;
int level;
};
strut spList
{ int radius;
struct spNode *link;
};
struct spList T[n];
struct edgeNode // Adjacent list for input graph G
{ int u, v;
struct edgeNode *next;
};
struct vertexList
{ struct edgeNode *edge;
};
struct vertexList G[n];
void addAsFirst(struct spNode *first, struct spNode *q)
{ q->next = first->next;
first->next = q;
}
struct spNode *newSPNodeLevel(edgeNode *p, int level)
{ struct spNode *q = new struct spNode;
q->u = p->u; q->v = p->v;
q->level = level + 1;
return q;
}
int radiusBFSSP(int u) // 以 u 為起點做 BFS
{ int v, i, visited[SIZE], level;
struct spNode *q;
for (i = 0; i < n; i++) visited[i] = 0;
visited[u] = 1;
T[u].radius = 0;
T[u].link = NULL;
Add_Queue(u, 0);
while (Queue 仍有頂點資料)
{ (v, level) = Delete_Queue();
for (p = G[v].edge; p; p = p->next) // 所有與 v 相鄰的頂點 w)
{ if (visited[p->v] == 0)
{ visited(p->v) = 1;
q = newSPNodeLevel(p, level);
addAsFirst(T[u].link, q);
Add_Queue(p->v, q->level);
if (q->level > T[u].radius) T[u].radius = q->level;
}
}
}
return T[u].radius;
}
int findSPMaxRadius()
{ int i, r, maxSPRadius = -1, maxSPRoot;
for (i=0; i<n; i++)
{ if ((r = radiusBFSSP(i)) > maxSPRadius)
{ maxSPRoot = i;
maxSPRadius = r;
}
}
return maxSPRoot; // maxSPRadius 即為 T[maxSPRoot].radius
}
```
---
---
## 第七章 排序
---
### 1. 請比較下列排序演算法的異同： <br>   (a) 挑選排序、氣泡排序和插入排序。 <br>   (b) Shell 排序和合併排序。
(a)
| |額外儲存空間|時間複雜度|穩定性|
|:------:|:------:|:------:|:------:|
| 挑選排序 | $O(1)$ | $O(n^2)$ | X |
| 氣泡排序 | $O(1)$ | $O(n^2)$ | O |
| 插入排序 | $O(1)$ | $O(n^2)$ | O |
(b)
| |額外儲存空間|時間複雜度|穩定性|
|:------:|:------:|:------:|:------:|
| Shell排序 | $O(1)$ | $O(n log^2n)$ | X |
| 合併排序 | $O(n)$ | $O(nlogn)$ | O |
註：$O(nlog^2n)$ 為 Shell排序 的 average case time complexity；在好的 $h_k$ 挑選下可期望在 $O(nlogn)$ 下完成。
---
### 2. 請實作本章所提的所有排序演算法。請以亂數產生欲排序的資料，記錄不同資料量 ($n$) 下，各演算法執行排序所需的時間；做出圖表（$n$ 值為 x 軸，時間為 y 軸），觀察並討論不同演算法在不同資料量下執行排序的表現。
Selection Sort 不管是好壞的情況時間複雜度皆為 $(n^2)$。
Insert Sort 若是好的情況則為 $O(n)$，不好則是 $O(n^2)$ 故會和 Selection Sort 有差不多的表現或比他好。
Bubble Sort 所花費的時間會是最高的不管資料量多寡。
Quick Sort、Merge Sort、Heap Sort 和 Radix Sort 皆為快速的排序，所以會需要更大筆的資料才有辦法更清楚的分出其差別。
---
### 3. 請說明本章所有排序演算法在輸入數列以下面兩種排序時的表現： <br>   (a) 排序完成 <br>   (b) 反向排序完成
| 排序法 |排序完成|反向排序完成|
|:------:|:------:|:------:|
| 挑選排序 | $O(n^2)$ | $O(n^2)$ |
| 插入排序 | $O(n)$ | $O(n^2)$ |
| 氣泡排序 | $O(n)$ | $O(n^2)$ |
|Shell排序| 與資料是否已排序無關 |
| 合併排序 | 與資料是否已排序無關，皆為 $O(nlogn)$ |
| 快速排序 | $O(n^2)$ | $O(n^2)$ |
| 基數排序 | 與資料是否已排序無關，皆為 $O(nlogn)$ |
| 堆積排序 | 與資料是否已排序無關，皆為 $O(nlogn)$ |
---
### 4. 請實作不同版本的基數排序法： <br>   (a) 以 $10$ 佇列存放各個位數排序的結果 <br>   (b) 用陣列來模擬 (a)。 <br>   並利用題 2 的實驗設計製作圖表，觀察並討論實驗結果。
(a)
```cpp=
#include <iostream>;
using namespace std;
struct LNode
{ int val;
LNode *next{0};
LNode() :next(0) {}
};
LNode *radixsort(LNode *L, int t)
{ int i, j, d, m = 1;
LNode *temp, *head[10], *tail[10];
for (j = 1; j <= t; j++)
{ for (i = 0; i <= 9; i++)
{ head[i] = 0;
tail[i] = 0;
}
while (L)
{ d = static_cast<int>(L->val / m) % 10;
temp = L;
L = L->next;
temp->next = 0;
if (head[d])
{ tail[d]->next = temp;
tail[d] = temp;
}
else
{ head[d] = temp;
tail[d] = temp;
}
}
d = 0;
while (!head[d]) d++;
L = head[d];
temp = tail[d];
d++;
while (d < 10)
{ if (head[d])
{ temp->next = head[d];
temp = tail[d];
}
d++;
}
m = m * 10;
}
return L;
}
int main()
{ int c, m, k = 0;
int n[100];
int i, max = -1, t = 0;
LNode *start = 0, *end = 0, *temp = 0;
cin >> c;
while (cin>>m, k<c)
{ n[k++] = m;
if (k == c) break;
}
for (i = 0; i < c; i++)
{ if (n[i] > max) max = n[i];
temp = new LNode();
temp->val = n[i];
if (start)
{ end->next = temp;
end = temp;
}
else
{ start = temp;
end = temp;
}
}
while (max > 0)
{ t = t + 1;
max = max / 10;
}
start = radixsort(start, t);
temp = start;
while (temp)
{ cout << temp->val << " ";
temp = temp->next;
}
cout << "\n";
}
```
(b)
```cpp=
# include <iostream>
using namespace std;
int maxbit(int n)
{ int d = 1, p = 10;
while ( n >= p)
{ n /= 10;
d++;
}
return d;
}
int main()
{ int n;
cin >> n;
int data[100], cot[100], index[100], temp[100];
int Max = 0, k;
for (int i = 0; i < n; i++)
{ cin >> data[i];
if ( data[i] > Max ) Max = data[i];
}
int radix = maxbit(Max);
for (int i = 1; i <= radix; i++)
{ for (int j = 0; j < 10; j++) cot[j] = 0;
for (int j = 0; j < n; j++)
{ k = (data[j] / radix) % 10;
cot[k]++;
}
index[0] = 0;
for (int j = 1; j <= 10; j++) index[j] = index[j - 1] + cot[j - 1];
for (int j = 0; j < n; j++)
{ k = (data[j] / radix) % 10;
temp[index[k]++] = data[j];
}
for (int j = 0; j < n; j++) data[j] = temp[j];
radix *= 10;
}
for (int j = 0; j < n; j++) cout << data[j] << " ";
cout << endl;
}
```
---
### 5. 請實作不同版本的快速排序法： <br>   (a) 遞迴版 <br>   (b) 利用堆疊和以迴圈控制版 <br>   (c\) 當 left~right 間的資料量少於 $10$ 時，直接用挑選或排序；不必再遞迴呼叫（或 push 入堆疊） <br>   (d) 取一個 $0$ ~ $n−1$ 的亂數 $i$，令 $target$ 為 $data[i]$ <br>   (e) 令 $target$ 為 $data[0]$、$data[n/2]$ 和 $data[n-1]$ 的中位數。 <br>   並利用題 2 的實驗設計製作圖表，觀察並討論實驗結果。
(a)
```cpp=
# include <iostream>
using namespace std;
void swap(int *x, int *y)
{ int t;
t = *x;
*x = *y;
*y = t;
}
void Quick(int data[], int left, int right)
{ int i, j, target;
if(left < right)
{ i = left + 1;
j = right;
target = data[left];
do
{ while((data[i] < target) && (i <= j)) i++;
while((data[j] >= target) && (i <= j)) j--;
if(i < j) swap(&data[i], &data[j]);
}while(i < j);
if(left < j)
swap(&data[left], &data[j]);
Quick(data, left, j - 1);
Quick(data, j + 1, right);
}
}
int main()
{ int n, i, count = 1;
int data[100], temp[100];
cin >> n;
for (i = 0; i < n; i++) cin >> data[i];
Quick(data, 0, n-1);
for (i = 0; i < n; i++) cout << data[i] << " ";
cout << endl;
}
```
(b)
```cpp=
# include <iostream>
using namespace std;
void swap(int *x, int *y)
{ int t;
t = *x;
*x = *y;
*y = t;
}
int top = -1;
struct StackNode
{ int l, r;
}*stack;
void push(int left, int right)
{ stack[++top].l = left;
stack[top].r = right;
}
struct StackNode *pop()
{ struct StackNode *p = new StackNode;
*p = stack[top--];
return p;
}
void QuickSort(int data[], int n)
{ stack = new StackNode[n];
int left = 0;
int right = n - 1;
int i, j, target;
push(left, right);
while(top != -1)
{ struct StackNode *p = pop();
left = p->l;
right = p->r;
target = data[left];
i = left + 1;
j = right;
do
{ while((data[i] < target) && (i <= j))
i++;
while((data[j] >= target) && (i <= j))
j--;
if(i < j)
swap(&data[i], &data[j]);
}while(i < j);
if(left < j)
swap(&data[left], &data[j]);
if((j + 1) < right)
push(j + 1, right);
if(left < (j - 1))
push(left, j - 1);
}
}
int main()
{ int n, i, count = 1;
int data[100], temp[100];
cin >> n;
for (i = 0; i < n; i++)
{ cin >> data[i];
}
QuickSort(data, n);
for (i = 0; i < n; i++)
{ cout << data[i] << " ";
}
cout << endl;
}
```
(c\)
```cpp=
# include <iostream>
using namespace std;
void swap(int *x, int *y)
{ int t;
t = *x;
*x = *y;
*y = t;
}
int top = -1;
struct StackNode
{ int l, r;
}*stack;
void push(int left, int right)
{ stack[++top].l = left;
stack[top].r = right;
}
struct StackNode *pop()
{ struct StackNode *p = new StackNode;
*p = stack[top--];
return p;
}
void QuickSort(int data[], int n)
{ stack = new StackNode[n];
int left = 0;
int right = n - 1;
if(n < 10)
{ for(int i = 0; i < n; i++)
{ int min = i;
for(int j = i + 1; j < n; j++)
{ if(data[j] < data[min])
{ min = j;
}
}
int temp = data[i];
data[i] = data[min];
data[min] = temp;
}
return;
}
int i, j, target;
push(left, right);
while(top != -1)
{ struct StackNode *p = pop();
left = p->l;
right = p->r;
if((right - left) < 10)
{ int range = right - left + 1;
for(int i = 0; i < range; i++)
{ int min = i;
for(int j = i + 1; j < range; j++)
{ if(data[j] < data[min])
{ min = j;
}
}
int temp = data[i];
data[i] = data[min];
data[min] = temp;
}
continue;
}
target = data[left];
i = left + 1;
j = right;
do
{ while((data[i] < target) && (i <= j))
i++;
while((data[j] >= target) && (i <= j))
j--;
if(i < j)
swap(&data[i], &data[j]);
}while(i < j);
if(left < j)
swap(&data[left], &data[j]);
if((j + 1) < right)
push(j + 1, right);
if(left < (j - 1))
push(left, j - 1);
}
}
int main()
{ int n, i;
int data[100];
cin >> n;
for (i = 0; i < n; i++)
{ cin >> data[i];
}
QuickSort(data, n);
for (i = 0; i < n; i++)
{ cout << data[i] << " ";
}
cout << endl;
}
```
(d)
```cpp=
# include <cstdlib>
# include <time.h>
# include <iostream>
using namespace std;
int partition(int arr[], int left, int right)
{ int pivot = arr[right];
int i = (left - 1);
for (int j = left; j <= right - 1; j++)
{ if (arr[j] <= pivot)
{ i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[right]);
return (i + 1);
}
int partition_r(int arr[], int left, int right)
{ srand(time(NULL));
int random = left + rand() % (right - left);
swap(arr[random], arr[right]);
return partition(arr, left, right);
}
void quickSort(int arr[], int left, int right)
{ if (left < right)
{ int pi = partition_r(arr, left, right);
quickSort(arr, left, pi - 1);
quickSort(arr, pi + 1, right);
}
}
void printArray(int arr[], int size)
{ int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
}
int main()
{ int n;
cin >> n;
int arr[100];
for (int i = 0; i < n; i++)
cin >> arr[i];
quickSort(arr, 0, n - 1);
cout << "Sorted array:";
printArray(arr, n);
return 0;
}
```
(e)
```cpp =
#include <cstdlib>
#include <iostream>
using namespace std;
int partition(int arr[], int left, int right)
{ int pivot = arr[right];
int i = (left - 1);
for (int j = left; j <= right - 1; j++)
{ if (arr[j] <= pivot)
{ i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[right]);
return (i + 1);
}
int partition_r(int arr[], int left, int right)
{ int mid, a = arr[left], b = arr[(right - left) / 2], c = arr[right - 1];
if (a >= b && a <= c || a <= b && a >= c)
mid = a;
else if (b >= a && b <= c || b <= a && b >= c)
mid = b;
else
mid = c;
swap(arr[mid], arr[right]);
return partition(arr, left, right);
}
void quickSort(int arr[], int left, int right)
{ if (left < right)
{ int pi = partition_r(arr, left, right);
quickSort(arr, left, pi - 1);
quickSort(arr, pi + 1, right);
}
}
void printArray(int arr[], int size)
{ int i;
for (i = 0; i < size; i++)
cout << arr[i] << " ";
}
int main()
{ int n;
cin >> n;
int arr[100];
for (int i = 0; i < n; i++)
{ cin>>arr[i];
}
quickSort(arr, 0, n - 1);
cout << "Sorted array:";
printArray(arr, n);
return 0;
}
```
---
### 6. 請實作不同版本的 Shell 排序法： <br>   (a) 以 $1, 4, 13, 40, 121, …$ 為遞增分組數列 <br>   (b) 以 $1, 2, 4, 8, 16, …$ 為遞增分組數列 <br>   (c\) 自行選定遞增分組數列。
(a)
```cpp=
# include <iostream>
using namespace std;
int h[20];
void Shell_Sort(int data[], int n, int hk)
{ for (int i = hk; i >= 0; i--)
{ int H = h[i];
for (int j = H; j < n; j++)
{ int target = data[j];
int k = j;
while ((k - H >= 0) && (data[k - H] > target))
{ data[k] = data[k - H];
k = k - H;
}
data[k] = target;
}
}
}
int main()
{ int n, data[100];
h[0] = 1;
for (int i = 1; i < 20; i++)
{ h[i] = h[i-1] * 3 + 1;
}
cin >> n;
for (int i = 0; i < n; i++)
{ cin >> data[i];
}
int hk = 0;
while (h[hk] < n) hk++;
Shell_Sort(data, n, hk-1);
for (int i = 0; i < n; i++)
{ cout << data[i] << " ";
}
}
```
(b)
```cpp=
# include <iostream>
using namespace std;
int h[20];
void Shell_Sort(int data[], int n, int hk)
{ for (int i = hk; i >= 0; i--)
{ int H = h[i];
for (int j = H; j < n; j++)
{ int target = data[j];
int k = j;
while ((k - H >= 0) && (data[k - H] > target))
{ data[k] = data[k - H];
k = k - H;
}
data[k] = target;
}
}
}
int main()
{ int n, data[100];
h[0] = 1;
for (int i = 1; i < 20; i++)
{ h[i] = h[i - 1] * 2;
}
cin >> n;
for (int i = 0; i < n; i++)
{ cin >> data[i];
}
int hk = 0;
while (h[hk] < n) hk++;
Shell_Sort(data, n, hk-1);
for (int i = 0; i < n; i++)
{ cout << data[i] << " ";
}
}
```
(c\)
請自行練習。
---
### 7. 請實作不同版本的堆積排序法： <br>   (a) 用陣列實作最小（大）堆積 <br>   (b) 用鍵結串列實作最小（大）堆積。 <br>   並利用題 2 的實驗設計製作圖表，觀察並討論實驗結果。
(a) 最小堆積排序
```cpp=
void restore(int data[], int s, int t)
{ int i = s, j;
while (i <= t / 2)
{ if (2 * i + 1 <= t && data[2 * i] > data[2 * i + 1])
j = 2 * i + 1;
else
j = 2 * i;
if (data[i] < data[j]) break;
swap(&data[i], &data[j]);
i = j;
}
}
void heapSort(int data[], int n)
{ // 建立最小堆積
for (int i = n / 2; i >= 1; i--)
{ restore(data, i, n);
}
// 排序
for (int i = n; i >= 1; i--)
{ // 輸出最小值（data[1]）
cout << data[1] << " ";
// 將最小值移至尾部
data[1] = data[i];
// 重新調整堆積
restore(data, 1, i - 1);
}
cout << endl;
}
```
最大堆積
```cpp=
void restore(int data[], int s, int t)
{ int i = s, j;
while (i <= t / 2)
{ if (2 * i + 1 <= t && data[2 * i] < data[2 * i + 1])
{ j = 2 * i + 1; // 選擇較大的子節點
}
else
{ j = 2 * i;
}
if (data[i] > data[j]) break; // 如果父節點已經是最大，則退出
swap(&data[i], &data[j]);
i = j;
}
}
void heapSort(int data[], int n)
{ // 建立最大堆積
for (int i = n / 2; i >= 1; i--)
{ restore(data, i, n);
}
// 排序
for (int i = n; i >= 1; i--)
{ // 輸出最大值（data[1]）
cout << data[1] << " ";
// 將最大值移至尾部
data[1] = data[i];
// 重新調整堆積
restore(data, 1, i - 1);
}
cout << endl;
}
```
(b) 最小堆積
```cpp=
struct Node
{ int val;
Node *next;
};
void insertNode(Node **head, int value)
{ Node* newNode = new Node(value);
newNode->next = *head;
*head = newNode;
}
void swap(Node *a, Node *b)
{ int temp = a->val;
a->val = b->val;
b->val = temp;
}
void restore(Node *head)
{ if (!head) return;
bool swapped;
do
{ swapped = false;
Node *current = head;
while (current->next)
{ if (current->val > current->next->val)
{ swap(current, current->next);
swapped = true;
}
current = current->next;
}
} while (swapped);
}
```
最大堆積
```cpp=
struct Node
{ int val;
Node *next;
};
void insertNode(Node **head, int value)
{ Node *newNode = new Node(value);
newNode->next = *head;
*head = newNode;
}
void swap(Node *a, Node *b)
{ int temp = a->val;
a->val = b->val;
b->val = temp;
}
void restore(Node *head)
{ if (!head) return;
bool swapped;
do
{ swapped = false;
Node *current = head;
while (current->next)
{ if (current->val < current->next->val)
{ swap(current, current->next);
swapped = true;
}
current = current->next;
}
} while (swapped);
}
```
下表列出以陣列和鏈結串列實作時，在不同資料量下的執行時間 (單位：秒)：
| 資料量 | $5000$ | $10000$ | $15000$ | $20000$ | $25000$ |
| --- | --- | --- | --- | --- | --- |
|陣列 | $0.000739$ | $0.001603$ | $0.002427$ | $0.003269$ | $0.003993$ |
| 鏈結串列 | $0.050275$ | $0.216635$ | $0.562879$ | $1.03964$ | $1.69686$
下表則以上表時間繪製圖形，方便比較：
由以上圖表可知，堆積排序法以陣列實作最小（大）堆積比起鏈結串列，會有較佳的執行效率。
---
### 8. (a) 證明當輸入串列已經排好順序時，快速排序需要 $O(n^2)$ 的時間。 <br>   (b) 證明快速排序最差情況時的複雜度為 $O(n^2)$。 <br>   (c\) 為何演算法 7-8 中第 3 行的 left < right 檢測，在快速排序中是必要的？
(a) 當輸入串列已經排好序時，且 target 都選第一個，其快速排序的過程如下圖 所示：
(b) 快速排序採分割和個自擊破的演算法，最好的情況就是每次剛好分割一半， 然後再合併，時間複雜度就可達到 $O(nlogn)$，而分割的越不平均則效果越差， 所以最差的情況就是每次分割一大一小只切割長度為 $n-1$ 和 $1$，其時間複雜度 就會是 $O(n^2)$
(c\) 因為 left < right 的判斷為遞迴的中止條件，若無此判斷，則遞迴程式將會一直做下去不會結束，故此判斷為必要的條件。
---
### 9. 證明當較小的子串列先排序時，那麼快速排序中的遞迴，可以用深度為 $O(logn)$ 的堆疊來模擬。
快速排序演算法，最好的情況就是每次剛好分割一半，時間複雜度就可達到 $O(nlogn)$，需要 $O(logn)$ 次的分割；而一次分割後先執行某一半資料的排序，另一半（的起點和終點）放堆疊，需要 $O(1)$ 的堆疊空間，總共分割 $O(logn)$ 次，會需要有 $O(logn)$ 的堆疊空間。若分割不平均，且較小的子數列先排序，較大的子數列要先放堆疊，空間 $O(1)$。小的子數列排序時所用的堆疊空間肯定少於 $O(logn)$，而它排序完成後，曾用到的堆疊空間（少於 $O(logn)$）會釋放出來，堆疊剩當時分割後較大的子數列（起點、終點）在堆疊。pop 後堆疊已空；數列又分割，又是小數列先排序—所用的堆疊空間肯定少於 $O(logn)$ …。以此類推，深度為 $O(logn)$ 的堆疊空間肯定足夠。
---
### 10. 快速排序不是一個穩定的排序法，舉出一個輸入串列的例子說明，其中具有相同鍵值的數個記錄之先後順序不再相同。
輸入串列為 $F=(10,10,10)$，在 QuickSort 中 $(s_1, s_2, s_3)$ 會先變成 $(s_1, s_3, s_2)$ 再變成 $(s_3, s_1, s_2)$，結果的順序與原先不相符，故 QuickSort 不具穩定性。
---
### 11. 請舉例說明基數排序的最差情形。
當要比較的數字中，大部分的數字位數為 $s$，但只有極少部分的數字位數為 $k$，當 $s$ 極小而 $k$ 極大時會有最差情形；也就是說因為有極大的 $k$ 值，使得所有位數皆要做一次排序，排了 $k$ 次，但大部分的值其實只須排 $s$ 次就完成。例如： $3, 1, 5, 20, 20360051470009000358454718$
---
### 12. 請說明本章所有排序演算法的最差情形。
---
### 13. 設計一個程序，將數列 $(x_1, x_2, ... , x_n)$ 向右環形移動 $p$ 個位置，其中 $0 ≤ p ≤ n$。此程序應有 $O(n)$ 的時間複雜度，而其空間複雜度應為 $O(1)$。
以下做法引用了排序中常用的交換 swap 運算；利用 swap 做數列的反轉 reverse
先看個例子，令 $p = 3$、$n=5$ :
$input: 1 2 3 4 5 6 7 8 9$
$output:7 8 9 1 2 3 4 5 6$
1. Reverse all numbers: 9 8 7 6 5 4 3 2 1
2. Reverse p numbers starting from position 0: 7 8 9
3. Reverse p numbers starting from position p: 1 2 3 4 5 6
4. Merging results of Steps 3 and 4 obtains what we need.
```cpp=
void Reverse(int *list, int first, int last)
{ int firstindex = first, lastindex = last;
while (firstindex < lastindex)
{ //swap
int temp = list[firstindex];
list[firstindex] = list[lastindex];
list[lastindex] = temp;
firstindex++;
lastindex--;
}
}
void RightCircularShift(int *list, int p, int n)
{ if (p>0 && p<n)
{ Reverse(list, 0, n-1);
Reverse(list, 0, p-1);
Reverse(list, p, n-1);
}
}
```
$O(n) + O(p) + O(n-p) = O(n)$
---
### 14. 如果有 $p$ 部電腦供各位使用，請討論排序在此 $p$ 部電腦中同時執行的可能演算法。
合併排序法、快速排序法，皆有很直覺平行化的演算法，讀者可在以「平行排序」(parallel sorting)為主題的學術論文中找到更多有趣的平行演算法。
奇偶排序法 (odd-even sort) 則是非常適合平行處理的排序方法，即令其循序的時間複雜度為：$O(n^2)$。下面程式以 javascript 撰寫：
```javascript=
function oddEvenSort(list)
{ function swap(list, i, j)
{ var temp = list[i];
list[i] = list[j];
list[j] = temp;
}
var sorted = false;
while (!sorted)
{ sorted = true;
for (var i = 1; i < list.length - 1; i += 2)
{ if (list[i] > list[i + 1])
{ swap(list, i, i + 1);
sorted = false;
}
}
for (var i = 0; i < list.length - 1; i += 2)
{ if (list[i] > list[i + 1])
{ swap(list, i, i + 1);
sorted = false;
}
}
}
}
```
---
Sign in with Wallet
Connect another wallet