第10章-基础数据结构

发表于 2021-12-04 更新于 2025-04-22 分类于算法阅读次数：本文字数： 260 阅读时长 ≈ 1 分钟

动态集合上的操作： - SEARCH(S, k)：查询， - INSERT(S, x)：插入 - DELETE(S, x)：删除 - MINMUM(S)：查询最小元素的指针 - MAXMUM(S)：查询最大元素的指针 - PREDECESSOR(S, x)：查询x前一个元素的指针

栈和队列

栈：假设用$S[1,2,3,...n]$表示一个可容纳n个元素的栈

先进后出（FILO）

插入操作称作：PUSH, 删除操作称作POP

def STRACK_EMPTY(S):
    if S.top == 0:
        return True
    else:
        return False
    
def PUSH(S, x):
    if S.top == n:
        raise "栈上溢（overflow）"
    S.top++
    S[S.top] = x

def POP(S):
    if STRACK_EMPTY(S):
        raise "栈下溢(underflow)"
    else:
    	S.top--
    return S[S.top+1]

队列：

先进先出（FIFO）

插入操作称作：ENQUEUE，删除称作：DEQUEUE

def ENQUEUE(Q, x):
    Q[Q.tail] = x
    if Q.tail == Q.length:
        Q.tail = 1
    else:
        Q.tail++
        
 def DEQUEUE(Q):
    x = Q[Q.head]
    if Q.head == Q.length:
        Q.head = 1
    else:
        Q.head++
    return x

链表

与数组不同的是，链表的顺序是由各个对象里的指针决定的。

# 搜索

def LIST_SEARCH(L, k):
    x = L.head
    while x != None && x.key != k:
        x = x.next
    return x

指针和对象的实现

有根树的表示

练习

思考题

第22章-基本图算法

发表于 2021-12-02 更新于 2025-04-22 分类于算法阅读次数：本文字数： 3.2k 阅读时长 ≈ 12 分钟

图的表示

图$G=(V, E)$，其中$V$表示结点，$E$表示边

邻接链表：表示稀疏图时，非常紧凑

稀疏图：边的条数（$|E|$）远远小于边的结点数（$|V|$）的图
- 需要空间$\Theta(E+V)$
- 邻接表表示由一个包含$|V|$条链表的数组$Adj$所构成，对于结点$u\in V$，$Adj[u]$表示图$G$中所有与$u$邻接的结点
邻接矩阵：能快速查询两个结点之间是否有相连

矩阵的行号表示起始点，列号表示终点
- 需要空间$\Theta(V^2)$
- 无向图的矩阵式一个对称矩阵，因为边$(u, v)$和边$(v, u)$是一样的

阅读全文 »

第24章-单源最短路径

发表于 2021-11-30 更新于 2025-04-22 分类于算法阅读次数：本文字数： 967 阅读时长 ≈ 4 分钟

单源最短路径

环路

前驱结点

前驱子图

松弛操作

松弛（relaxation）技术：对于每个结点$v$来说，我们维持一个属性$v.d$，用来记录从源结点$s$到结点$v$的最短路径权重的上界。我们称$v.d$为s到$v$的最短路径估计

最短路径估计和前驱结点进行初始化:

INITIALIZE-SINGLE-SOURCE(G, s):
	for each vertex v in G.V
		v.d = infty 
		v.pi = NIL 
	s.d = 0

对一条边（$u$, $v$）的松弛过程:

测试是否可以对$s$到$v$的最短距离进行改善
- 将$s$到$u$的最短路径，加上结点$u$到$v$的权重,与当前$s$到$v$的最短距离进行比较
- 如果前者更小，则更新$v.d$和$v.\pi$

RELAX(u, v, w):
	if v.d > u.d + w(u, v):
		v.d = u.d + w(u, v)
		v.pi = u

其中 w(u, v)表示：点u到点v的权重 v.d: 表示从源s到v的最短距离 v.pi: 表示v的上一个节点

松弛操作和最短路径的性质

三角不等式性质
上界性质
非路径性质
收敛性质
路径松弛性质
前驱子图性质

Bellman-Ford算法

边的权重可以为负值

给定带权重的有向图$G=(V, E)$和权重函数$w: E\rightarrow R$

算法返回一个布尔值

如果存在权重为负值的环路，返回false（负值的环路，不停的循环，可以使总权重一直降低）
反之，给出最短路径和他们的权重

BELLMAN-FORD(G, w, s):
	INITIALIZE-SINGLE-SOURCE(G, s)
	for i=1 to |G.V| - 1
		for each edge(u, v) in G.E
			RELAX(u, v)
	for each edge(u, v) in G.E
		if u.d > v.d + w(u, v):
			return False
	return True

有向无环图中的单源最短路径问题

Dijkstra算法

差分约束和最短路径

最短路径的证明

练习

24.1-1

在图24-4中运行Bellman-Ford算法,使用结点$z$作为源结点。在每一遍松弛过程中以图中相同的次序对每条边进行松弛，给出每遍松弛操作后的$d$值和$\pi$值。然后，把边$(z, x)$的权重改为4，再次运行该算法，这次使用$s$作为结点。

使用$z$作为源节点：

$d$的值:

松弛次数	$s$	$t$	$x$	$y$
0	$\infty$	$\infty$	$\infty$	$\infty$
1	2	$\infty$	7	$\infty$
2	2	5	7	9
3	2	5	6	9
4	2	4	6	9

$\pi$的值：

$s$	$t$	$x$	$y$	$z$
NIL	NIL	NIL	NIL	NIL
$z$	NIL	$x$	NIL	NIL
$z$	$x$	$x$	$s$	NIL
$z$	$x$	$y$	$s$	NIL
$z$	$x$	$y$	$s$	NIL

修改权重之后

24.1-2

证明推论24.3

证明:

24.1-3

给定$G=(V, E)$是一个带权重且没有权重为负值的环路的有向图，对于所有结点$v\in V$，从源结点$s$到结点$v$之间的最短路径中，包含边的条数的最大值为$m$。（这里，判断最短路径的根据是权重，不是边的条数。）请对算法BELLMAN-FORD进行简单修改，可以让其在$m+1$遍松弛操作之后种植，即使$m$不是事先知道的一个值。

24.1-4

修改BELLMAN-FORD算法，使其对于所有结点v来说，如果从源节点$s$到结点$v$的一条路径上存在权重为负值的环路，则将$v.d$的值设置为$-\infty$

24.1-5

设$G=(V, E)$为一个带权重的有向图，其权重函数为$w: E \rightarrow R$。请给出一个时间复杂度为$O(VE)$的算法，对于每个结点$v \in V$，计算出数值$^*(v) = {(u, v)} $

24.1-6

假定$G=(V, E)$为一个带权重的有向图，并且图中存在一个权重为负值的环路。给出与i个有限的算法来列出所有该环路上的结点。请证明算法的正确性。

思考题

算法导论

发表于 2021-11-30 更新于 2025-04-22 分类于算法阅读次数：本文字数： 406 阅读时长 ≈ 1 分钟

算法导论

goroutine编程题

发表于 2021-11-22 更新于 2025-04-22 分类于算法阅读次数：本文字数： 400 阅读时长 ≈ 1 分钟

题目

创建10个goroutine,id分别是0,1,2,3...9

每个goroutine只能打印最后一位是自己id号的数字，例如: 3号只能打印3, 13, 23, 33...

编写一个程序，依次打印1-10000

第一想法是全局锁，如果只用一个锁，那就是10个goroutine一起抢锁，10个协程加10个锁的话,还要交替解锁。所以选择用channel，goroutine交替向下个管道发送消息。

读取空的channel会根据channel类型返回空的数据，所以需要判断channel读取是否成功，i, ok <- c,判断ok的值

我的解答

解析题目，10个goroutine，但是需要依次打印1-10000，

import (
	"fmt"
	"time"
)


var IsRunning = true

func print(gid int, m map[int]chan int) {
	curChan := m[gid]
	nextChan := m[(gid+1)%10]
	for IsRunning {
		select {
		case i, ok := <-curChan:
			if ok {
				fmt.Println(fmt.Sprintf("%d   goroutine id=%d", i, gid))
				i++
				if i > 10000 {
					IsRunning = false
				} else {
					nextChan <- i
				}
			}
		}
	}

}

func printInOrder() {

	memo := map[int]chan int{}
	for i := 0; i < 10; i++ {
		c := make(chan int, 1)
		memo[i] = c
	}
	fmt.Printf("%#+v\n", memo)

	for i := 0; i < 10; i++ {
		go print(i, memo)
	}
	firstChan := memo[0]
	firstChan <- 0
	for IsRunning {
		// time.Sleep(time.Millisecond)
	}
	defer func() {
		for k, c := range memo {
			fmt.Printf("关闭: %d\n", k)
			close(c)
		}
	}()
}

func main() {
	start := time.Now()
	printInOrder()
	fmt.Printf("用时: %s", time.Since(start))
}

# 输出:
9976   goroutine id=6
9977   goroutine id=7
9978   goroutine id=8
9979   goroutine id=9
9980   goroutine id=0
9981   goroutine id=1
9982   goroutine id=2
9983   goroutine id=3
9984   goroutine id=4
9985   goroutine id=5
9986   goroutine id=6
9987   goroutine id=7
9988   goroutine id=8
9989   goroutine id=9
9990   goroutine id=0
9991   goroutine id=1
9992   goroutine id=2
9993   goroutine id=3
9994   goroutine id=4
9995   goroutine id=5
9996   goroutine id=6
9997   goroutine id=7
9998   goroutine id=8
9999   goroutine id=9
10000   goroutine id=0
用时: 392.8411ms