我正在研究一些计算机科学问题,许多问题都是关于图遍历和最短路径的。例如,系统可能会要求您查找从图形中的一个点到另一个点的最短路径。为了解决这个问题,人们将使用广度优先搜索。最主要的是,图通常具有相关函数,可以为节点可能具有的任何相邻节点提供。
但是,如果问题有一个 2-D 矩阵,假设 1 和 0,其中一个 1 可遍历而 0 不可遍历,那么如何解决这样的问题?例如:
1101
0110
1011
如果给定了一个坐标,比如 [0][0],可能会要求您找到所有可能的路径或到 [n][n] 点的最短路径。你会怎么做?如果有人有任何代码示例,我将不胜感激。
我假设您呈现的矩阵是一种地图或迷宫,而不是邻接矩阵。因此,在您的矩阵中
1101
0110
1011
你可以从[0][0]
到[1][0]
,或者从[1][1]
到[1][0]
或[2][1]
,如果允许对角线移动,你可能[0][0]
,[0][2]
和[2][2]
。
要将图算法应用于此类矩阵,您首先需要通过为矩阵中的每个条目或节点分配索引来将其转换为邻接列表或邻接矩阵:
0 1 2 3
4 5 6 7
8 9 10 11
现在,您列出了可从node 0
或[0][0]
访问的所有节点:
0 -> 1, 5
因为我们可以从0
1
和5
两个节点。(我在这里假设允许对角线移动。这将为您提供邻接列表中的第一个条目。邻接矩阵的等效项为:
0 1 0 0 0 1 0 0 0 0 0 0
作为矩阵的第一行(第 0 行(。
对矩阵中的每个节点重复此过程,您将拥有完整的邻接列表或矩阵,以便在普通图形算法中使用。
检查一些最好的算法 - Dijkstra算法和BFS。它将解决您的问题。
https://en.wikipedia.org/wiki/Breadth-first_search
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm