精华内容
下载资源
问答
我要提问
  • 多重邻接表 图的存储结构--多重邻接表（邻接多重表） 千次阅读
    2018-10-23 15:02:32

    和十字链表类似。

    区别在于数组存的链表的元素的结构不同。

    十字链表数组元素的结构是：数据、第一条入边引用、第一条出边引用。

    十字链表链表的元素结构是：边的起点、边的终点、下一条出边引用、下一条入边引用

    而

    多重邻接表数组元素结构是：数据、包含 当前索引对应顶点 的第一条边引用。

    多重邻接表链表的元素结构是：边的起点、包含当前边的起点的另一条边的引用、边的终点、包含当前边终点的另一条边的引用。

     

    图的存储结构
    更多相关内容

  • 多重邻接表的建立

     2022-03-05 13:54:19
    #include #include #include #define MVNUM 50 typedef bool VisitIf; typedef char VerTex; typedef struct ArcNode { VisitIf visitIf;...可以先去看完其他文章理解一下多重邻接表的原理再看应该就可以理解啦。 
    #include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define MVNUM 50


typedef bool VisitIf;
typedef char VerTex;

typedef struct ArcNode
{
	VisitIf visitIf;
	int ivex;
	int jvex;
	struct ArcNode* ilink;
	struct ArcNode* jlink;
}ArcNode;

typedef struct VexNode
{
	VerTex vex;
	ArcNode* firstArc;
}Vex[MVNUM];

typedef struct
{
	Vex Vertrices;
	int vexnum;
	int arcnum;
}AMLGraph;

void CleanCache()
{
	char ch;
	while ((ch = getchar()) != '\n' && ch != EOF);
}

int GetIndex(AMLGraph &G, VerTex vex)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		if (vex == G.Vertrices[i].vex)
		{
			return i;
		}
	}
	return -1;
}

ArcNode* CreateArcNode()
{
	ArcNode* newnode = (ArcNode*)malloc(sizeof(ArcNode));
	if (NULL == newnode)
	{
		printf("分配内存失败!\n");
		exit(-1);
	}
	return newnode;
}

void CreateUDM(AMLGraph &G)
{
	printf("请输入顶点和边个数：\n");
	scanf_s("%d%d", &G.vexnum, &G.arcnum);

	for (int i = 0; i < G.vexnum; i++)
	{
		printf("请输入第%d个节点的信息:\n", i + 1);
		CleanCache();
		scanf_s("%c", &G.Vertrices[i].vex, 1);
		G.Vertrices[i].firstArc = NULL;
	}

	for (int k = 0; k < G.arcnum; k++)
	{
		printf("请输入第%d条边的信息:\n", k + 1);
		CleanCache();
		VerTex ctemp1;
		VerTex ctemp2;
		scanf_s("%c%c", &ctemp1, 1, &ctemp2, 1);
		int i = GetIndex(G, ctemp1);
		int j = GetIndex(G, ctemp2);

		ArcNode* arcNode = CreateArcNode();
		arcNode->visitIf = false;
		arcNode->ivex = i;
		arcNode->ilink = G.Vertrices[i].firstArc;
		G.Vertrices[i].firstArc = arcNode;

		arcNode->jvex = j;
		arcNode->jlink = G.Vertrices[j].firstArc;
		G.Vertrices[j].firstArc = arcNode;
	}
}

void PrintUDM(AMLGraph& G)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		printf("顶点:%c\n", G.Vertrices[i].vex);

		printf("邻接点:");
		ArcNode* ptemp = G.Vertrices[i].firstArc;
		while (ptemp)
		{
			if (ptemp->ivex == i)
			{
				printf("%4c", G.Vertrices[ptemp->jvex].vex);
				ptemp = ptemp->ilink;
			}
			else
			{
				printf("%4c", G.Vertrices[ptemp->ivex].vex);
				ptemp = ptemp->jlink;
			}
		}
		printf("\n");
	}
}

int main(void)
{
	AMLGraph G;

	CreateUDM(G);

	PrintUDM(G);

	return 0;
}

    没有注释，大家应该看不懂吧。可以先去看完其他文章理解一下多重邻接表的原理再看应该就可以理解啦。
    收起
    展开全文
    c语言 c++ 数据结构

  • 图的存储结构——邻接多重表（多重邻接表）的实现

     千次阅读 2020-04-26 13:39:03
    7.2 图的存储结构7.2.3 邻接多重表（多重邻接表）Adjacency Multilist邻接多重表的类定义邻接多重表的顶点结点类模板邻接多重表的边结点类模板邻接多重表的类模板邻接多重表与邻接表的对比 7.2.3 邻接多重表（多重...

    7.2 图的存储结构

    7.2.3 邻接多重表（多重邻接表）Adjacency Multilist

    在无向图的邻接表中可以看到，每一条边（vi,vj）在邻接表中有两个边结点：一个在顶点vi的边链表中，表示(vi,vj)；一个在顶点vj的边链表中，表示(vj,vi)。
    在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。

    邻接多重表的类定义

    在这里插入图片描述

    邻接多重表的顶点结点类模板

    对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
    data域存储有关顶点的信息；
    firstarc域是链接指针，指向第一条依附于该顶点的边。
    所有的顶点结点组成一个顺序表。

    
template <class ElemType ,class WeightType>
class MultiAdjListNetworkVex
{
public:
	ElemType data;
	MultiAdjListNetworkArc<WeightType> *firstarc;

	MultiAdjListNetworkVex()
	{
		firstarc = NULL;
	}
	MultiAdjListNetworkVex(ElemType val, MultiAdjListNetworkArc<WeightType>* adj = NULL)
	{
		data = val;
		firstarc = adj;
	}
};

    邻接多重表的边结点类模板

    在无向图的邻接多重表中，图的每一条边用一个边结点表示，它由六个域组成，其中：
    tag是标记域，标记该边是否被处理或被搜索过；
    weight为边的信息域，用于存储边的权值；adjvexl和adjvex2是顶点域，表示该边所依附的两个顶点在图中的序号；
    nextarcl1域是链接指针，指向下一条依附于顶点adjvexl的边；
    nextarc2也是链接指针，指向下一条依附于顶点adjvex2的边。
    在这里插入图片描述

    template <class WeightType>
class MultiAdjListNetworkArc
{
public:
    int mark;                                       //标记该边是否被搜索或处理过
	WeightType weight;                              //边的权重
	int adjVex1;                                    //边的一个顶点
	MultiAdjListNetworkArc<WeightType>* nextarc1;   //指向下一条依附于adjvex1的边,eg:1-2-->1-3-->5-1
	int adjVex2;
	MultiAdjListNetworkArc<WeightType>* nextarc2;

	MultiAdjListNetworkArc()
	{
		adjVex1= -1;
		adjVex2= -1;
	}
	MultiAdjListNetworkArc(int v1, int v2, WeightType w, MultiAdjListNetworkArc<WeightType>* next1 = NULL,MultiAdjListNetworkArc<WeightType>* next2 = NULL)
	{
		adjVex1 = v1;       adjVex2 = v2;
		weight = w;
		nextarc1 = next1;   nextarc2=next2;
		mark = 0;           //0表示未被搜索，1表示被搜索过
	}

    邻接多重表的类模板

    1.类定义

    template <class ElemType,class WeightType>
class MultiAdjListNetwork
{
protected:
    int vexNum, vexMaxNum, arcNum;
    MultiAdjListNetworkVex<ElemType, WeightType>* vexTable;
    int* tag;
    WeightType infinity;

public:
    MultiAdjListNetwork(ElemType es[], int vertexNum,int vertexMaxNum= DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

    MultiAdjListNetwork(int vertexMaxNum = DEFAULT_SIZE, WeightType infinit = (WeightType)DEFAULT_INFINITY);

    void Clear();
    bool IsEmpty()
    {
        return vexNum == 0;
    }
    int GetArcNum()const
    {
        return arcNum;
    }
    int GetvexNum()const
    {
        return vexNum;
    }


    int FirstAdjVex(int v)const;
    int NextAdjVex(int v1, int v2)const;
    MultiAdjListNetworkArc<WeightType>* NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;
    MultiAdjListNetworkArc<WeightType>* LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const;

    void InsertVex(const ElemType& d);
    void InsertArc(int v1, int v2, WeightType w);

    void DeleteVex(const ElemType& d);
    void DeleteArc(int v1, int v2);

    MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy);
    MultiAdjListNetwork<ElemType, WeightType> &operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy);

    ///深度优先遍历
    void DFS1(const int v);
    void DFS1Traverse();
    void DFS2();

    int GetAdjVex(int head,int pre);//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
    void DFS3();

    void BFS();
    void Show();
};

    2.函数的实现
    研讨题，能够运行，但是代码不一定是最优的。

    #include <stack>
#include <queue>

template <class ElemType,class WeightType>
MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(ElemType es[],int vertexNum,int vertexMaxNum,WeightType infinit)
{
    if(vertexMaxNum < 0)
        throw Error("允许的顶点最大数目不能为负！");
    if (vertexMaxNum < vertexNum)
        throw Error("顶点数目不能大于允许的顶点最大数目！");
    vexNum = vertexNum;
    vexMaxNum = vertexMaxNum;
    arcNum = 0;
    infinity = infinit;
    tag = new int[vexMaxNum];
    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
    for (int v = 0; v < vexNum; v++)
    {
        tag[v] = 0;
        vexTable[v].data = es[v];
        vexTable[v].firstarc = NULL;
    }
}
template <class ElemType,class WeightType>
MultiAdjListNetwork<ElemType,WeightType>::MultiAdjListNetwork(int vertexMaxNum, WeightType infinit)
{
    if (vertexMaxNum < 0)
        throw Error("允许的顶点最大数目不能为负！");
    vexNum = 0;
    vexMaxNum = vertexMaxNum;
    arcNum = 0;
    infinity = infinit;
    tag = new int[vexMaxNum];
    vexTable = new MultiAdjListNetworkVex<ElemType, WeightType>[vexMaxNum];
}
template<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::FirstAdjVex(int v)const
{
    if (v < 0 || v >= vexNum)
        throw Error("v不合法！");
    if (vexTable[v].firstarc == NULL)
        return -1;
    else
        return vexTable[v].firstarc->adjVex1;
}

template<class ElemType, class WeightType>
int MultiAdjListNetwork<ElemType, WeightType>::NextAdjVex(int v1, int v2)const
{
    MultiAdjListNetworkArc<WeightType>* p;
    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
    if (v1 == v2)
        throw Error("v1不能等于v2！");
    p = vexTable[v1].firstarc;
    while (p != NULL && p->adjVex1 != v2 && p->adjVex2 != v2)
        p = p->nextarc;
    if (p == NULL || p->nextarc == NULL)
        return -1;  //不存在下一个邻接点
    else if(p->adjVex1==v2)
        return (p->nextarc2->adjVex1==v1?p->nextarc2->adjVex2:p->nextarc2->adjVex1);
    else
        return (p->nextarc1->adjVex1==v1?p->nextarc1->adjVex2:p->nextarc1->adjVex1);
}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::Clear()
{
    if (IsEmpty()) return;
    int n = vexNum;
    for (int u = 0; u < n ; u++)
        DeleteVex(vexTable[0].data);
    return;
}
template<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::~MultiAdjListNetwork()
{
    Clear();
}
template<class ElemType, class WeightType>
MultiAdjListNetwork<ElemType, WeightType>::MultiAdjListNetwork(const MultiAdjListNetwork<ElemType, WeightType>* copy)
{
    vexMaxNum = copy.vexMaxNum;
    vexNum = copy.vexNum;
    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    arcNum = 0;
    infinity = copy.infinity;
    tag = new int[vexMaxNum];

    for (int v = 0; v < vexNum; v++)
    {
        tag[v] = 0;
        vexTable[v].data = copy.vexTable[v].data;
        vexTable[v].firstarc = NULL;
    }
    MultiAdjListNetworkArc<WeightType>* p;

    for (int u = 0; u < vexNum; u++)
    {
        p = copy.vexTable[u].firstarc;
        while (p != NULL)
        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
            p=NextArc(u,p);
        }
    }
}
template<class ElemType, class WeightType> MultiAdjListNetwork<ElemType, WeightType>&
MultiAdjListNetwork<ElemType, WeightType>::operator=(const MultiAdjListNetwork<ElemType, WeightType>& copy)
{
    if (this == &copy) return *this;
    Clear();
    vexMaxNum = copy.vexMaxNum;
    vexNum = copy.vexNum;
    vexTable = new MultiAdjListNetworkVex<ElemType,WeightType>[vexMaxNum];
    arcNum = 0;
    infinity = copy.infinity;
    tag = new int[vexMaxNum];

    for (int v = 0; v < vexNum; v++)
    {
        tag[v] = 0;
        vexTable[v].data = copy.vexTable[v].data;
        vexTable[v].firstarc = NULL;
    }
    MultiAdjListNetworkArc<WeightType>* p;

    for (int u = 0; u < vexNum; u++)
    {
        p = copy.vexTable[u].firstarc;
        while (p != NULL)
        {
            InsertArc(p->adjVex1, p->adjVex2, p->weight);
            p=NextArc(u,p);
        }
    }
    return *this;
}
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>::NextArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
    if(p==NULL) return NULL;
    if(p->adjVex1==v1)
        return p->nextarc1;
    else
        return p->nextarc2;
}
template<class ElemType, class WeightType> MultiAdjListNetworkArc<WeightType>*
MultiAdjListNetwork<ElemType, WeightType>::LastArc(int v1,MultiAdjListNetworkArc<WeightType>*p)const
{
    if(p==NULL)return NULL;
    MultiAdjListNetworkArc<WeightType> *q=vexTable[v1].firstarc;
    if(q==p)
        return NULL;
    while(q)
    {
        if(q->nextarc1==p ||q->nextarc2==p)
            break;
        q=NextArc(v1,q);
    }
    return q;
}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::InsertVex(const ElemType& d)
{
    if (vexNum == vexMaxNum)
        throw Error("图的顶点数不能超过允许的最大数！");
    vexTable[vexNum].data = d;
    vexTable[vexNum].firstarc = NULL;
    tag[vexNum] = 0;
    vexNum++;
}
template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::InsertArc(int v1, int v2, WeightType w)
{
    MultiAdjListNetworkArc<WeightType>* p,*q;
    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
    if (v1 == v2)
        throw Error("v1不能等于v2！");
    if (w == infinity)
        throw Error("w不能为无穷大！");


    p = vexTable[v1].firstarc;
    while(p)
    {
        if(p->adjVex1==v2||p->adjVex2==v2)//边已经在顶点的邻接边中
        {
            if(p->weight!=w)
                p->weight=w;
            return;
        }

        p=NextArc(v1,p);
    }
    p = vexTable[v1].firstarc;
    q = vexTable[v2].firstarc;
    vexTable[v1].firstarc = new MultiAdjListNetworkArc<WeightType>(v1,v2, w, p,q);//头插法
    vexTable[v2].firstarc =vexTable[v1].firstarc;
    arcNum++;
}

template<class ElemType, class WeightType>
void MultiAdjListNetwork<ElemType, WeightType>::DeleteArc(int v1, int v2)
{

    MultiAdjListNetworkArc<WeightType>* p, * q,*r;
    if (v1 < 0 || v1 >= vexNum)
        throw Error("v1不合法！");
    if (v2 < 0 || v2 >= vexNum)
        throw Error("v2不合法！");
    if (v1 == v2)
        throw Error("v1不能等于v2！");

    p = vexTable[v1].firstarc;
    while (p != NULL && p->adjVex2!= v2&&p->adjVex1!=v2)
    {
        q = p;
        p = NextArc(v1,p);
    }//找到要删除的边结点p及其前一结点q

    if (p != NULL)//找到v1-v2的边
    {
        r=LastArc(v2,p);
        if (vexTable[v1].firstarc == p)//第一条边，q此时为NULL
            if(p->adjVex2==v2)
                vexTable[v1].firstarc = p->nextarc1;
            else vexTable[v1].firstarc=p->nextarc2;
        else//不是第一条边
        {
            if(q->adjVex1==v1)
                q->nextarc1 = NextArc(v1,p);
            else
                q->nextarc2=NextArc(v1,p);

        }
        if(r==NULL)
            if(p->adjVex2==v2)
                vexTable[v2].firstarc = p->nextarc2;
            else vexTable[v2].firstarc=p->nextarc1;
        else
        {
            if(r->adjVex2==v2)
                r->nextarc2 = NextArc(v2,p);
            else
                r->nextarc1=NextArc(v2,p);
        }
        delete p;
        arcNum--;
    }

}
template<class ElemType, class WeightType> void
MultiAdjListNetwork<ElemType, WeightType>::DeleteVex(const ElemType& d)
{
    int v;
    MultiAdjListNetworkArc<WeightType>* p;
    for (v = 0; v < vexNum; v++)//找到d对应顶点
        if (vexTable[v].data == d)
            break;
    if(v==vexNum)
        throw Error("图中不存在要删除的顶点！");

    for (int u = 0; u < vexNum; u++)//删除与d相连的边
        if (u != v)
        {
            DeleteArc(u, v);
        }
    vexTable[v].firstarc=NULL;

    vexNum--;///将原来的vexTable[vexNum-1]即最后一个节点移动到原来v的位置
    vexTable[v].data = vexTable[vexNum].data;
    vexTable[v].firstarc = vexTable[vexNum].firstarc;
    vexTable[vexNum].firstarc = NULL;
    tag[v] = tag[vexNum];
    //原来与最后一个顶点相连的边改为与v相连
    for (int u = 0; u < vexNum; u++)
    {
        if (u != v)
        {
            p = vexTable[u].firstarc;
            while (p)
            {
                if (p->adjVex1==vexNum)
                    p->adjVex1= v;
                else if(p->adjVex2==vexNum)
                    p->adjVex2=v;
                p = NextArc(u,p);
            }
        }
    }
}
///深度优先遍历
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::DFS1(const int v)
{
    tag[v]=1;
    cout<<setw(3)<<vexTable[v].data;
    MultiAdjListNetworkArc<WeightType> *p;
    p=vexTable[v].firstarc;
    while(p)
    {
        if(tag[p->adjVex1]==0)
            DFS1(p->adjVex1);
        else if(tag[p->adjVex2]==0)
            DFS1(p->adjVex2);
        p=NextArc(v,p);
    }
}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::DFS1Traverse()
{
    for(int i=0; i<vexNum; i++)
        tag[i]=0;
    for(int v=0; v<vexNum; v++)
    {
        if(tag[v]==0)
            DFS1(v);
    }
}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::DFS2()
{
    stack<int> s;
    int tmp;
    MultiAdjListNetworkArc<WeightType> *p,*q;
    for(int i=0; i<vexNum; i++)
        tag[i]=0;
    for(int i=0; i<vexNum; i++)
    {
        tmp=i;
        while(tag[tmp]==0||!s.empty())
        {
            p=vexTable[tmp].firstarc;
            while(tag[tmp]==0)
            {
                s.push(tmp);
                cout<<setw(3)<<vexTable[tmp].data;
                tag[tmp]=1;
                p=vexTable[tmp].firstarc;
                if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
                tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
                //cout<<" 1st     tmp="<<tmp<<endl;
            }
            if(!s.empty())
            {
                tmp=s.top();
                s.pop();
                q=vexTable[tmp].firstarc;
                int t=tmp;
                while(q&&tag[tmp]!=0)
                {
                    tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
                    //cout<<" 2nd     tmp="<<tmp<<endl;
                    q=NextArc(t,q);
                }
                if(tag[tmp]==0)
                    s.push(t);
                ///1、对应上面连通分支只有1个点的情况
                ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
                ///tmp要么等于找到的第一个未访问节点，
                ///要么等于与t相连最后一个点（已被访问过）
                ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
            }
        }
    }
}
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
template<class ElemType, class WeightType> int
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
{
    if(head==pre)
        return -1;

    MultiAdjListNetworkArc<WeightType> *p;
    p=vexTable[head].firstarc;
    if(pre==-1&&p!=NULL)
        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    //pre!=-1&&p!=NULL
    while(p!=NULL)
    {
        if(p->adjVex1==head && p->adjVex2!=pre)
            p=p->nextarc1;
        else if(p->adjVex2==head && p->adjVex1!=pre)
            p=p->nextarc2;
        else if(p->adjVex1==head && p->adjVex2==pre)
        {
            p=p->nextarc1;
            break;
        }
        else if(p->adjVex2==head && p->adjVex1==pre)
        {
            p=p->nextarc2;
            break;
        }
    }
    if(p!=NULL)
    {
        return p->adjVex1==head?p->adjVex2:p->adjVex1;
    }
    else
        return -1;
}


template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::DFS3()
{
    stack<int> s;
    int p,cur,pre;
    //MultiAdjListNetworkArc<WeightType> *p,*q;
    for(int i=0; i<vexNum; i++) tag[i]=0;//初始化

    for(int i=0; i<vexNum; i++)
    {
        cur=i;pre=-1;
        while(tag[cur]==0||!s.empty())
        {
            while(tag[cur]==0)
            {
                cout<<vexTable[cur].data<<"  ";
                s.push(cur);
                tag[cur]=1;
               //初次访问，标记入栈

               p=GetAdjVex(cur,pre);//p是cur的连通顶点
               if(p==-1)
               {
                   pre=cur;s.pop();
                   break;
               }
               else
               {
                   pre=cur;
                   cur=p;
               }

            }
            while(!s.empty())
            {
                cur=s.top();
                p=GetAdjVex(cur,pre);
                if(tag[p]==0)
                {
                    pre=cur;
                    cur=p;
                    break;
                }
                else
                {
                    pre=s.top();
                    s.pop();
                }

            }

        }
    }
}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
{
    for(int i=0; i<vexNum; i++)
        tag[i]=0;
    queue<int> q;
    int tmp,t;
    MultiAdjListNetworkArc<WeightType> *p;
    for(int i=0; i<vexNum; i++)
    {
        if(tag[i]==0)
        {
            tag[i]=1;
            q.push(i);
            cout<<setw(3)<<vexTable[i].data;
        }
        while(!q.empty())
        {
            tmp=q.front();
            q.pop();
            p=vexTable[tmp].firstarc;
            while(p!=NULL)
            {
                t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
                if(tag[t]==0)
                {
                    cout<<setw(3)<<vexTable[t].data;
                    tag[t]=1;
                    q.push(t);
                }
                p=NextArc(tmp,p);
            }
        }
    }
}
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
{
    MultiAdjListNetworkArc<WeightType> *p;
    cout << "无向图有" << vexNum << "个点，分别为:";
    for (int i = 0; i < vexNum; i++)
        cout << vexTable[i].data << " ";
    cout << endl;
    cout << "无向图有" << arcNum << "条边"<<endl;
    for (int i = 0; i < vexNum; i++)
    {
        cout<<"和" << vexTable[i].data << "有关的边:";
        p = vexTable[i].firstarc;
        while (p != NULL)
        {
            cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
            p=NextArc(i,p);
        }
        cout << endl;
    }
}

    邻接多重表与邻接表的对比

    邻接表链接
    在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
    在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
    为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。

    至此，邻接多重表完毕#

    收起
    展开全文

  • 多重邻接表

     千次阅读 2016-07-15 17:15:35
    好好看一遍,数据结构这本书老师很多东西都没有讲,不怪老师,因为下面没人听。所以自己看看，写一下： 给你一幅图你能够画出多重邻接表的结构图你就明白了。 所以给出如下一幅图： 结构图如下： 代码以后再写。

     好好看一遍,数据结构这本书老师很多东西都没有讲,不怪老师,因为下面没人听。所以自己看看，写一下：

    给你一幅图你能够画出多重邻接表的结构图你就明白了。

    所以给出如下一幅图：

    结构图如下：




    代码就不写了，因为你会写十字链表，多重邻接表就不在话下。如果不会请戳这里


    收起
    展开全文
    图的存储 C++

  • 数据结构 多重邻接表

     2020-09-24 00:00:03
    前言 有向图的表示结构有多种，由于其有向性，结构中要人...和十字链表类似，多重邻接表是无向图的一种链式存储结构，区别的是多重邻接表： 对于结点的设置不再把出边和入边分成两张链表，而是一张链表表示邻边； 对于
    收起

  • 图的四种表示方法(邻接表, 邻接矩阵, 十字链表, 邻接多重表).cpp

     2021-05-12 18:33:17
    学习数据结构和离散数学的同学, 这是我的理解和相关代码
    收起

  • 邻接表、邻接多重表、十字链表的介绍

     千次阅读 2020-04-07 18:31:04
    邻接表 使用邻接表存储图时，对于图中的每一个顶点和它相关的邻接点，都存储到一个链表中。每个链表都配有头结点，头结点的数据域不为NULL，而是用于存储顶点本身的数据；后续链表中的各个结点存储的是当前顶点的...
    收起
    数据结构

  • 数据结构实验：图遍历的演示——以多重邻接表实现

     千次阅读 多人点赞 2019-11-20 22:03:21
    以邻接多重表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。 【测试数据】 这里我将可视化数据提取特征，变为可利用数据，...
    收起
    数据结构 DFS BFS

  • 邻接多重表 操作实现

     2021-12-05 19:52:24
    邻接多重表是一种比较重要的无向简单图存储结构，鉴于无向图在数据结构课程中的重要性，邻接表多重操作实现必须要予以解决。图论及其算法在编译原理中具有很重要的地位，图着色的寄存器分配就要用到无向简单图，所以...
    收起
    数据结构 c++

  • 邻接表、邻接多重表、十字链表实现图

     2021-01-16 17:58:36
    邻接表实现相对简单 // 邻接表实现(adjacency list) // B----A // | | // D----C public class AdjList { private VexNode[] vexs;// 顶点数组 // 顶点表 private class VexNode{ int data;// 顶点值 Edge ...
    收起
    数据结构

  • 构建复杂网络的几种方法（邻接矩阵，邻接表，十字链表，邻接多重表）

     千次阅读 2022-04-12 03:37:53
    简单地说，线性结构就是表中各个结点具有线性关系。如果从数据结构的语言来描述，线性结构应该包括如下几点： 1、线性结构是非空集。 2、线性结构有且仅有一个开始结点和一个终端结点。 3、线性结构所有结点都...
    收起
    数组 复杂网络

  • 十字链表与邻接多重表的画法

     千次阅读 2021-11-06 13:32:08
    近期一直在构建算法技能树的数据，借此机会，重新把数据结构与算法又温习了一遍，在看到十字链表与邻接多重表的画法时，十分的不理解，在C站找资料时，发现也看不懂，于是上B站，终于明白了十字链表与多重邻接表的...
    收起
    链表 数据结构

  • 邻接多重表

     千次阅读 多人点赞 2020-04-07 18:41:40
    邻接表虽然已经能够很好地表示无向图了，但是无向图访问或者删除一条边(Vi,Vj)时需要同时访问两个链表i和j并分别找到对应的边结点，这给针对图的边的操作（标记或删除）带来不便利。邻接多重表因此而演变过来的。 ...
    收起
    数据结构

  • （数据结构）无向图的邻接多重表(Adjacency Multilist)表示

     千次阅读 2020-12-08 16:40:57
    无向图的邻接多重表(Adjacency Multilist)表示
    收起
    数据结构 链表 算法

  • 数据结构——邻接多重表（C语言实现）

     千次阅读 热门讨论 2020-11-08 13:33:12
    小弟最近在学数据结构，昨天自己实现了一下邻接多重表，写之前...邻接多重表相较于邻接表大大节省了空间（一半），邻接多重表中定义相邻顶点的结构体时表示的并不是一个顶点，而是一条边由node_1到node_2的一条边，并且
    收起
    数据结构 c语言 链表 指针

  • 无向图 邻接多重表的创建 - c语言

     2020-10-30 16:50:31
    } } } void InputGraph(AMLGraph G)//邻接多重表的输出 { int i,j;//记录次数 EBox *p1,*p2;//用于遍历链表 printf("邻接多重表为：\n"); //为了能验证创建的图是否正确 for(i=0;i;i++)//利用循环输出 { ...
    收起
    数据结构 c语言

  • 邻接多重表C++实现

     2019-12-17 18:26:34
    邻接多重表是面向无向图的另一种链式存储结构，从边出发构建整个图，方便访问标记，删除边等操作，存储空间最少。易判断顶点之间的关系。 #include<iostream> using namespace std; const int maxnum = 100;...
    收起

  • 邻接表、邻接多重表、十字链表及C语言实现

     2021-05-19 13:08:59
    邻接表使用邻接表存储图时，对于图中的每一个顶点和它相关的邻接点，都存储到一个链表中。每个链表都配有头结点，头结点的数据域不为NULL，而是用于存储顶点本身的数据；后续链表中的各个结点存储的是当前顶点的所有...
    收起

  • 迪杰斯特拉算法（邻接表求解）

     千次阅读 2020-11-19 20:20:18
    与邻接矩阵表示的方法不同的是，在更新dis数组和path数组时，只需要把求u到j距离的g.edges[u][j]换成邻接表表示 g.edges[u][j]表示u到j的距离，因此可以写一个getWeight(g, u, j)算法用于计算u到j的距离 [核心函数]...
    收起
    数据结构 算法 c语言

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,007
精华内容 2,002
热门标签
关键字：

多重邻接表