简单有向图(c++版）

DiGraph.h

#pragma once
#include <iterator>
#include <fstream>
#include <memory>
#include <array>
#include <iostream>
#include <stack>
#include <vector>
#include <queue>

class DiGraph
{
private:
    class AdjacentcyList
    {
    private:
        class Node
        {
        public:
            std::shared_ptr<Node> next;
            int link;
        public:
            Node(const int& l) :link(l), next(nullptr)
            {

            }
        };
        std::shared_ptr<Node> head = nullptr;
    public:
        class Iterator
        {
        private:
            std::shared_ptr<Node> it;
        public:
            Iterator(std::shared_ptr<Node> i) :it(i)
            {

            }
            bool operator == (const Iterator& rhs)const
            {
                return it == rhs.it;
            }
            bool operator != (const Iterator& rhs)const
            {
                return !(*this == rhs);
            }
            const Iterator& operator ++()
            {
                it = it->next;
                return *this;
            }
            int operator *()const
            {
                return it->link;
            }
        };
public:
/**********************************************
函数名称:  addNode
函数说明:  为adjacentcyList增加结点
返回值:       void
**********************************************/
        void addNode(const int& i)
        {
            if (head == nullptr)
            {
                head = std::make_shared<Node>(Node(i));
                return;
            }
            std::shared_ptr<Node> curr = head;
            while (curr->next != nullptr)
                curr = curr->next;
            curr->next = std::make_shared<Node>(Node(i));
            return;
        }
        Iterator begin()const
        {
            return Iterator(head);
        }
        Iterator end()const
        {
            return Iterator(nullptr);
        }
    };
private:
    std::unique_ptr<AdjacentcyList[]> adj;
    int npoint;
    int nedge;
public:
    //构造有向图
    DiGraph(const std::string& file):nedge(0)
    {
        std::ifstream in(file);
        std::istream_iterator<int> st(in);
        std::istream_iterator<int> end;
        npoint = *st;
        adj = move(std::unique_ptr<AdjacentcyList[]>(new AdjacentcyList[npoint]));
        for (auto it = ++st; it != end; ++it)
        {
            int pre = *it;
            int curr = *++it;
            adj[pre].addNode(curr);
            ++nedge;
        }
    }
    DiGraph(const int& i):npoint(i),nedge(0)
    {
        adj = move(std::unique_ptr<AdjacentcyList[]>(new AdjacentcyList[npoint]));
    }
/******************************************
函数名称:   reDiGraph
函数说明:   得到该图的逆向图
*******************************************/
    DiGraph* reDiGraph()
    {
        DiGraph* ret = new DiGraph(npoint);
        for (int i = 0; i < npoint; ++i)
            for (auto w : adj[i])
            {
                ret->adj[w].addNode(i);
                ++ret->nedge;
            }
        return ret;
    }
private:
    //有向图深度遍历有关算法类
    class DirectionDFS
    {
    private:
        std::unique_ptr<bool[]> marked;
        std::unique_ptr<int*[]> edgeTo;
        std::unique_ptr<bool[]> onStack;
        DiGraph *dg;
        std::vector<std::stack<int>> cycle;
        std::queue<int> predfs;
        std::queue<int> sufdfs;
        std::stack<int> resufdfs;
        std::unique_ptr<int[]> id;
        int connect;
        std::vector<std::vector<bool>> link;
    private:
        void init()
        {
            for (int i = 0; i < dg->npoint; ++i)
            {
                marked[i] = false;
                edgeTo[i] = nullptr;
            }
        }
/******************************************
函数名称:   visit
函数说明:   得到DFS的前序遍历,后序遍历结果
若有向图无环则可得到逆后序遍历(拓扑排序结果)
返回值:        void
*******************************************/
        void visit()
        {
            init();
            for (int i = 0; i < dg->npoint; ++i)
                if (!marked[i]) visit(i);
        }
        void visit(const int& s)
        {
            marked[s] = true;
            predfs.push(s);
            for (auto w : dg->adj[s])
            {
                if (!marked[w])
                    visit(w);
            }
            sufdfs.push(s);
            if (cycle.empty())
            resufdfs.push(s);
        }
/******************************************
函数名称:   getConnect
函数说明:   得到连通图及个数
返回值:        void
步骤: 1.得到处理有向图的逆向图
        2.得到逆向图的逆后序排列结果
        3.按逆后序排列结果进行dfs搜索
*******************************************/
        void getConnect()
        {
            std::stack<int> sk;
            DiGraph* get = dg->reDiGraph();
            get_resufdfs(get, sk);
            init();
            while (!sk.empty())
            {
                if (!marked[sk.top()])
                {
                    ++connect;
                    get_dfs(sk.top());
                }
                sk.pop();
            }
        }
        void get_resufdfs(DiGraph* get,std::stack<int>& sk)
        {
            init();
            for (int i = 0; i < get->npoint; ++i)
                if (!marked[i]) get_resufdfs(get, sk, i);
        }
        void get_resufdfs(DiGraph *get,std::stack<int>& sk,const int& s)
        {
            marked[s] = true;
            for (auto w : get->adj[s])
                if (!marked[w])
                    get_resufdfs(get, sk, w);
            sk.push(s);
        }
        void get_dfs(const int& i)
        {
            marked[i] = true;
            id[i] = connect;
            for (auto w : dg->adj[i])
                if (!marked[w])
                    get_dfs(w);
        }
/******************************************
函数名称:   getLink
函数说明:将顶点之间的关系存储于数据成员link中
返回值:        void            
*******************************************/
        void getLink()
        {
            for (int i = 0; i < dg->npoint; ++i)
            {
                init();
                if (!marked[i])
                    getLink(i);
            }
        }
        void getLink(const int& i)
        {
            marked[i] = true;
            for (auto w : dg->adj[i])
            {
                if (!marked[w])
                {
                    link[i][w] = true;
                    getLink(w);
                }
            }
        }
    public:
        DirectionDFS(DiGraph *dg):dg(dg),connect(0)
        {
            marked = move(std::unique_ptr<bool[]>(new bool[dg->npoint]));
            edgeTo = move(std::unique_ptr<int*[]>(new int*[dg->npoint]));
            onStack = move(std::unique_ptr<bool[]>(new bool[dg->npoint]));
            id = move(std::unique_ptr<int[]>(new int[dg->npoint]));
            link.resize(dg->npoint);
            for (auto &v : link)
                v.resize(dg->npoint);
            getLink();
            getConnect();
            init();
            for (int i = 0; i < dg->npoint; ++i)
                if (!marked[i]) dfs(i);
            visit();
        }
        void dfs(const int& s)
        {
            marked[s] = true;
            onStack[s] = true;
            for (auto w : dg->adj[s])
            {
                if (!marked[w])
                {
                    edgeTo[w] = new int(s);
                    dfs(w);
                }
                else if (onStack[w])
                {
                    std::stack<int> sk;
                    sk.push(w);
                    sk.push(s);
                    for (int *i = edgeTo[s]; i != nullptr; i = edgeTo[*i])
                    {
                        if (*i == w)
                            break;
                        sk.push(*i);
                    }
                    sk.push(w);
                    cycle.push_back(sk);
                }
            }
            onStack[s] = false;
        }
/******************************************
函数名称:   print_cycle
函数说明:   打印环
返回值:        void
*******************************************/
        void print_cycle()
        {
            if (cycle.empty())
                return;
            for (auto s : cycle)
            {
                while (!s.empty())
                {
                    std::cout << s.top() << std::ends;
                    s.pop();
                }
                std::cout << std::endl;
            }
        }
/******************************************
函数名称:   print_TopSort
函数说明:   若图无环,则打印拓扑排序结果
返回值:        void
*******************************************/
        void print_TopSort()
        {
            while (!resufdfs.empty())
            {
                std::cout << resufdfs.top() << std::ends;
                resufdfs.pop();
            }
            std::cout << std::endl;
        }
/******************************************
函数名称:   print_predfs
函数说明:   打印dfs前序遍历结果
返回值:        void
*******************************************/
        void print_predfs()
        {
            while (!predfs.empty())
            {
                std::cout << predfs.front() << std::ends;
                predfs.pop();
            }
            std::cout << std::endl;
        }
/******************************************
函数名称:   print_sufdfs
函数说明:   打印有向图的后序遍历结果    
返回值:        void
*******************************************/
        void print_sufdfs()
        {
            while (!sufdfs.empty())
            {
                std::cout << sufdfs.front() << std::ends;
                sufdfs.pop();
            }
            std::cout << std::endl;
        }
/******************************************
函数名称:   print_Connect
函数说明:   打印连通图
返回值:     void
*******************************************/
        void print_Connect()
        {
            for (int i = 1; i <= connect; ++i)
            {
                std::cout << "第" << i << "个连通图: ";
                for (int j = 0; j < dg->npoint; ++j)
                    if (id[j] == i)
                        std::cout << j << std::ends;
                std::cout << std::endl;
            }
        }
/******************************************
函数名称:   isLink
函数说明:   返回两节点是否连接
返回值:        bool
*******************************************/
        bool isLink(const int& s,const int& e)
        {
            return link[s][e];
        }
    };
    public:
    void print_cycle()
    {
        DirectionDFS(this).print_cycle();
    }
    void print_TopSort()
    {
        DirectionDFS(this).print_TopSort();
    }
    void print_predfs()
    {
        DirectionDFS(this).print_predfs();
    }
    void print_sufdfs()
    {
        DirectionDFS(this).print_sufdfs();
    }
    void print_Connect()
    {
        DirectionDFS(this).print_Connect();
    }
    bool isLink(const int& s, const int& e)
    {
        return DirectionDFS(this).isLink(s, e);
    }
};

main.cpp

#include <iostream>
#include "DiGraph.h"

using namespace std;

int main()
{
    DiGraph dg("test.txt");
    //dg.print_cycle();
    cout << "拓扑排序: ";
    dg.print_TopSort();
    dg.print_predfs();
    dg.print_sufdfs();
    dg.print_Connect();
    cout << boolalpha << dg.isLink(8, 7) << endl;
    system("pause");
    return 0;
}

测试拓扑文件 Text.txt

13
8 7
7 6
2 3
2 0
3 5
0 6
0 1
0 5
6 9
6 4
9 10
9 11
9 12
11 12
5 4

其他测试文件:

13
4 2
2 3
3 2
6 0
0 1
2 0
11 12
12 9
9 10
9 11
8 9
10 12
11 4
4 3
3 5
7 8
8 7
5 4
0 5
6 4
6 9
7 6

运行：