Finding largest connected tree in a matrix
Assume I have a matrix MxN, filled with values between 0 and 5. I now want to determine the largest connected tree in that matrix, where the values of the matrix are considered to be the nodes. A pair of nodes is said to be connected if it's nodes are adjacent to each other either horizontally or vertically, and if the value of both nodes is the same. The size of a tree is equal to the nodes in the tree.
An example:
1 0 3 0 0 2 2 0 0 0 0 0
1 1 2 2 2 0 2 0 0 0 0 0
0 1 0 3 0 0 2 0 0 0 0 2
3 1 0 3 0 0 2 0 2 2 2 2
0 0 0 0 0 0 0
3 0 0 3 3 0 0
3 3 3 3 0 0 0
On the left side, the 1-nodes on the left side form the largest tree. On the right side, the 3-nodes form the largest tree, while there are two other trees consisting of 2-nodes.
I know I could probably do a simple depth-first search, but I'm wondering if there is something well-known that I'm missing, maybe in the realm of graph theory (like Kruskal's minimum spanning tree algorithm, but for this example).
Effectively what you're looking for are Connected components. Connected component is a set of nodes, where you could travel from any node to any other within that component.
Connected components are applicable generally to a graph. Connected components can be found using BFS/DFS and from algorithm complexity perspective given adjacency matrix input there is no better way to do that. The running time of the algorithm is O(N^2) , where N is a number of nodes in a graph.
In your case graph has more constrains, such as each node can be adjacent to at most 4 other nodes. With BFS/DFS , this gives you a running time of O(4N) = O(N) , where N is a number of nodes. There can't possibly be an algorithm with a better complexity, as you need to consider each node at least once in the worst case.
You are looking for disjoint sets so I would suggest a disjoint-set data structure and a find/union algorithm:
see http://en.wikipedia.org/wiki/Disjoint-set_data_structure#Disjoint-set_forests
The union operation is symmetric so you really only need to compare each element of the matrix with its neighbor to the right and its neighbor below applying the union operation when the compared elements have the same value.
Sweep through each of the elements again using the find operation to count the size of each set keeping track of the largest. You will need storage for the counts.
The computational complexity will be O(MN A-1(MN,MN)) where A-1 is the Inverse Ackermann function, which one can consider a small constant (< 5) for any useful value of MN. And the extra storage complexity will be O(MN).
链接地址: http://www.djcxy.com/p/63792.html下一篇: 在矩阵中查找最大的连通树