无向图的邻接多重表存储-淘娜娜副业社

对于有向图，为便于计算出度、入度，可采用十字链表存储；对于无向图，如果采用邻接表存储，会浪费一倍边的空间，而且在增加边、删除边时也要分别进行两次操作，为避免这些问题，可采用邻接多重表存储方式。

邻接多重表是参照十字链表思想对无向图的一种存储方式。理解的关键点在于边结点存储的两个端点没有头尾顺序，谁先谁后没有影响，唯一要注意的是某个端点要与连接该端点的下一条边的指针相对应（这两个是牢牢捆绑在一起的！！！），由于边结点上述的特点，所以在删除边的操作时会比较麻烦一些。

定义顶点结点：

struct VerNode{
    int num;
    EdgeNode* fstarc;
    VerNode(int n=-1,EdgeNode* fa=NULL)
            :num(n),fstarc(fa){}
};

定义边结点：

struct EdgeNode{
    int ivex;
    EdgeNode* ilink;
    int jvex;
    EdgeNode* jlink;
    int info;
    EdgeNode(int i=-1,EdgeNode* il=NULL,int j=-1,EdgeNode* jl=NULL,int wg=0)
            :ivex(i),ilink(il),jvex(j),jlink(jl),info(wg){}
};

增加边的操作：

bool addEdge(int iv,int jv,int val){
//数据输入非法，退出
    if(iv>=VerNum||iv=VerNum||jvivex+temp->jvex)==(iv+jv)) {
            return false;
        }
        else{
            if(temp->ivex==iv)
                temp=temp->ilink;
            else
                temp=temp->jlink;
        }
    }
//在边表头部插入 
    EdgeNode* edge=new EdgeNode(iv,NULL,jv,NULL,val);
    if(vn[iv].fstarc==NULL){
        vn[iv].fstarc=edge;
    }
    else{
        edge->ilink=vn[iv].fstarc;
        vn[iv].fstarc=edge;
    }
//同时也要更新另一个端点的链表，也是头插
    if(vn[jv].fstarc==NULL){
        vn[jv].fstarc=edge;
    }
    else{
        edge->jlink=vn[jv].fstarc;
        vn[jv].fstarc=edge;
    }
    return true;
}

删除边的操作：

bool delEdge(int iv,int jv){
//数据输入非法，退出
    if(iv>=VerNum||iv=VerNum||jvivex+iedge->jvex)==(iv+jv)){
//此处，iv可能存储在ivex中，也可能存储在jvex中，与输入边时的端点顺序有关
        if(iedge->ivex==iv)
            vn[iv].fstarc=iedge->ilink;
        else
            vn[iv].fstarc=iedge->jlink;
    }
    else{
//如果不是链表的头，则找到该点，并更新前驱结点iv对应的指针域
        while(iedge!=NULL){
            if((iedge->ivex+iedge->jvex)==(iv+jv))
                break;
            itemp=iedge;
            if(iedge->ivex==iv)
                iedge=iedge->ilink;
            else
                iedge=iedge->jlink;
        }
        if(iedge==NULL)
            return false;
        else{
            if(iedge->ivex==iv){
                if(itemp->ivex==iv)
                    itemp->ilink=iedge->ilink;
                else
                    itemp->jlink=iedge->ilink;
            }
            else{
                if(itemp->ivex==iv)
                    itemp->ilink=iedge->jlink;
                else
                    itemp->jlink=iedge->jlink;
            }
        }
    }
//对另一个端点，同样判断是否是边链表的头
    if(vn[jv].fstarc==iedge){
        if(iedge->ivex==jv)
            vn[jv].fstarc=iedge->ilink;
        else
            vn[jv].fstarc=iedge->jlink;
    }
//不是边链表的头，则找到该点，从上两段代码可知，此边结点肯定存在
    else{
        while(jedge!=iedge){
            jtemp=jedge;
            if(jedge->ivex==jv)
                jedge=jedge->ilink;
            else
                jedge=jedge->jlink;
        }
        if(jedge->ivex==jv){
            if(jtemp->ivex==jv)
                jtemp->ilink=jedge->ilink;
            else
                jtemp->jlink=jedge->ilink;
        }
        else{
            if(jtemp->ivex==jv)
                jtemp->ilink=jedge->jlink;
            else
                jtemp->jlink=jedge->jlink;
        }
    }
    delete jedge;
    return true;
}

邻接多重表删除边的操作非常麻烦，涉及到头结点的判断、边结点的查找、指针域的判断更新等，所以面对这种情况时，建议先理清思路，画出流程图，完善细节信息，再根据流程图一步步写出代码，可避免思路的混乱。

参考代码：

#include 
using namespace std;
const int VerNum=5;
bool addEdge(int iv,int jv,int val);
bool delEdge(int iv,int jv);
struct EdgeNode{
    int ivex;
    EdgeNode* ilink;
    int jvex;
    EdgeNode* jlink;
    int info;
    EdgeNode(int i=-1,EdgeNode* il=NULL,int j=-1,EdgeNode* jl=NULL,int wg=0)
            :ivex(i),ilink(il),jvex(j),jlink(jl),info(wg){}
};
struct VerNode{
    int num;
    EdgeNode* fstarc;
    VerNode(int n=-1,EdgeNode* fa=NULL)
            :num(n),fstarc(fa){}
};
VerNode vn[VerNum];
int main(){
    freopen("data.in","r",stdin);
    freopen("data.out","w",stdout);
    for(int i=0;i<VerNum;i++)
        vn[i].num=i;
    for(int i=0;i>iv>>jv>>val;
        addEdge(iv,jv,val);
    }
    addEdge(3,4,10);
    delEdge(0,3);
    for(int i=0;i<VerNum;i++){
        EdgeNode* p=vn[i].fstarc;
        while(p!=NULL){
            cout<ivex<<""<jvex<<"  val:"<info<ivex==i)
                p=p->ilink;
            else
                p=p->jlink;
        }
        cout<<"--------------------"<=VerNum||iv=VerNum||jvivex+temp->jvex)==(iv+jv)) {
            return false;
        }
        else{
            if(temp->ivex==iv)
                temp=temp->ilink;
            else
                temp=temp->jlink;
        }
    }
    EdgeNode* edge=new EdgeNode(iv,NULL,jv,NULL,val);
    if(vn[iv].fstarc==NULL){
        vn[iv].fstarc=edge;
    }
    else{
        edge->ilink=vn[iv].fstarc;
        vn[iv].fstarc=edge;
    }
    if(vn[jv].fstarc==NULL){
        vn[jv].fstarc=edge;
    }
    else{
        edge->jlink=vn[jv].fstarc;
        vn[jv].fstarc=edge;
    }
    return true;
}
bool delEdge(int iv,int jv){
    if(iv>=VerNum||iv=VerNum||jvivex+iedge->jvex)==(iv+jv)){
        if(iedge->ivex==iv)
            vn[iv].fstarc=iedge->ilink;
        else
            vn[iv].fstarc=iedge->jlink;
    }
    else{
        while(iedge!=NULL){
            if((iedge->ivex+iedge->jvex)==(iv+jv))
                break;
            itemp=iedge;
            if(iedge->ivex==iv)
                iedge=iedge->ilink;
            else
                iedge=iedge->jlink;
        }
        if(iedge==NULL)
            return false;
        else{
            if(iedge->ivex==iv){
                if(itemp->ivex==iv)
                    itemp->ilink=iedge->ilink;
                else
                    itemp->jlink=iedge->ilink;
            }
            else{
                if(itemp->ivex==iv)
                    itemp->ilink=iedge->jlink;
                else
                    itemp->jlink=iedge->jlink;
            }
        }
    }
    if(vn[jv].fstarc==iedge){
        if(iedge->ivex==jv)
            vn[jv].fstarc=iedge->ilink;
        else
            vn[jv].fstarc=iedge->jlink;
    }
    else{
        while(jedge!=iedge){
            jtemp=jedge;
            if(jedge->ivex==jv)
                jedge=jedge->ilink;
            else
                jedge=jedge->jlink;
        }
        if(jedge->ivex==jv){
            if(jtemp->ivex==jv)
                jtemp->ilink=jedge->ilink;
            else
                jtemp->jlink=jedge->ilink;
        }
        else{
            if(jtemp->ivex==jv)
                jtemp->ilink=jedge->jlink;
            else
                jtemp->jlink=jedge->jlink;
        }
    }
    delete jedge;
    return true;
}

———END———
限时特惠： 本站每日持续更新海量各大内部创业教程，永久会员只需109元，全站资源免费下载点击查看详情
站长微信： nanadh666

声明：1、本内容转载于网络，版权归原作者所有！2、本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。3、本内容若侵犯到你的版权利益，请联系我们，会尽快给予删除处理！

无向图的邻接多重表存储

站长简介

最新实战项目

小红书引流私域旅游资料售卖，复制粘贴，三分钟一篇图文，日入1000+，小白终身可做

剪映电脑版实战教程，0基础打造短视频剪辑高手，详解功能、工具与实操案例

短视频制作与运营，从0到10万粉丝变现方法，剪映特效与热门视频制作教程

【高端精品】外面收费1988的咔咔一通剪视频批量处理，合并，裁剪，转图片，视频去重等功能【剪辑助手+详细教程】

主播直播特训营：抖音直播间运营知识+开播准备+流量考核，轻松上手

同城店铺短视频引流变现：掌握抖音平台规则，打造爆款内容，实现流量变现

小红书实战运营课：从开通店铺到直播话术，打造爆款笔记与高效直播

AI工具PPT制作教程：AI工具助力PPT制作，高质量PPT一分钟搞定

无向图的邻接多重表存储

相关文章

站长简介

最新实战项目