図処理アルゴリズム-Kosaraju's-アルゴリズム

1.アルゴリズムの授業で図面のある宿題について書きました.
c++で大きな配列を開くとsegment faultが出やすくなり,その後スタックで開くようになった.図の隣接表はチェーンテーブルで表されている. 

long int numVertexes = 875714;
long int numEdges;
VertexNode* adjList = new VertexNode[875714];

2.図の格納については、隣接チェーンテーブルで格納する(vector配列よりチェーンテーブルでアクセス速度がずっと速い).
2.1辺表

/********  ***********/
class EdgeNode
{
public:
    long int adjvex; //    
    EdgeNode *next; //          
    EdgeNode(long int adj, EdgeNode *n = NULL): adjvex(adj), next(n){}
    
};

2.2頂点テーブル

/*********   **********/
class VertexNode
{
public:
    long int data;    //      
    EdgeNode *firstEdge; //      
//    VertexNode(long int d, EdgeNode *fir = NULL) : data(d), firstedge(fir) {}
};

2.3図辺を初期化する際にヘッドプラグを用いた

/*************   *************************/
    void addEdge(long int a, long int b)
    {
        EdgeNode *enode = new EdgeNode(b,NULL);
        enode->next = (adjList+a)->firstEdge;
        (adjList+a)->firstEdge = enode; 
    }

3.深さ優先検索
3.1再帰的実現
疑似コードは次のとおりです.
入力:図Gと頂点i
1.頂点iをアクセス済みとしてマークします.
2.エッジ(i,j)、すなわち頂点iの隣接点jを遍歴する.
3.ifある頂点jがアクセスされていない場合、頂点jにアクセスする.
DFS(G,j)
c++コードは以下の通りです.

/*---------------------   dfs-------------------*/
void DFS(Graph graph, long int i) 
    {
        marked[i] = true;
        
        list<long int>::iterator iter;
        for(iter = graph._storage[i].begin(); iter != graph._storage[i].end(); iter++)
        {
            long int temp = *iter;
            if(!marked[temp])
            {
                DFS(graph, temp);
            }
        }
        time++;
        ff[time-1] = i;
    }

/*---------------   dfs---------------*/
void DFS2(Graph graph, long int i)
    {
        marked[i] = true;
        leader[i] = s;

        list<long int>::iterator iter;
        for(iter = graph._storage[i].begin(); iter != graph._storage[i].end(); iter++)
        {
            long int temp = *iter;
            if(!marked[temp])
            {
                DFS2(graph, temp);
            }
        }
    }

 
3.2非再帰的な実装
疑似コードは次のとおりです.
入力:図G、頂点iへ.
1.スタックを初期化し、頂点iをスタックに入れ、iをアクセス済みとしてマークします.
2.while(スタックが空でない)
x=スタックトップ要素
3.エッジ(x,j)を巡回する:
if:ある頂点jがアクセスされていない:
jをアクセス済みとマークする
jをスタックに入れる
　　break
else:
x出桟
c++コード:

/*================   dfs================*/
    void dfsLoop1(Graph graph)
    {
        markedInit();
        time = 0; 
        for(long int i = length-1; i >= 0; i--)
        {
            if(!marked[i])
            {
                DFS1(graph, i);
            }
        }
    }
    void DFS1(Graph graph, long int i)
    {
        stack< VertexNode* > stack;
        stack.push(graph.adjList+i);
        marked[i] = true;
        while(!stack.empty())
        {
            VertexNode *temp = new VertexNode;
            temp = stack.top();
            EdgeNode *p = new EdgeNode(0, NULL);
            p = temp->firstEdge;
            int flag = 0;
            while(p)
            {
                if(!marked[p->adjvex])
                {
                    marked[p->adjvex] = true;
                    stack.push(graph.adjList + (p->adjvex));        
                    flag = 1;
                    break;
                }
                p = p->next;
            }
            if(!flag)
            {
                ff[time] = temp->data;
                time++;
                stack.pop();
            }
        }
    }

/*================   dfs================*/
    void dfsLoop2(Graph graph)
    {
        markedInit();
        time = 0;
        for(long int i = length-1; i >=0 ; i--)
        {
            if(!marked[ff[i]])
            {
                s = ff[i];
                DFS2(graph, ff[i]);
            }
        }
    }
void DFS2(Graph graph, long int i)
    {
        stack < VertexNode* > stack;
        stack.push(graph.adjList+i);
        leader[i] = s;
        marked[i] = true;
        while(!stack.empty())
        {
            VertexNode *temp = new VertexNode;
            temp = stack.top();
            marked[temp->data] = true;
            EdgeNode *p = new EdgeNode(0,NULL);
            p = temp->firstEdge;
            int flag = 0;
            while(p)
            {
                if(!marked[p->adjvex])
                {
                    marked[p->adjvex] = true;
                    stack.push(graph.adjList + p->adjvex);
                    flag = 1;
                    break;
                }
                p = p->next;
            }
            if(!flag)
            {
                leader[temp->data] = s;
                stack.pop();
            }


        }
    }

完全なコード:https://github.com/Shinered/Kosaraju/blob/master/dfs3.cpp
 
転載先:https://www.cnblogs.com/Shinered/p/8999688.html