我无法理解唐纳德约翰逊发表的关于在图表中查找周期(电路)的论文的某些部分.
更具体的是我无法理解伪代码的以下行中提到的矩阵Ak是什么:
Ak:=由{s,s + 1,...... n}引起的G子图中具有最小顶点的强分量K的邻接结构;
为了让事情变得更糟,有些线路是"为了我在Vk做"而没有声明Vk是什么......
据我所知,我们有以下几点:1)一般来说,强组件是图的子图,其中对于该子图的每个节点,都有到子图的任何节点的路径(换句话说,您可以从子图的任何其他节点访问子图的任何节点)
2)由节点列表引起的子图是包含所有这些节点以及连接这些节点的所有边的图.在文中,数学定义是"F是由W引起的G的子图,如果W是V的子集,并且F =(W,{u,y)| u,W在W中,而y(y,y)在E中)})其中u,y是边,E是图中所有边的集合,W是一组节点.
3)在代码实现中,节点由整数1 ... n命名.
4)我怀疑 Vk是强组件K的节点集.
现在回答这个问题.假设我们有一个图G =(V,E),其中V = {1,2,3,4,5,6,7,8,9},它可以分为3个强组分,SC1 = {1, 4,7,8} SC2 = {2,3,9} SC3 = {5,6}(及其边缘)
任何人都可以给我一个s = 1,s = 2,s = 5的例子,如果根据代码将成为Vk和Ak怎么办？
伪代码是我之前在Donald B. Johnson算法中理解伪代码的问题
这篇论文可以在唐纳德·约翰逊的算法中理解伪代码中找到
先感谢您