转载

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

最近看到一篇新闻: 英超再现恐怖食物链!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算法来计算：

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)
}

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

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

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

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

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

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

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

原文 http://colobu.com/2016/12/10/Food-Chain-of-Premier-League/

正文到此结束

所属分类：编程技术

本文标签： 程序员 git 代码 GitHub IO 数据 ACE UI http map src 食物 Connection tar 百度
版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
本文海报： 生成海报一生成海报二

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

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

热门推荐

相关文章

说给你听

本文目录

随机标签

书籍教程

近期评论

网站信息

其他链接

关于本站

问题交流