Число Бейкона и Графы

Число Бейкона


Немного истории, Кевин Бейкон американский актёр сыгравший во множествах фильмам, в 1994 отметил что актёры, с которыми он снимался, работали со всеми голливудскими (и не только) актёрами. Общественность тут же отреагировала и создала игру “назвать имя актёра и связать его с Кевином Бейконом”. Корпорация добра даже встроила игру в свой поисковик, например Число Бейкона для актёра Джона Траволты равно 2 (Джон снимался с Оливией Ньютон-Джон в фильме Бриолин, она же, в свою очередь, сыграла с Кевином Бейконом в фильме “У нее будет ребенок”).

А теперь давайте поговорим о том, как эту игру можно представить, и как можно вычислить число Бейкона при помощи графа.

Граф


В данном случае, я буду рассматривать направленный невзвешенный граф, где вершинами будут актеры, a ребрами — фильмы (данные можно взять с IMDb), в которых они снимались, под стартовой (нулевой) вершиной будет Кевин Бейкон. Число Бейкона в таком графе будет равно количеству hop`ов от стартовой вершины до искомой или для всех остальных. Для примера я выбрал такой вот граф:
image

Алгоритм который производит поиск называется “Поиск в ширину” (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.
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 6

    +4
    • UFO just landed and posted this here
        0
        Алгори́тм Де́йкстры (англ. Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных.
          0
          Алгоритм Дейкстры работает когда граф взвешенный и не имеет отрицательного расстояния между вершинами. В статье граф невзешенный(или расстояние между вершинами равно константе). В общем, bfs — считает сколько вершин надо пройти, чтоб попасть в необходимую, дейкстра — по ребрам какой длины нам лучше это сделать.
            0
            У вас взвешенный граф с весами равными единице.
            Так что, алгоритм Дейкстры вполне себе работает.
            И да, алгоритм Дейкстры — это bfs.
              0
              Единственное отличие в том, что в алгоритме Дейкстры
              используется приоритетным очередь, а у вас обычная.
              Если говорить про оптимизацию, то тогда надо смотреть
              на алгоритм топологической сортировки.

        Only users with full accounts can post comments. Log in, please.