当前位置:操作系统 > Unix/Linux >>

邻接多重表存储无向图以及有关操作

 

数据结构是编程里面最重要的一门基础课之一,所以学多少遍都不可以嫌多,算法的知识当然是融在其中,多练习,多思考,基础打好了,其他的东西学起来也就so easy了。

 

邻接多重表,是对用邻接表存储无向图的一种压缩存储,当然也是链式存储,邻接多重表的相关概念,可以百度、谷歌、或者看有关书籍。大部分书都没有详细介绍这个结构的应用(至少我目前还没看到有书上有写),只是说 这个结构在对无向图的边进行操作的时候会比较方便,确实有一点吧,在插入和删除边的时候,虽然不用想邻接表那样去找两条,但是也是需要进行一些判判断。下面是代码,邻接多重表存储的无向图的一些相关操作:

 

文件"graph.h"

 

 

#include <iostream> 

#include <string> 

#include <queue> 

#include <stack> 

using namespace std; 

 

bool visited[100]; //顶点是否被访问标志 

 

//邻接多重表的存储 

//边结点 

struct EBox 

    int mark;//标志域,指示该边是否被访问过(0:没有1:有) 

    int ivex,jvex;//该边关联的两个顶点的位置 

    EBox *ilink,*jlink;//分别指向关联这两个顶点的下一条边 

}; 

 

//顶点结点 

struct VexBox 

    string data;  //顶点名称 

    EBox *firstedge;//指向第一条关联该结点的边 

}; 

 

class AMLGraph 

private: 

    VexBox *adjmulist; //顶点数组指针 

    int vexnum; //定点数目 

    int arcnum; //边数目 

    int maxnum; //顶点数最大值 

public: 

    AMLGraph(int num=20) 

    { 

        adjmulist=new VexBox[num]; 

        maxnum=num; 

    } 

     

    ~AMLGraph() 

    { 

        delete[]adjmulist; 

    } 

 

    //定位顶点在顶点数组中的位置 

    int Locate_Vex(string v) 

    { 

        for(int i=0;i<vexnum;i++) 

            if(adjmulist[i].data == v) 

                return i; 

        return -1; 

    } 

 

    void CreateUDG_AML() 

    { 

        //邻接多重表,存储无向图 

        string v1,v2; 

        int i,j,k; 

        cout<<"输入定点数目和弧的数目:"; 

        cin>>vexnum>>arcnum; 

 

        while(vexnum>maxnum) 

        { 

            cout<<"顶点数目太多,请重新输入顶点数和边数:"; 

            cin>>vexnum>>arcnum; 

        } 

 

        cout<<"输入每个顶点的名称:"; 

        for(i=0;i<vexnum;i++) 

        { 

            cin>>adjmulist[i].data; 

            adjmulist[i].firstedge=NULL; 

        } 

 

        for(k=0;k<arcnum;k++) 

        { 

            cout<<"输入边的两个顶点:"; 

            cin>>v1>>v2; 

            while(Search_Arc(v1,v2)) 

            { 

                cout<<"该边已存在,本图不支持存在平行边"<<endl; 

                cout<<"重新输入边的两个顶点:"; 

                cin>>v1>>v2; 

            } 

 

            i=Locate_Vex(v1); 

            j=Locate_Vex(v2); 

 

            while(i == -1 || j == -1) 

            { 

                cout<<"两个顶点中有不符合要求的,请重新输入:"; 

                cin>>v1>>v2; 

                i=Locate_Vex(v1); 

                j=Locate_Vex(v2); 

            } 

 

            //采用头插入方式,代码较好写,无向图顺序并不重要,所以没关系 

            EBox *p=new EBox; 

            p->ivex=i; 

            p->jvex=j; 

            p->ilink=adjmulist[i].firstedge; 

            p->jlink=adjmulist[j].firstedge; 

            adjmulist[i].firstedge=adjmulist[j].firstedge=p; 

        } 

 

        cout<<"无向图构造完成"<<endl; 

    } 

 

    bool Search_Arc(string v1,string v2) 

    { 

        //搜索对应的边是

CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,