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

最近看到一篇新闻: 英超再现恐怖食物链!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轮还未输球。有兴趣的读者可以计算一下目前西甲的最大的食物链包括哪些球队。