查看: 1388|回复: 0

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

字体大小: 正常放大

杨利霞

5273 主题	82 听众	17万积分

TA的每日心情

	开心 2021-8-11 17:59

签到天数: 17 天

[LV.4]偶尔看看III

网络挑战赛参赛者

自我介绍: 本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

群组: 2018美赛大象算法课程

群组: 2018美赛护航培训课程

群组: 2019年数学中国站长建

群组: 2019年数据分析师课程

群组: 2018年大象老师国赛优

电梯直达

1^#

发表于 2020-4-26 15:26 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

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

7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
邻接多重表的类定义
邻接多重表的顶点结点类模板
邻接多重表的边结点类模板
邻接多重表的类模板
邻接多重表与邻接表的对比
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist

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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：: w- o4 L, N* k0 i. V# y5 O
data域存储有关顶点的信息；$ p3 v; x3 | u7 x% i* `
firstarc域是链接指针，指向第一条依附于该顶点的边。
/ F, \ J* D- L9 n3 y所有的顶点结点组成一个顺序表。

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.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>:

perator=(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.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>:

astArc(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>:

eleteArc(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>:

eleteVex(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.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>:

FS1(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>:

FS1Traverse()
{
for(int i=0; i<vexNum; i++)
      tag=0;7 b, }  T1 o9 h/ ?& Z+ D
for(int v=0; v<vexNum; v++), M' _2 p9 P* m2 J9 A* @, _
{
+ }! R- c7 Z1 ?+ L# N' k8 V       if(tag[v]==0)
' l' y  y3 c/ p- d/ f& y          DFS1(v);3 P7 q2 Z' n. _2 y8 m% L0 L
}
* x1 A. h0 M# y}
3 M# _# F- {9 V) l. Mtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()8 i5 G5 A3 P* ^1 p+ v
{' E, b- t. R( ]" V1 ?4 l# e$ T4 ^
stack<int> s;
' w8 y& d8 J4 O# v( D int tmp;
( O4 L( ~- F3 c/ \. M( x' i MultiAdjListNetworkArc<WeightType> *p,*q;
* L9 J( r) \7 Z. ` for(int i=0; i<vexNum; i++)$ g; S+ I2 h. c+ Y/ V% m4 m, o
      tag=0;9 s- p; g0 X! m" y" W
for(int i=0; i<vexNum; i++)
8 Z# ^% r! \2 X# j' A9 K {
1 I! o9 V% e; @7 t5 r, A       tmp=i;
) |1 C9 B3 _. s       while(tag[tmp]==0||!s.empty())+ e; e& h8 ~% z$ l4 W
      {
! B0 A1 j+ E. B0 U* k2 S, y9 O          p=vexTable[tmp].firstarc;0 w3 n1 a. R0 Q% K2 t5 u
         while(tag[tmp]==0)
( H. W8 o  C, u; \3 X6 V$ ^          {& g  N7 w3 N( \/ O# Y6 w& T- h
            s.push(tmp);" H; |8 z5 o* ^. Z6 ], ~
            cout<<setw(3)<<vexTable[tmp].data;9 t, k/ }/ j' ~; ]5 M
            tag[tmp]=1;$ m* l$ q2 F5 M8 `* L" A( |+ E
            p=vexTable[tmp].firstarc;
- c  v: W% t7 R* S* [  n             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
2 L9 g( d  y) Q6 f; [) d8 T             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
" f' O) Y* b/ q3 C6 y$ X; @( s! u* F             //cout<<" 1st    tmp="<<tmp<<endl;
4 @4 `) X5 P4 B, h- p7 K7 _" c7 e          }) Q) g9 Z2 z: d) B( t! i
         if(!s.empty())
* N' b: D/ p6 `- K! Y4 E          {4 F2 T! R& A0 Z2 b5 t
            tmp=s.top();
. k2 `9 i3 i) g, P             s.pop();2 b! ?. X# i% ?' \8 v
            q=vexTable[tmp].firstarc;5 z9 z' w" x6 S6 V+ x# F  Z2 x* r
            int t=tmp;* T- a' J- u* E6 e$ ]: U7 I( o
            while(q&&tag[tmp]!=0)6 L: D5 I. }7 P
            {# \; D) {4 }  T+ y; u; Q
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
7 T' t* k' j' O/ i. g) M3 I# u5 S                   //cout<<" 2nd    tmp="<<tmp<<endl;
& {# N( k) t) D. a+ u/ B! N+ z                   q=NextArc(t,q);' |# Y5 V! V7 Y; n; i' s# [* [* |
            }
. K* T: W+ f0 i) }( @: b             if(tag[tmp]==0)& a) s: [9 y% W4 o1 h8 o
                  s.push(t);# O7 h' `  R% Y0 u; w( l8 }* z
            ///1、对应上面连通分支只有1个点的情况
" S8 b. p- Q/ L2 V5 n& Y             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
+ p5 ?: ]! Y7 S5 q2 N             ///tmp要么等于找到的第一个未访问节点，% m& e; F# z# l5 K& l" h; {% P
            ///要么等于与t相连最后一个点（已被访问过）
3 H- r# l  s, ^3 n, Y             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
; H7 J" g& I! {          }
" b8 y% r& D- f" V4 Q       }
0 i0 x5 L6 Q9 ?1 M' H; } }. [( d* R4 O& G& b3 A
}, T6 ]" x) L" E& c+ |) C$ b
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-13 E( c( k) a8 I) z$ \# x& {
template<class ElemType, class WeightType> int6 G0 W0 V. d3 ]; ^  {
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
9 b+ ~; Q& c( Y& o3 o' W{. @) r% y$ n! |7 ?
if(head==pre)
( u, Q& @( t  Z3 d       return -1;1 z; U" c9 H8 S4 B- A2 S
: B# M) k/ |. [
MultiAdjListNetworkArc<WeightType> *p;
9 j: H" j9 F7 V3 G7 z0 W* |& R9 K$ W p=vexTable[head].firstarc;
% c6 A, @! v. _6 ? if(pre==-1&&p!=NULL)' g! j; S- |! e6 n7 ]. D
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
! X  `; |' i, ?9 W6 M3 R, L //pre!=-1&&p!=NULL
6 G$ W- ~% x% E2 W while(p!=NULL)
5 q4 B+ i# |- o# y2 i- l$ ? {& C, g0 }1 v  {6 y6 Q
      if(p->adjVex1==head && p->adjVex2!=pre)
8 b- g8 M( y+ C" q3 B, Q) i          p=p->nextarc1;
! d. T& p& j2 y  C6 L9 b+ y       else if(p->adjVex2==head && p->adjVex1!=pre)# |9 N: [$ S4 R6 J% g) t& L) I8 N
         p=p->nextarc2;7 R1 F3 z! \* r; Y& `7 W$ ~
      else if(p->adjVex1==head && p->adjVex2==pre)
# ]6 L# \4 F7 c1 b/ I& t2 Y# I/ W       {
5 j( q2 i$ |$ ^% [. b          p=p->nextarc1;
' H1 t( D  f/ B% q1 f0 g  U          break;& N" p4 ~# K% v6 _7 P
      }
/ W: ?( M+ A) y& m# x4 k/ l  _       else if(p->adjVex2==head && p->adjVex1==pre)1 ?6 I- j! j- ~+ z9 b
      {% X8 x9 Q: q" a' w2 S
         p=p->nextarc2;8 a/ I7 K2 _, ?0 H7 _
         break;
6 L# F  B1 m! r       }& s0 ~; O! [, g/ O: }3 `
}: L6 M- V) r9 g& g3 j" t
if(p!=NULL)' x  |8 I2 M/ H/ F- P" B) l6 E% x
{+ m& S# ~3 E  q& a4 _* C: U
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
$ Q  k& |! m( n }
) t; @# t5 e1 {3 h else
% ]1 C3 _8 k0 h! S       return -1;, Z/ n8 `$ E3 O6 W% [! A3 Z  ]6 v7 f
}
; h& o4 q+ N( Q* a# I
. a3 G0 X5 Y" M) ]6 h  w: y/ ]3 j( E
$ V( L! o9 |6 l% vtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()( ~3 s7 e+ r& b$ n2 B
{6 q+ m' i; E; a0 m4 k! j  u
stack<int> s;* X- F% K' J) }! p/ f$ J
int p,cur,pre;# ]5 p( |- ^/ ^. r$ n- O' g4 `
//MultiAdjListNetworkArc<WeightType> *p,*q;8 i; F: H' g# V' g$ X
for(int i=0; i<vexNum; i++) tag=0;//初始化( k; G  ^& x+ U( `# z7 b& A* b& v, v
7 ^9 `. p4 F2 N# Z
for(int i=0; i<vexNum; i++). y; b! P- ~9 @) Z
{
6 m# k  s; q2 I3 _7 }$ R       cur=i;pre=-1;
& o7 O7 |- ]( F' I! x' ^- x       while(tag[cur]==0||!s.empty())* R# d  n/ E/ r9 k$ e$ ^% w
      {
9 Q5 \- s( j4 y' r1 m3 n$ |          while(tag[cur]==0)# p# ], o' s, m" L0 ?8 Z. u
         {4 P* N  e. E  O
            cout<<vexTable[cur].data<<"  ";
; q9 F! L0 z9 O: K( j4 \             s.push(cur);
1 o" Y, f4 m# s4 A7 D             tag[cur]=1;5 u7 ~5 p5 D9 |* |* O9 q
            //初次访问，标记入栈
) L- ~# j$ V" D- `: B8 ?
% p: U, v& A1 c; [9 K; ~) ^             p=GetAdjVex(cur,pre);//p是cur的连通顶点
% i+ `! W0 ]% I/ ~" z$ b) ^             if(p==-1). f" b3 u( |, V
            {5 l- h8 P* }1 x9 V5 B5 b$ b
               pre=cur;s.pop();7 @# d; [2 x8 n7 a3 B. |" q
               break;0 l1 K, r5 D* C2 L
            }
( ~6 f0 t4 ?' H/ m. S# r$ D             else0 G9 @  D% X3 I8 X  Z& p
            {
4 B" u3 I3 ~) q8 s; f9 A                pre=cur;
+ w0 c7 X% s$ F                cur=p;
/ m1 o' {' T2 K, }! ~1 @; y             }. W9 Y5 p+ m9 }# i- C
7 {4 C) ^6 J& R5 C! {, u# f
         }5 x$ w  L! i( D, p
         while(!s.empty())( C0 X7 o; M" m" i! S
         {/ W( _3 P8 M/ @- u7 U- t. o
            cur=s.top();+ X& ?& @/ S7 l, D9 C9 f
            p=GetAdjVex(cur,pre);
, ~0 B4 r3 n! ?; p             if(tag[p]==0)6 Y7 w0 ]7 c$ V1 }# L
            {. j$ M( m5 T* u$ i' T% j; Y; G
                  pre=cur;: R, c3 q$ d6 T' d. H
                  cur=p;
. R8 L, C9 V, q/ p                   break;) A/ D! D4 ~+ o, l! m2 b' S
            }
" V! Z/ @+ _& h. M. ]. o% I             else2 k/ y6 V* e) k. H& j! L4 S' K
            {1 ^# J3 r; g+ E8 r0 ]
                  pre=s.top();. _1 `6 v/ Z: h6 M
                  s.pop();
/ j, j0 I9 r' x4 p+ v8 ]' D# c             }
* g) l: B) ]0 a8 m* {- D1 k' ~0 R1 k/ Q0 G1 `1 _, n
         }, q. \4 E6 q  n
1 v. p8 |# h4 Y* o2 `
      }
/ c2 a" [& w* o8 n- k9 e( f }( w2 a6 j/ h4 R, u
}
& N# L# F0 F- K  ]5 _" e$ c' [template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()+ q3 Y% o- r( L- z
{
( B1 u/ K6 g$ @" ?1 N5 `6 ]" r; p for(int i=0; i<vexNum; i++)
/ u$ [: {- t5 c  [       tag=0;
+ a8 f9 F+ ?# t% ~) d4 b% `5 s) _ queue<int> q;
% P5 a8 ^  J$ |- ^+ X9 k% { int tmp,t;+ X" W- x4 F0 U# ]* k/ A
MultiAdjListNetworkArc<WeightType> *p;
+ Q9 m( h# h+ `' K; S. I for(int i=0; i<vexNum; i++)" U: A0 E/ X6 s( U  n+ O
{, C& X$ [  J' G
      if(tag==0)- m' `5 g, P# n$ k! A
      {
/ I# b& {- l9 N! z3 l% B          tag=1;
8 B: I0 @, e, W          q.push(i);
; [+ c1 r0 I* `6 e          cout<<setw(3)<<vexTable.data;
' ?" ]; S+ P) k9 M& w       }% C3 u' [8 a9 I. n* H
      while(!q.empty())( H: F1 k& y6 Q3 d9 N
      {3 w2 m$ ^! @- P9 @) k2 U+ _. m
         tmp=q.front();6 H% p, }5 y# |% u3 B1 j4 f  A
         q.pop();
" s. x, X5 o, s0 C3 c          p=vexTable[tmp].firstarc;
$ q: C0 ]5 T6 E# S) V; v( Y          while(p!=NULL)
3 R2 J  v* Y! u% g5 X0 m          {
" M5 }  |" u' p5 T) N             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);* a8 B2 ^9 e$ M" H. G) B6 t) q
            if(tag[t]==0)* G9 e; T' J1 T0 Z
            {
# d" z6 l; p  z. y                   cout<<setw(3)<<vexTable[t].data;+ o7 L- b! H3 Q  W
                  tag[t]=1;
& ~3 P* R- u8 E3 M4 f7 K1 n5 y                   q.push(t);
0 N0 G5 g& ]% D- L             }. g; c& f+ V5 ]: l4 N! |
            p=NextArc(tmp,p);3 g- Z% c" F, }
         }
6 r& {4 l. `9 Q; T       }! V( X! `2 N7 g/ X0 X. x1 P6 {
}
; {: i  W" D2 ]; ]}
; r4 l1 \5 _, O0 ~- N' v, Ntemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
# ~6 o: {2 u. [% V' Z9 @" L{
- h3 h: c. }8 O! z MultiAdjListNetworkArc<WeightType> *p;
) U8 D% s% r$ Y cout << "无向图有" << vexNum << "个点，分别为:";
! _7 Y0 a8 t6 [8 N2 o for (int i = 0; i < vexNum; i++)1 X: S! s" e* {2 W0 }) O* _
      cout << vexTable.data << " ";% \" |, x) R$ w* j6 J
cout << endl;3 e# ]5 p1 l. I+ w
cout << "无向图有" << arcNum << "条边"<<endl;
; ^0 y! R& v* T6 A: m for (int i = 0; i < vexNum; i++)
+ {& S4 ^$ B( c; r% H3 ]* M+ h {! F- Z; G0 e+ |
      cout<<"和" << vexTable.data << "有关的边:";( k+ Y  K- G% p& }
      p = vexTable.firstarc;
3 Q0 G4 i, u* f) f7 l       while (p != NULL)2 S. A3 e; ]8 D; b
      {$ t% Z) V, a9 E# e/ |9 k0 N
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";/ D5 w1 _6 p& B& K& a& M/ j
         p=NextArc(i,p);
3 h* c+ _  }2 J& D+ k  c       }
3 P0 T% [' A2 J# s* W       cout << endl;
6 \* R4 C! H: q, i+ Q }( Q; R4 u8 U$ `7 q
}  y& o5 k- Q% U7 i0 i8 ?

8 b% g) |9 l! v+ r$ p
' g' E3 y3 K. i. h- s0 F5 U. L; Z邻接多重表与邻接表的对比1 W7 K* Y6 n% C& ~+ Y

0 V, p% r! q! n! w$ Y/ U邻接表链接
2 C- K- ]" w8 f5 K, @2 L, H$ E在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
: w0 b/ q& p5 E3 g! o9 n在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。, c7 g9 u1 M2 D* e* r; C
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
$ e( A% E2 F, \- ?# |0 ?————————————————2 x, I# o9 f; J" I  F: Q
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
4 y! l; Q5 h& y$ A' s原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958+ ?9 F  ^2 L* E7 b5 M* G

1 {  G1 s2 U1 ~. u; V. d1 h/ s3 o9 I' i8 B: u4 C% V3 w$ x
0 I7 r" Z7 O( ~, t2 M: [
: b3 |8 i% N" ?8 p
————————————————
) v+ M% ~* s# s* _/ s6 `  Z$ y1 F版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。$ b8 l+ W5 `6 w$ `
原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669589 D& m, \( a( ]+ J9 P" S# d& X2 P& ^
' n! k9 q* a( V
4 B+ Z% P) w& ]1 ]