Задача поиска пути на графе

Question

Дан граф переходов:

graph = {A: [B,D], B: [C,N,Z], D: [E,F], F:[S]}

Известно, что в графе нет петель и путь только один (или же пути нет).

Необходимо:

Написать алгоритм поиска пути между двумя узлами графа.
Оценить эффективность алгоритма по памяти и по времени.

Например для данного графа получим:

A->N = [A,B,N]
A->S = [A,D,F,S]
B->S = []

Мой вариант решения приведен ниже. Прошу знатоков указать на проблемы/ошибки.

Также меня интересуют вопросы:

Как оценить эффективность алгоритма по памяти и по времени?
Как можно распараллелить алгоритм на несколько потоков? (возможно кто нибудь сможет предложить иное решение, что так же приветствуется)

val routeData = HashMap<String, List<String>>().apply {
    put("A", listOf("B", "D"))
    put("B", listOf("C", "N", "Z"))
    put("D", listOf("E", "F"))
    put("F", listOf("S"))
}

val result = FindEngine(routeData).findRoute("A", "S")
        
        
class FindEngine(private val routeData: HashMap<String, List<String>>) {
    fun findRoute(from: String, to: String): List<String> {
        var currentNode: Node? = Node(from)

        while (currentNode != null) {
            if (!currentNode.routesAdded) {
                addRoutes(currentNode)

                findDestInRoutes(currentNode, to)?.let { node ->
                    return getResultRoute(node)
                }
            }

            if (currentNode.routes.isNotEmpty()) {
                currentNode = currentNode.routes.first()
            } else {
                currentNode.parent?.routes?.remove(currentNode)
                currentNode = currentNode.parent
            }
        }

        return emptyList()
    }

    private fun addRoutes(currentNode: Node) {
        routeData[currentNode.name]?.let { routes ->
            for (item in routes) {
                currentNode.routes.add(Node(item, currentNode))
            }
        }
        currentNode.routesAdded = true
    }

    private fun findDestInRoutes(node: Node, dest: String): Node? {
        for (item in node.routes) {
            if (item.name == dest) {
                return item
            }
        }

        return null
    }

    private fun getResultRoute(node: Node): List<String> {
        val result = ArrayList<String>()
        var current: Node? = node

        while (current != null) {
            result.add(current.name)
            current = current.parent
        }

        return result.reversed()
    }

    private class Node(
        val name: String,
        val parent: Node? = null,
        val routes: MutableList<Node> = mutableListOf()
    ) {
        var routesAdded = false
    }
}

Answer 1

Проблемы

Постановка задачи

Задача поставлена без знания общепринятой терминологии. Должно быть что-то такое:

Дан ациклический направленный граф, по данным двум вершинам отыскать путь из первой во вторую.

Нестандартное решение стандартной задачи

Граф назван "маршрутными данными", путь – маршрутом. Много кода, много промежуточных данных. Стандартное решение – рекурсия для поиска по графу в глубину почти без дополнительных данных.

Структуры данных ...

... взяты из Java. А раз пишем на Kotlin, так и структуры желательно брать из стандартной библиотеки языка.

Решение

search делает поиск в глубину. path хранит текущий путь. Решение рекурсивное, так как нет требований к размеру графа. Если потребуется обрабатывать большие графы, можно перенести на цикл со стеком. Рекурсия проще и короче. Скорость работы – оптимальная, расход памяти – минимальный.

import kotlin.collections.List
import kotlin.collections.Map

fun findPath(
    graph: Map<String, List<String>>, start: String, target: String
): List<String> {

    val path = mutableListOf<String>()

    fun search(node: String): Boolean {
        path.add(node)
        if (node == target) {
            return true
        }
        graph[node]?.forEach {
            if (search(it)) {
                return true
            }
        }
        path.removeLast()
        return false
    } 

    search(start)
    return path
}

fun main() {
    val graph = mapOf(
        "A" to listOf("B", "D"),
        "B" to listOf("C", "N", "Z"),
        "D" to listOf("E", "F"),
        "F" to listOf("S"),
    )

    println(findPath(graph, "A", "S"))
}

БЛОГ НА HUSL