blocks|key|437031|text|...a+Back+Edge是连接顶点和在其父节点之前发现的顶点的边缘。|type|blockquote|depth|inlineStyleRanges|entityRanges|data|437032|从你的来源。|unstyled|offset|length|437033|可以这样想:当您在图上应用DFS时，您会修复算法所选择的一些路径。现在，在给定的情况下：0->1->2->3->4。正如本文所提到的，源图包含边4-2和3-1。当DFS达到3时，它可以选择1，但1已经在您的路径中，因此它是一个back+edge，因此，正如源中所提到的，它是一个可能的替代路径。|style|CODE|437034|回答你的第二个问题:+2-1，3-2和4-3背边也是吗？换一条不同的路。假设您的DFS选择0->1->3->2->4，那么2-1和4-3是后边。|437035|​|437036|📷|atomic|437037|437038|entityMap|0|LINK|mutability|MUTABLE|url|https://www.hackerearth.com/practice/algorithms/graphs/articulation-points-and-bridges/tutorial/|1|IMAGE|IMMUTABLE|imageUrl|https://developer.qcloudimg.com/http-save/yehe-900000/a87714a5c00eab63653d461523313bb6.png|imageAlt^0|0|3|2|0|0|18|D|20|3|24|3|35|9|0|19|D|1P|3|1T|3|0|0|0|1|1|0|0^^$0|@$1|2|3|4|5|6|7|16|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|17|8|@]|9|@$E|18|F|19|1|1A]]|A|$]]|$1|G|3|H|5|D|7|1B|8|@$E|1C|F|1D|I|J]|$E|1E|F|1F|I|J]|$E|1G|F|1H|I|J]|$E|1I|F|1J|I|J]]|9|@]|A|$]]|$1|K|3|L|5|D|7|1K|8|@$E|1L|F|1M|I|J]|$E|1N|F|1O|I|J]|$E|1P|F|1Q|I|J]]|9|@]|A|$]]|$1|M|3|N|5|D|7|1R|8|@]|9|@]|A|$]]|$1|O|3|P|5|Q|7|1S|8|@]|9|@$E|1T|F|1U|1|1V]]|A|$]]|$1|R|3|N|5|D|7|1W|8|@]|9|@]|A|$]]|$1|S|3|-4|5|D|7|1X|8|@]|9|@]|A|$]]]|T|$U|$5|V|W|X|A|$Y|Z]]|10|$5|11|W|12|A|$13|14|15|-4]]]]

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

from your <a href="https://www.hackerearth.com/practice/algorithms/graphs/articulation-points-and-bridges/tutorial/" rel="noreferrer">source</a>.

Think about it like this: When you apply a DFS on a graph you fix some path that the algorithm chooses. Now in the given case: <code>0-&gt;1-&gt;2-&gt;3-&gt;4</code>. As in the article mentioned, the source graph contains the edges <code>4-2</code> and <code>3-1</code>. When the DFS reaches 3 it could choose 1 but 1 is already in your path so it is a <code>back edge</code> and therefore, as mentioned in the source, a possible alternative path.

Addressing your second question: Are 2-1, 3-2, and 4-3 back edges too? For a different path they can be. Suppose your DFS chooses <code>0-&gt;1-&gt;3-&gt;2-&gt;4</code> then <code>2-1</code> and <code>4-3</code> are back edges. 

<a href="https://i.stack.imgur.com/NAi4Q.png" rel="noreferrer"><img src="https://i.stack.imgur.com/NAi4Q.png" alt="enter image description here"></a>

blocks|key|1733145|text|本质上，当您执行DFS时，如果图中有节点A、B和C之间的循环，并且发现了边A-B，那么稍后您就会发现边缘B-C，然后，由于您已经到达节点C，您将发现边缘C-A，但是在搜索过程中您需要忽略这条路径，以避免无限循环。所以，在你的搜索中，and和back不是后边，但是C是后边，因为这个边形成一个循环返回到一个已经访问过的节点。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1733146|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

In essence, when you do a DFS, if there are cycles in your graph between nodes A, B and C and you have discovered the edges A-B, later you discover the edge B-C, then, since you have reached node C, you will discover the edge C-A, but you need to ignore this path in your search to avoid infinite loops. So, in your search A-B and B-C were not back edges, but C-A is a back edge, since this edge forms a cycle back to an already visited node.

blocks|key|1733275|text|考虑使用DFS进行以下(有向)图遍历。在这里，节点的颜色表示以下内容：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1733276|花白的节点是尚未被访问的节点。|ordered-list-item|1733277|灰色节点是被访问的和堆栈上的节点。|1733278|黑色节点是从堆栈中弹出的节点。|1733279|注意，当节点13通过边缘13->0发现节点0时，节点0仍然在堆栈上。这里，13->0是一个后边，它表示一个循环的存在(三角形0->1->13)。|1733280|​|1733281|📷|atomic|offset|length|1733282|1733283|entityMap|0|IMAGE|mutability|IMMUTABLE|imageUrl|https://developer.qcloudimg.com/http-save/yehe-900000/cb6728e026e16ff642602206948a3845.gif|imageAlt^0|0|0|0|0|0|0|0|1|0|0|0^^$0|@$1|2|3|4|5|6|7|11|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|12|8|@]|9|@]|A|$]]|$1|E|3|F|5|D|7|13|8|@]|9|@]|A|$]]|$1|G|3|H|5|D|7|14|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|15|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|16|8|@]|9|@]|A|$]]|$1|M|3|N|5|O|7|17|8|@]|9|@$P|18|Q|19|1|1A]]|A|$]]|$1|R|3|L|5|6|7|1B|8|@]|9|@]|A|$]]|$1|S|3|-4|5|6|7|1C|8|@]|9|@]|A|$]]]|T|$U|$5|V|W|X|A|$Y|Z|10|-4]]]]

Consider the following (directed) graph traversal with DFS. Here the colors of the nodes represent the following:
<ol>
<li>The floral-white nodes are the ones that are yet to be visited</li>
<li>The gray nodes are the nodes that are visited and on stack</li>
<li>The black nodes are the ones that are popped from the stack.</li>
</ol>
Notice that when the node 13 discovers the node 0 through the edge 13-&gt;0 the node 0 is still on the stack. Here, 13-&gt;0 is a back edge and it denotes the existence of a cycle (the triangle 0-&gt;1-&gt;13).
<a href="https://i.stack.imgur.com/vJ1Lf.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/vJ1Lf.gif" alt="enter image description here" /></a>

blocks|key|1778928|text|从提到的文章中：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1778929|给定图的DFS树，Back+Edge是连接顶点和在其父级之前发现的顶点的边。|blockquote|1778930|2-1，3-2，4-3不是“后缘”，因为它们将DFS树中的顶点与其父节点连接起来。|1778931|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$]]|$1|E|3|F|5|6|7|K|8|@]|9|@]|A|$]]|$1|G|3|-4|5|6|7|L|8|@]|9|@]|A|$]]]|H|$]]

From article mentioned: 

<blockquote>
 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.
</blockquote>

2-1, 3-2, 4-3 are not "Back edge" because they link the vertices with their parents in DFS tree.

blocks|key|437225|text|下面是更好地理解的代码：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|437226|#include<bits/stdc%2B%2B.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%2B%2B;

++++vertices[u].start=+t;


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

++++++++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%2B%2B;

++++vertices[u].finish=+t;

++++return+cycleExists;

}

void+DFS(){

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

++++++++vertices[i].color=WHITE;

++++++++vertices[i].parent=NULL;

++++}

++++t=0;

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

++++++++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;
}|code-block|syntax|javascript|437227|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

<h2>Here is the code for a better understand:</h2>
<pre><code>#include&lt;bits/stdc++.h&gt;

using namespace std;

struct vertex{

 int node;

 int start;

 int finish;

 int color;

 int parent;

};


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

vector&lt;int&gt; 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 &lt;&lt; &quot;Cycle detected at edge - (&quot;&lt;&lt;u&lt;&lt;&quot;, &quot;&lt;&lt;adjList[u][i]&lt;&lt;&quot;)&quot;&lt;&lt;endl;

 cycleExists = true;
 }

 }

 vertices[u].color=BLACK;

 t++;

 vertices[u].finish= t;

 return cycleExists;

}

void DFS(){

 for(int i=0;i&lt;num_of_verts;i++){

 vertices[i].color=WHITE;

 vertices[i].parent=NULL;

 }

 t=0;

 for(int i=0;i&lt;num_of_verts;i++){

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

 cout &lt;&lt; &quot;Traversing component &quot;&lt;&lt;i&lt;&lt;&quot;-&quot;&lt;&lt;endl;


 bool cycle = DFS_visit(i);

 cycle==1? cout&lt;&lt;&quot;Cycle Exists\n\n&quot;:cout &lt;&lt;&quot;Cycle does not exist\n\n&quot;;

 
}
 
 }


}


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;
}
</code></pre>

I'm having a hard time understanding Tarjan's algorithm for articulation points. I'm currently following this tutorial here: <a href="https://www.hackerearth.com/practice/algorithms/graphs/articulation-points-and-bridges/tutorial/" rel="noreferrer">https://www.hackerearth.com/practice/algorithms/graphs/articulation-points-and-bridges/tutorial/</a>. 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.<a href="https://i.stack.imgur.com/OqGy9.png" rel="noreferrer"><img src="https://i.stack.imgur.com/OqGy9.png" alt="enter image description here"></a>

Back edges in a graph

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我很难理解Tarjan的发音点算法。我现在在这里学习本教程：。在任何其他教程中，我真正看不到，也看不到的是，“后边缘”到底是什么意思。考虑到给出的图，我知道3-1和4-2是后边，但是2-1，3-2和4-3后边也是吗？谢谢。​

问图中的后边
EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问图中的后边EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问图中的后边
EN