Tarjan算法和Kosaraju算法的比较

秋萱君_3542

秋萱君_3542

2023-09-04

912人浏览

转载

tarjan算法和kosaraju算法的比较

Tarjan 算法是在有向图中定位强链接组件,Robert Tarjan 在 1972 年创建了称为 Tarjan 算法的图遍历技术。它无需遍历先前处理的节点,而是使用深度有效地定位和处理每个高度相关的组件首先是搜索策略和栈数据结构。该算法经常用于计算机科学和图论,并具有多种用途,包括算法创建、网络分析和数据挖掘。

Kosaraju 的算法由对图的两次遍历组成。在第一遍中,以相反的顺序遍历图,并为每个节点分配“完成时间”。在第二遍中,按照节点的完成时间顺序访问节点,并识别和标记每个强连接组件。

Tarjan算法方法

在本例中,Graph 类在程序开头定义,其构造函数根据图中的顶点数初始化邻接表数组。通过将目标顶点包含在源顶点的邻接列表中,addEdge 函数向图中添加一条边。

SCCUtil 方法是 SCC 方法用来发现 SCC 的基于 DFS 的递归函数,它构成了该程序的基础。当前顶点u、发现时间disc的数组、低值low的数组、顶点堆栈st的数组以及跟踪顶点是否在堆栈中的布尔值数组stackMember是该函数的输入。

该过程将当前顶点放入堆栈,并在首先为其分配发现时间和低值后将其 stackMember 值更改为 true。之后,它以递归的方式将所有附近顶点的低值更新到当前顶点。

该技术迭代地访问未发现的顶点 vs 并修改 u 的低值。如果v已经在堆栈中,该方法根据v的发现时间修改u的低值。

Tarjan算法

  • 初始化算法

  • 开始遍历图表

  • 检查强连接组件

  • 重复直到所有节点都被访问过

  • 返回强连通分量

该方法将所有顶点从堆栈中弹出,直到当前顶点 u 被弹出,打印弹出的顶点,如果 u 是头节点(即,如果其低值等于其发现时间),则将其 stackMember 值设置为 false。

示例

// C++ program to find the SCC using
// Tarjan's algorithm (single DFS)
#include <iostream>
#include <list>
#include <stack>
#define NIL -1
using namespace std;

// A class that represents
// an directed graph
class Graph {
    // No. of vertices
    int V;

    // A dynamic array of adjacency lists
    list<int>* adj;

    // A Recursive DFS based function
    // used by SCC()
    void SCCUtil(int u, int disc[], int low[], stack<int>* st, bool stackMember[]);

    public:
    // Member functions
    Graph(int V);
    void addEdge(int v, int w);
    void SCC();
};

// Constructor
Graph::Graph(int V) {
    this->V = V;
    adj = new list<int>[V];
}

// Function to add an edge to the graph
void Graph::addEdge(int v, int w) {
    adj[v].push_back(w);
}

// Recursive function to finds the SCC
// using DFS traversal
void Graph::SCCUtil(int u, int disc[],  int low[], stack<int>* st,  bool stackMember[]) {
    static int time = 0;

    // Initialize discovery time
    // and low value
    disc[u] = low[u] = ++time;
    st->push(u);
    stackMember[u] = true;

    // Go through all vertices
    // adjacent to this
    list<int>::iterator i;

    for (i = adj[u].begin();
        i != adj[u].end(); ++i) {
        // v is current adjacent of 'u'
        int v = *i;

        // If v is not visited yet,
        // then recur for it
        if (disc[v] == -1) {
           SCCUtil(v, disc, low, st, stackMember);

           // Check if the subtree rooted
           // with 'v' has connection to
           // one of the ancestors of 'u'
            low[u] = min(low[u], low[v]);
        }

        // Update low value of 'u' only of
        // 'v' is still in stack
        else if (stackMember[v] == true)
            low[u] = min(low[u], disc[v]);
    }

    // head node found, pop the stack
    // and print an SCC

    // Store stack extracted vertices
    int w = 0;

    // If low[u] and disc[u]
    if (low[u] == disc[u]) {
    // Until stack st is empty
        while (st->top() != u) {
            w = (int)st->top();

            // Print the node
            cout pop();
        }
        w = (int)st->top();
        cout pop();
    }
}

// Function to find the SCC in the graph
void Graph::SCC() {
    // Stores the discovery times of
    // the nodes
    int* disc = new int[V];

    // Stores the nodes with least
    // discovery time
    int* low = new int[V];

    // Checks whether a node is in
    // the stack or not
    bool* stackMember = new bool[V];

    // Stores all the connected ancestors
    stack<int>* st = new stack<int>();

    // Initialize disc and low,
    // and stackMember arrays
    for (int i = 0; i <h3>输出</h3>
<pre class="brush:php;toolbar:false;">1
2
0
4 3 

方法2-Kosaraju

Kosaraju算法

  • 启动时创建已访问节点的集合和空堆栈。

  • 从图中每个节点尚未访问过的第一个节点开始深度优先搜索。将整个搜索过程中访问过的每个节点推入堆栈。

    Trae Solo
    Trae Solo

    一款AI开发辅助工具,主要用于字节旗下Trae推出的独立AI编程智能体工具,适合需要提升相关任务效率的用户。

    下载
  • 每个图形边缘的方向都应该反转。

  • 如果堆栈中仍充满节点,则将节点从堆栈中弹出。 如果尚未访问该节点,则从该节点执行深度优先搜索。将搜索过程中访问过的每个节点标记为当前高度链接组件的成员。

  • 重复直到所有节点都被访问过

  • 。
  • 每个高度关联的组件都将在程序结束时得到识别和注释。

下面的 C++ 代码使用 Kosaraju 算法来查找有向图中的强连通分量 (SCC)。软件定义了一个名为Graph的类,它有以下成员函数:

Graph(int V):构造函数,输入顶点数量 V 并初始化图的邻接列表。

Void addEdge(int v, int w):使用两个整数 v 和 w 作为输入,此方法创建一条连接图中顶点 v 到顶点 w 的边。

void printSCCs() 函数使用 Kosaraju 算法来打印图中的每个 SCC。

Graph getTranspose() 方法提供了图的转置。

使用递归函数 void fillOrder(int v, bool Visited[, stack& Stack], int v) 将顶点按照其完成时间的顺序添加到堆栈中。

示例 2

// C++ program to print the SCC of the 
// graph using Kosaraju's Algorithm 
#include <iostream> 
#include <list>
#include <stack> 
using namespace std; 
 
class Graph {
   // No. of vertices 
   int V; 
    
   // An array of adjacency lists 
   list<int>* adj; 
    
   // Member Functions 
   void fillOrder(int v, bool visited[], 
   stack<int>& Stack); 
   void DFSUtil(int v, bool visited[]); 
    
   public: 
   Graph(int V); 
   void addEdge(int v, int w); 
   void printSCCs(); 
   Graph getTranspose(); 
}; 
 
// Constructor of class 
Graph::Graph(int V) { 
   this->V = V; 
   adj = new list<int>[V]; 
} 
 
// Recursive function to print DFS 
// starting from v 
void Graph::DFSUtil(int v, bool visited[])  { 
   // Mark the current node as 
   // visited and print it 
   visited[v] = true; 
   cout ::iterator i; 
    
   // Traverse Adjacency List of node v 
   for (i = adj[v].begin(); 
   i != adj[v].end(); ++i) { 
       
      // If child node *i is unvisited 
      if (!visited[*i]) 
      DFSUtil(*i, visited); 
   } 
} 
 
// Function to get the transpose of 
// the given graph 
Graph Graph::getTranspose()  { 
   Graph g(V); 
   for (int v = 0; v ::iterator i; 
      for (i = adj[v].begin(); 
      i != adj[v].end(); ++i) { 
         // Add to adjacency list 
         g.adj[*i].push_back(v); 
      } 
   } 
    
   // Return the reversed graph 
   return g; 
} 
 
// Function to add an Edge to the given 
// graph 
void Graph::addEdge(int v, int w)  { 
   // Add w to v’s list 
   adj[v].push_back(w); 
} 
 
// Function that fills stack with vertices 
// in increasing order of finishing times 
void Graph::fillOrder(int v, bool visited[], 
stack<int>& Stack)  { 
   // Mark the current node as 
   // visited and print it 
   visited[v] = true; 
    
   // Recur for all the vertices 
   // adjacent to this vertex 
   list<int>::iterator i; 
    
   for (i = adj[v].begin(); 
   i != adj[v].end(); ++i) { 
    
      // If child node *i is unvisited 
      if (!visited[*i]) { 
         fillOrder(*i, visited, Stack); 
      } 
   } 
    
   // All vertices reachable from v 
   // are processed by now, push v 
   Stack.push(v); 
} 
 
// Function that finds and prints all 
// strongly connected components 
void Graph::printSCCs()  { 
   stack<int> Stack; 
    
   // Mark all the vertices as 
   // not visited (For first DFS) 
   bool* visited = new bool[V]; 
   for (int i = 0; i <h3>输出</h3>
<pre class="brush:php;toolbar:false;">0 1 2 
4
3<p></p>

结论

总之,Tarjan 和 Kosaraju 方法的时间复杂度为 O(V + E),其中 V 表示图中的顶点集,E 表示图中的边集。 Tarjan 算法中的常数因子明显低于 Kosaraju 方法中的常数因子。 Kosaraju 的方法至少遍历该图两次,因此常数因子可能是两倍。当我们完成第二个 DFS 时,我们可以使用 Kosaraju 的方法来生成现在处于活动状态的 SCC。一旦找到 SCC 子树的头部,用 Tarjan 算法打印 SCC 需要更长的时间。

尽管两种方法的线性时间复杂度相同,但 SCC 计算所使用的方法或流程存在一些差异。虽然 Kosaraju 的技术在图上运行两个 DFS(如果我们希望保持原始图不被修改,则运行三个 DFS),并且与确定图的拓扑排序的方法非常相似,但 Tarjan 的方法仅依赖于节点记录DFS 对图进行分区。

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

120

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

100

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

60

15

Postman身份认证怎么配置
Postman身份认证怎么配置

本专题从实际API接口调试场景出发,讲解Postman身份认证的完整配置流程,包括常见认证协议介绍、授权参数设置、访问令牌填写、OAuth 2.0授权及认证失败排查,帮助用户正确完成接口授权与访问验证。

2026.11.06

160

12

Postman请求头Headers怎么设置
Postman请求头Headers怎么设置

围绕Postman HTTP请求头配置展开,讲解Headers选项的具体使用方式,包括Key和Value参数填写、请求头信息添加、常见Header字段设置及请求头修改方法,帮助用户解决接口调试过程中遇到的请求头配置问题。

2026.11.06

140

13

Postman接口请求发送教程
Postman接口请求发送教程

详细介绍Postman接口请求的创建与发送方法,涵盖GET和POST请求、URL配置、请求参数、Headers请求头、Body请求体设置以及响应结果查看,帮助用户掌握Postman接口请求的完整操作流程。

2026.11.06

120

10

DBeaver怎么导入数据
DBeaver怎么导入数据

DBeaver数据导入专题,整理Excel、CSV、SQL、TXT等常见文件的数据导入方法,涵盖目标数据库选择、数据表创建、字段映射、数据类型设置及导入参数配置等操作,帮助用户将本地文件中的数据写入数据库,并了解批量导入、重复数据处理和导入失败等常见问题的解决方法。

2026.11.05

100

12

DBeaver安全防护教程大全
DBeaver安全防护教程大全

DBeaver安全防护专题,围绕数据库连接安全、账号密码保护和访问权限管理展开,整理SSL/TLS加密连接、SSH隧道、数据库凭据保存及证书验证等配置方法,同时介绍敏感信息保护、远程连接风险和高权限账号使用等注意事项,帮助用户提高数据库日常管理的安全性。

2026.11.05

100

12

DBeaver连接创建与配置教程
DBeaver连接创建与配置教程

本专题聚焦DBeaver数据库连接配置与管理,覆盖从新建连接、选择数据库类型到填写连接参数和验证连接的完整流程。针对MySQL、PostgreSQL、SQL Server等常见数据库,整理相应的连接设置方法,并提供驱动缺失、认证失败和连接异常等问题的排查方向。

2026.11.04

100

16

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
php初学者入门课程
php初学者入门课程

共10课时 | 1万人学习

QQ音乐客户端实战开发(electron)
QQ音乐客户端实战开发(electron)

共27课时 | 9.1万人学习

JavaScript学习指南
JavaScript学习指南

共63课时 | 21.5万人学习