Homework 4

标★的题目为选做题，仅供学有余力的同学尝试，并且评分标准也更严格。请先做完不标★的题目，再尝试做标一个★的题目，再尝试做更多★的题目。

• 图：35+2.2
• 树：9+0.4
• BFS：3+0.0
• DFS：8+0.1
• 二分图：4+0.0
• 拓扑排序与有向无环图：5+0.5

本次作业总分：64+3.2

图

“链式前向星”（11.7分）

我们来介绍一个存储有向图的方法（如果要存储无向图，一般情况下可以把每条边存成两条边，这里不详细介绍了）。

我们用类似邻接表的思想来存储，但并不直接套用vector或list。假定每条边上有一个权值，那么我们可以用这样的方法表示一条边：

struct Edge
{
    Edge *pre;     // 在表中的上一条边
    int to;        // 边的目标点
    Weight weight; // 边的权值，我们不太关心具体是什么类型
};

假设图的点用[0, n)的整数编号，边用[0, m)的整数编号，n与m均小于MAXN与MAXM，则我们只需要用两个数组描述这张图：

Edge edge[MAXM];   // 存储每条边的信息
Edge *first[MAXN]; // 存储每个点的表尾是哪条边（可以为NULL）
int edgeCnt;       // 记录目前一共有多少条边

初始化的过程是比较显然的：

void init()
{
    edgeCnt = 0;
    memset(first, NULL, sizeof(first));
}

(1)

完成这个“遍历”的代码：

void traverse(int u)
{
    // 输出从u出发的所有的边信息
    for(Edge *cur = first[u]; ___①___; cur = cur->pre)
        cout << "Found edge from " << u
             << " to " << cur->to
             << " weight " << cur->weight
             << endl;
    // 这个是按照被添加顺序的逆序输出的
}

cur!=NULL

(2)

完成这个“插入”的代码：

void addEdge(int u, int v, Weight w)
{
    Edge *cur = &edge[edgeCnt++];
    cur->to = ___②___;
    cur->weight = ___③___;
    cur->pre = ___④___;
    ___⑤___ = ___⑥___;
}

v
w
first[u]
first[u]
cur

(3)

完成这个"查找"的代码：

bool findEdge(int u, int v, Weight &w)
{
    // 找是否存在从u到v的边
    // 保证在调用该函数时最多有一条符合条件的边
    // 如果有，在w中存下其权值，并返回true
    // 如果没有，不要改w，并返回false
    for(___⑦___; ___⑧___; ___⑨___)
        if(___⑩___)
        {
            w = ___⑾___;
            return true;
        }
    return false;
}

Edge* cur=first[u]
cur!=NULL
cur=cur->pre
cur->to==v
cur->weight

★(4)

完成这个"删除"的代码：

void removeEdge(int u, int v)
{
    // 删除从u到v的所有边
    ___⑿___;
    for(___⒀___; ___⒁___; ___⒂___)
        if(___⒃___)
        {
            ___⒄___;
            ___⒅___;
        }
}

if(first[u]->to==v) {first[u]=first[u]->pre; return;}
Edge* cur=first[u]
cur!=NULL
cur=cur->pre
cur->pre->to==v
cur->pre=cur->pre->pre;
removeEdge(v,u)//这个是我瞎猜的

复杂度（21.5分）

对于以下这些存储有向图的方法：

• 邻接矩阵//1
• ★以vector实现的邻接表，每个vector的元素无序//2
• 以vector实现的邻接表，每个vector的元素有序//3
• 以list实现的邻接表，每个list的元素无序//4
• ★以list实现的邻接表，每个list的元素有序//5
• ★★以set实现的邻接表//6
• 上述“链式前向星”//7

设图有$n$个点，$m$条边，写出下列复杂度。除了空间复杂度以外，如果是均摊，则必须注明这个复杂度是均摊复杂度，同时注明此时的最坏复杂度。

1. 空间复杂度
2. 添加一条边的时间复杂度（假设边的起点当前的入度为$k$）
3. 查找一条边的时间复杂度（$k$同上）
4. 删除一条边的时间复杂度（假设这条边已被找到，$k$同上；但对于“链式前向星”，以上述removeEdge函数为准）
5. 列出从某个点出发的所有边的时间复杂度（$k$同上）

子图计数（4分）

对于一个$n$个点，$m$条边的无向简单图：

1. 有多少个生成子图？ 2^m
2. 有多少个导出子图？
3. 有多少个边导出子图？
4. 给出一个时间复杂度为$O(n^2 2^n)$的算法，计算其有多少个子图。

树

时间复杂度（3.1分）

某同学设计了一个算法，这个算法接受一棵树作为输入，其运行时间是所有点的度数的$k$次方之和。对于以下的$k$值，分别求这个算法的最坏时间复杂度，并给出一个例子（无需证明）。

1. $k=1$
2. $k=2$
3. $k=3$
4. ★$k=0.5$

二叉树的叶子（6分）

1. 对于8个点的二叉树，求其最少与最多的叶子个数，并分别举出一个例子。
   最少：一个【退化成链】 最多：4个【完全二叉树】
2. 证明所有$n$个点的真二叉树的叶子个数都相同，并求出这个叶子个数。
   

   对于一个真二叉树，假设有k个叶子，那么有n-k个点不是叶子。其中有n-k-1个点满足：自己不是叶子，也是某个点的儿子。n-k个点不是叶子，但是为了满足真二叉树性质，需要有2*n-2*k个儿子。总共的儿子的数量=n-k-1+k=2n-2k ,得到k=(n+1)/2.

★★无聊的证明题（0.3分）

1. n个结点，n-1条边的连通无向图
2. 无向无环连通图
3. 任意两个结点之间有且仅有一条简单路径的无向图

请你证明这一点。你可以分别证明“1→2”“2→3”“3→1”，或分别证明“1→3”“3→2”“2→1”，或用你喜欢的方法证明。

BFS

阅读理解（3分）

下面这段代码试着在某个有向图上进行BFS。它从某个起点出发开始搜索，按照搜索的顺序依次输出每个点及其到起点的距离。

int dist[MAXN];
bool visit[MAXN];
queue<int> q;
q.push(起点);
dist[起点] = 0;
memset(visit, false, sizeof(visit));
while(q.size())
{
    int u = q.top(); q.pop();
    //visit[u] = true;
    输出：搜索到了点u，其距离为dist[u]
    for(u出发的每一条边的另一个点v)
        if(!visit[v])
        {
            dist[v] = dist[u] + 1;
            q.push(v);
            //visit[v]=1;
        }
}

1. 给出一个图，使得上述代码不正确（包括但不限于：死循环、运行错误、输出距离错误、多次输出同一个点等）。
   1 2
2 1
1 1
2. 改正上述代码。
3. 举出一个有向图的例子，使得在正确的BFS下，虽然每个点到起点的距离是唯一确定的，但是输出所有点的顺序（即BFS序列）会随着每个点遍历相邻点的顺序的变化而发生变化。
   1 2
2 3
2 4
1 5
5 6
5 7

DFS

全排列（3分）

以下程序试图输出序列[1, 2, 3, ..., n]的全排列。请将其补全。

bool visit[MAXN];
int a[MAXN];
int n;
void dfs(int x)
{
    if(x > n)
    {
        for(int i = 1; i <= n; i++)
            cout << a[i] << " \n"[i == n];
    }
    else
    {
        for(int i = 1; i <= n; i++)
            if(!visit[i])
            {
                ___①___;//visit[i]=1
                a[x] = i;
                dfs(x + 1);
                ___②___;//visit[i]=0
            }
    }
}
int main()
{
    memset(visit, false, sizeof(visit));
    cin >> n;
    dfs(___③___);//1
    return 0;
}

找父亲（5分）

在通常的有关树的题目当中，输入数据格式往往只像一般的无向图一样，只给出“谁和谁之间有边”的信息，而不告诉你点之间的父子关系。

本题中我们要做的就是用DFS的方法求出父子关系来。

设输入的树有n个点，用[1, n]这些正整数编号。

(1)

假设输入格式为n - 1行，每行两个整数表示一条边。先将这些边存到一个邻接表中：

vector<int> adj[MAXN];
主程序中调用：
for(int i = 1; i < n; ++i)
{
    int u, v;
    scanf("%d%d", &u, &v);
    ___①___adj[u].push_back(v);adj[v].push_back(u);
}

(2)

然后我们用DFS求出父亲。令点1为根，并规定其父亲为0：

int father[MAXN]; // 记录每个点的父亲
void dfs(int u, int fa)
{
    // 当前搜索u的子树，且u的父亲为fa
    father[x] = fa;
    for(adj[u]中的每个元素v)
        if(___②___)//v!=fa
            dfs(___③___, ___④___);//v    //u
}
主程序中调用：
dfs(1, 0);

(3)

最后，如果有需要的话，建立每个点的儿子列表：

vector<int> childs[MAXN];
主程序中调用：
for(int i = 1; i <= n; i++)
    ___⑤___;//for(adj[u]中的每个元素v) childs[u].push_back(v);

★两个方法等价吗？（0.1分）

某同学希望写个程序判断一个n个点的无向图是否是连通图。首先，他写了一个DFS程序：

vector<bool> visited;
void dfs(int x)
{
    // 假设所有的点标号为[0, n)的整数
    if(visited[x])
        return;
    visited[x] = true;
    for(每个与x相邻的点y)
        dfs(y);
}

他想到了两种方法判断。第一种是：

bool connected1()
{
    visited.resize(n);
    for(int i = 0; i < n; i++)
        visited[i] = false;
    dfs(0);
    for(int i = 0; i < n; i++)
        if(!visited[i])
            return false;
    return true;
}

然而，他之前写了另一个程序，用来计算一个图的连通分支数：

int components()
{
    visited.resize(n);
    for(int i = 0; i < n; i++)
        visited[i] = false;
    int ans = 0;
    for(int i = 0; i < n; i++)
        if(!visited[i])
        {
            dfs(i);
            ++ans;
        }
    return ans;
}

所以，他的第二种方法就是：

bool connected2()
{
    return components() == 1;
}

现在，他希望你判断这两种方法是否等价。假定输入的n不太大，最多不会超过几万的级别。

你需要做以下几件事情的任何一个就算完成本题：

• 证明这两种方法是等价的。
• 提供一个输入的图，使得这两个函数的返回值不相等（两个函数同时返回了错误结果也不行，必须让它们的返回值不相等）。
• 提供一个输入的图，使得这两个函数的某一个无法得到结果（包括运行时错误、死循环等）。

二分图

二分图（4分）

对于$n$个点的二分图：

1. 最少有多少条边？n-1
2. 最多有多少条边？(n/2)^(n/2)
3. 如果给每个点染色，使得任意一条边连接的两个点的颜色都不同，有多少种方案？
4. 证明$n$个点的树一定是二分图。
   对于一个树来说，两点之间只有一条路径，所以一定没有环。

拓扑排序与有向无环图

拓扑排序及方案（4.2分）

给你一个有向图，有$n$个点和$m$条边。

• 简要描述一个算法，能在$O(n+m)$的时间内判断是否有拓扑排序方案。

下面假定方案存在。

• 简要描述一个算法，能在$O(n+m)$的时间内输出一个拓扑排序方案。
• 简要描述一个算法，能在$O(n+m)$的时间内检验一个拓扑排序方案是否合法。

下面如果要求方案数，你可以假定只需对某个不超过计算机字长的质数取模。

• 简要描述一个算法，能在$O(k(n+m))$的时间内求出拓扑排序的方案数，并输出所有的方案。其中$k$表示方案数。
• ★简要描述一个算法，能在$O(n^2 2^n)$的时间内求出拓扑排序的方案数。
• ★★简要描述一个算法，能在$O(2^n)$的时间内求出拓扑排序的方案数。

有向无环图上的单源最短路（1.3分）

给你一个有向无环图，边上带权（为整数），和一个特殊点作为起点。

1. 假设所有的边权均为1，简要描述一个算法，能在$O(n+m)$的时间内求出起点到每个点的最短路长度。
   /dijkstra算法：每次将当前点所连接的所有点入队，更新到新点的最短路径，最后得到终点最短路/
2. ★不对边权做任何假设（可能为负数），简要描述一个算法，能在$O(n+m)$的时间内求出起点到每个点的最短路长度（提示：可先拓扑排序，当然这不是必要的）。
3. ★不对边权做任何假设，并另外给出一个特殊点作为终点，简要描述一个算法，能在$O(n+m)$的时间内求出起点到终点的最短路长度，并输出一条可行的路径。
4. ★★不对边权做任何假设，并另外给出一个特殊点作为终点，简要描述一个算法，能在$O(n+m)$的时间内求出起点到终点的最短路长度，并输出最短路的条数。

Written with StackEdit.