图中的后边

Question

我很难理解 Tarjan 的关节点算法。我目前正在这里学习本教程：https://www.hackerearth.com/practice/algorithms/graphs/articulation-points-and-bridges/tutorial/. What I really can't see, and couldn't see in any other tutorial, is what exactly a "back edge" means. Considering the graph given there, I know 3-1 and 4-2 are back edges, but are 2-1, 3-2, and 4-3 back edges too? Thank you.

Answer 1

来自提到的文章：

Given a DFS tree of a graph, a Back Edge is an edge that connects a vertex to a vertex that is discovered before it's parent.

2-1、3-2、4-3 不是 "Back edge"，因为它们 link 是 DFS 树中父节点的顶点。

Answer 2

...a Back Edge is an edge that connects a vertex to a vertex that is discovered before it's parent.

来自你的 source.

这样想：当你在图上应用 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->4 那么 2-1 和 4-3 是后边。

Answer 3

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

Answer 4

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

floral-white 个节点是尚未访问的节点
灰色节点是被访问过并在堆栈上的节点
黑色节点是从堆栈中弹出的节点。

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

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;
}

图中的后边

Back edges in a graph

algorithm

graph-theory

graph

depth-first-search

tarjans-algorithm

为了更好理解，这里附上代码：