Huangstomach's Blog

有的时候总是能听到许多新的名词，并且背后的解释还容易令人混淆。有的时候重复造轮子，有的时候换汤不换药。

并发和并行

并发的概念经常可以听到，也总会和并行放到一起讨论，但是实际上并发和并行是两个不同的概念。简单来说并发可以认为是早期单核CPU做完成的工作，让多个程序来一段时间内来回切换让大家认为计算机在同时执行多个程序。而并行则是多核CPU的概念，可以真正的同时执行多个程序。

并发

处理多个待定任务，一次处理一个或者一部分，然后转而处理另一个任务，再转而处理另一个任务，如此循环。对于单核的CPU，如果操作系统的调度程序支持交叉执行待定任务，也能实现并发。并发也叫多任务处理。

并行

同时执行多个计算任务的能力。需要一个多核CPU、多个CPU、一个GPU或一个集群中的多台计算机。

并行是真正意义上的同时做，类似于团队协作，多个人聚在一起分工合作完成一个任务。当然一个任务也可以由一个人来完成，但这些任务在一个人的手中永远是不停切换来做的，而不是真正意义上的同时做，这就是并发。

并发和并行在开发中离不开执行单元的支持，比如进程、线程、协程等。

执行单元

进程

进程是计算机程序运行时的一个实例，消耗内存和部分的CPU时间。进程与进程之间相互隔离，都隔离在自己的私有内存空间中，进程之间的通信需要通过进程间通信（IPC）的方式。进程可以派生子进程，子进程可以继承父进程的资源，但是子进程的内存空间是独立的。操作系统的调度程序会定期挂起运行中的进程，让其他进程运行，这样挂起单个进程不会导致整个系统的挂起。

线程

单个进程中的执行单元。一个进程启动后只使用一个主线程，但是可以创建多个子线程。线程之间共享进程的资源，比如内存空间，但是每个线程都有自己的寄存器和栈空间。线程之间的通信可以通过共享内存或者消息传递的方式。线程之间的切换不会导致整个进程的挂起，但是线程之间的切换需要操作系统的调度程序来完成。线程在同一份作业下，消耗的资源比进程少。

协程

可以挂起自身并在以后恢复的函数。协程可以在执行过程中挂起，然后转而执行其他协程，这个过程可以重复多次。协程支持协作式多任务处理：一个协程必须使用yield或await或其他挂起点显式地放弃控制权，以便其他协程可以执行。协程可以在单线程中实现并发，因为它们是协作式的，而不是抢占式的。

以前对协程的非常不理解，总觉得一定要属于更细粒度的线程以及具备更多的并发操作空间。实际上不然，协程主要是通过程序来控制并保存当前状态，切换代价较小，具备线程所不具备的效率。

例如在网络请求中，数据需要经过网络以及其他的IO缓冲区，此时可以应用协程发出请求后立即转移CPU所有权，等待数据返回后再将CPU所有权转移回协程，这样就可以在等待数据的时候不阻塞主线程，提高了程序的执行效率。

或者遍历发送多个网络请求，在使用协程时，每个协程在发送请求后不会阻塞，控制权会交还给事件循环，于是可以同时发送多个请求而不用排队等待。最后可以遍历协程的实例来按照完成顺序获得结果。

再或者在构建Web服务的时候，定义接收请求的函数为协程，当遇到IO阻塞操作时将其交由协程操作（或特殊情况交由其他线程），可以不阻塞主线程，使其可以转而处理其他请求，实现了在单线程中处理多请求的效果。

协程的实现方式有很多，比如Python中的asyncio，Go中的goroutine，Java中的Quasar等。其中Javascript中的generator和async/await是比较常用的。async/await也是生成器和Promise的语法糖，整体使用上比较简单，各种语言具体使用也极为相似。

至于纤程的概念，此文中有详细的讨论，大部分场景下没有区别。

github的一些简单妙用

Pull request

Pull request在参与开源项目的时候是一个非常常用的功能，可以在提交代码时不影响到当前分支，并由项目所有团队进行审核讨论，依据结果考虑是否合并。

为开源项目贡献代码操作很简单，fork想要贡献的项目，然后在本地clone自己的项目，修改后提交到自己的项目，就可以在git上提交pr(pull request)了。

但是经常会遇到的一个问题，当提交完pr之后，源项目仍然会有其他的开发者贡献代码，当自己再想要提交pr的时候会发现本地的clone项目和源项目已经不一致了，这时候就需要同步源项目的代码到自己的项目了。

不过这个功能很难在github上直接找到，不过可以先观察第一次创建pr时候的方法。以开源项目mbrn/material-table为例，当我们点击clone项目的New pull request按钮时：

会跳转到提交新pr的页面，可以看到url形如：

1

https://github.com/mbrn/material-table/compare/master...HuangStomach:material-table:master

的url，对应界面则可以看到：

直观的理解就是将本地clone项目的提交，形成pr提交到源项目。

同理，为了实现同步源项目的代码到clone项目，我们只需要将url的内容进行调换，url形如：

1

https://github.com/HuangStomach/material-table/compare/master...mbrn:material-table:master

将这个url输入到浏览器，可以看到：

我们就将源项目的代码提交同步到了自己的clone项目，这样就可以再次提交pr了。

Diff

diff这个功能很常用，在本地查阅自己的本地修改都涉及到哪些文件的哪些内容时经常会用到，往往出现在git的commit信息中。

但有时候有这样的需求，希望观察某个提交head到某个提交head之间文件都做了哪些更改，可以考虑使用git diff命令：

1
2
3
4
5
6

usage: git diff [<options>] [<commit>] [--] [<path>...]
   or: git diff [<options>] --cached [--merge-base] [<commit>] [--] [<path>...]
   or: git diff [<options>] [--merge-base] <commit> [<commit>...] <commit> [--] [<path>...]
   or: git diff [<options>] <commit>...<commit> [--] [<path>...]
   or: git diff [<options>] <blob> <blob>
   or: git diff [<options>] --no-index [--] <path> <path>

不过这种diff显示的输出被称为source diff，不是很直观。尤其在想整体显示具体更改了哪些内容时，这种diff显示就不太友好了。而这种需要，称之为rich diff。

rich diff由于其局限性难以在命令行中显示，此时可以考虑使用git diff --word-diff来通过wdiff进行展示。

不过对应上文的url大法，我们也可以在github上更加直观的查看rich diff，考虑url形如：

1

https://github.com/HuangStomach/{rep}/compare/{commit_id}...{commit_id}

则会在web页面直接输出该repository下两commit之间的不同，还可以更加优雅的直接显示rich diff：

记录一下最近进行深度学习开发所使用的一些简单的操作

Pytorch

PyTorch是一个开源的深度学习框架，它为研究工作提供了灵活和模块化，并具有生产部署所需的稳定性和支持。PyTorch为张量计算（如NumPy）等高级功能提供了一个Python包，具有强大的GPU加速功能，并提供TorchScript，以便在急切模式和图形模式之间轻松转换。随着PyTorch的最新发布，该框架提供了基于图形的执行、分布式训练、移动部署和量化。

虽然是由Meta的人工智能团队开发，但有时候Google团队居然也会使用。

Dataset

在进行深度学习训练时，我们一般来说都会需要一个训练集，让我们的算法与模型来从其中学习规律（模式），从而达到基于学得的规律来进行决策的能力。

在使用的深度学习框架时，往往就需要使用它们对应的数据集类，来进行数据的读取和处理。

当然也可以不用，但是不使用的话在出现大规模计算等情况下自己实现一些方法太过复杂也没有必要，往往还是选择对应的框架提供的数据基类来进行实现。

针对Pytorch来说，初始化一个基础的数据集类非常简单，以映射数据集为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

import torch
from torch.utils.data import Dataset

class MyDataset(Dataset):
    def __init__(self, train = True):
        self.device = device
        self.train = train
        
        self.feature_x1 = torch.randn(100, 1)
        self.feature_x2 = torch.randn(100, 1)
        self.y = torch.randn(100, 1)

    def __getitem__(self, index):
        return (
            self.feature_x1[index], 
            self.feature_x2[index], 
            self.y[index]
        )

    def __len__(self):
        return self.y.size(dim=0)

    def _check_exists(self):
        pass

只需要简单的继承Dataset类，然后实现__init__、__getitem__、__len__三个方法即可。

其中__len__方法需要返回数据集的数据条目长度（样本规模），__getitem__方法需要返回对应索引的数据。

代码中简单实现了一个具有两种特征的数据集，每个样本都有两个特征和一个标签，__getitem__方法返回的是一个元组，包含了对应索引的特征和标签。

对于比较小的数据集，可以一股脑的把数据丢入模型中，直接进行梯度下降计算。不过有些数据集（比如计算机视觉）非常的大，可能无法一次性加载到内存中，所以可以考虑只在__init__时存储索引，而在__getitem__时再从硬盘读取，这样虽然比较慢但是可以节省内存。

但有时候，我们需要使用GPU来进行训练，虽然整个数据集合在内存中可以存储，但传递到GPU中又有些勉强，这时候可以考虑使用Dataloader来进行数据的读取。

Dataloader

1
2
3
4
5
6
7
8

from torch.utils.data import DataLoader

train = MyDataset()
trainLoader = DataLoader(train, batch_size=128, shuffle=True)

for epoch in range(1000):
    for x1, x2, y in trainLoader:
        pass

如代码所示，简易的DataLoader可以只传递三个参数，分别是数据集、batch_size和shuffle。

其中batch_size来决定每次在GPU中进行张量计算的数据量，shuffle来决定是否在每个epoch开始时对数据进行打乱。

这样在模型进行反向传播时就转化为了小批量梯度下降，虽然达到最优解的路程会比较坎坷，但是可以有效的减少内存占用，加快训练速度。

Tips

有时候我们的数据集合比较简单，但是计算机性能非常强大，有时候却反而会出现训练速度非常的慢，对应计算单元的占用也非常的低。这时候有一种可能是进行计算推演的时间远远小于将数据集转移到张量计算上的时间，可以考虑进一步增加batch_size来减小到GPU之间的数据交换次数。

学习中常用到的含有特殊意义的罗马字符的英文标识和注音，方便查阅来进行变量命名

C++中，免不了要与指针和地址打交道，但是看着繁多的*和&有时又容易混乱。

*与&

简单来说*在声明时代表的是变量所处地址的指针，可以理解为幸运大转盘的箭头，指向幸运大转盘的一个位置，也就是变量所处的地址。而&表示的就是取该变量的地址，也就是大转盘针头指着的地方。

1
2
3
4
5
6

void main() {
    int num = 1;
    cout << &num << endl;
    int* p = &num;
    cout << p << endl;
}

如上所示，&num打印出来后就是该变量所处的地址信息，也许是40013ac7H，而第四行的int*则是声明了一个指向num地址的指针，这里容易混淆，为何赋值表达式左右是*和&，但意义却不一样？其中*更像一个定位的标志，告诉你该指针现在指向什么地方，比如在连续空间（如数组）中，可以通过对指针进行加法操作：p++来进行顺序访问数组元素，也就是让本指向数组中某个位置的箭头往后移动一位。

1
2
3
4
5
6

void main() {
    int num = 1;
    int* p = #
    cout << *p << endl;
    cout << &p << endl;
}

其中如果在指针变量前加入*则可以获得指针指向的存储空间的内容，这里就是1，而再在前方加上&则可以获取到指针在内存中的地址，毕竟哪怕是一个箭头既然声明了，那么也需要相应的内存空间进行存储。
如果我们再次进行*操作：

1
2
3
4
5
6

void main() {
    int num = 1;
    int* p = #
    cout << *&p << endl;
    cout << **&p << endl;
}

其中*&p中&p是指针（也就是箭头）的地址，那么刚才说了，加上*可以获得箭头所指的内容，那么实际上箭头所指的就是num的地址，也就是&num。如果再加上*那么就能取到&num地址所存放的内容，也就是1了。

左值与右值

左值很好解释：

1
2
3
4

void main() {
    int x = 'x';
    int num = 1;
}

这些在内存中占用空间并拥有地址的值，都是左值，那么什么是右值？

1
2
3
4

void main() {
    int num;
    num = 1 + 2;
}

其中1 + 2就是右值，它只是一个临时的表达式，并没有自己的地址，同时如果去取地址也只会得到报错。

那么右值有什么用呢？在传统的c++中，一行普通的代码可能如下：

1
2
3
4
5
6

class A {}
void main() {
    A a();
    A b();
    a = b;
}

这时候我们会有什么样的操作呢？我们可能得到了b的复制（当然取决于如何定义operator=)，但是这样呢？

1
2
3
4
5
6

class A {}
void main() {
    A a();
    A b();
    a = b + b;
}

这时候b + b明显的是一个右值，我们是否可以得到复制呢？参数列表中我们往往会声明一个A& a的参数，但是刚才有说过，右值往往不拥有自己的地址，那么我们的代码就只能报错了吗？（假定已经实现了operator+），不尽然：

1
2
3
4
5
6
7
8

class A {}
A & A::operator=(A&& a) {}

void main() {
    A a();
    A b();
    a = b + b;
}

我们可以看到，参数列表中的变量类型为A&&，这时候我们就可以简单的捕获到右值了。
右值引用的加入，使得我们可以更好的分辨出移动与复制，也填补了C++中的空白。

最近在阅读清华大学的数据结构教材时，发现其中对于拓扑排序的更为易懂的实现。

拓扑排序，之前也写过，即为一种将杂乱无章的调度问题规划为一个线性的有序排列的排序算法，其中书上是这么描述的:

什么是拓扑排序？简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

说实话如果对离散数学不太了解，突然一看还是很难懂的。不过其中对于该排序的实现则很简单易懂。

入度

入度，这个概念其实很简单，之前所说拓扑排序基本是在有向无环图（即图中路径均是从一个节点指向另一个节点的，且其中不存在循环路径）中产生的，所以必然会有指向某个节点的路径。

其中，被指向的路径的个数则称为入度，也可以想象成被多少个人指着，千夫所指的话这个人的入度就是这个千了。其中入度为0的节点（即没有路径指向该节点）则可以被视为起点，还是应用之前的装修例子来表述，那么就是一项可以无需等待其他工程完成的工程，比如砸墙。

同样，出度所描述的就是该节点指向其他节点的路径数。

拓扑排序

有了入度概念的引入拓扑排序就很简单了，简单的说我们就是要将当前可以直接进行的工作进行排序，于是我们可以直接在构造图，或者拿到图的时候，对其进行一个入度的记录并排序，简单的使用对象或数组都可以做到：

1
2
3
4
5

vector<int, int> 

struct Node {
    int in;
}

我们只要找到一个起点，选择他为入度，就可以开始排序。

将起点放入我们拓扑排序的栈顶，然后将该节点所链接的节点的入度均减少1，然后从中找到入度为0的节点，再次进行同样的操作，拓扑排序就简单的完成了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

// 书中的示意代码
InitStack(S);
for (int i = 0, i < G.vexnum; i++) {
    if (!indegree[i]) Push(S, i); // 查找入度为0的节点
}

count = 0;
while (!StackEmpty(S)) {
    Pop(S, i); // 取出入度为0的节点
    count++;
    for (Node p = G.verices[i].firstarc; p; p = p->nextarc) {
        k = p->adjvex;
        if (!--indegree[i]) Push(S, k); // 入度减为0，则入栈
    }
}

if (count < G.vexnum) return ERROR;

Git要求开发者在编写提交的时候，尽量要填写有用的信息；在工作中更甚，提交写的完善完备更能让问题追踪变得容易可控，不过可能会遇到不小心写错了提交内容的情况，这时候就一定要在推送之前想办法把错误的提交信息修正掉。

提交

Git提交是一件非常简单的事情，对于我来说不过是先检查一下需要提交的文件，然后直接一个git commmit就结束了的工作，当敲下回车，就会出现熟悉的界面：

1
2
3
4
5
6
7
8
9
10
11
12

# Please enter the commit message for your changes. Lines starting
# with '#' will be ignored, and an empty message aborts the commit.
#
# Date:      Mon Aug 5 10:17:05 2019 +0800
#
# On branch master
# Your branch is ahead of 'origin/master' by 1 commit.
#   (use "git push" to publish your local commits)
#
# Changes to be committed:
#       new file:   source/_posts/Git提交与修改.md
#

其中第一行就是提交描述信息，也是最重要的地方；第六行是提交时间，第十二行开始则是本次提交修改的文件概览。

有的时候开发者比较自信或者非常熟练，直接使用git commit -m <message>来进行快速提交。其实commit中除了-m --message之外还可以快速设置一些其他的信息:

1
2
3
4
5
6
7

Commit message options
    --author <author>             override author for commit
    --date <date>                 override date for commit
    -m, --message <message>       commit message
    -c, --reedit-message <commit> reuse and edit message from specified commit
    -C, --reuse-message <commit>  reuse message from specified commit
    --reset-author                the commit is authored by me now (used with -C/-c/--amend)

这边随便列举了几个，如我们可以快速设置作者、时间，甚至使用--reset-author来把某个提交的作者设置成自己，这个参数的说明很有意思，而且后面标注了，要伴随-C/-c/--amend使用，这是什么参数？

修改提交

我们使用man命令来查看一下说明，可以看到其实和：

1
2
3

$ git reset --soft HEAD^
$ #... do something else to come up with the right tree ...
$ git commit -c ORIG_HEAD

是等价的，实际上是创建了一个新的提交而不是直接修改上一个提交，当我键入git commit --amend之后，就会出现熟悉的界面了，这时候就可以把错误的提交信息修正掉了。

同时也可以和其他快捷参数一起使用，比如说你不想看你之前提交信息写的究竟是什么，也可以直接使用

1

$ git commit --amend -m <message>

来快速修改提交信息，同时也可以根据上述参数描述进行修改，比如修改时间：

1

$ git commit --amend --date <date>

不过这里需要注意的是这里的参数是特定的时间格式，可以尝试使用date，不过不能直接使用date命令，因为此处的参数是要求符合RFC 2822标准的，所以需要使用如下命令来查看：

1
2

$ date -R
Mon, 05 Aug 2019 10:50:35 +0800

然后再根据这个格式修改时间就可以完成修改commit提交时间的操作了

1

$ git commit --amend --date='Mon, 05 Aug 2019 10:50:35 +0800'

最近在搞装修，发现在装修的过程中，很容易无法区分各种节点的主次，这时候就想起了拓扑排序。

装修

装修的过程中，一般都要经历很多的节点，比如：砌墙、刷漆、安装空调新风、吊顶、铺设地板瓷砖、水电等等。

大部分的功能其实是相互依赖的，比如你必须砌墙了才能刷漆；安装了新风空调才能吊顶；确定了电器才能打橱柜等等等等。这种繁琐的问题自己捋的时候经常混乱，有时候不得不就咨询施工方，总是怕自己耽误了进度。

这时候突然想到了算法中的调度问题。

逆后序

一般来说，数据结构（尤其是图）的遍历一般分为三种排列顺序。

• 前序
• 后序
• 逆后序

其中逆后序定义是：在递归调用之后将顶点压入栈

也就是说，在节点没有被彻底搜索完之前是不会进入到栈中的，也就是说最先被加入栈的则是没有后续节点的节点，也就是最后的工序比如：进家具。

其中，这些步骤，也就是我们的节点，相互的依赖关系则将它们形成了一副有向图，这也是进行逆后序的关键。

拓扑排序

拓扑排序有可能有很多种算法来实现，主要是为了将杂乱无章的调度问题规划为一个线性的有序排列，为我们解决各种各样的问题，比如装修。逆后序就是其中的一种简单算法。

逆后序实现起来非常简单，如定义一样，只需要在深度优先搜索中加入简单的一段代码：

1
2
3
4
5
6
7
8
9
10
11
12

private boolean[] marked;
private Stack<Integer> reversePost;

// 示意

private void dfs(Digraph G, int v) {
    marked[v] = true;
    for (int w: G.adj(v)) {
        if (!marked[w]) dfs(G, w);
    }
    reversePost.push(v);
}

其中再想获取拓扑排序的时候，只需要简单的进行出栈操作：

1
2
3

for (int v: reversePost) {
    System.out.println(v);
}

就可以非常简单直观的输出所需要的顺序，从而简化了调度任务。

我也就知道我得先赶紧买空调和新风了。

最近在学习字符串查找算法时，遇到了KMP算法，其中关于这块的介绍较为晦涩，记录一下自己的理解

字符串查找

字符串查找是一个应用非常多的功能，无论什么语言都会拥有该功能相关的一些周边函数或者概念，比如SQL。

通常来说，普通开发日常使用的时候，最简单的算法也就是暴力查找：

1
2
3
4
5
6
7
8
9
10
11
12
13

int M = pat.length(); // 需匹配的字符串
int N = txt.length(); // 原文本

for (int i = 0; i <= N - M; i++) {
    int j
    for (j = 0; j < M; j++) {
        if (txt.charAt(i + j) != pat.charAt(j)) break;
    }

    if (j == M) return i;
}

return -1;

这也是非常好理解的一种算法，将原文本中的每个字符都和匹配串的第一个字符进行比较，如果不匹配就去匹配下一个，如果匹配，则继续在匹配字符串中继续查找，直到匹配到末尾则是为成功。

这个算法可以直接达到目的，但是其中仍然有一些可以优化的地方，比如在字符串AABAABAAAA中查找字符串AABAAA时，当匹配到AABAAB的B时，则必然出现匹配失败，按照暴力算法的代码，则会回退到第二个A再次进行匹配，然而很明显，我们知道实际上完全不需要进行这么多的回退，KMP 算法则是为了解决该问题而出现的。

KMP算法

KMP算法网上大多也有介绍，基本上都是基于next[]来判断需要进行多少个字符的回退。

在Sedgewick的《Algorithms》一书中则使用了一种不太一样的计算方法，使得回退无需依赖于原字符串，而是仅仅使用匹配字符串就可以进行回退字符个数的预计，这就要归功于有限状态自动机

有限状态自动机

概念非常简单，就是记录在有限状态下，每个状态可以迁移到的0个或多个状态。简单来说，就类似于一种固定好的有向图，当给入一个属于字母表中的字符的时候，都可以按照预先定义好的状态，按照方向转移到下一个状态中，对应KMP算法则意味着回退到什么地方。

以图中为例，当匹配字符串为ABABAC时，有限状态机定义如下：

先暂定输入字母表为ABC三个字符

• 当输入A的时候，A被匹配到，状态机会认为其可以进行到状态1，输入另外两个则无法进行匹配，则为0

• 当再次输入A的时候，B则无法被匹配到，A字符的状态则被回滚到上个地方1，而输入B被匹配记录状态为2

• 再次输入A则又可以匹配到，此时的A会被记录状态为3，另外两个字符则还是会进行回退

• 当再次输入A的时候，B则无法被匹配到，A字符的状态则被回滚到上个地方1，而输入B被匹配记录状态为4

• 再次输入A则又可以匹配到，此时的A会被记录状态为5，另外两个字符则还是会进行回退

• 再次输入A和B的时候都无法被匹配到，A还是会回滚到1处，而B因为此时重启状态为3，则退回到4的位置

其中重启状态是个比较有意思的概念，就是需要回退到的状态，由于需要右移和忽略最后一个匹配失败，回退状态会在charAt(1)到charAt(j - 1)之间，也就是上一个可以达到的状态。

这种基于有限状态自动机的方式无需进行查找字符串中的回退，减少了消耗，是一种高效的查找算法

开发一种不断使用环的性质的算法来计算最小生成树

环的性质

当构建出一副无向图的最小生成树时可以发现，在无向图中任意将一条边加入最小生成树，都会构建出一个环；因为生成树(不一定最小)实际上会达到图中的所有点，再加入任何一条边都相当于多连接了一遍两个顶点，必然会产生环。

利用这个性质，可一每次都从新产生的环中删除权重最大的边，来不停构造最小生成树。

Vyssotsky

首先可以先随便拟定一个生成树（不一定最小）:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

edges = new Queue<Edge>();
mst = new EdgeWeightedGraph(G.V());
boolean[] marked = new boolean[G.V()];
for (Edge e: G.edges()) {
    int v = e.either();
    int w = e.other(v);
    if (marked[v] && marked[w]) {
        edges.enqueue(e);
        continue;
    }
    
    marked[v] = true;
    marked[w] = true;
    mst.addEdge(e);
}

使用marked来记录点是否已经被连接过，如果两个顶点均被连接过，则将该条边放入备选edges中，否则加入新图，也就是生成树中。

然后不停地将备选边中的边加入到生成树中：

1
2
3
4

while (edges.size() > 0) {
    Edge e = edges.dequeue();
    mst.addEdge(e);
}

此时一定会产生环，使用深度优先算法对环进行检测，从而找到权重最大的边：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public boolean dfs(int start, int end, int skip) {
    for (Edge e: mst.adj(start)) {
        if (set.contains(e.weight())) continue;

        int v = e.other(start);
        if (v == skip) continue;

        if (v == end || dfs(v, end, start)) {
            max = Math.max(max, e.weight());
            return true;
        }
    }
    return false;
}

其中寻找的时候要把前一条边的起点忽略掉，这里就没没有再使用marked数组了。

删除边

然后就是要将权重最大的边删除掉，这里给的加权无向图EdgeWeightedGraph中没有提供删除边的API，也没有说需要自行扩展，这里就利用了所有权重均不相同的性质，将最大权重加入到集合中:

1
2
3
4
5
6
7
8
9

while (edges.size() > 0) {
    Edge e = edges.dequeue();
    max = e.weight();
    mst.addEdge(e);
    
    int v = e.either();
    dfs(v, e.other(v), e.other(v));
    set.add(max);
}

这样虽然是全部边都加入了新图中，但是在我们获取最小生成树的时候，如果遇到了边的权重在集合中，则进行跳过：

1
2
3
4
5
6
7
8

public Iterable<Edge> edges() {
    Queue<Edge> queue = new Queue<Edge>();
    for (Edge e: mst.edges()) {
        if (set.contains(e.weight())) continue;
        queue.enqueue(e);
    }
    return queue;
}

写了下测试，可以通过。整体代码：

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

import java.util.HashSet;

import edu.princeton.cs.algs4.*;

class VyssotskyMST {
    private Queue<Edge> edges;
    private EdgeWeightedGraph mst;
    private HashSet set;
    private double max;
    
    public VyssotskyMST(EdgeWeightedGraph G) {
        edges = new Queue<Edge>();
        set = new HashSet<Double>();
        mst = new EdgeWeightedGraph(G.V());
        boolean[] marked = new boolean[G.V()];
        for (Edge e: G.edges()) {
            int v = e.either();
            int w = e.other(v);
            if (marked[v] && marked[w]) {
                edges.enqueue(e);
                continue;
            }
            
            marked[v] = true;
            marked[w] = true;
            mst.addEdge(e);
        }

        while (edges.size() > 0) {
            Edge e = edges.dequeue();
            max = e.weight();
            mst.addEdge(e);
            
            int v = e.either();
            dfs(v, e.other(v), e.other(v));
            set.add(max);
        }
    }

    public boolean dfs(int start, int end, int skip) {
        for (Edge e: mst.adj(start)) {
            if (set.contains(e.weight())) continue;

            int v = e.other(start);
            if (v == skip) continue;

            if (v == end || dfs(v, end, start)) {
                max = Math.max(max, e.weight());
                return true;
            }
        }
        return false;
    }

    public Iterable<Edge> edges() {
        Queue<Edge> queue = new Queue<Edge>();
        for (Edge e: mst.edges()) {
            if (set.contains(e.weight())) continue;
            queue.enqueue(e);
        }
        return queue;
    }

    public static void main(String[] args) {
        In in = new In(args[0]);
        EdgeWeightedGraph G = new EdgeWeightedGraph(in);
        VyssotskyMST mst = new VyssotskyMST(G);
        for (Edge e: mst.edges()) {
            System.out.println(e);
        }
    }
}

自己描述一边算法也是对思路的一个整理，现在发现其实在第一次遍历中就可以开始环的判断了，没有必要收集起来再做遍历。

目前自己都觉得性能不太好，之后有机会还是会进行优化。