algorithm - 图中的后边

Question

我很难理解 Tarjan 的关节点算法。我目前正在这里学习本教程：https ://www.hackerearth.com/practice/algorithms/graphs/articulation-points-and-bridges/tutorial/ 。我真正看不到，在任何其他教程中也看不到的是“后边缘”的确切含义。考虑到那里给出的图表，我知道 3-1 和 4-2 是后边，但 2-1、3-2 和 4-3 也是后边吗？谢谢你。

Answer 1

...后边是将顶点连接到在其父顶点之前发现的顶点的边。

从你的来源。

可以这样想：当您在图上应用 DFS 时，您会修复算法选择的某些路径。现在在给定的情况下：0->1->2->3->4. 如文章所述，源图包含边4-2和3-1。当 DFS 达到 3 时，它可以选择 1 但 1 已经在您的路径中，因此它是一条back edge，因此，如源代码中所述，它是一个可能的替代路径。

解决您的第二个问题：2-1、3-2 和 4-3 后缘也是如此吗？对于不同的路径，它们可以是。假设您的 DFS 选择0->1->3->2->4then2-1并且4-3是后边缘。

Answer 2

本质上，当你做一个 DFS 时，如果你的图中节点 A、B 和 C 之间存在循环，并且你发现了边 AB，稍后你会发现边 BC，那么，由于你已经到达节点 C，你会发现边缘 CA，但您需要在搜索中忽略此路径以避免无限循环。因此，在您的搜索中，AB 和 BC 不是后边，但 CA 是后边，因为这条边形成了一个循环，返回到已经访问过的节点。

Answer 3

考虑以下使用 DFS 的（有向）图遍历。这里节点的颜色代表如下：

1. 花白色节点是尚未访问的节点
2. 灰色节点是被访问并在堆栈上的节点
3. 黑色节点是从堆栈中弹出的节点。

请注意，当节点 13 通过边 13->0 发现节点 0 时，节点 0 仍在堆栈上。这里，13->0 是一个后边缘，它表示存在一个循环（三角形 0->1->13）。

Answer 4

从文章提到：

给定图的 DFS 树，后边是将顶点连接到在其父节点之前发现的顶点的边。

2-1、3-2、4-3 不是“后边”，因为它们将顶点与 DFS 树中的父节点链接起来。

Answer 5

这是为了更好地理解的代码：

#include<bits/stdc++.h>

using namespace std;

struct vertex{

    int node;

    int start;

    int finish;

    int color;

    int parent;

};


int WHITE=0, BLACK=1, GREY=2;

vector<int> adjList[8];

int num_of_verts = 8;
struct vertex vertices[8];

int t=0;

bool DFS_visit(int u){

    bool cycleExists = false;

    vertices[u].color=GREY;

    t++;

    vertices[u].start= t;


    for( int i=0;   adjList[u][i]!=-1; i++){

        if( vertices[adjList[u][i]].color == WHITE ){

            if(!cycleExists) cycleExists = DFS_visit(adjList[u][i]);

            else DFS_visit(adjList[u][i]);

        }

        else {

            cout << "Cycle detected at edge - ("<<u<<", "<<adjList[u][i]<<")"<<endl;

            cycleExists = true;
        }

    }

    vertices[u].color=BLACK;

    t++;

    vertices[u].finish= t;

    return cycleExists;

}

void DFS(){

    for(int i=0;i<num_of_verts;i++){

        vertices[i].color=WHITE;

        vertices[i].parent=NULL;

    }

    t=0;

    for(int i=0;i<num_of_verts;i++){

        if(vertices[i].color==WHITE){

           cout << "Traversing component "<<i<<"-"<<endl;


            bool cycle = DFS_visit(i);

            cycle==1? cout<<"Cycle Exists\n\n":cout <<"Cycle does not exist\n\n";

        
}
   
 }


}


int main(){


    adjList[0] = {4, -1};

    adjList[1] = {0, 5, -1};

    adjList[2] = {1, 5, -1};

    adjList[3] = {6, 7, -1};

    adjList[4] = {1, -1};

    adjList[5] = {-1};

    adjList[6] = {2, 5, -1};

    adjList[7] = {3, 6, -1};



    DFS();

    return 0;
}