Как отсортировать массив с зависимостями элементов друг от друга?

Question

[Александр Синицын]

Массив вида

[
	[
	  "name1" => ["value" => "v", "depends" => ["name3, name 5"]
	],
	[
	  "name2" => ["value" => "v", "depends" => ["name1"]
	],
	[
	  "name3" => ["value" => "v", "depends" => ["name5"]
	],
	[
	  "name4" => ["value" => "v", "depends" => ["name1, name 2"]
	],
	[
	  "name5" => ["value" => "v", "depends" => []
	],
]

Привести к виду

[
	[
	  "name5" => ["value" => "v", "depends" => []
	],
	[
	  "name3" => ["value" => "v", "depends" => ["name5"]
	],
	[
	  "name1" => ["value" => "v", "depends" => ["name3, name 5"]
	],
	[
	  "name2" => ["value" => "v", "depends" => ["name1"]
	],
	[
	  "name4" => ["value" => "v", "depends" => ["name1, name 2"]
	],
]

Как правильнее сделать?

Answer 1

[Mercury13]

Это так называемая «топологическая сортировка». Делается через последовательный поиск в глубину, начиная со всех возможных элементов.

алг recurse(поссылке x : элемент, поссылке результат : список)
  если x.метка = чёрный
    возврат
  если x.метка = серый
    стоп ("найдена циклическая зависимость")
  x.метка := серый
  для всех y : зависимых от x
    recurse(y)
  x.метка := чёрный
  результат.добавить(x)

алг main()
  для всех x : массив
    x.метка := белый
  result := []
  для всех x : массив
    recurse(x, result)

Вкратце: проводим стандартный поиск в глубину, начиная со всех элементов, и при выходе вносим элемент в список.

Comments

[Александр Синицын]

Классно! Самое оно )