大连理工大学算法分析与设计算法总结

一，马步程序 简要算法描述：

算法从1号节点作为当前节点开始进行搜索。从小到大深度优先尝试所有相连的节点，并把它作为下一次搜索的当前节点，如果最终能够回到起始点，并且每个节点经过且仅经过一次，则存在一条哈密顿回路。否则不存在哈密顿回路。 优化：

1， 如果走一步之后发现，存在度数小于2的未走过的节点，则没有必要继续搜索，只能尝试其他节点。 2， 如果发现，当前存在大于等于两个度数为2的节点，则直接回溯到上一层节点，没有必要继续搜索。 3， 回溯到第一个节点后，如果没找到哈密顿回路则直接退出，没有必要尝试其他走法，因为另一条路径与当

前遍历过的路径是对称的。 #include #include #include using namespace std; const int Maxn = 10000;

int dirx[] = {-1, -2, -2, -1, 1, 2, 2, 1}; int diry[] = {-2, -1, 1, 2, 2, 1, -1, -2}; int n1, n2, n; bool used[Maxn]; int ans[Maxn];

int degree[Maxn], deg[Maxn]; int graph[Maxn][8]; bool valid(int x, int y) {

return x >= 0 && x < n1 && y >= 0 && y < n2; }

void getGraph() {

for (int i = 0; i < n; ++i) {

int row = i / n2; int col = i % n2; degree[i] = 0;

for (int j = 0; j < 8; ++j) {

int x = row + dirx[j]; int y = col + diry[j]; if (!valid(x, y)) continue;

graph[i][degree[i]++] = x * n2 + y; }

deg[i] = degree[i]; } }

void resume(int cur) {

for (int i = 0; i < degree[cur]; ++i) {

int next = graph[cur][i]; if (used[next]) continue; deg[next]++; } }

bool update(int cur) {

bool ret = true;

for (int i = 0; i < degree[cur]; ++i) {

int next = graph[cur][i]; if (used[next]) continue; deg[next]--;

if (deg[next] < 2 && next != graph[0][1]) ret = false; }

if (!ret) {

resume(cur); return false; }

return true; }

bool dfs(int step, int cur) //递归版 {

ans[step] = cur; if (step == n - 1) {

if (graph[0][1] != cur) return false; for (int i = 0; i < n; ++i) printf(\, ans[i]); puts(\); return true; }

for (int i = 0; i < degree[cur]; ++i) {

if (cur == 0 && i) break; int next = graph[cur][i]; if (used[next]) continue;

used[next] = true; if (!update(cur)) {

used[next] = false; continue; }

if (dfs(step + 1, next)) return true; resume(cur); used[next] = false; }

return false; }

bool check()// goto 版 {

int w[Maxn] = {0};

memset(used, false, sizeof(used)); int cur = 0, next; used[0] = true; int i, step = 0; l0:

i = -1, ans[step] = cur; if (step == n - 1) {

if (graph[0][1] != cur) goto l2; for (int i = 0; i < n; ++i) printf(\, ans[i]); puts(\); return true; } l1:

w[step] = ++i;

if (i >= degree[cur]) goto l2; next = graph[cur][i]; if (used[next]) goto l1; used[next] = true; if (!update(cur)) {

used[next] = false; goto l1; } step++; cur = next; goto l0; l2 :

cur = ans[--step]; resume(cur);

next = graph[cur][w[step]]; used[next] = false; if (step > 0) {

i = w[step]; goto l1; }

return false; }

int main() {

while (scanf(\, &n1, &n2) != EOF) {

cout << \<< n1 <<\ << n2 << endl; n = n1 * n2;

getGraph();

if (!check()) cout <<\ << endl; }

return 0; }

二，归并排序 & 快速排序

归并排序：主要思想是分而治之合并已经排序好的两个数组。这样按照块大小从小到大的顺序，处理完所有元素之后，就用O(nlogn)的时间复杂度完成排序. 优化：见程序注释

快速排序: 主要思想仍然是分而治之，但他与归并排序处理数据的顺序正好相反，按照块大小从大到小的顺序处理，每次选取一个参考元素x，将比x小的放在左边，其他的放在右边，然后用同样的方法处理每个子块。平均时间复杂度为O（nlogn）,最坏时间复杂度为O(n^2).

#include \ #include \ #include \ #include \ using namespace std; const int Maxn = 1000000; template struct InsertSort {

void static sort(T* a, int n) {

for (int i = 1; i < n; ++i)

{

int j; T tmp = a[i];

for (j = i - 1; j >= 0; --j)

if (tmp < a[j]) a[j + 1] = a[j]; else break; a[j + 1] = tmp; } } };

//与插入相结合 不递归 不回写

//如果想实现无逆序会使得各个块的大小不相同因此必须新加一个数组记录各个块的起始位置，这样做得不偿失

所以暂时无法加入无逆序的优化

template struct MergeSort {

T tmp[Maxn];

void sort(T* arr, int n) {

for (int i = 0; i < n; i += 16)//小于16 采用插入排序 InsertSort::sort(arr + i, min(n - i, 16));

for (int i = 16; i < n; i <<= 1) //归并的单个块大小 {

//s表示第一块归并起点，a表示第一个块处理完的大小， b表示第二个块处理完的大小 s+i 表示第二块归并起点

int s, a, b;

//两块有序集合进行合并 奇数次归并 从左向右

for (a = 0, b = 0, s = 0; s < n; s += (i << 1), a = 0, b = 0) //第一块起始位置 {

int la = min(s + i, n) - s;

int lb = min(s + i + i, n) - (s + i); int cnt = 0;

while (a < la || b < lb)//归并 {

while (a < la && (b >= lb || !(arr[s + i + b] < arr[a + s]))) tmp[s + (cnt++)] = arr[(a++) + s];

while (b < lb && (a >= la || arr[b + s + i] < arr[a + s])) tmp[s + (cnt++)] = arr[(b++) + s + i]; } }

i <<= 1;

if (i >= n) {

for (int j = 0; j < n; ++j) arr[j] = tmp[j]; break; }

//两块有序集合进行合并 偶次归并 从右向左 int remain = (n % i);

int N = (remain == 0 ? n : n - remain + i);

for (a = N - n, b = 0, s = N - 1; s >= 0; s -= (i << 1), a = 0, b = 0) {

int la = s - max(s - i, -1);

int lb = s - i - max(s - i - i, -1); int cnt = a;

while (a < la || b < lb) {

while (b < lb && (a >= la || !(tmp[s - i - b] < tmp[s - a]))) //由于从右向左 所以找大的

arr[s - (cnt++)] = tmp[s - i - (b++)];

while (a < la && (b >= lb || tmp[s - i - b] < tmp[s - a])) arr[s- (cnt++)] = tmp[s - (a++)]; } } } } };

//优化：1，非递归 // 2，与插入相结合 template struct QuickSort {

pair stack[100]; //logn 的大小 快排额外空间大小为logn int top;

int partion(T* arr, int n) { //获取pivot

int mid = n / 2;

if (arr[mid] < arr[0]) swap(arr[mid], arr[0]);

if (arr[n - 1] < arr[mid]) swap(arr[mid], arr[n - 1]); if (arr[mid] < arr[0]) swap(arr[mid], arr[0]); T tmp = arr[mid]; arr[mid] = arr[0]; //快排

int a, b;

for (a = 0, b = n - 1; a < b; ) {

while (b > a && !(arr[b] < tmp)) b--; if (b > a) arr[a++] = arr[b];

while (a < b && !(tmp < arr[a])) a++; if (a < b) arr[b--] = arr[a]; }

arr[a] = tmp;

return a; }

void sort(T* arr, int n) {

top = 0;

stack[top++] = make_pair(0, n); while (top >= 0) {

pair seg = stack[--top];

if (seg.second <= 16) InsertSort :: sort(arr + seg.first, seg.second); else {

int mid = partion(arr + seg.first, seg.second); if (1 < mid) stack[top++] = make_pair(seg.first, mid);

if (mid + 1 + 1 < seg.second) stack[top++] = make_pair(seg.first + mid+ 1, seg.second - (mid + 1)); } } } };

MergeSort Merge; QuickSort Quick; int a[Maxn]; int main() {

int n; cin >> n;

for (int i = 0; i < n; ++i) cin >> a[i]; Merge.sort(a, n);

for (int i = 0; i < n; ++i) cout << a[i] <<\; cout << endl;

random_shuffle(a, a + n); Quick.sort(a, n);

for (int i = 0; i < n; ++i) cout << a[i] <<\; cout << endl; return 0; }

三，堆排序

算法思想：堆分为最大堆和最小堆，其实就是完全二叉树。最大堆要求节点的元素都要大于其孩子，最小堆要求节点元素都小于其左右孩子，两者对左右孩子的大小关系不做任何要求，其实很好理解。有了上面的定义，我们可以得知，处于最大堆的根节点的元素一定是这个堆中的最大值。堆排序算法就是抓住了堆的这一特点，每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最大堆，依次类推，最终得到排序的序列。

void Heap_Sort(int a[], intlen) {

//构建最大堆

for(int i = len / 2 - 1; i >= 0; i--) Heap_Adjust(a, i, len);

for(i = len - 1; i > 0; i--) {

int temp; temp = a[0]; a[0] = a[i]; a[i] = temp;

Heap_Adjust(a, 0, i); } }

void Heap_Adjust(int a[], int i, intlen) { //调整堆 int child; //保存父亲节点 int temp;

for(temp = a[i]; 2 * i + 1

//左孩子坐标 child = 2 * i + 1; //找到较大的孩子

if(child + 1

//如果较大的孩子比父亲大，将大孩子上移 if(a[child] > temp)

{

a[i] = a[child]; a[child] = temp; } else break; } }

四，红黑树

利用AVL树中的左旋与右旋操作达到调节红黑树黑节点高度一致的问题. 1,红黑红红：将根节点变为红色，两个孩子变为黑色 最终变为黑红黑红 2,黑红红：变色，移跟变方向（旋转根节节点为孩子节点）。

#include #include #include #include using namespace std; const int Maxn = 1000000; class RedBlackTree {

private : struct Node {

int lc, rc, key; bool red;

void clear(int k) {

lc = rc = 0; key = k; red = true; } }node[Maxn]; int size, root; void init() {

size = 1; root = 0;

node[0].clear(0); node[0].red = false; }

void rotateL(int &cur) // rotate left direction {

int c = cur; cur = node[c].rc;

node[c].rc = node[cur].lc; node[cur].lc = c; }

void rotateR(int &cur) // rotate right direction {

int c = cur; cur = node[c].lc;

node[c].lc = node[cur].rc; node[cur].rc = c; }

void insert(int &cur, int key) {

if (cur == 0) // insert at leaf node {

cur = size++;

node[cur].clear(key); return; }

int lc = node[cur].lc, rc = node[cur].rc; if (key <= node[cur].key) // go left {

insert(node[cur].lc, key);

// deal with conflict when it happens in left child node

if (node[cur].red || node[lc].red == false) return; // no need to rotate if (node[node[lc].rc].red) // promise the same direction rotateL(node[cur].lc), lc = node[cur].lc; if (node[rc].red) {

if (node[node[lc].lc].red) // red black red red {

node[lc].red = false; node[rc].red = false; node[cur].red = true; } } else {

if (node[node[lc].lc].red) // black red red {

node[cur].red = true; rotateR(cur);

node[cur].red = false;

} } }

else // go right {

insert(node[cur].rc, key);

if (node[cur].red || node[rc].red == false) return; if (node[node[rc].lc].red)

rotateR(node[cur].rc), rc = node[cur].rc; if (node[lc].red) {

if (node[node[rc].rc].red) // red black red red {

node[rc].red = false; node[lc].red = false; node[cur].red = true; } } else {

if (node[node[rc].rc].red) // black red red {

node[cur].red = true; rotateL(cur);

node[cur].red = false; } } } } public : RedBlackTree() {

init(); }

void insert(int key) {

if (root == 0) {

root = 1;

node[size].clear(key); node[size].red = false; size++; return;

}

insert(root, key); node[root].red = false; }

int que[Maxn]; void out() {

int in = 0, out = 0; if (root == 0) {

puts(\); return; }

que[in++] = root; while (in > out) {

int cur = que[out++];

cout << \ << cur <<\ << node[cur].key <<\

\ << (node[cur].red ? \ : \) <<\left child = \ << node[cur].lc <<\right child = \ << node[cur].rc << endl; if (node[cur].lc)

que[in++] = node[cur].lc; if (node[cur].rc)

que[in++] = node[cur].rc;

assert((node[cur].red && node[node[cur].lc].red) == false); assert((node[cur].red && node[node[cur].rc].red) == false); } } }tree; int main() {

for (int i = 0; i < 20000; ++i) tree.insert(rand()); tree.out(); return 0; }

五，Prim & Dijikstra & Kruscal & floyd

Prim & Dijikstra：主要思想是采用贪心算法，贪心的选取最小代价的节点放入目标集合中，之后用已选节点更新所有其他未选节点，如此循环，直到所有点均放入目标集合中，程序结束。如果采用堆进行优化可以将复杂度从O(n^2 + m)降到O(nlogn + m).

Kruscal: 算法从原理上仍然属于贪心算法，只不过是按照边从小到大进行贪心的。因此kruscal首先要对所有边进行排序，之后遍历每条边，如果不形成环则选用此边，否则放弃

此边。验证是否存在环可以采用可并堆（并查集）来实现，复杂度O(mlogm)。当原图为完全图时，kruscal算法比prim慢，相当于O(n^2*log(n^2))。

Floyd ：三层for循环，寻找多源多汇最短路径，复杂度O(n^3)。

#include #include #include #include #include using namespace std;

const int Maxn = 1000, INF = 0x3f3f3f3f; int graph[Maxn][Maxn]; int n, m; int prim() {

bool used[Maxn]; int ret = 0; int cost[Maxn];

memset(used, false, sizeof(used)); cost[1] = 0; used[1] = true;

for (int i = 2; i <= n; ++i) cost[i] = graph[1][i]; for (int i = 0; i < n - 1; ++i) {

//找最小值

int minCost = INF, minID; for (int j = 1; j <= n; ++j) {

if (used[j]) continue; if (minCost > cost[j]) {

minCost = cost[j]; minID = j; } }

ret += minCost;

if (minCost == INF) break; used[minID] = true; //更新节点

for (int j = 1; j <= n; ++j) {

if (used[j]) continue;

cost[j] = min(cost[j], graph[minID][j]);

} }

return ret; }

int dijikstra(int s = 1, int t = n)//s为起点 t为终点 {

bool used[Maxn]; int cost[Maxn];

memset(used, false, sizeof(used)); used[s] = true;

for (int i = 1; i <= n; ++i) cost[i] = graph[s][i]; for (int i = 0; i < n - 1; ++i) {

//找最小值

int minCost = INF, minID; for (int j = 1; j <= n; ++j) {

if (used[j]) continue; if (minCost > cost[j]) {

minCost = cost[j]; minID = j; } }

if (minCost == INF) break; used[minID] = true; //更新节点

for (int j = 1; j <= n; ++j) {

if (used[j]) continue;

cost[j] = min(cost[j], graph[minID][j] + cost[minID]); } }

return cost[t]; }

void floyd(int (*dist)[Maxn]) {

for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) if (i == j) dist[i][j] = 0; else dist[i][j] = graph[i][j]; for (int k = 1; k <= n; ++k) for (int i = 1; i <= n; ++i)

for (int j = 1; j <= n; ++j)

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); }

struct Edge {

int x, y, v;

bool operator < (const Edge &e) const {

return v < e.v; }

}edge[Maxn * Maxn];

int root[Maxn]; //可并堆（并查集）的树根 int getRoot(int x) {

int ret = x;

while (root[ret] >= 0) //找根 ret = root[ret];

while (x != ret)//优化 将所有节点变为树根的孩子 {

int y = root[x]; root[x] = ret; x = y; }

return ret; }

int kruscal() {

sort(edge, edge + m);

memset(root, -1, sizeof(root)); int ret = 0;

for (int i = 0; i < m; ++i) {

int x = edge[i].x, y = edge[i].y; int rx = getRoot(x), ry = getRoot(y); if (rx == ry) continue;//在同一集合内 ret += edge[i].v;

if (root[rx] < root[ry]) //小树根指向大树根 {

root[rx] += root[ry]; root[ry] = rx;

if (root[rx] == -n) break; }

else {

root[ry] += root[rx]; root[rx] = ry;

if (root[ry] == -n) break;// 已找到生成树 } }

return ret; }

int main() {

scanf(\, &n, &m);

memset(graph, INF, sizeof(graph));//graph 置0 for (int i = 1; i <= n; ++i) graph[i][i] = 0; for (int i = 0; i < m; ++i) {

int x, y, v;

scanf(\, &x, &y, &v); assert(x >= 1 && x <= n);

assert(y >= 1 && y <= n);//保证顶点号满足[1, n] graph[x][y] = graph[y][x] = v;

edge[i].x = x, edge[i].y = y, edge[i].v = v; }

cout << \ << prim() << \ << dijikstra() << endl; cout <<\ <

六，基于边的双连通分支算法并找割点

首先利用深度优先搜索求出一颗深度优先搜索树。 割点验证方法：

1对于根节点如过存在两个或两个以上子树，则根节点为割点 2 其他节点要看该节点是否存在某个孩子不含有指向该节点上方的回边，如果存在则为根节点。

连通分支验证方法：

每个节点有一个low值和visit值，low值表示通过当前节点能够回到的最小的标号，visit值表示当前节点标号，标号采用深度优先搜索顺序递增。 当该节点的所有子孙都遍历过后：

如果某个节点的visit值等于其low值，则产生了一个新的连通分支

如果某个节点的visit值小于其low值，则用low值更新其父节点的low值

不可能出现其他情况。具体找连通分支中的点需要使用一个栈来维护，参见程序。

#include \ #include \

#include \

using namespace std;

const int Maxn = 100000, Maxm = 1000000; int low[Maxn], visit[Maxn], dfn; struct Edge {

int to, next; Edge(){}

Edge(int to, int next) : to(to), next(next){} }edge[Maxm];

int head[Maxn], size; void add(int from, int to) {

edge[size] = Edge(to, head[from]); head[from] = size++; } int n, m;

int color[Maxn]; int stack[Maxn], top;

bool isCut[Maxn];//是否为割点 void tarjan(int x, int last) {

int min0 = low[x] = visit[x] = dfn++; color[x] = 1;//变为gray stack[top++] = x; int cnt = 0;

for (int i = head[x]; i != -1; i = edge[i].next)//遍历所有与x相连的边 {

int ne = edge[i].to;

if(i == (last ^ 1)) continue;//同一条边

if(color[ne] == -1) tarjan(ne, i); else if (color[ne] == 0) continue; if(low[ne] >= visit[x]) isCut[x] = true;

min0 = min(min0, low[ne]); cnt++; }

if (last == -1)//根节点的情况 isCut[x] = (cnt > 1);

low[x] = min0;

if (low[x] == visit[x])//找到一个连通分支

{

cout <<\ << endl; while(true) {

int tmp = stack[--top]; cout << tmp << \; if(tmp == x) break; }

cout << endl; }

color[x] = 0; }

int main() {

scanf(\, &n, &m);

memset(head, -1, sizeof(head)); size = 0;

for (int i = 0; i < m; ++i) {

int x, y;

scanf(\, &x, &y); add(x, y), add(y, x);//无向图 } dfn = 0;

memset(color, -1, sizeof(color));//所有元素均为white top = 0;

memset(isCut, false, sizeof(isCut)); for (int i = 1; i <= n; ++i) if (color[i] == -1)tarjan(i, -1); cout <<\ << endl; for (int i = 1; i <= n; ++i) if (isCut[i]) cout <

七，给定长度为n的有序元素序列K1， K2，…，Kn，其各个元素被查找的概率（或频率）分别为p1，p2，…，pn。描述构造最优二分树的算法

算法思路：定义函数cost(low, high)，表示用K(low)…K(high)构造得到的最优二分树的总代价，root(low, high)表示相应二分树的树根位置。 则状态转移方程为：

当 low>high (low = high-1)时， 令cost(low, high = 0)

root(low, high) = -1

当low <= high 时，

cost(low, high) = p(low)+…+p(high) + min{cost(low, k-1) + cost(k+1, high) | low<=k<=high} 式(1)

root(low, high) = k ( 式(1)中对应cost(low, high)的k )

代码如下：

int cost[n+1][n+1],root[n+1][n+1] voidgetBestBinaryTree() {

// 初始化数组的对角线元素，即(t+1, t) for( i=1; i<=n+1; i++ ) cost[i][i-1] = 0; root[i][i-1] = -1;

// 按一定的顺序填充数组 for( low=n; low>=1; low-- ) for( high=low; high<=n; high++)

cost[low][high] = maxNum;//maxNum表示无穷大 for (k=low; k<=high; k++)//选取不同的元素作为当前树的树根 currentCost = low…high的概率和 + cost(low, k-1) + cost(k+1, high) if (currentCost< cost[low][high]) cost[low][high] = currentCost; root[low][high] = k; }

最终，cost[1][n]即为最优二分树的代价。

对root数组进行先序遍历，即可得到最优二分树。

八，对于矩阵乘法：

第1个乘号第(n-1)个乘号

A1 × A2 ×…× An

d0 × d1 d1× d2 dn-1 ×dn

给出每个乘法运算的执行顺序，使得进行整个矩阵乘法运算过程中进行的数值乘法次数最少。

算法思想：

定义函数cost(low, high)，表示计算矩阵A(low)×…×A(high)所需的最少数值乘法次数，root(low, high)表示相应于上述cost(low, high)的进行的最后一次乘法的位置。 则状态转移方程为：

当low == high时，cost(low, high) = 0，root(low, high) = -1 当low < high 时，

cost(low, high) = min{cost(low, k) + cost(k+1, high) + d(low-1)×dk×d(high) | low<=k<=high-1} 式(1)

root(low, high) = k (式(1)中的k) 代码如下：

Int root[n][n],cost[n][n];

voidgetMultiOrder() {

for( i=1; i<=n; i++ ) cost[i][i] = 0; root[i][i] = -1;

// 按一定的顺序填充数组 for( low=n-1; low>=1; low-- )

for( high=low+1; high<=n; high++)

cost[low][high] = maxNum; //maxNum表示无穷大 for (k=low; k

算法执行完对root数组进行如下的后序遍历，即可得到代价最少的乘法次序