具有周期边界条件的连通分量

Question

通常，为了找到一组点上的连接分量，我从放置在二维欧几里德空间中的点构建一个图，其中边缘是用阈值确定的。也就是说，如果两点之间的距离小于预定的截止半径，那么我将它们视为邻居。然后我对这个图进行深度优先搜索，以确定连接的组件。

这种方法的问题是我必须首先使用阈值来构建图。我不是计算机科学家，所以我从来没有上过算法课。我想知道是否有一种算法可以让我找到最近的邻居或连接的组件，而不需要用阈值构建边缘?使阈值法如此可取的主要原因是这个方框是周期性的。这就是为什么单独搜索对我帮助不大的原因。

我的代码是这样的:

// +++++
// Graph
// +++++
// ( Note that edges are lines connecting nodes or vertices )
class Graph
{
public:
    Graph() {}
    ~Graph() {}
    void setNumNodes( int nds );
    int getNumNodes() { return numNodes; }
    void addEdge( int nd_idx, set<int> dest );
    map<int,set<int> > edges; // [node, destination]
    void setThreshold( double cutoff, double carpan );
    double getThreshold() { return threshold; }
private:
    int numNodes;
    double threshold;
};
void Graph::setNumNodes( int nds ){
    numNodes = nds;
}
void Graph::addEdge( int nd_idx, set<int> dest ){
    edges.insert( pair<int,set<int> >( nd_idx, dest ) );
}
void Graph::setThreshold( double cutoff, double carpan ){
    threshold = 2*R + carpan*cutoff;
}

// +++++
// Function for depth-first search from a starting node
int dfsFromNode( Graph& graph, int i, stack<int>& S, vector<bool>& visited ){
    int connected_comp = 0;
    // Add the node to the stack
    S.push( i );
    // While there are nodes that are not visited
    // (so as long as stack is not empty ..)
    while( !S.empty() ){
        // Remove the top of the stack (backtracking process)
        S.pop();
        if( !visited[i] ){
            visited[i] = true;
            connected_comp++;
            set<int> neighbors;
            neighbors = graph.edges[i];
            for( auto j: neighbors ){
                i = j;
                S.push( i );
            }
        } // if the node is visited before, get out
    } // while loop to check if the stack is empty or not
    return connected_comp;
} 

编辑:

重申这个问题，我如何才能找到最近的邻居或连接的组件，而不做阈值在周期边界设置?

Answer 1

要查找连接的组件，可以使用kd-trees。k-d树，简称。k维树)是一种算法，在这种算法中，你将数据点分成两个在每个自由度上相互正交的方向。我发现下面的链接对解释很有用。

具体来说，在周期性边界条件的情况下，你可以只在主框外ghost/image粒子，并构建包含这些粒子的kd-tree。