Проблема реализации алгоритма Косараю - PullRequest
1 голос
/ 14 апреля 2020
  #include <bits/stdc++.h>

using namespace std;

multiset<unsigned long long> connectedComp;
unsigned long long int counter = 0;
unsigned long long int numComponents = 0;

class Graph{
public:
    unsigned long long int size;
    list<unsigned long long> *adjList;
    bool *visited;
    stack<unsigned long long int> s;
    Graph(unsigned long long int);
    void addEdge(unsigned long long int,unsigned long long int);
    void reverse();
    void DFS1(unsigned long long int);
    unsigned long long int DFS2(unsigned long long int);
    void Kosaraju(void);
    void initialize(void);
};

Graph::Graph(unsigned long long int s){
    size = s;
    adjList = new list<unsigned long long>[size];
    visited = new bool[size];
}

void Graph::addEdge(unsigned long long int src,unsigned long long int dest){
    adjList[src].push_back(dest);
}

void Graph::DFS1(unsigned long long int src) {
    initialize();
    stack<int> stack;
    stack.push(src);
    stack.push(src);

    while(!stack.empty()){
        src = stack.top();
        stack.pop();
        if(!visited[src]){
            visited[src] = true;
        }
        else if(visited[src]) s.push(src);

        for(auto it = adjList[src].begin();it!= adjList[src].end();it++){
            if(!visited[*it]){ stack.push(*it); stack.push(*it);}
        }
    }
} 


void Graph::initialize(void){
    for(unsigned long long int i = 0;i<size;i++) visited[i] = false;
}

unsigned long long int Graph::DFS2(unsigned long long int src){
    counter = 0;
    stack<int> stack; 
    stack.push(src); 

    while (!stack.empty()) { 
        counter++;
        src = stack.top(); 
        stack.pop(); 
        if (!visited[src]) 
            visited[src] = true; 

        for (auto i = adjList[src].begin(); i != adjList[src].end(); ++i)
            if (!visited[*i]) 
                stack.push(*i);

    } 
    return counter;
} 

void Graph::reverse(){
    list<unsigned long long> *tempAdj = new list<unsigned long long>[size];
    list<unsigned long long>::iterator it;
    for(unsigned long long int i = 0;i<size;i++){
        it = adjList[i].begin();
        for(it;it!= adjList[i].end();it++){
            tempAdj[*it].push_back(i);
        }
    }
    adjList = tempAdj;  
}

void Graph::Kosaraju(void){
    for(unsigned long long int i = 0;i<size;i++){
        if(!visited[i]) DFS1(i);
    }
    reverse();
    initialize();
    while (!s.empty()){
        unsigned long long int v = s.top(); s.pop();
        if (!visited[v])
        {
            connectedComp.insert(DFS2(v));
            visited[v] = true;
            numComponents++;
        }
    }

}


int main(void){
    Graph g(11);
    g.addEdge(0,2);
    g.addEdge(1,0);
    g.addEdge(2,1);
    g.addEdge(2,3);
    g.addEdge(3,4);
    g.addEdge(4,5);
    g.addEdge(5,3);
    g.addEdge(6,5);
    g.addEdge(6,7);
    g.addEdge(7,8);
    g.addEdge(8,9);
    g.addEdge(9,6);
    g.addEdge(9,10);
    g.Kosaraju();
    for(auto it = connectedComp.rbegin();it != connectedComp.rend();it++){
        cout<<*it<<endl;
    }
}

Я сделал реализацию алгоритма Косараю для сильно связанных компонентов, однако моя реализация вычисляет неверное число связанных компонентов, один из которых находится в данном коде. Интересно, что не так с точки зрения логики c. Например, мой код работает с таким порядком узлов: Graph g (5); g.addEdge (1, 0); g.addEdge (0, 2); g.addEdge (2, 1); g.addEdge (0, 3); g.addEdge (3, 4);

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...