Go
by smallnest

使用算法检测英超中的食物链

最近看到一篇新闻: 英超再现恐怖食物链!20强相生相克 今年用了14轮，对于足球和英超感兴趣的读者一定了解，所谓食物链是指A队胜过B队，B队胜过C队,……，N队也胜过A队，截止到英超第14轮，根据所有的队伍的胜负关系，一条最大的食物链已经形成，英超20队都加入到这个食物链中，相生相克。

我看到这篇新闻的时候，有一点点程序员的不由自主的想法，能否通过算法检查目前最大的食物链，以及能否将食物链罗列出来？这也算是算法解决实际问题的一个很好的例子吧。

很自然的，可以通过图来表示两队之间的已经比赛的关系，因为我们我们只考虑胜负关系，不考虑平局，所以可以使用有向图来表示。食物链可以单纯用胜或者负来表示，所以我们的有向图中以胜表示两个节点之间的关系。

当然，我对图相关的算法不是很熟悉，所以特地搜了一下相关的成熟的算法。对于食物链这个求解，我们可以看成求解这个有向图中是否存在一个环，这个环包含所有的20个节点（20个英超队）。也就是求解这个图中的强连通分量。

百度百科： 有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。

相关的算法包括 Kosaraju、Tarjan、Gabow等, 感兴趣的朋友可以搜搜相关的介绍。

我使用 http://github.com/looplab/tarjan 提供的tarjon算法来计算：

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
package main
import (
	"fmt"
	"github.com/looplab/tarjan"
)
func main() {
	graph := make(map[interface{}][]interface{})
	graph["切尔西"] = []interface{}{"曼城", "热刺", "米德尔斯堡", "埃弗顿", "南安普顿", "曼联", "莱切斯特城", "胡尔城", "伯恩利", "沃特福德", "西汉姆"}
	graph["阿森纳"] = []interface{}{"西汉姆", "伯恩茅斯", "桑德兰", "斯旺西", "伯恩利", "切尔西", "胡尔城", "南安普顿", "沃特福德"}
	graph["利物浦"] = []interface{}{"桑德兰", "沃特福德", "水晶宫", "西布罗姆维奇", "斯旺西", "胡尔城", "切尔西", "莱切斯特城", "阿森纳"}
	graph["曼城"] = []interface{}{"水晶宫", "伯恩利", "西布罗姆维奇", "斯旺西", "伯恩茅斯", "曼联", "西汉姆", "斯托克城", "桑德兰"}
	graph["热刺"] = []interface{}{"斯旺西", "西汉姆", "曼城", "米德尔斯堡", "桑德兰", "斯托克城", "水晶宫"}
	graph["曼联"] = []interface{}{"斯旺西", "莱切斯特城", "胡尔城", "南安普顿", "伯恩茅斯"}
	graph["西布罗姆维奇"] = []interface{}{"沃特福德", "伯恩利", "莱切斯特城", "西汉姆", "伯恩茅斯", "水晶宫"}
	graph["埃弗顿"] = []interface{}{"西汉姆", "斯托克城", "西布罗姆维奇"}
	graph["斯托克城"] = []interface{}{"伯恩利", "沃特福德", "斯旺西", "胡尔城", "桑德兰"}
	graph["伯恩茅斯"] = []interface{}{"利物浦", "斯托克城", "胡尔城", "埃弗顿", "西布罗姆维奇"}
	graph["沃特福德"] = []interface{}{"莱切斯特城", "胡尔城", "米德尔斯堡", "曼联", "西汉姆"}
	graph["南安普顿"] = []interface{}{"埃弗顿", "伯恩利", "西汉姆", "斯旺西"}
	graph["米德尔斯堡"] = []interface{}{"胡尔城", "伯恩茅斯", "桑德兰"}
	graph["水晶宫"] = []interface{}{"南安普顿", "桑德兰", "斯托克城", "米德尔斯堡"}
	graph["埃弗顿"] = []interface{}{"西汉姆", "米德尔斯堡", "桑德兰"}
	graph["伯恩利"] = []interface{}{"水晶宫", "埃弗顿", "沃特福德", "利物浦"}
	graph["莱切斯特城"] = []interface{}{"水晶宫", "伯恩利", "斯旺西"}
	graph["西汉姆"] = []interface{}{"桑德兰", "水晶宫", "伯恩茅斯"}
	graph["桑德兰"] = []interface{}{"莱切斯特城", "胡尔城", "伯恩茅斯"}
	graph["胡尔城"] = []interface{}{"南安普顿", "斯旺西", "莱切斯特城"}
	graph["斯旺西"] = []interface{}{"水晶宫", "伯恩利"}
	output := tarjan.Connections(graph)
	fmt.Printf("%d, %v\n", len(output[0]), output)
}

运行可以得到它的强连通分量:

1
20, [[阿森纳 热刺 曼联 曼城 切尔西 斯旺西 西布罗姆维奇 利物浦 伯恩茅斯 米德尔斯堡 沃特福德 伯恩利 斯托克城 水晶宫 莱切斯特城 桑德兰 西汉姆 埃弗顿 南安普顿 胡尔城]]

可以看到，这个强连通分量包含所有的20个队伍，说明第14轮结束后英超最长的食物链已经形成。

但是这个结果并没有将这个食物链返回，这个结果只是表明这20个队伍形成了食物链。

因为本人对相关的算法不熟悉，了解的读者回答下面的问题，或者提供自己的代码：

  1. Tarjan算法和Gabow算法不能将这个拓扑关系计算出来，而Kosaraju算法可以？
  2. 因为数据量不大，可以直接通过 DFS 算法进行搜索？

西甲的最大食物链是否形成了，答案是否定的，因为皇马前14轮还未输球。有兴趣的读者可以计算一下目前西甲的最大的食物链包括哪些球队。