algorithm - 从给定的列表或 map 中找到转换器的最佳路径

Question

问题:您将获得 pdf 到文件转换器、文件到 unicode 转换器、unicode 到图像转换器等 ...

Eg: A-> b , b -> c , c-> d , d -> e
    Z-> g , g -> e.

在上述两种方式中，转换为 e 的最短、最有效的路径是 z->g ，g -> e 应该被打印..

鉴于有许多路径通向同一个转换器，实现该解决方案的最佳方法是什么？

编辑:路径可能不相交 -A -> B 只是一个文件如何转换的表示 - 面试官只是想要一种找到最佳转换格式的优化方法。假设以列表或映射的形式给出以下路径作为键值对-

jpg -> pdf，pdf -> 文本，文本 ->unicode，unicode -> 十六进制文件， jpg -> png , png -> 十六进制文件

找到将 jpg 转换为 hex 文件的最佳路径。输出应该是 jpg -> png , png -> hex 文件

Answer 1

从你的例子:

1. JPG -> PDF； PDF -> 文本；文本-​​>Unicode； UNICODE->HEX
2. JPG->PNG； PNG->十六进制

这些代表图形中的“边”，因此您可以构建一个 adjacency list在这些路径之外。

如果你构建一个图表，它看起来像:

所以最短的路径是 JPG -> PNG -> HEX

但是为了以编程方式实现这一点，您需要执行 Breadth First Search保证从源节点到目标节点的最短路径。

你可以有多个 connected components没有共同的节点。

对所有连接的组件进行搜索以获得所需的路径。