我有简单的矩阵(矩阵,它代表二维游戏中的地形图,包含ASCII字符,例如'm‘代表山脉,'v’代表河谷,'r‘代表河流),在地图上可能有一条河流,也可能没有河流。河流可以从矩阵的任何位置流向任何位置(并且始终将两个不同部分的地图分开,=>地图上不可能有河流的来源,总是从一端进入而存在于另一端)。如果有河流,如何在两个集群上分离矩阵/地形图?v v v v v m m r r m m m m m
m m v
我的方法是使用DFS算法。我知道当visitedM[iVertices]为true或者节点被访问两次时,这意味着它不是一个树。我还使用下面的定理来判断一个图是否为树。Theorem: Any connected graph with n vertices and n-1 edges is a tree6边是无向的,一旦从最小的顶点id开始,就会在文件中列出。例如,对于边2-5和5-2,文件将只有2-5。
我<