精华内容
下载资源
问答
  • 邻接多重表 操作实现
    2021-12-05 19:52:24

    邻接多重表是一种比较重要的无向简单图存储结构,鉴于无向图在数据结构课程中的重要性,邻接表多重操作实现必须要予以解决。图论及其算法在编译原理中具有很重要的地位,图着色的寄存器分配就要用到无向简单图,所以自己尝试实现一下邻接多重表的操作。

    一开始很天真的以为邻接多重表的实现难度和十字链表应该相差不大,十字链表能够实现邻接多重表应该也不成问题,但实际开始动手后才发现情况并非如此,邻接多重表实现比十字链表更为复杂。不得不承认自己实在太笨,问题没考虑全面就急匆匆敲代码,结果运行后不是发现这里没考虑到就是那里存在错误,于是就反反复复修改编译修改编译,真是被折磨死了。图结构及其算法确实是数据结构中最难的部分之一,我已经深有体会了。用了整整两天时间总算正确实现了邻接多重表的操作,实现了添加边,删除边,删除顶点,复制,合并,销毁,添加顶点这些重要的API,其他接口应该没有那么重要,需要的话以后还可以添加。

    C++代码清单:

    #include "pch.h"
    #include <iostream>
    #include <vector>
    #include <set>
    using namespace std;
    
    template <typename V, typename E>
    class Graph   //无向简单图类,存储结构为多重邻接表
    {
        friend vector<vector<int>> *convertToAdjaMatrix(Graph<size_t, size_t> *undigraph);
    public:
        struct VertexNode;
        struct EdgeNode   //边节点类型
        {
            E *edge_data_field = nullptr;   //边节点数据域
            typename vector<VertexNode *>::size_type left = 0;   //边一端对应顶点
            typename vector<VertexNode *>::size_type right = 0;  //边另一端对应顶点
            EdgeNode *same_left_ptr = nullptr;   //指向一端仍为left的下一个边节点的指针
            EdgeNode *same_right_ptr = nullptr;  //指向另一端仍为right的下一个边节点的指针
            EdgeNode() = default;
            EdgeNode(typename vector<VertexNode *>::size_type l, typename vector<VertexNode *>::size_type r, E *e) :left(l), right(r), edge_data_field(e) {}
            ~EdgeNode() { delete edge_data_field; }
        };
    
        struct VertexNode   //顶点节点
        {
            V *vertex_data_field = nullptr;  //顶点数据域
            typename vector<VertexNode *>::size_type number = 0;   //顶点编号
            EdgeNode *first_ptr = nullptr;   //指向和该顶点关联的第一条边的指针
            VertexNode *seilring = nullptr;  //指向当前顶点,表示存在自环
            E *Edgeseilring = nullptr;   //自环边
    
            VertexNode() = default;
            VertexNode(typename vector<VertexNode *>::size_type n, V *v) :number(n), vertex_data_field(v) {}
            ~VertexNode() { delete vertex_data_field; delete Edgeseilring; }
        };
    
        Graph() = default;
        Graph(typename vector<VertexNode *>::size_type n) :set_of_vertex(n, nullptr) {}
        virtual ~Graph();  //释放多重邻接表并销毁图
        Graph<V, E> *copy();   //拷贝当前无向图并返回指向副本的指针
        typename vector<typename VertexNode *>::size_type addVertex(V *vertex);   //添加顶点,vertex为顶点数据域
        bool addEdge(typename vector<VertexNode *>::size_type left, typename vector<VertexNode *>::size_type right, E *edge);  //添加边(left, right),edge为边数据域
        void deleteVertex(typename vector<VertexNode *>::size_type vertex);  //删除顶点vertex
        bool deleteEdge(typename vector<VertexNode *>::size_type left, typename vector<VertexNode *>::size_type right);  //删除边(left, right)
        Graph<V, E> *merge(Graph<V, E>& Bemerged, bool copyOrNot);   //将Bemerged和当前无向图合并,copyOrNot=true拷贝当前图返回合并后得到的新的无向图的指针,=false直接合并至当前图返回空指针
        typename vector<VertexNode *>::size_type getVertexNum() { return set_of_vertex.size(); }  //获取无向图中顶点数目
    protected:
        vector<VertexNode *> set_of_vertex;  //无向图顶点集
    };
    
    template <typename V, typename E>
    typename vector<typename Graph<V, E>::VertexNode *>::size_type Graph<V, E>::addVertex(V *vertex)
    {
        set_of_vertex.push_back(new VertexNode(set_of_vertex.size(), vertex));
        return set_of_vertex.size() - 1;
    
    }
    
    template <typename V, typename E>
    bool Graph<V, E>::addEdge(typename vector<VertexNode *>::size_type left, typename vector<VertexNode *>::size_type right, E *edge)  //从left和right顶点节点开始检索插入位置并插入,该过程会保持和left或right关联的边节点的另一端顶点的编号的有序性(从小到大)
    {
        if (left >= set_of_vertex.size() || right >= set_of_vertex.size())
        {
            throw new out_of_range("无效的顶点参数\\n");
        }
        if (left == right)
        {
            set_of_vertex[left]->seilring = set_of_vertex[left];
            set_of_vertex[left]->Edgeseilring = new E(*edge);
            return true;
        }
    
        EdgeNode *start = set_of_vertex[left]->first_ptr;
        EdgeNode *pre = nullptr;
        if (start == nullptr)
        {
            set_of_vertex[left]->first_ptr = new EdgeNode(left, right, edge);
            if (set_of_vertex[right]->first_ptr == nullptr)
            {
                set_of_vertex[right]->first_ptr = set_of_vertex[left]->first_ptr;
                return true;
            }
        }
        else
        {
            for (; start != nullptr; )
            {
                if ((start->left == left ? start->right : start->left) == right)
                    return false;
                else if ((start->left == left ? start->right : start->left) < right)
                {
                    pre = start;
                    if (start->left == left)
                    {
                        start = start->same_left_ptr;
                    }
                    else
                    {
                        start = start->same_right_ptr;
                    }
                }
                else
                {
                    if (pre == nullptr)
                    {
                        pre = set_of_vertex[left]->first_ptr;
                        set_of_vertex[left]->first_ptr = new EdgeNode(left, right, edge);
                        set_of_vertex[left]->first_ptr->same_left_ptr = pre;
                        if (set_of_vertex[right]->first_ptr == nullptr)
                        {
                            set_of_vertex[right]->first_ptr = set_of_vertex[left]->first_ptr;
                            return true;
                        }
                        pre = set_of_vertex[left]->first_ptr;
                    }
                    else
                    {
                        if (pre->left == left)
                        {
                            pre->same_left_ptr = new EdgeNode(left, right, edge);
                            pre->same_left_ptr->same_left_ptr = start;
                            if (set_of_vertex[right]->first_ptr == nullptr)
                            {
                                set_of_vertex[right]->first_ptr = pre->same_left_ptr;
                                return true;
                            }
                            pre = pre->same_left_ptr;
                        }
                        else
                        {
                            pre->same_right_ptr = new EdgeNode(left, right, edge);
                            pre->same_right_ptr->same_left_ptr = start;
                            if (set_of_vertex[right]->first_ptr == nullptr)
                            {
                                set_of_vertex[right]->first_ptr = pre->same_right_ptr;
                                return true;
                            }
                            pre = pre->same_right_ptr;
                        }
                    }
                    break;
                }
            }
            if (start == nullptr)
            {
                if (pre->left == left)
                {
                    if (pre->right == right)
                        return false;
                    pre->same_left_ptr = new EdgeNode(left, right, edge);
                    if (set_of_vertex[right]->first_ptr == nullptr)
                    {
                        set_of_vertex[right]->first_ptr = pre->same_left_ptr;
                        return true;
                    }
                    pre = pre->same_left_ptr;
                }
                else
                {
                    if (pre->left == right)
                        return false;
                    pre->same_right_ptr = new EdgeNode(left, right, edge);
                    if (set_of_vertex[right]->first_ptr == nullptr)
                    {
                        set_of_vertex[right]->first_ptr = pre->same_right_ptr;
                        return true;
                    }
                    pre = pre->same_right_ptr;
                }
            }
        }
    
        if (pre == nullptr)
        {
            pre = set_of_vertex[left]->first_ptr;
        }
    
        EdgeNode *p = nullptr;
        for (EdgeNode *start = set_of_vertex[right]->first_ptr; start != nullptr; )
        {
            if ((start->right == right ? start->left : start->right) < left)
            {
                p = start;
                if (start->right == right)
                {
                    start = start->same_right_ptr;
                }
                else
                {
                    start = start->same_left_ptr;
                }
            }
            else
            {
                if (p == nullptr)
                {
                    p = set_of_vertex[right]->first_ptr;
                    set_of_vertex[right]->first_ptr = pre;
                    pre->same_right_ptr = p;
                }
                else
                {
                    if (p->right == right)
                    {
                        p->same_right_ptr = pre;
                    }
                    else
                    {
                        p->same_left_ptr = pre;
                    }
                    pre->same_right_ptr = start;
                }
                return true;
            }
        }
    
        if (p->right == right)
        {
            p->same_right_ptr = pre;
        }
        else
        {
            p->same_left_ptr = pre;
        }
        return true;
    }
    
    template <typename V, typename E>
    Graph<V, E>::~Graph()   //删除算法较为简洁,原因是和顶点关联的所有边另一端的顶点编号保持有序,这样我们只需从小到大考察每个顶点,如果和顶点关联的边全部删除,first_ptr指针为空,算法会自动跳过,否则依次分离出和顶点关联的每一条边,从该边关联的非当前顶点的另一
    {                       //顶点处对分离出的边节点进行摘链(根据删除算法的执行顺序,被摘链的边节点一定是和另一顶点关联的边链表中的第一个节点),然后释放分离出的边节点,所有顶点处理完后销毁set_of_vertex
        for (typename vector<VertexNode *>::size_type run = 0; run < set_of_vertex.size(); ++run)
        {
            EdgeNode *ptr = nullptr;
            while (set_of_vertex[run]->first_ptr != nullptr)
            {
                ptr = set_of_vertex[run]->first_ptr;
                if (ptr->left == run)
                {
                    set_of_vertex[run]->first_ptr = ptr->same_left_ptr;
                    set_of_vertex[ptr->right]->first_ptr = ptr->same_right_ptr;
                }
                else
                {
                    set_of_vertex[run]->first_ptr = ptr->same_right_ptr;
                    set_of_vertex[ptr->left]->first_ptr = ptr->same_left_ptr;
                }
                delete ptr;
            }
        }
    
        while (set_of_vertex.empty() == false)
        {
            delete set_of_vertex.back();
            set_of_vertex.pop_back();
        }
    
    }
    
    template <typename V, typename E>
    Graph<V, E> *Graph<V, E>::copy() //依次考察原图每一个顶点,对每一个顶点依次考察关联的每一边节点,如果该边节点副本已在尚未拷贝完成的图副本中,则将边节点副本链接至图副本对应顶点副本的边链表的尾部,否则创建新节点(为当前边节点副本)链接至图副本对应顶点副本的边链表的尾部
    {                                //同时搜索图副本中已部分形成的通过和新边节点关联的另一端顶点(非原图中当前遍历到的顶点)对应的链接指针链接形成的边链表的第一个边节点,由该边节点循链找到部分形成的边链表尾部,将新节点链接至尾部即可
        Graph<V, E> *temp = new Graph<V, E>(set_of_vertex.size());
        for (typename vector<VertexNode *>::size_type run = 0; run < set_of_vertex.size(); ++run)
        {
            temp->set_of_vertex[run] = new VertexNode(set_of_vertex[run]->number, new V(*(set_of_vertex[run]->vertex_data_field)));
            if (set_of_vertex[run]->seilring != nullptr)
            {
                temp->set_of_vertex[run]->seilring = temp->set_of_vertex[run];
                temp->set_of_vertex[run]->Edgeseilring = new E(*(set_of_vertex[run]->Edgeseilring));
            }
    
            if (set_of_vertex[run]->first_ptr == nullptr)
                continue;
    
            EdgeNode *p = nullptr;
            for (EdgeNode *start = set_of_vertex[run]->first_ptr; start != nullptr; )
            {
                if ((start->left == run ? start->right : start->left) < run)
                {
                    EdgeNode *q = nullptr;
                    if (start->left == run)
                    {
                        q = temp->set_of_vertex[start->right]->first_ptr;
                        for (; q != nullptr; )
                        {
                            if (q->left == start->right)
                            {
                                if (q->right == run)
                                    break;
                                q = q->same_left_ptr;
                            }
                            else
                            {
                                if (q->left == run)
                                    break;
                                q = q->same_right_ptr;
                            }
                        }
                    }
                    else
                    {
                        q = temp->set_of_vertex[start->left]->first_ptr;
                        for (; q != nullptr; )
                        {
                            if (q->left == start->left)
                            {
                                if (q->right == run)
                                    break;
                                q = q->same_left_ptr;
                            }
                            else
                            {
                                if (q->left == run)
                                    break;
                                q = q->same_right_ptr;
                            }
                        }
                    }
    
                    if (p == nullptr)
                    {
                        p = temp->set_of_vertex[run]->first_ptr = q;
                    }
                    else
                    {
                        if (p->left == run)
                        {
                            p = p->same_left_ptr = q;
                        }
                        else
                        {
                            p = p->same_right_ptr = q;
                        }
                    }
                }
                else
                {
                    if (p == nullptr)
                    {
                        p = temp->set_of_vertex[run]->first_ptr = new EdgeNode(start->left, start->right, new E(*(start->edge_data_field)));
                    }
                    else
                    {
                        if (p->left == run)
                        {
                            p = p->same_left_ptr = new EdgeNode(start->left, start->right, new E(*(start->edge_data_field)));
                        }
                        else
                        {
                            p = p->same_right_ptr = new EdgeNode(start->left, start->right, new E(*(start->edge_data_field)));
                        }
                    }
    
                    if (start->left == run)
                    {
                        EdgeNode *m = nullptr;
                        typename vector<VertexNode *>::size_type i = 0;
                        for ( ; i < run; ++i)
                        {
                            for (m = temp->set_of_vertex[i]->first_ptr; m != nullptr;)
                            {
                                if (m->left == i)
                                {
                                    if (m->right == start->right)
                                        break;
                                    m = m->same_left_ptr;
                                }
                                else
                                {
                                    if (m->left == start->right)
                                        break;
                                    m = m->same_right_ptr;
                                }
                            }
                            if (m != nullptr)
                                break;
                        }
    
                        if (i != run)
                        {
                            while (true)
                            {
                                if (m->right == start->right)
                                {
                                    if (m->same_right_ptr == nullptr)
                                        break;
                                    m = m->same_right_ptr;
                                }
                                else
                                {
                                    if (m->same_left_ptr == nullptr)
                                        break;
                                    m = m->same_left_ptr;
                                }
                            }
                            if (m->right == start->right)
                            {
                                m->same_right_ptr = p;
                            }
                            else
                            {
                                m->same_left_ptr = p;
                            }
                        }
                    }
                    else
                    {
                        EdgeNode *m = nullptr;
                        typename vector<VertexNode *>::size_type i = 0;
                        for (; i < run; ++i)
                        {
                            for (m = temp->set_of_vertex[i]->first_ptr; m != nullptr;)
                            {
                                if (m->left == i)
                                {
                                    if (m->right == start->left)
                                            break;
                                    m = m->same_left_ptr;
                                }
                                else
                                {
                                    if (m->left == start->left)
                                            break;
                                    m = m->same_right_ptr;
                                }
                            }
                            if (m != nullptr)
                                break;
                        }
    
                        if (i != run)
                        {
                            while (true)
                            {
                                if (m->right == start->left)
                                {
                                    if (m->same_right_ptr == nullptr)
                                        break;
                                    m = m->same_right_ptr;
                                }
                                else
                                {
                                    if (m->same_left_ptr == nullptr)
                                        break;
                                    m = m->same_left_ptr;
                                }
                            }
                            if (m->right == start->left)
                            {
                                m->same_right_ptr = p;
                            }
                            else
                            {
                                m->same_left_ptr = p;
                            }
                        }
                    }
                }
    
                if (start->left == run)
                {
                    start = start->same_left_ptr;
                }
                else
                {
                    start = start->same_right_ptr;
                }
            }
        }
        return temp;
    }
    
    template <typename V, typename E>
    bool Graph<V, E>::deleteEdge(typename vector<VertexNode *>::size_type left, typename vector<VertexNode *>::size_type right)  //从顶点left,right处搜索边节点,摘链并释放边节点
    {
        if (left >= set_of_vertex.size() || right >= set_of_vertex.size())
        {
            throw new out_of_range("无效的顶点参数\\n");
        }
    
        if (left == right)
        {
            set_of_vertex[left]->seilring = nullptr;
            delete set_of_vertex[left]->Edgeseilring;
            set_of_vertex[left]->Edgeseilring = nullptr;
            return true;
        }
    
        if (set_of_vertex[left]->first_ptr == nullptr)
            return false;
    
        EdgeNode *q = nullptr;
        EdgeNode *p = set_of_vertex[left]->first_ptr;
        for (; p != nullptr; )
        {
            if (p->left == left)
            {
                if (p->right == right)
                {
                    break;
                }
                else if (p->right < right)
                {
                    q = p;
                    p = p->same_left_ptr;
                }
                else
                {
                    return false;
                }
            }
            else
            {
                if (p->left == right)
                {
                    break;
                }
                else if (p->left < right)
                {
                    q = p;
                    p = p->same_right_ptr;
                }
                else
                {
                    return false;
                }
            }
        }
        if (p == nullptr)
        {
            return false;
        }
        else
        {
            if (q == nullptr)
            {
                if (p->left == left)
                {
                    set_of_vertex[left]->first_ptr = p->same_left_ptr;
                }
                else
                {
                    set_of_vertex[left]->first_ptr = p->same_right_ptr;
                }
            }
            else
            {
                if (q->left == left && p->left == left)
                {
                    q->same_left_ptr = p->same_left_ptr;
                }
                else if (q->left != left)
                {
                    if (p->left != left)
                    {
                        q->same_right_ptr = p->same_right_ptr;
                    }
                    else
                    {
                        q->same_right_ptr = p->same_left_ptr;
                    }
                }
                else
                {
                    q->same_left_ptr = p->same_right_ptr;
                }
            }
        }
    
        EdgeNode *q2 = nullptr;
        while (true)
        {
            if (q2 == nullptr)
            {
                if (set_of_vertex[right]->first_ptr->left == left || set_of_vertex[right]->first_ptr->right == left)
                    break;
                q2 = set_of_vertex[right]->first_ptr;
                continue;
             }
            else
            {
                if (q2->right == right)
                {
                    if (q2->same_right_ptr->left == left || q2->same_right_ptr->right == left)
                        break;
                    q2 = q2->same_right_ptr;
                }
                else
                {
                    if (q2->same_left_ptr->left == left || q2->same_left_ptr->right == left)
                        break;
                    q2 = q2->same_left_ptr;
                }
            }
        }
    
        if (q2 == nullptr)
        {
            if (p->left == left)
            {
                set_of_vertex[right]->first_ptr = p->same_right_ptr;
            }
            else
            {
                set_of_vertex[right]->first_ptr = p->same_left_ptr;
            }
        }
        else
        {
            if (q2->left == right && p->left == left)
            {
                q2->same_left_ptr = p->same_left_ptr;
            }
            else if (q2->left != right)
            {
                if (p->left != left)
                {
                    q2->same_right_ptr = p->same_right_ptr;
                }
                else
                {
                    q2->same_right_ptr = p->same_left_ptr;
                }
            }
            else
            {
                q2->same_left_ptr = p->same_right_ptr;
            }
        }
        delete p;
    }
    
    template <typename V, typename E>
    void Graph<V, E>::deleteVertex(typename vector<VertexNode *>::size_type vertex)  //分离出和vertex关联的每一边节点,从该边节点另一端顶点(和vertex相对应)出搜索边节点,摘链并释放边节点
    {                                                                                //随后从set_of_vertex中删去vertex并调整图中顶点编号和边节点中顶点编号
        if (vertex >= set_of_vertex.size())
        {
            throw new out_of_range("无效的顶点参数\\n");
        }
    
        EdgeNode *ptr = nullptr;
        while (set_of_vertex[vertex]->first_ptr != nullptr)
        {
            ptr = set_of_vertex[vertex]->first_ptr;
            if (ptr->left == vertex)
            {
                set_of_vertex[vertex]->first_ptr = ptr->same_left_ptr;
                EdgeNode *q2 = nullptr;
                while (true)
                {
                    if (q2 == nullptr)
                    {
                        if (set_of_vertex[ptr->right]->first_ptr->left == vertex || set_of_vertex[ptr->right]->first_ptr->right == vertex)
                            break;
                        q2 = set_of_vertex[ptr->right]->first_ptr;
                        continue;
                    }
                    else
                    {
                        if (q2->right == ptr->right)
                        {
                            if (q2->same_right_ptr->left == vertex || q2->same_right_ptr->right == vertex)
                                break;
                            q2 = q2->same_right_ptr;
                        }
                        else
                        {
                            if (q2->same_left_ptr->left == vertex || q2->same_left_ptr->right == vertex)
                                break;
                            q2 = q2->same_left_ptr;
                        }
                    }
                }
    
                if (q2 == nullptr)
                {
                    set_of_vertex[ptr->right]->first_ptr = ptr->same_right_ptr;
                }
                else
                {
                    if (q2->left == ptr->right)
                    {
                        q2->same_left_ptr = ptr->same_right_ptr;
                    }
                    else 
                    {
                        q2->same_right_ptr = ptr->same_right_ptr;
                    }
                }
            }
            else
            {
                set_of_vertex[vertex]->first_ptr = ptr->same_right_ptr;
                EdgeNode *q2 = nullptr;
                while (true)
                {
                    if (q2 == nullptr)
                    {
                        if (set_of_vertex[ptr->left]->first_ptr->left == vertex || set_of_vertex[ptr->left]->first_ptr->right == vertex)
                            break;
                        q2 = set_of_vertex[ptr->left]->first_ptr;
                        continue;
                    }
                    else
                    {
                        if (q2->right == ptr->left)
                        {
                            if (q2->same_right_ptr->left == vertex || q2->same_right_ptr->right == vertex)
                                break;
                            q2 = q2->same_right_ptr;
                        }
                        else
                        {
                            if (q2->same_left_ptr->left == vertex || q2->same_left_ptr->right == vertex)
                                break;
                            q2 = q2->same_left_ptr;
                        }
                    }
                }
    
                if (q2 == nullptr)
                {
                    set_of_vertex[ptr->left]->first_ptr = ptr->same_left_ptr;
                }
                else
                {
                    if (q2->left != ptr->left)
                    {
                        q2->same_right_ptr = ptr->same_left_ptr;
                    }
                    else
                    {
                        q2->same_left_ptr = ptr->same_left_ptr;
                    }
                }
            }
            delete ptr;
        }
    
        delete set_of_vertex[vertex];
        for (typename vector<VertexNode *>::size_type i = vertex; i < set_of_vertex.size() - 1; ++i)
        {
            set_of_vertex[i] = set_of_vertex[i + 1];
            --set_of_vertex[i]->number;
        }
    
        set_of_vertex.pop_back();
        set<EdgeNode *> visited;
        for (typename vector<VertexNode *>::size_type i = 0; i < set_of_vertex.size(); ++i)
        {
            for (EdgeNode *q = set_of_vertex[i]->first_ptr; q != nullptr; )
            {
                if (visited.find(q) == visited.end())
                {
                    if (q->left > vertex)
                    {
                        q->left = q->left - 1;
                    }
    
                    if (q->right > vertex)
                    {
                        q->right = q->right - 1;
                    }
                    visited.insert(q);
                }
                if (q->left == i)
                {
                    q = q->same_left_ptr;
                }
                else
                {
                    q = q->same_right_ptr;
                }
            }
        }
    }
    
    template <typename V, typename E>
    Graph<V, E> *Graph<V, E>::merge(Graph<V, E> &Bemerged, bool copyOrNot)   //合并函数比较简单,可以参考我在LALR(1)语法分析表生成程序中对十字链表的实现
    {
        Graph<V, E> *temp1 = nullptr;
        typename vector<VertexNode *>::size_type Ca1 = 0;
        if (copyOrNot)
        {
            temp1 = copy();
            Ca1 = temp1->set_of_vertex.size();
        }
        else
        {
            Ca1 = set_of_vertex.size();
        }
    
        {
            Graph<V, E> *temp2 = Bemerged.copy();
            for (typename vector<VertexNode *>::size_type p = 0; p < temp2->set_of_vertex.size(); ++p)
            {
                if (copyOrNot)
                {
                    temp1->set_of_vertex.push_back(temp2->set_of_vertex[p]);
                }
                else
                {
                    set_of_vertex.push_back(temp2->set_of_vertex[p]);
                }
            }
            while (temp2->set_of_vertex.empty() == false)
            {
                temp2->set_of_vertex.pop_back();
            }
            delete temp2;
        }
    
        set<EdgeNode *> visited;
        for (typename vector<VertexNode *>::size_type p = Ca1; ; ++p)
        {
            EdgeNode *q = nullptr;
            if (copyOrNot)
            {
                if (p >= temp1->set_of_vertex.size())
                    break;
                temp1->set_of_vertex[p]->number = p;
                q = temp1->set_of_vertex[p]->first_ptr;
            }
            else
            {
                if (p >= set_of_vertex.size())
                    break;
                set_of_vertex[p]->number = p;
                q = set_of_vertex[p]->first_ptr;
            }
    
            for (; q != nullptr; )
            {
                if (visited.find(q) == visited.end())
                {
                    q->left = q->left + Ca1;
                    q->right = q->right + Ca1;
                    visited.insert(q);
                }
                if (q->left == p)
                {
                    q = q->same_left_ptr;
                }
                else
                {
                    q = q->same_right_ptr;
                }
            }
        }
    
        if (copyOrNot)
          return temp1;
        else
          return nullptr;
    
    }
    
    Graph<size_t, size_t> *convertToGraph(vector<vector<int>> &adjacency_matrix)  //由邻接矩阵构造基于邻接多重表的有向图并返回该图的指针
    {
        vector<vector<int>>::size_type size = adjacency_matrix.size();
        Graph<size_t, size_t> *temp = new Graph<size_t, size_t>();
        for (size_t i = 0; i < size; ++i)
        {
            temp->addVertex(new size_t(i));
        }
        for (size_t i = 0; i < size; ++i)
        {
            for (size_t j = i; j < size; ++j)
            {
                if (adjacency_matrix[i][j] == 1)
                {
                    temp->addEdge(i, j, new size_t(j));
                }
            }
        }
        return temp;
    }
    
    vector<vector<int>> *convertToAdjaMatrix(Graph<size_t, size_t> *undigraph)  //由基于邻接多重表无向图构造邻接矩阵并返回邻接矩阵
    {
        vector<vector<int>> *temp = new vector<vector<int>>(undigraph->getVertexNum(), vector<int>(undigraph->getVertexNum(), 0));
        for (size_t i = 0; i < undigraph->set_of_vertex.size(); ++i)
        {
            if (undigraph->set_of_vertex[i]->seilring != nullptr)
                (*temp)[i][i] = 1;
            for (Graph<size_t, size_t>::EdgeNode *p = undigraph->set_of_vertex[i]->first_ptr; p != nullptr;)
            {   
                if (p->left == i)
                {
                    (*temp)[p->left][p->right] = 1;
                    p = p->same_left_ptr;
                }
                else
                {
                    (*temp)[p->right][p->left] = 1;
                    p = p->same_right_ptr;
                }
            }
        }
        delete undigraph;
        return temp;
    }
    
    int main()
    {
        vector<vector<int>> test = { {1, 0, 1, 1, 0, 1, 0}, {0, 1, 0, 1, 1, 0, 1}, {1, 0, 0, 0, 1, 1, 1}, {1, 1, 0, 1, 1, 0, 0}, {0, 1, 1, 1, 0, 1, 1}, {1, 0, 1, 0, 1, 0, 1}, {0, 1, 1, 0, 1, 1, 0} };  //测试用邻接矩阵
        vector<vector<int>> *test2 = convertToAdjaMatrix(convertToGraph(test));   //测试addEdge函数
        for (const auto &i : *test2)
        {
            for (const auto &j : i)
            {
                cout << j << " ";
            }
            cout << endl;
        }
        delete test2;
        
        /*Graph<size_t, size_t> *temp = convertToGraph(test);     //测试copy函数
        Graph<size_t, size_t> *temp2 = temp->copy();
        vector<vector<int>> *test2 = convertToAdjaMatrix(temp2);   
        for (const auto &i : *test2)
        {
            for (const auto &j : i)
            {
                cout << j << " ";
            }
            cout << endl;
        }
        */
        /*Graph<size_t, size_t> *temp = convertToGraph(test);     //测试deleteEdge函数
        for (size_t i = 0; i < test.size(); ++i)
        {
            for (size_t j = i; j < test.size(); ++j)    
            {
                if (test[i][j] == 1)
                {
                    cout << "删除边("<<i<<","<< j << ")" << endl;
                    temp->deleteEdge(i, j);
                }
            }
        }
        vector<vector<int>> *test2 = convertToAdjaMatrix(temp);
        for (const auto &i : *test2)
        {
            for (const auto &j : i)
            {
                cout << j << " ";
            }
            cout << endl;
        }
        */
        
        /*Graph<size_t, size_t> *temp = convertToGraph(test);      //测试deleteVertex函数
        size_t num = temp->getVertexNum();
        for (size_t i = 0; i < num; ++i)
        {
            cout << "删除顶点" << i << endl;       
            temp->deleteVertex(0);
        }
        vector<vector<int>> *test2 = convertToAdjaMatrix(temp);
        if (test2->empty())
        {
            cout << "图为空" << endl;
        }
        else
        {
            cout << "错误!" << endl;
        }
        */
        /*Graph<size_t, size_t> *temp1 = convertToGraph(test);        //测试merge函数
        Graph<size_t, size_t> *temp2 = convertToGraph(test);
        temp1->merge(*temp2, false);
        vector<vector<int>> *test2 = convertToAdjaMatrix(temp1);
        for (const auto &i : *test2)
        {
            for (const auto &j : i)
            {
                cout << j << " ";
            }
            cout << endl;
        }
        */
        return 0;
    }

     2018.11.12日更新 


    优化了deleteEdge函数第一个for循环,搜索待删除边时搜索的边链表上每一个边节点的与边链表上所有边节点共同关联的顶点对应的边节点一端相对的一端的顶点的编号严格递增,所以如果发现被删除边的前述一端的顶点编号夹在边链表上俩边节点前述一端的顶点编号之间或小于边链表上前述一端的顶点编号最小的边节点的顶点编号,则函数直接退出,没有必要继续搜索

    更多相关内容
  • 学习数据结构和离散数学的同学, 这是我的理解和相关代码
  • 邻接多重表

    千次阅读 多人点赞 2020-04-07 18:41:40
    邻接多重表因此而演变过来的。 邻接多重表中,无向图中的每一个顶点分配一个顶点结点,所有顶点结点构成一个顶点数组adjmultiList[num]。另外每条边也分配一个边结点。 顶点结构如下所示: 其中data用...

    基本概念

    邻接表虽然已经能够很好地表示无向图了,但是无向图访问或者删除一条边(Vi,Vj)时需要同时访问两个链表i和j并分别找到对应的边结点,这给针对图的边的操作(标记或删除)带来不便利。邻接多重表因此而演变过来的。

    邻接多重表中,无向图中的每一个顶点分配一个顶点结点,所有顶点结点构成一个顶点数组adjmultiList[num]。另外每条边也分配一个边结点。

    顶点结构如下所示:
    在这里插入图片描述
    其中data用来记录顶点的信息,firstEdge用来表示依附于该顶点的第一条边。

    顶点数组如下所示:
    在这里插入图片描述
    边结点结构如下所示:
    在这里插入图片描述
    其中mark表示标志位,用于标记该边是否已经被访问过;iVex和jVex表示该边的两个顶点在顶点数组adjmultiList[num]中的位置;iLink和jLink分别表示指向依附于顶点iVex和jVex下一条边的指针。

    从上面的顶点和边的结构来看,邻接多重表和邻接表的主要区别在于:邻接多重表中的边结点同时被链入对应边顶点的链表内(2条);邻接表中的边用两个表结点表示。另外,邻接多重表中的边结点就表示一条边,比较容易理解。

    举个例子。某无向图如下图所示:
    在这里插入图片描述
    当采用邻接表表示该无向图时,其邻接表入下图所示:
    在这里插入图片描述
    如上图所示,图中黄色标记的结点表示A-D之间的边,在邻接表中一条边需要两个结点表示。因此如果对于边的操作(标记或者删除)则需要访问两条链表。

    当采用邻接多重表表示该无向图时,其邻接多重表入下图所示:
    在这里插入图片描述
    如上图所示,结点A-D 之间的边,在邻接多重表中只需要一个边结点既可以表示。另外,在该结构中,每个边结点被链入了两个不同的链表。其中A-D之间的边被链入了红色和绿色标记的链表中。如果需要访问一条边,则可以从该边的两个顶点结点中的任何一个出发,遍历依附于该顶点的边构成的链表即可。如果需要删除一条边,则只需要删除一个边结点,但是需要修改这条边依附的两个顶点所对应的链表。另外,需要注意的是,在无向图中,边结点中的iVex和jVex链域与该边所依附的顶点无关,即iVex=0,jVex=3和iVex=3,jVex=0这都表示同一条边A-D,因此这给链表的指针修改带来一定的麻烦。

    基本操作

    1.建立无向图的临界多重表
    输入ABCDE五个顶点V={A,B,C,D,E},然后输入边E={(A,B),(B,C),(B,E),(C,D),(C,E),(D,A)},建立如下无向图:
    在这里插入图片描述
    代码如下:

    Status createAMLGraph(AMLGraph &G, int vexNum){
    	G.vexNum = vexNum;
    	G.edgeNum = 0;
    	for(int i = 0; i< G.vexNum; i++){
    		cin>>G.adjmultiList[i].data;
    		G.adjmultiList[i].firstEdge = NULL;
    	}
     
    	cout<<"Try to input arcs info"<<endl;
    	while(1){
    		char SWITCH;
    		cout<<"are you going to add a edge into AMLGraph?(y?n)"<<endl;
    		
    		cin>>SWITCH;
    		if(SWITCH == 'y'){
    			cout<<"please input two nodes of "<<G.edgeNum+1<<"-th arc"<<endl;
     
    			vertexNode node1, node2;
    			cin>>node1.data>>node2.data;
    			insertEdge(G, node1, node2);
    			G.edgeNum++;
    		}
    		else
    			break;
    	}
    	return 1;
    }
    

    2.打印无向图的临界多重表
    在这里插入图片描述
    代码如下:

    Status printAMLGraph(AMLGraph &G){
    	for(int i = 0; i<G.vexNum; i++){
    		cout<<i<<" "<<G.adjmultiList[i].data;
    		edgeNode *edge = G.adjmultiList[i].firstEdge;
     
    		while(edge){
    			cout<<"-->|"<<edge->iVex<<"|"<<edge->jVex<<"|";
    			if(edge->iVex == i){
    				edge = edge->iLink;
    			}
    			else{
    				edge = edge->jLink;
    			}
    		}
    		cout<<"-->NULL"<<endl;
    	}
    	return 1;
    }
    

    3.向无向图中添加结点
    向无向图中添加结点F。
    在这里插入图片描述
    代码如下:

    Status insertNode(AMLGraph &G, vertexNode node){
    	G.adjmultiList[G.vexNum].data = node.data;
    	G.adjmultiList[G.vexNum].firstEdge = NULL;
    	G.vexNum++;
    	return 1;
    }
    

    4.向无向图中添加边
    向无向图中添加A-C。
    在这里插入图片描述
    代码如下:

    void insertEdgeAction(AMLGraph &G, int index1, int index2){
    	edgeNode *p, *q;
    	edgeNode *edge = new edgeNode[1];
    	
    	edge->iVex = index1;
    	edge->jVex = index2;
     
    	p = G.adjmultiList[index1].firstEdge;//相当于链表的插入
    	if(!p){
    		G.adjmultiList[index1].firstEdge = edge;
    		edge->iLink = NULL;
    	}
    	else{
    		G.adjmultiList[index1].firstEdge = edge;
     
    		edge->iLink = p;
    	}
     
    	q = G.adjmultiList[index2].firstEdge;//相当于链表的插入
    	if(!q){
    		G.adjmultiList[index2].firstEdge = edge;
    		edge->jLink = NULL;
    	}
    	else{
    		G.adjmultiList[index2].firstEdge = edge;
    		edge->jLink = q;
    	}
    }
     
    Status insertEdge(AMLGraph &G, vertexNode node1, vertexNode node2){
    	int index1 = locateNode(G, node1);//i和j表示AdjList[MAX_VERTEX_NUM]中的位置
    	int index2 = locateNode(G, node2);
    	if(index1<0 || index2<0) exit(-1);
    	
    	insertEdgeAction(G, index1, index2);
     
    	return 1;
    }
    

    5.删除无向图中的边
    删除无向图中的边B-C。
    在这里插入图片描述
    代码如下:

    Status deleteEdgeAction(AMLGraph &G, int index1, int index2){
    	edgeNode *curEdge = G.adjmultiList[index1].firstEdge;
    	edgeNode *preEdge = curEdge;
    	int count = 0;
     
    	if(!curEdge) return 1;
    	else{
    		while(curEdge){
    			count++;
    			if((curEdge->iVex == index1&&curEdge->jVex == index2)||(curEdge->iVex == index2&&curEdge->jVex == index1)){
    				break;
    			}
    			preEdge = curEdge;
    			if(curEdge->iVex ==index1)
    				curEdge = curEdge->iLink;
    			else
    				curEdge = curEdge->jLink;
    		}
    	}
     
    	if(!curEdge)
    		return 1;
    	else if(count<=1){
    		if(preEdge->iVex == index1)
    			G.adjmultiList[index1].firstEdge = preEdge->iLink;
    		else 
    			G.adjmultiList[index1].firstEdge = preEdge->jLink;
    	}
    	else{
    		if(preEdge->iVex == index1){ 
    			if (curEdge->iVex == index1)
    				preEdge->iLink = curEdge->iLink;
    			else
    				preEdge->iLink = curEdge->jLink;
    		}
    		else{
    			if (curEdge->iVex == index1)
    				preEdge->jLink = curEdge->iLink;
    			else
    				preEdge->jLink = curEdge->jLink;
    		}
    	}
    	return 1;
    }
     
    Status deleteEdge(AMLGraph &G, vertexNode node1, vertexNode node2){
    	int index1 = locateNode(G, node1);
    	int index2 = locateNode(G, node2);
     
    	deleteEdgeAction(G, index1, index2);
    	deleteEdgeAction(G, index2, index1);
     
    	return 1;
    }
    

    6.删除无向图中的顶点
    删除结点C。
    在这里插入图片描述
    代码如下:

    Status deleteNode(AMLGraph &G, vertexNode node){
    	//删除结点时,结点不真实删除而只是删除结点相关的边以及赋值该结点的data为特殊值‘0’
    	int index = locateNode(G, node);
     
    	for(int i = 0; i<G.vexNum; i++){
    		if(i == index) continue;
    		else{
    			deleteEdge(G, G.adjmultiList[index], G.adjmultiList[i]);
    		}
    	}
    	G.adjmultiList[index].firstEdge = NULL;
    	G.adjmultiList[index].data = '0';
    	return 1;
    }
    

    7.全部代码

    // 邻接多重表.cpp : Defines the entry point for the console application.
    //
     
    #include "stdafx.h"
    #include <iostream>
     
    using namespace std;
     
    #define MAX_VERTEX_NUM 20
     
    typedef int infoType;
    typedef char vertexType;
    typedef int Status;
     
    typedef struct edgeNode{
    	int iVex, jVex;
    	struct edgeNode *iLink, *jLink;
    	infoType *info;
    }edgeNode;
     
    typedef struct vertexNode{
    	vertexType data;
    	edgeNode *firstEdge;
    }vertexNode;
     
    typedef struct{
    	vertexNode adjmultiList[MAX_VERTEX_NUM];
    	int vexNum, edgeNum;
    }AMLGraph;
     
    int locateNode(AMLGraph &G, vertexNode node){
    	for(int i=0; i<G.vexNum;i++){
    		if(node.data == G.adjmultiList[i].data)
    			return i;
    	}
    	return -1;
    }
     
    Status insertEdge(AMLGraph &G, vertexNode node1, vertexNode node2);
     
    Status createAMLGraph(AMLGraph &G, int vexNum){
    	G.vexNum = vexNum;
    	G.edgeNum = 0;
    	for(int i = 0; i< G.vexNum; i++){
    		cin>>G.adjmultiList[i].data;
    		G.adjmultiList[i].firstEdge = NULL;
    	}
     
    	cout<<"Try to input arcs info"<<endl;
    	while(1){
    		char SWITCH;
    		cout<<"are you going to add a edge into AMLGraph?(y?n)"<<endl;
    		
    		cin>>SWITCH;
    		if(SWITCH == 'y'){
    			cout<<"please input two nodes of "<<G.edgeNum+1<<"-th arc"<<endl;
     
    			vertexNode node1, node2;
    			cin>>node1.data>>node2.data;
    			insertEdge(G, node1, node2);
    			G.edgeNum++;
    		}
    		else
    			break;
    	}
    	return 1;
    }
     
    void insertEdgeAction(AMLGraph &G, int index1, int index2){
    	edgeNode *p, *q;
    	edgeNode *edge = new edgeNode[1];
    	
    	edge->iVex = index1;
    	edge->jVex = index2;
     
    	p = G.adjmultiList[index1].firstEdge;//相当于链表的插入
    	if(!p){
    		G.adjmultiList[index1].firstEdge = edge;
    		edge->iLink = NULL;
    	}
    	else{
    		G.adjmultiList[index1].firstEdge = edge;
     
    		edge->iLink = p;
    	}
     
    	q = G.adjmultiList[index2].firstEdge;//相当于链表的插入
    	if(!q){
    		G.adjmultiList[index2].firstEdge = edge;
    		edge->jLink = NULL;
    	}
    	else{
    		G.adjmultiList[index2].firstEdge = edge;
    		edge->jLink = q;
    	}
    }
     
    Status insertEdge(AMLGraph &G, vertexNode node1, vertexNode node2){
    	int index1 = locateNode(G, node1);//i和j表示AdjList[MAX_VERTEX_NUM]中的位置
    	int index2 = locateNode(G, node2);
    	if(index1<0 || index2<0) exit(-1);
    	
    	insertEdgeAction(G, index1, index2);
     
    	return 1;
    }
     
    Status printAMLGraph(AMLGraph &G){
    	for(int i = 0; i<G.vexNum; i++){
    		cout<<i<<" "<<G.adjmultiList[i].data;
    		edgeNode *edge = G.adjmultiList[i].firstEdge;
     
    		while(edge){
    			cout<<"-->|"<<edge->iVex<<"|"<<edge->jVex<<"|";
    			if(edge->iVex == i){
    				edge = edge->iLink;
    			}
    			else{
    				edge = edge->jLink;
    			}
    		}
    		cout<<"-->NULL"<<endl;
    	}
    	return 1;
    }
     
    Status insertNode(AMLGraph &G, vertexNode node){
    	G.adjmultiList[G.vexNum].data = node.data;
    	G.adjmultiList[G.vexNum].firstEdge = NULL;
    	G.vexNum++;
    	return 1;
    }
     
    Status deleteEdgeAction(AMLGraph &G, int index1, int index2){
    	edgeNode *curEdge = G.adjmultiList[index1].firstEdge;
    	edgeNode *preEdge = curEdge;
    	int count = 0;
     
    	if(!curEdge) return 1;
    	else{
    		while(curEdge){
    			count++;
    			if((curEdge->iVex == index1&&curEdge->jVex == index2)||(curEdge->iVex == index2&&curEdge->jVex == index1)){
    				break;
    			}
    			preEdge = curEdge;
    			if(curEdge->iVex ==index1)
    				curEdge = curEdge->iLink;
    			else
    				curEdge = curEdge->jLink;
    		}
    	}
     
    	if(!curEdge)
    		return 1;
    	else if(count<=1){
    		if(preEdge->iVex == index1)
    			G.adjmultiList[index1].firstEdge = preEdge->iLink;
    		else 
    			G.adjmultiList[index1].firstEdge = preEdge->jLink;
    	}
    	else{
    		if(preEdge->iVex == index1){ 
    			if (curEdge->iVex == index1)
    				preEdge->iLink = curEdge->iLink;
    			else
    				preEdge->iLink = curEdge->jLink;
    		}
    		else{
    			if (curEdge->iVex == index1)
    				preEdge->jLink = curEdge->iLink;
    			else
    				preEdge->jLink = curEdge->jLink;
    		}
    	}
    	return 1;
    }
     
    Status deleteEdge(AMLGraph &G, vertexNode node1, vertexNode node2){
    	int index1 = locateNode(G, node1);
    	int index2 = locateNode(G, node2);
     
    	deleteEdgeAction(G, index1, index2);
    	deleteEdgeAction(G, index2, index1);
     
    	return 1;
    }
     
    Status deleteNode(AMLGraph &G, vertexNode node){
    	//删除结点时,结点不真实删除而只是删除结点相关的边以及赋值该结点的data为特殊值‘0’
    	int index = locateNode(G, node);
     
    	for(int i = 0; i<G.vexNum; i++){
    		if(i == index) continue;
    		else{
    			deleteEdge(G, G.adjmultiList[index], G.adjmultiList[i]);
    		}
    	}
    	G.adjmultiList[index].firstEdge = NULL;
    	G.adjmultiList[index].data = '0';
    	return 1;
    }
     
    int _tmain(int argc, _TCHAR* argv[])
    {
    	int vexNum = 5;
    	AMLGraph G;
    	cout<<"Try to create a adjacence multilist of a graph ..."<<endl;
    	createAMLGraph(G, vexNum);
    	printAMLGraph(G);
     
    	cout<<"Try to insert a node into the graph..."<<endl;
    	vertexNode node;
    	cout<<"   please input the data of the node to insert:"<<endl;
    	cin>>node.data;
    	insertNode(G, node);
    	printAMLGraph(G);
     
    	cout<<"Try to insert a edge into the graph..."<<endl;
    	vertexNode node1, node2;
    	cout<<"   please choose two node:"<<endl;
    	cin>>node1.data>>node2.data;
    	insertEdge(G, node1, node2);
    	printAMLGraph(G);
     
    	cout<<"Try to delete the edge between two nodes..."<<endl;
    	vertexNode node3, node4;
    	cout<<"   please choose a edge with specifing two nodes:"<<endl;
    	cin>>node3.data>>node4.data;
    	deleteEdge(G, node3, node4);
    	printAMLGraph(G);
     
    	cout<<"Try to delete a node of the graph..."<<endl;
    	vertexNode node5;
    	cout<<"   please choose a node:"<<endl;
    	cin>>node5.data;
    	deleteNode(G, node5);
    	printAMLGraph(G);
     
    	system("pause");
    	return 0;
    }
    
    展开全文
  • 邻接表 使用邻接表存储图时,对于图中的每一个顶点和它相关的邻接点,都存储到一个链表中。每个链表都配有头结点,头结点的数据域不为NULL,而是用于存储顶点本身的数据;后续链表中的各个结点存储的是当前顶点的...

    邻接表

    使用邻接表存储图时,对于图中的每一个顶点和它相关的邻接点,都存储到一个链表中。每个链表都配有头结点,头结点的数据域不为NULL,而是用于存储顶点本身的数据;后续链表中的各个结点存储的是当前顶点的所有邻接点。

    所以,采用邻接表存储图时,有多少顶点就会构建多少个链表,为了便于管理这些链表,常用的方法是将所有链表的链表头按照一定的顺序存储在一个数组中(也可以用链表串起来)。

    在邻接表中,每个链表的头结点和其它结点的组成成分有略微的不同。头结点需要存储每个顶点的数据和指向下一个结点的指针,由两部分构成:而在存储邻接点时,由于各个顶点的数据都存储在数组中,所以每个邻接点只需要存储自己在数组中的位置下标即可。另外还需要一个指向下一个结点的指针。除此之外,如果存储的是网,还需要一个记录权值的信息域。所以表头结点和其它结点的构造分别为:
    在这里插入图片描述
    图1 表结点结构
    info 域对于无向图来说,本身不具备权值和其它相关信息,就可以根据需要将之删除。

    例如,当存储图 2(A)所示的有向图时,构建的邻接表如图 2 (B)所示:
    在这里插入图片描述
    图2 有向图和对应的邻接表

    邻接表存储图的存储结构为:

    #define  MAX_VERTEX_NUM 20//最大顶点个数
    #define  VertexType int//顶点数据的类型
    #define  InfoType int//图中弧或者边包含的信息的类型
    typedef struct ArcNode{
        int adjvex;//邻接点在数组中的位置下标
        struct ArcNode * nextarc;//指向下一个邻接点的指针
        InfoType * info;//信息域
    }ArcNode;
    
    typedef struct VNode{
        VertexType data;//顶点的数据域
        ArcNode * firstarc;//指向邻接点的指针
    }VNode,AdjList[MAX_VERTEX_NUM];//存储各链表头结点的数组
    
    typedef struct {
        AdjList vertices;//图中顶点及各邻接点数组
        int vexnum,arcnum;//记录图中顶点数和边或弧数
        int kind;//记录图的种类
    }ALGraph;
    

    邻接表计算顶点的度

    使用邻接表存储无向图时,各顶点的度为各自链表中包含的结点数;存储有向图时,各自链表中具备的结点数为该顶点的出度。求入度时,需要遍历整个邻接表中的结点,统计数据域和该顶点数据域相同的结点的个数,即为顶点的入度。

    对于求有向图中某结点的入度,还有一种方法就是再建立一个逆邻接表,此表只用于存储图中每个指向该顶点的所有的顶点在数组中的位置下标。例如,构建图 2(A)的逆邻接表,结果为:
    在这里插入图片描述
    图3 逆邻接表
    对于具有 n 个顶点和 e 条边的无向图,邻接表中需要存储 n 个头结点和 2e 个表结点。在图中边或者弧稀疏的时候,使用邻接表要比前一节介绍的邻接矩阵更加节省空间。

    十字链表

    十字链表存储的对象是有向图或者有向网。同邻接表相同的是,图(网)中每个顶点各自构成一个链表,为链表的首元结点。同时,对于有向图(网)中的弧来说,有弧头和弧尾。一个顶点所有的弧头的数量即为该顶点的入度,弧尾的数量即为该顶点的出度。每个顶点构成的链表中,以该顶点作为弧头的弧单独构成一个链表,以该顶点作为弧尾的弧也单独构成一个链表,两个链表的表头都为该顶点构成的头结点。

    这样,由每个顶点构建的链表按照一定的顺序存储在数组中,就构成了十字链表。

    所以,十字链表中由两种结点构成:顶点结点和弧结点。各自的结构构成如下图所示:
    在这里插入图片描述
    图4 十字链表的结点构成
    弧结点中, tailvex 和 headvex 分别存储的是弧尾和弧头对应的顶点在数组中的位置下标; hlink 和 tlink 为指针域,分别指向弧头相同的下一个弧和弧尾相同的下一个弧; info 为指针域,存储的是该弧具有的相关信息,例如权值等。

    顶点结点中,data 域存储该顶点含有的数据; firstin 和 firstout 为两个指针域,分别指向以该顶点为弧头和弧尾的首个弧结点。
    在这里插入图片描述
    图5 有向图及其十字链表

    十字链表存储图的存储结构为:

    #define  MAX_VERTEX_NUM 20
    #define  InfoType int//图中弧包含信息的数据类型
    #define  VertexType int
    typedef struct ArcBox{
        int tailvex,headvex;//弧尾、弧头对应顶点在数组中的位置下标
        struct ArcBox *hlik,*tlink;//分别指向弧头相同和弧尾相同的下一个弧
        InfoType *info;//存储弧相关信息的指针
    }ArcBox;
    typedef struct VexNode{
        VertexType data;//顶点的数据域
        ArcBox *firstin,*firstout;//指向以该顶点为弧头和弧尾的链表首个结点
    }VexNode;
    typedef struct {
        VexNode xlist[MAX_VERTEX_NUM];//存储顶点的一维数组
        int vexnum,arcnum;//记录图的顶点数和弧数
    }OLGraph;
    

    十字链表计算顶点的度

    采用十字链表表示的有向图,在计算某顶点的出度时,为 firstout 域链表中结点的个数;入度为 firstin 域链表中结点的个数。

    其他请见:
    链接: link.

    邻接多重表

    使用邻接表解决在无向图中删除某两个结点之间的边的操作时,由于表示边的结点分别处在两个顶点为头结点的链表中,所以需要都找到并删除,操作比较麻烦。处理类似这种操作,使用邻接多重表会更合适。

    邻接多重表可以看做是邻接表和十字链表的结合体。和十字链表唯一不同的是顶点结点和表结点的结构组成不同;同邻接表相比,不同的地方在于邻接表表示无向图中每个边都用两个结点,分别在两个不同链表中;而邻接多重表表示无向图中的每个边只用一个结点。
    邻接多重表的顶点结点和表结点的构成如图 5 所示:
    在这里插入图片描述
    图6 邻接多重表

    表结点构成:
    –mark 为标志域,作用是标记某结点是否已经被操作过,例如在遍历各结点时, mark 域为 0 表示还未遍历;mark 域为 1 表示该结点遍历过;
    –ivex 和 jvex 分别表示该结点表示的边两端的顶点在数组中的位置下标; ilink 指向下一条与 ivex 相关的边;
    –jlink 指向下一条与 jvex 相关的边;
    –info 指向与该边相关的信息。

    顶点结点构成:
    –data 为该顶点的数据域;
    –firstedge 为指向第一条跟该顶点有关系的边。

    在这里插入图片描述
    图7 无向图及对应的邻接多重表

    邻接多重表的存储结构用代码表示为:

    #define MAX_VERTEX_NUM 20                   //图中顶点的最大个数
    #define InfoType int                        //边含有的信息域的数据类型
    #define VertexType int                      //图顶点的数据类型
    typedef enum {unvisited,visited}VisitIf;    //边标志域
    typedef struct EBox{
        VisitIf mark;                           //标志域
        int ivex,jvex;                          //边两边顶点在数组中的位置下标
        struct EBox * ilink,*jlink;             //分别指向与ivex、jvex相关的下一个边
        InfoType *info;                         //边包含的其它的信息域的指针
    }EBox;
    typedef struct VexBox{
        VertexType data;                        //顶点数据域
        EBox * firstedge;                       //顶点相关的第一条边的指针域
    }VexBox;
    typedef struct {
        VexBox adjmulist[MAX_VERTEX_NUM];//存储图中顶点的数组
        int vexnum,degenum;//记录途中顶点个数和边个数的变量
    }AMLGraph;
    

    其他请见:
    链接: link.

    总结

    1.邻接表适用于所有的图结构,无论是有向图(网)还是无向图(网),存储结构较为简单,但是在存储一些问题时,例如计算某顶点的度,需要通过遍历的方式自己求得。

    2.十字链表适用于有向图(网)的存储,使用该方式存储的有向图,可以很容易计算出顶点的出度和入度,只需要知道对应链表中的结点个数即可。

    3.邻接多重表适用于无向图(网)的存储,该方式避免了使用邻接表存储无向图时出现的存储空间浪费的现象,同时相比邻接表存储无向图,更方便了某些边操作(遍历、删除等)的实现。

    展开全文
  • 图存储之邻接多重表

    2020-10-17 15:28:20
    邻接多重表同十字链表类似,在邻接多重表中,每条边用一个结点表示,结构如下: 其中,mark为标志域,可用以标记该条边是否被搜索过;ivex和jvex为该边依附的两个顶点在图中的位置;ilink指向下一条依附于顶点...

    一 概述

    邻接多重表是无向图的另一种链式存储结构。在邻接表中,容易求得顶点和边的各种信息,但在邻接表中求两个顶点之间是否存在边而对边执行删除等操作时,需要分别在两个顶点的边表中遍历,效率较低。

    二 邻接多重表

    邻接多重表同十字链表类似,在邻接多重表中,每条边用一个结点表示,结构如下:

    其中,mark为标志域,可用以标记该条边是否被搜索过;ivex和jvex为该边依附的两个顶点在图中的位置;ilink指向下一条依附于顶点ivex的边;jlink指向下一条依附于顶点jvex的边,info为指向和边相关的各种信息的指针域。

    每个顶点也用一个结点表示,它包含两个域,分别为存储该顶点相关信息的data域和指示第一条依附于该顶点的边的firstedge域。

    在邻接多重表中,所有依附于同一顶点的边串联在同一个链表中,由于每条边依附于两个顶点,由于每条边依附于两个顶点,因此每个边结点同时链接在两个链表中。对无向图而言,其邻接多重表和邻接表的差别仅在于,同一条边在邻接表中用两个结点表示,而在邻接多重表中只有一个结点。

    无向图的邻接多重表表示法,邻接多重表的各种基本操作的实现和邻接表的类似。

    展开全文
  • 十字链 十字链是有向图的一种链式存储结构。在十字链表中,对应于有向图中的每条弧有一个结点,对应于每个顶点也有一个结点。 弧结点中有5个域:尾域(tailvex)和头域(headvex)分别指示弧尾和弧头这两个顶点在图...
  • 数据结构——邻接多重表(C语言实现)

    千次阅读 热门讨论 2020-11-08 13:33:12
    小弟最近在学数据结构,昨天自己实现了一下邻接多重表,写之前是有一点小问题的,本来想找一位大佬写的程序参考一下,但是并么有找到令人满意的,所以只能自己独立写了。小弟写这个程序全程只参考了课本中对邻接多重...
  •   由主函数中图的顶点数组和邻接矩阵,给出图的已知信息,据此建立无向图的邻接多重表。   因为对于无向图的邻接链表来说,一条边对应的顶点间的连接关系会在两个顶点的邻接链表里各出现一次,造成存储上的资源...
  • c++实现图的邻接多重表
  • 邻接表实现相对简单 // 邻接表实现(adjacency list) // B----A // | | // D----C public class AdjList { private VexNode[] vexs;// 顶点数组 // 顶点 private class VexNode{ int data;// 顶点值 Edge ...
  • 十字链表与邻接多重表的画法

    千次阅读 2021-11-06 13:32:08
    近期一直在构建算法技能树的数据,借此机会,重新把数据结构与算法又温习了一遍,在看到十字链表与邻接多重表的画法时,十分的不理解,在C站找资料时,发现也看不懂,于是上B站,终于明白了十字链表与多重邻接表的...
  • } } } void InputGraph(AMLGraph G)//邻接多重表的输出 { int i,j;//记录次数 EBox *p1,*p2;//用于遍历链表 printf("邻接多重表为:\n"); //为了能验证创建的图是否正确 for(i=0;i;i++)//利用循环输出 { ...
  • 上一节介绍了如何使用顺序存储...使用链式存储结构表示图的常用方法有 3 种:邻接表、邻接多重表和十字链表。 邻接的意思是顶点之间有边或者弧存在,通过当前顶点,可以直接找到下一个顶点。 邻接表 使用邻接表存...
  • 邻接多重表 1. 邻接多重表图文解析 邻接多重表是无向图的一种存储结构 因为不考虑边的方向,所以和十字链表相比较,顶点结点只需要一个指针域指向所连接的边结点即可 邻接多重表的边结点和顶点结点如下图: 由...
  • 邻接多重表 顶点结构和边表结构 无向图的邻接多重表 无向图的邻接多重表存储表示 #define MAX_VERTEX_NUM 20 typedef enmu{unvisited,visited} VisitIf; //枚举类型,将变量限定在一定范围内 //链表中的边结点 ...
  • 7.2 图的存储结构7.2.3 邻接多重表(多重邻接表)Adjacency Multilist邻接多重表的类定义邻接多重表的顶点结点类模板邻接多重表的边结点类模板邻接多重表的类模板邻接多重表与邻接表的对比 7.2.3 邻接多重表(多重...
  • 邻接多重表 邻接多重表是无向图的另一种存储链式存储结构。 存储结构 顶点 data:存储和顶点相关的信息 firstedge:第一条依附于该顶点的边 边 ivex:该边依附的顶点 jvex:该边依附的顶点 ilink:指向下一条依附于 ...
  • 十字链表:有向图 邻接多重表:无向图
  • 7.2.4 邻接多重表

    2021-01-28 00:44:02
    邻接多重表是对于无向图而言, 十字链表对于有向图而言。 邻接多重表也是一种链式存储结构。
  • 邻接多重表创建图,Floyd算法求最短路径
  • 无向图的邻接多重表(Adjacency Multilist)表示
  • 文章目录一:邻接矩阵——适合存储稠密图(1)邻接矩阵定义(2)代码二:邻接表 一:邻接矩阵——适合存储稠密图 (1)邻接矩阵定义 图的邻接矩阵(Adjacency Matrix):采用两个数组表示图。一个一维数组存储图中顶点...
  • 图的存储结构:邻接多重表邻接多重表的定义:邻接多重表的代码定义:十字链表与邻接多重表的对比 邻接多重表的定义: 顶点表节点: 1、data:顶点数据域 2、firstedge:边表节点的头指针 边表节点: 1、ivex:该边的...
  • 【数据结构】邻接多重表

    万次阅读 多人点赞 2017-05-06 11:57:32
    介绍了无向图的另一种链式存储方式--邻接多重表
  • 二、无向图的存储结构邻接多重表法 2.1 邻接多重表法定义 顶点结构定义 data:数据域,存放顶点数据 firstedge:第一条边的指针 边表节点结构定义 ivex:边的两个顶点其中一个顶点 i 的序号 ilink:边的两个顶点...
  • 邻接多重表,是在邻接表的基础上改进的,因为十字链表是适合有向图的,所以需要一个数据结构适合无向图,也就是邻接多重表。 我们发现,在无向图邻接表中,边节点存在冗余,也就是说,我们在无向图的邻接表中能找到...
  • ps: 1.部分内容我设置了隐藏,...这次的内容主要难点在删除吧,因为邻接多重表的结构,每个结点都有两个指针指向他 所以要分别找到这两个结点,让他们的后续指针跳过删除的结点 下面直接上代码吧 #include<stdio...
  • 邻接矩阵、邻接表、十字链表、邻接多重表是图的四种常用存储结构。图的邻接矩阵表示法(Adjacency Matrix)也称作数组表示法。它采用两个数组来表示图:一个是用于存储顶点信息的一维数组,另一个是用于存储图中顶点...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,459
精华内容 2,183
关键字:

邻接多重表