时间戳

首页 > 解决方案 > 如何从加权图的文件中编码邻接矩阵

java - 如何从加权图的文件中编码邻接矩阵

问题描述

我刚开始学习图和邻接矩阵，我必须从加权图的文本文件中创建一个邻接矩阵。文本文件将如下所示：

0 4 5 0 6
4 0 0 3 6
5 0 0 0 8
0 3 0 0 0
6 6 8 0 0

（我们可以假设矩阵总是对称的）

由此，我们必须创建一种方法来进行广度优先搜索和深度优先搜索。我了解图形和搜索的理论，但我在编码时遇到了麻烦。另外，如果您可以编写 sudo 代码而不是实际代码，那么我仍然可以自己学习/自己做，那就太好了！太感谢了！

标签： javagraph-theorydepth-first-searchbreadth-first-search

解决方案

对于深度优先搜索，我将递归地使用一个函数，并传递当前节点的 int 和已经访问过的节点列表，然后递归直到所有节点都被访问，然后返回递归以到达下一个节点被访问过

check node(currentNode, ListOfVisited)

     check=0
     while(check!=n)//where n is the size of the array
         if (matrix.get(check,currentNode) is not in ListOFVisited)
         add n to listOfVisted 
         checkNode(currentNode, ListOfVisited)
     end while

//当函数“备份”时将调用此代码

check++

 end while

对于 bredth first search 我也会递归地进行，但首先检查所有邻居并将它们放在队列中，然后在队列中重复

 queue is empty

 checknode(node, visited)
     check=0
     while(check!=n)
         if (matrix.get(check,currentNode) isn't in visited)
             queue.add(check)
         end if
         check++
     end while
 while(queue isn't empty)
     checkNode(queue.pop)
 end while

推荐阅读