c++ - 查找图中由一个顶点分隔的顶点

Question

你知道一些算法(比蛮力更好)可以找到图中被一个顶点分隔并且彼此之间没有连接的顶点。示例:

在此图中找到的路径为:

• 1 - 4
• 2 - 4
• 3 - 5

最好的是使用 STL 列表数组作为图形表示的 c++ 代码，但使用任何其他过程语言或伪代码的代码也可以。

Answer 1

一种方法是基于广度优先搜索，对于图中的每个顶点 i，我们扫描与 i 相邻的顶点(即两级邻接!)。

mark = array[0..n-1] of 0
flag = 1

for i = nodes in graph do

// mark pattern of nodes adjacent to i 
    mark[i] = flag
    for j = nodes adjacent to i do
        mark[j] = flag
    endfor

// scan nodes adjacent to those adjacent to i
// (separated by one vertex!)
    for j = nodes adjacent to i do
    for k = nodes adjacent to j do
        if mark[k] != flag  and k > i then
        // i,k are separated by another vertex
        // and there is no edge i,k

        // prevent duplicates
            mark[k] = flag
        endif
    endfor
    endfor

// implicit unmarking of current pattern
    flag += 1

endfor

如果图的每个顶点有 m 条边，这将是一个 O(n * m^2) 算法，需要 O(n) 额外的空间。