简单无向图(c++版)

Graph.h

#pragma once
#include <string>
#include <sstream>
#include <fstream>
#include <iterator>
#include <stack>
#include <queue>

class Graph
{
private:
    class EdgeList
    {
    public:
        class Node
        {
        public:
            int link;
            Node* next = nullptr;
        public:
            Node(const int& n) :link(n)
            {

            }
        };
        Node* head = nullptr;
    public:
        class Iterator
        {
        private:
            Node* it;
        public:
            Iterator(Node* i) :it(i) {}
            Iterator operator++()
            {
                it = it->next;
                return *this;
            }
            Iterator operator++(int)
            {
                Node* i = it;
                it = it->next;
                return Iterator(i);
            }
            bool operator == (const Iterator& rhs)
            {
                if (it == nullptr && rhs.it == nullptr)
                    return true;
                if (it != nullptr && rhs.it != nullptr)
                {
                    if (it == rhs.it)
                        return true;
                }
                return false;
            }
            bool operator != (const Iterator& rhs)
            {
                return !(*this == rhs);
            }
            const int& operator *()
            {
                if (it == nullptr)
                    throw std::logic_error("* nullptr error");
                return it->link;
            }
        };
/******************************************
函数名称:   begin
函数说明:   返回迭代器begin位置
*******************************************/
        Iterator begin()const
        {
            return Iterator(head);
        }
/******************************************
函数名称:   end
函数说明:   返回迭代器尾部也就是nullptr
返回值     Iterator
*******************************************/
        Iterator end()const
        {
            return Iterator(nullptr);
        }
/******************************************
函数名称:   addNode
函数说明:   给邻接表增加节点
返回值:        void
*******************************************/
        void addNode(const int& link)
        {
            if (head == nullptr)
            {
                head = new Node(link);
                return;
            }
            Node* curr = head;
            while (curr->next != nullptr)
                curr = curr->next;
            curr->next = new Node(link);
            return;
        }
    };
private:
    int V;
    int E;
    EdgeList* adj;
public:
    Graph(const std::string& file)
    {
        std::ifstream in(file);
        std::istream_iterator<int> beg(in);
        std::istream_iterator<int> end;
        V = *beg;
        adj = new EdgeList[V];
        for (auto it = ++beg; it != end; ++it)
        {
            int pre = *it;
            int curr = *++it;
            adj[pre].addNode(curr);
            adj[curr].addNode(pre);
            ++E;
        }
    }
/******************************************
函数名称:   degree
函数说明:   计算结点v的度数
返回值:        int
*******************************************/
    int degree(const int& v)
    {
        if (v > V - 1)
            throw std::out_of_range("结点超出范围");
        int count = 0;
        for (auto &i : adj[v])
            ++count;
        return count;
    }
/******************************************
函数名称:   max_degree
函数说明:   计算所有顶点的最大度数
返回值:        int
*******************************************/
    int max_degree()
    {
        int max = 0;
        for (int i = 0; i < V; ++i)
            if (degree(i) > max)
                max = degree(i);
        return max;
    }
/******************************************
函数名称:   avge_degree
函数说明:   计算所有顶点的平均度数
返回值:        double
*******************************************/
    double avge_degree()
    {
        if (V == 0)
            return 0.0;
        return 2 * E / V;
    }
/******************************************
函数名称:   numSelfLoops
函数说明:   计算自环的个数
返回值:        int
*******************************************/
    int numSelfLoops()
    {
        int count = 0;
        for (int i = 0; i < V; ++i)
            for (auto& w : adj[i])
                if (i == w)
                    ++count;
        return count;
    }
/******************************************
函数名称:   ncount
函数说明:   返回图的结点个数
返回值:        int
*******************************************/
    int ncount()
    {
        return V;
    }
/******************************************
函数对象(有状态的函数)
生成用于连通性，是否连通，连通结点个数等算法
*******************************************/
    class DeepFirstSearch
    {
    private:
        bool *marked;
        int count;
        Graph *g;
        int **edgeTo;
        int *id;
        int nconnect;
    private:
        void init()
        {
            for (int i = 0; i < g->ncount(); ++i)
            {
                marked[i] = false;
                edgeTo[i] = nullptr;
            }
            count = 0;
        }
    public:
        DeepFirstSearch(Graph* g):g(g),count(0),nconnect(0)
        {
            marked = new bool[g->ncount()];
            edgeTo = new int*[g->ncount()];
            id = new int[g->ncount()];
            init();
        }
        void dfs(const int& s,std::string mode = "no")
        {
            if (mode == "display")
                std::cout << s << "----";
            marked[s] = true;
            ++count;
            id[s] = nconnect;
            for (auto &w : g->adj[s])
                if (!marked[w])
                {
                    edgeTo[w] = new int(s);
                    dfs(w,mode);
                }
        }
/******************************************
函数名称: isLink
函数说明: 判断两节点是否连通
返回值:      bool
*******************************************/
        bool isLink(const int& s, const int& e)
        {
            init();
            dfs(s);
            return marked[e];
        }
/******************************************
函数名称:   display
函数说明:   打印一条该节点在图中的通路
返回值     void
*******************************************/
        void display(const int& s)
        {
            dfs(s, "display");
        }
        int size(const int& s)
        {
            init();
            dfs(s);
            return count;
        }
/******************************************
函数名称:   manyConnect
函数说明:   计算图中有多少连通图
返回值:        int
******************************************/
        int manyConnect()
        {
            init();
            for (int i = 0; i < g->ncount(); ++i)
            {
                if (!marked[i])
                {
                    ++nconnect;
                    dfs(i);
                }
            }
            return nconnect;
        }
/*****************************************
函数名称:   printConnect
函数说明:   打印连通图
返回值:        void
******************************************/
        void printConnect()
        {
            manyConnect();
            for (int i = 1; i <= nconnect; ++i)
            {
                std::cout << "第" << i << "幅连通图 : ";
                for (int j = 0; j < g->ncount(); ++j)
                {
                    if (id[j] == i)
                        std::cout << j << "--";
                }
                std::cout << std::endl;
            }
        }
/******************************************
函数名称:   printPath
函数说明:   打印起点s到终点e的一条路径
返回值:        void
*******************************************/
        void printPath(const int& s,const int& e)
        {
            init();
            dfs(s);
            std::stack<int> sk;
            for (int* i = edgeTo[e]; i != nullptr; i = edgeTo[*i])
                sk.push(*i);
            bool flag = sk.empty();
            while (!sk.empty())
            {
                std::cout << sk.top() << "--->";
                sk.pop();
            }
            if (!flag)
                std::cout << e << std::endl;
        }
        ~DeepFirstSearch()
        {
            if (marked != nullptr)
                delete marked;
            if (edgeTo != nullptr)
                delete edgeTo;
        }
    };
    //应用于图
    int count(const int& s)
    {
        DeepFirstSearch Dfs(this);
        return Dfs.size(s);
    }
    void display(const int& s)
    {
        DeepFirstSearch(this).display(s);
    }
    bool isLink(const int& s, const int& e)
    {
        return DeepFirstSearch(this).isLink(s, e);
    }
    void printPath(const int& s,const int& e)
    {
        return DeepFirstSearch(this).printPath(s, e);
    }
    int manyConnect()
    {
        return DeepFirstSearch(this).manyConnect();
    }
    void printConnect()
    {
        DeepFirstSearch(this).printConnect();
    }
    private:
        class BreadthFirstSearch
        {
        private:
            bool* masked;
            int count;
            int** edgeTo;
            Graph* g;
            void init()
            {
                for (int i = 0; i < g->ncount(); ++i)
                {
                    masked[i] = false;
                    edgeTo[i] = nullptr;
                }
            }
        public:
            BreadthFirstSearch(Graph *g):g(g)
            {
                masked = new bool[g->ncount()];
                edgeTo = new int*[g->ncount()];
            }
            void bfs(const int& s)
            {
                std::queue<int> q;
                q.push(s);
                masked[s] = true;
                while (!q.empty())
                {
                    for (auto& w : g->adj[q.front()])
                    {
                        if (!masked[w])
                        {
                            edgeTo[w] = new int(q.front());
                            masked[w] = true;
                            q.push(w);
                        }
                    }
                    q.pop();
                }
            }
/******************************************
函数名称:   shortestPath    
函数说明:   得到起点s到e的最短路径
返回值:        void
*******************************************/
        void shortestPath(const int& s,const int& e)
        {
            init();
            bfs(s);
            std::stack<int> sk;
            sk.push(e);
            for (int* i = edgeTo[e]; i != nullptr; i = edgeTo[*i])
            {
                sk.push(*i);
                if (*i == s)
                    break;
            }
            if (sk.top() != s)
                return;
            while (!sk.empty())
            {
                if (sk.top() != e)
                    std::cout << sk.top() << "--->";
                else
                    std::cout << sk.top();
                sk.pop();
            }
        }
    };
    public:
        void shortestPath(const int& s, const int& e)
        {
            BreadthFirstSearch(this).shortestPath(s, e);
        }
};

main.cpp

#include <iostream>
#include "Graph.h"
using namespace std;

int main()
{
    Graph g("test.txt");
    cout << "结点0的度数为: " << g.degree(0) << endl;
    cout << "最大度数为: " << g.max_degree() << endl;
    cout << "平均度数为: " << g.avge_degree() << endl;
    cout << "自环个数为: " << g.numSelfLoops() << endl;
    cout << "与0能连通的结点个数为: " << g.count(0) << endl;
    cout << "0 与 9 能连通吗? :" << (g.isLink(0, 9) ? "能" : "不能") << endl;
    cout << "打印0的一条连接序列: " << endl;
    g.display(0);
    cout << "打印0到6的连接序列: " << endl;
    g.printPath(0, 6);
    cout << "打印0到6的最短路径: " << endl;
    g.shortestPath(9, 12);
    cout << endl;
    cout << "有多少连通图: " << g.manyConnect();
    cout << endl;
    cout << "打印连通图: " << endl;
    g.printConnect();
    system("pause");
    return 0;
}

测试文件: test.txt

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

运行: