斯坦福算法专项课程Course2 week1习题解析

这一部分将带来Course2 week1的习题解析。

选择题

选择题1

给定有向图的邻接列表表示,其中每个顶点记录其出去的边的数组(不是入边的数组),在最坏的情况下,需要多长时间来计算给定顶点的入度?

像往常一样,我们使用$n$和$m$分别表示给定图的顶点和边的数量。还有,让$k$表示顶点的最大入度。(回想一下顶点的入度是输入它的边数。)

  • 无法确定
  • $\theta(k)$
  • $\theta(m)$
  • $\theta(n)$

只要遍历一遍全部的边,就可以计算出每个顶点的入度,所以为$\theta(m)$

选择题2

考虑以下问题:给定有$n$个顶点$m$条边的无向图$G$以及两个顶点$s$和$t$,是否存在至少一个$s-t$路径?

如果$G$用邻接列表表示,则可以在$\theta(m+n)$时间解决上述问题 ,使用BFS或DFS。

如果$G$用邻接矩阵表示。在最坏的情况下,需要什么运行时间才能解决上述计算问题?(假使,假设$G$没有平行的边缘。)

  • $\theta(n^2)$
  • $\theta(m+n\log n )$
  • $\theta(m+n)$
  • $\theta(m\times n)$

可以先通过邻接矩阵构造邻接表,时间为$\theta(n^2)$,接着使用BFS,时间复杂度为$\theta(n+m)$,因为$m= O(n^2)$,所以总共的时间复杂度为$\theta(n^2)$

选择题3

此问题探讨了关于图距离的两个定义之间的关系。在这个问题中,我们只考虑无向和连接的图。图的直径是任意两点$s,t$的最短距离的最大值。(回想一下$s,t$之间的最短路径距离是$s,t$中边数最少的路径。)

接下来,对于顶点$s$,令$l(s)$表示所有顶点$t$距离$s$的最短距离的最大值。图的半径是所有$l(s)$中的最小值。

对于半径$r$和直径$d$,以下哪个不等式总是成立

  • $r\ge d$
  • $r\le d / 2$
  • $r\ge d / 2$
  • $r\le d$

令$c$是使得$l(s)$最小的顶点,$d(x,y)$表示$x,y$之间的最短距离。

那么对于任意的顶点$s,t$,显然$d(s,c) \le l(c) =r,d(t,c) \le l(c) =r$,路径$s-c-t$的长度显然大于等于$s-t$的最短路径,由$s,t$的任意性可知

另外,由定义可知$l(s) \le d$,所以$r\le d$,因此第三项和第四项正确。

选择题4

考虑我们用于计算基于深度优先搜索的拓扑排序的算法(即,不是“直接解决方案”)。假设图$G$不是非循环的。显然它不会计算拓扑顺序(因为不存在)。它是否计算了一个最小化后退边数的排序?

例如,考虑具有六个有向边的四节点图$(s,v),(s,w),(v,w),(v,t),(w,t),(t,s)$ 。假设顶点的顺序是$s,v,w,t$。然后有一个向后的弧线,$(t,s)$弧。没有顺序的顶点具有零向后弧。

  • 总是
  • 当且仅当图示有向图
  • 有时候可以,有时候不行
  • 从不

这题没有完全理解,感觉是第三个选项。

选择题5

向有向图添加一个额外边$G$,强连接组件(SCC)的数量.?

  • 永远不会减少超过1
  • 永远不会减少
  • 肯定不会改变
  • 可以保持不变

查看下图即可,添加一个额外边,SCC数量不变,最后一项正确:

编程题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <stack>
using namespace std;

const int N = 1e6;

//定义图
vector <int> G[N], Grev[N];
//判断是否访问过
int flag[N];
//leader数组
int leader[N];
//结束时间
int finish[N];
//结束时间->节点编号
int Index[N];
//leader
int s;
//访问时间
int t;
//节点数量
int n = 1;

bool cmp(int a, int b){
return a > b;
}

//深度优先搜索(第一轮)
void DFS_v1(vector <int> Graph[], int i){
//初始化栈
stack <int> Q;
Q.push(i);
flag[i] = 1;
//记录顺序
vector <int> tmp;
while (!Q.empty()){
int u = Q.top();
Q.pop();
leader[u] = s;
//存储结果
tmp.push_back(u);
//入队
for (int k = 0; k < Graph[u].size(); k++){
int v = Graph[u][k];
if (flag[v] == 0){
flag[v] = 1;
Q.push(v);
}
}
}
//计算finish, Index;
for (int j = tmp.size() - 1; j >= 0; j--){
int u = tmp[j];
t++;
finish[u] = t;
Index[t] = u;
}
}

//深度优先搜索(第二轮)
void DFS_v2(vector <int> Graph[], int i, int& cnt){
//初始化栈
stack <int> Q;
Q.push(i);
flag[i] = 1;
while (!Q.empty()){
int u = Q.top();
Q.pop();
//入队
for (int k = 0; k < Graph[u].size(); k++){
int v = Graph[u][k];
if (flag[v] == 0){
flag[v] = 1;
Q.push(v);
}
}
//更新计数
cnt++;
}
}

//递归版本
//void DFS_v1(vector <int> Graph[], int i){
// flag[i] = 1;
// leader[i] = s;
// for (int k = 0; k < Graph[i].size(); k++){
// int j = Graph[i][k];
// if (flag[j] == 0){
// DFS_v1(Graph, j);
// }
// }
// t++;
// finish[i] = t;
// //记录时间和索引的关系
// Index[t] = i;
//}

//void DFS_v2(vector <int> Graph[], int i, int &cnt){
// flag[i] = 1;
// cnt++;
// for (int k = 0; k < Graph[i].size(); k++){
// int j = Graph[i][k];
// if (flag[j] == 0){
// DFS_v2(Graph, j, cnt);
// }
// }
//}

int main(){
//输入
//文件名
char filename[] = "SCC.txt";
freopen(filename, "r", stdin);
//记录节点数量
int u, v;
while (scanf("%d %d", &u, &v) != EOF){
n = max(n, u);
n = max(n, v);
G[u].push_back(v);
Grev[v].push_back(u);
}

//第一轮
//初始化
memset(flag, 0, sizeof(flag));
t = 0;
for (int i = n; i >= 1; i--){
if (flag[i] == 0){
//设置leader
s = i;
DFS_v1(Grev, i);
}
}

//第二轮
memset(flag, 0, sizeof(flag));
//记录SCC的元素数量
vector <int> res;
for (int k = n; k >= 1; k--){
int i = Index[k];
int cnt = 0;
if (flag[i] == 0){
DFS_v2(G, i, cnt);
res.push_back(cnt);
}
}

//排序
sort(res.begin(), res.end(), cmp);
//输出
int m = (res.size() > 5)? 5: res.size();
for (int i = 0; i < m; i++){
printf("%d", res[i]);
if (i < m - 1){
printf(", ");
}else{
printf("\n");
}
}

return 0;
}

思考题

思考题1

In the 2SAT problem, you are given a set of clauses, where each clause is the disjunction of two literals (a literal is a Boolean variable or the negation of a Boolean variable). You are looking for a way to assign a value “true” or “false” to each of the variables so that all clauses are satisfied —- that is, there is at least one true literal in each clause. For this problem, design an algorithm that determines whether or not a given 2SAT instance has a satisfying assignment. (Your algorithm does not need to exhibit a satisfying assignment, just decide whether or not one exists.) Your algorithm should run in $O(m+n)$ time, where $m$ and $n$ are the number of clauses and variables, respectively. [Hint: strongly connected components.]

参考资料:https://wenku.baidu.com/view/0f96c3daa58da0116c1749bc.html

假设布尔变量集为$B=\left\{b_{1}, b_{2}, \cdots, b_{n}\right\}$,包含$B$元素取反的集合为$\hat{B}=\left\{b_{1}, b_{2}, \cdots, b_{n}, \neg b_{1}, \neg b_{2}, \cdots, \neg b_{n}\right\}$,将$\hat B$中$2n$个节点视为图的节点,我们的目标是选择这$2n$个节点中$n$个节点($b_i ,\neg b_i$不能同时出现),使得这些节点的值为true。接着考虑$x\vee y $表示的含义,注意到我们有

所以如果选择了$\neg x$,即$\neg x = \text{true}$,那么必然要选择$y$(即$\neg y = \text{false}$);反之,如果选择了$\neg y$,那么必然要选择$x$,所以$x\vee y$,对应了图中两条边$(\neg x, y),(\neg y, x)$。注意到如果选择了$y$,那么不一定需要选择$\neg x$,所以该边是有向的。因为一共有$m$组clause,所以图中一共有$2m$条边,这样就构造了一个有向图。

接着对该图计算SCC,如果存在$b_i , \neg b_i$属于同一个强连通分量,那么该2SAT问题必然无解,反之有解,因为该图一共有$2n$个节点,$2m$条边,所以时间复杂度为$O(m+n )$