algorithm - 如何在无向加权图中找到给定 k 个不同顶点的公共(public)最近邻顶点？

Question

给定一个无向加权图 G(V,E)。任意三个顶点让 u、v 和 w。找到 G 的顶点 x，使得 dist(u,x) + dist(v,x) + dist(w,x) 最小。 x 可以是 G 中的任意顶点(包括 u、v 和 w)。有没有针对这个问题的特定算法？

Answer 1

您可以使用堆栈算法来完成此操作，如下面的伪代码:

void FindNeigh(node node1, node node2,int graphsize)
{
    byte[graphsize] isGraphProcessed; // 0 array

    stack nodes1, nodes2; //0 arrays
    nodes1.push(node1);
    nodes2.push(node2);
    bool found = false;

    while(!nodes1.empty && !nodes2.empty())
    {
        stack tmp = null;
        for(node: nodes1)
            for(neigh : node.neighbors)
                if(!isGraphProcessed[neigh.id])
                {
                    tmp.push(neigh.id);
                    isGraphProcessed[neigh.id] = 1; // Flags for node 1
                }
                else if(isGraphProcessed[neigh.id] == 2) // The flag of node 2 is set
                    return neigh;
        nodes1 =tmp;
        tmp = null;
        for(node: nodes2)
            for(neigh : node.neighbors)
                if(!isGraphProcessed[neigh.id])
                {
                    tmp.push(neigh.id);
                    isGraphProcessed[neigh.id] = 2; // Flags for node 2
                }
                else if(isGraphProcessed[neigh.id] == 1) // The flag of node 1 is set
                    return neigh;
        nodes2 = tmp;
    }
    return NULL; // don't exist
}

它是如何工作的

• 从图表的两个边缘开始
• 您检查堆栈中的邻居
• 如果邻居已经被添加到另一个节点的堆栈中，则意味着另一个节点已经到达它 --> 他是最近的节点。我们将其退回。
• 如果没有找到任何东西，我们会对邻居的邻居做同样的事情(递归地依此类推)，直到找到东西。
• 如果无法从节点 1 到达节点 2，则返回 0。

注意:该算法用于查找 2 条边之间的最小距离。如果您想对 3 个边执行此操作，您可以添加第三个堆栈并查找具有 3 个标志(例如 1、2 和 4)的第一个节点。

希望有帮助:)