Algorithm for checking connectivity of a lattice graph in Rn

3 次查看（过去 30 天）
Haoran
Haoran 2023-2-9
评论： Haoran 2023-2-12
Two points are adjacent if they have n-1 equal coordinates and 1 coordinate that differ by 1. For example, (1,4,3,0) in R^4 is adjacent to 8 points (0,4,3,0), (2,4,3,0), (1,3,3,0), (1,5,3,0), (1,4,2,0), (1,4,4,0), (1,4,3,-1) and (1,4,3,1). Two points are connected if there is a sequence of points between them, every two consecutive points are adjacent.
Suppose the input is a set of lattice points in R^n. What is a fast algorithm to check if they are connected? I only need to determine the connectivity (no need to find connected components); suppose all the points are contained in a given cube say [0,k]^n if this helps.
Thanks.
  4 个评论
显示 2更早的评论
Dyuman Joshi
Dyuman Joshi 2023-2-9
How are the points stored? As numeric arrays corresponding to each dimension?
Please specify if otherwise.
Haoran
Haoran 2023-2-9
Say we have k points in Rn. Then it is a k * n matrix, each row gives the coordinates of one point.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Dinesh
Dinesh 2023-2-9
Hi Haoran,
If you have 'k' input points and there are 'n' different dimensions for a single point, then you can model this problem as a graph and then try to apply any of the two well-known graph traversal algorithms. These algorithms are DFS (Depth First Search) and BFS (Breadth First Search) algorithms.
These points can be modelled as vertices and the connections between points as edges. In the worst case, these algorithms have a run time of O(k + y) where 'k' is the number of vertices and 'y' is the number of edges. In simple terms, it means that either of these algorithms in the worst case should traverse the number of times that equals to the sum of their number of vertices and their edges.
Please refer to this link for more information on DFS.
Make sure to use a 'visited' array to mark the previously visited vertices to avoid infinite loops.
Once the entire traversal is complete, you can just check if all the points are visited in the 'visited' array. If not, then it is clear that all the points are not connected together. In each step of the DFS, you have to check if two points are connected to each other which can take at most 'n' steps because there can be 'n' different dimensions for a single point.
The time complexity of the algorithm to implement this is O(n * (k + y)) where 'n' is the number of dimensions, 'k' is the number of points and 'y' is the number of vertices.
  3 个评论
显示 1更早的评论
Dinesh
Dinesh 2023-2-10
Yes @Haoran. In this question, the number of edges can be at most k^2 as a single point can be connected to all the other points and this is applicable for all the points. Please note that 'y' is the number of edges as I've mentioned and this can be equated to 'k^2' to simplify the time complexity further. So the time complexity would be O(n * (k+k^2)) which can be approximated to O(n * k^2). Please note that 'n' is very important to include here because every time we check if two points are connected, it takes 'n' steps in the worst case. No matter how we try to simplify, it is not possible to improve the time complexity of this problem in the worst case. So, DFS can still be used.

请先登录，再进行评论。

更多回答（0 个）

类别

在 Help Center 和 File Exchange 中查找有关 Directed Graphs 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by