Число Бейкона
Немного истории, Кевин Бейкон американский актёр сыгравший во множествах фильмам, в 1994 отметил что актёры, с которыми он снимался, работали со всеми голливудскими (и не только) актёрами. Общественность тут же отреагировала и создала игру “назвать имя актёра и связать его с Кевином Бейконом”. Корпорация добра даже встроила игру в свой поисковик, например Число Бейкона для актёра Джона Траволты равно 2 (Джон снимался с Оливией Ньютон-Джон в фильме Бриолин, она же, в свою очередь, сыграла с Кевином Бейконом в фильме “У нее будет ребенок”).
А теперь давайте поговорим о том, как эту игру можно представить, и как можно вычислить число Бейкона при помощи графа.
Граф
В данном случае, я буду рассматривать направленный невзвешенный граф, где вершинами будут актеры, a ребрами — фильмы (данные можно взять с IMDb), в которых они снимались, под стартовой (нулевой) вершиной будет Кевин Бейкон. Число Бейкона в таком графе будет равно количеству hop`ов от стартовой вершины до искомой или для всех остальных. Для примера я выбрал такой вот граф:
Алгоритм который производит поиск называется “Поиск в ширину” (Breadth-first search) и делает необходимые нам вычисления за O(n+m) операций, где n — количество вершин, а m — количество рёбер, то есть, за линейное время, что весьма неплохо. Для реализации алгоритма нам понадобится обычная очередь (FIFO), куда мы будет помещать все встретившиеся нам вершины.
И так первый шаг, взять стартовую вершину и поместить её в очередь. Далее у нас будет цикл, условием выхода из которого будет проверка очереди на пустоту. В каждой итерации достаём вершину из очереди, берём всех потомков этой вершины, при этом помечая ребро как исследованное, и если вершина все ещё не исследована, то помечаем её таковой и отправляем в очередь.
Как это выглядит на нашем примере:
— помечаем вершину 0 как стартовую и помещаем её в очередь
Далее цикл пока очередь не пуста
— достаём нулевую вершину, по рёбрам (0,1) и (0,2) берём потомков, т.к. эти вершины встречаются нам первый раз, то помещаем их в очередь, отметив их исследованными и установив их HopLevel на единицу больше чем у родителя (в данном случае 1)
— следующая вершина, при её обработке в очередь попадут вершины 3 и 4, при этом уровень для них установится равный 2
— далее вершина 2, в этом случаем потомок 4 не попадёт в очередь т.к. он уже исследован выше, только 5 будет отравлена в очередь с уровнем равным 2
— вершина 3, которая отправит в очередь потомка 6 с уровнем 3
— остальные вершины будут просто изъяты из очереди.
— на вершине 6 очередь опустеет и цикл завершится
Небольшой код на Go:
Код
package main import ( "container/heap" "fmt" ) type Node struct { HopLevel int Explored bool Edges []int index int //internal variable } type Graph []*Node type Queue []*Node func (q Queue) Len() int { return len(q) } func (q Queue) Less(i, j int) bool { return q[i].index < q[j].index } func (q Queue) Swap(i, j int) { q[i], q[j] = q[j], q[i] } func (q *Queue) Push(x interface{}) { *q = append(*q, x.(*Node)) } func (q *Queue) Pop() interface{} { old := *q n := len(old) x := old[n-1] *q = old[0 : n-1] return x } var ( operationsNumber int = 0 ) func main() { g := createGraph() bfs(*g, 0) for index, node := range *g { fmt.Printf(" node%d is on %d HopLevel \n", index, node.HopLevel) } fmt.Printf("Total number of operations is %d", operationsNumber) } func bfs(g Graph, startIndex int) { queue := &Queue{} heap.Init(queue) start := g[startIndex] start.index = 0 start.HopLevel = 0 start.Explored = true index := 1 heap.Push(queue, start) for queue.Len() > 0 { node := heap.Pop(queue).(*Node) for _, childNodeIndex := range node.Edges { childNode := g[childNodeIndex] if !childNode.Explored { childNode.Explored = true childNode.HopLevel = node.HopLevel + 1 childNode.index = index index++ heap.Push(queue, childNode) } operationsNumber++ } operationsNumber++ } } func createGraph() *Graph { node0 := &Node{Edges: []int{1, 2}} node1 := &Node{Edges: []int{3, 4}} node2 := &Node{Edges: []int{1, 4, 5}} node3 := &Node{Edges: []int{6}} node4 := &Node{Edges: []int{6}} node5 := &Node{Edges: []int{6}} node6 := &Node{Edges: []int{}} return &Graph{node0, node1, node2, node3, node4, node5, node6} }
В реализации я использовал пакет heap, который позволяет создать нужную нам очередь определив 5 методов, так же, в структуре Node появилась внутренняя переменная index, необходимая нам для очереди.
Результаты:
node0 is on 0 HopLevel node1 is on 1 HopLevel node2 is on 1 HopLevel node3 is on 2 HopLevel node4 is on 2 HopLevel node5 is on 2 HopLevel node6 is on 3 HopLevel Total number of operations is 17
Граф который указан на рисунке выше состоит из 7 вершин и 10 рёбер, и как мы видим количество операций равно 17 и каждой вершины определён уровень насколько она далека от стартовой.
Примечания:
— Вместо пакета heap можно было бы использовать chanel и это было бы более разумно
— Так как граф направленный, я не стал отмечать ребра как исследованные.
— Алгоритм можно использовать для конкретной вершины, тогда к условию выхода так же добавится проверка не искомая ли вершина взята из очереди на обработку.
— Кевин Бейкон не является самым оптимальным актёром для такой игры, есть кандидаты значительно лучше, максимальное число Бейкона равно 9.