查看: 1580|回复: 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)。
在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
% J4 X; G, H7 ?/ vdata域存储有关顶点的信息；" H3 N4 \- n7 E
firstarc域是链接指针，指向第一条依附于该顶点的边。$ w( l7 R/ g. J( ?
所有的顶点结点组成一个顺序表。

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;3 {$ C9 `5 F: n5 c8 E2 O
for(int v=0; v<vexNum; v++)4 s! h: o/ q. f" f! A5 r# r
{* h) U3 t, r. @
      if(tag[v]==0)
# u/ ^+ j* y) M5 C8 Y7 l8 |          DFS1(v);* X% Q$ i* ]7 Q7 b/ R9 [& D! n5 c( u
}
3 ?' T8 r& w* H% E4 g- N7 N}
) |/ K! [4 S7 H, @9 t5 U7 _template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
4 k3 _7 m5 I4 o9 z/ q$ Z4 c( F{
+ ]4 e+ U2 @, `) U! V7 M2 a stack<int> s;# ^$ E! [& B1 U# |- d  X1 J+ ]* l
int tmp;
5 u3 l% U/ u& P$ O* ~( R MultiAdjListNetworkArc<WeightType> *p,*q;% ~. x3 q5 F) f- q; z9 s+ d
for(int i=0; i<vexNum; i++)% G8 {, _3 D- s7 v' t( v) b0 J
      tag=0;7 X) z0 |  q: b. m+ W# K( l
for(int i=0; i<vexNum; i++)
% u# K9 m" U" y5 P8 y9 q" U" D5 `% Z {
6 a7 u% v" i" S% j       tmp=i;
  R! d3 y% _7 _6 ?1 N7 ]! p       while(tag[tmp]==0||!s.empty()): J4 n1 C2 J: ~& R
      {- u3 @3 Z8 F6 d. R4 O+ t2 b1 N
         p=vexTable[tmp].firstarc;! Y  U) `4 z, o' q6 G
         while(tag[tmp]==0)! c% Y( x" j* d5 R! e
         {
1 N3 T: v/ @/ z; l             s.push(tmp);
' K: F& B2 O8 |8 f8 }' I             cout<<setw(3)<<vexTable[tmp].data;1 r4 [" [0 v& K* `( t
            tag[tmp]=1;
5 H+ K" H7 D; Y3 I7 G- ]" n             p=vexTable[tmp].firstarc;
* q8 c* `$ Y7 Y8 O  }             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for, i4 x# B3 |# K3 a1 C1 Q
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
/ C1 f$ ?3 p: F2 ]3 U; g             //cout<<" 1st    tmp="<<tmp<<endl;
7 [. Z4 _; B- F% q/ Q6 C          }5 Z4 v3 ^# k% O
         if(!s.empty())! I9 p0 P' ^; j3 @# R  R1 e6 g, T
         {/ ?1 n7 ?' M3 n6 @- G7 ^6 H5 u
            tmp=s.top();. u1 n& t2 x  W# r) T9 C3 ^4 R
            s.pop();0 O5 F! u# i- S; h. O% J3 m( C
            q=vexTable[tmp].firstarc;4 t1 b* d% C+ [( Y* U5 e
            int t=tmp;
) E& W+ p% o! w% ?             while(q&&tag[tmp]!=0)# p% \! c  r! ~9 P& M7 d3 O
            {
. h4 `7 Y; a- w3 u, J                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
* J9 e: U  F% I8 S                   //cout<<" 2nd    tmp="<<tmp<<endl;
1 O/ y) B; c8 f$ g# H: E                   q=NextArc(t,q);
+ Z  D* y8 y" D$ w( ~6 {             }5 B3 D9 v6 A4 Z% t
            if(tag[tmp]==0)
2 i+ R6 ?+ Z# _; e/ J6 t4 |                   s.push(t);
# z0 i% `5 a8 s* ?/ g/ q0 M+ }9 |             ///1、对应上面连通分支只有1个点的情况& h& ?7 V2 K; M! W; A3 U! |+ d
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
3 x! c5 g- U0 G& ?6 S* g1 Z             ///tmp要么等于找到的第一个未访问节点，+ ^1 ?  }' e9 [* ]/ l
            ///要么等于与t相连最后一个点（已被访问过）
/ q8 b4 u% `, z* L             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
* e8 J* o, Y/ z. m3 q' w; p; w, ?$ T          }
, X6 B8 e1 |) Z* j       }# c8 e, m/ h' l3 Z  r$ h
}
% q) J1 t8 G) B; I# D9 L4 }: L}  t9 j" ^! u4 S2 Z" g  l
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-14 k% K- O6 K$ x' w: s9 P/ K  G' {
template<class ElemType, class WeightType> int
8 k  L$ n( V" e2 Q/ NMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre), ?" T; A3 @# @+ q( D
{
: W7 Q5 F) N* G) R3 k- c  e( P8 B if(head==pre)! l+ a  x$ n- L7 a3 G2 ~
      return -1;
0 X" q% {4 J& q7 ]9 p" x; I! p+ `' D) f3 ]! H( ~
MultiAdjListNetworkArc<WeightType> *p;
( m! C* L8 O5 ]0 z p=vexTable[head].firstarc;
2 `. V9 Y- L2 y7 N if(pre==-1&&p!=NULL)0 z0 i2 l0 @2 |5 m, e% d
      return p->adjVex1==head?p->adjVex2:p->adjVex1;: n5 R; b4 X' w! O9 {& Y0 g! U
//pre!=-1&&p!=NULL
7 r& ]6 c$ L  ~* W while(p!=NULL)
+ S; l9 q  q3 W& o {
4 n7 r+ j. [1 {/ L) s2 c% B       if(p->adjVex1==head && p->adjVex2!=pre)
8 P( O; g2 ]$ O- v5 Y          p=p->nextarc1;1 r6 H1 I. E* N7 H) c- h: X2 [
      else if(p->adjVex2==head && p->adjVex1!=pre)7 L8 Z" Y( M% H. K! y4 T' G
         p=p->nextarc2;
) E" e- W. w4 w1 [3 J" F       else if(p->adjVex1==head && p->adjVex2==pre)
# y" F2 j0 O9 T  D       {: |4 G; |8 p7 E3 K8 K- U5 ^
         p=p->nextarc1;1 K" x0 p5 p) }" S
         break;# Z5 c% p) F6 t( j  D" q' m
      }
: E) g* _/ B5 l% B; B       else if(p->adjVex2==head && p->adjVex1==pre)
9 P. k) K% E$ w1 V, K7 u       {
; d! p2 }7 ~! o1 ^; [          p=p->nextarc2;7 B4 o& Y& J/ c1 z( Y1 C0 `( c
         break;
1 _+ J, z, D9 H% |0 B. v       }1 u0 E. I& ^0 ?# q6 f. g* `
}+ P" T, [4 E- \- B
if(p!=NULL): }+ s+ a* L* q9 Q5 s8 Q1 `
{" q7 ?2 u' S" z9 T
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
1 W; M5 X* Z$ @/ ?4 T3 \ }3 e" h0 O6 \' O8 ?9 s; M) p5 x
else
0 O- O9 t: W/ e' D# ?       return -1;! `' w5 D+ C6 ^4 J% I6 p
}0 l  \4 }6 C# Z. w* H8 |8 b

$ H, @9 l2 n6 U; x  i8 h1 P
9 E& O$ C* d* M1 |. k8 i6 Dtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()5 n  Y/ |" O7 {! P
{
. k6 C7 i' I1 M0 d# A stack<int> s;6 y, F) U9 H. l) I* b5 E& r* t8 r
int p,cur,pre;
. q) s; }* F$ U0 p* S) G6 z //MultiAdjListNetworkArc<WeightType> *p,*q;
: e) X7 Q& P+ f/ Y# r1 N for(int i=0; i<vexNum; i++) tag=0;//初始化4 b% ]- }# C; Q# Z( d" Z# `2 j
1 N, T; a! O' \3 X5 `' e
for(int i=0; i<vexNum; i++)
8 H4 C- D0 @5 Q* J9 Q {
4 g0 e$ U1 z* H* ]1 N3 l# R) V/ }7 m       cur=i;pre=-1;( Z. \0 ~3 m5 I0 q8 ~: W
      while(tag[cur]==0||!s.empty())2 Q' R) l: g/ S, Z& w$ U
      {$ x8 S8 z* l1 H, g6 v8 ~8 X
         while(tag[cur]==0)
' ]. R5 M% T1 a, p# z1 g' D3 N5 z          {
, n: K! s( P% C4 v" J6 N) }3 s             cout<<vexTable[cur].data<<"  ";
2 p8 l* V7 K" A0 J# U: M1 R3 l             s.push(cur);: A' B& |) N- A& ^! R9 B8 s( ?! ?
            tag[cur]=1;/ U% H2 \6 {# A& N3 M. t; t& t( f
            //初次访问，标记入栈
$ H( r8 w7 {" |! T$ m$ R7 q8 R! O7 y
% z5 B4 n( C& Z9 U  M2 Y             p=GetAdjVex(cur,pre);//p是cur的连通顶点
2 @8 S7 Z; n9 f7 Z1 }             if(p==-1)9 ~; p! O; m; d
            {* J( A& ?0 N4 [1 F, h8 m
               pre=cur;s.pop();
, N' l" V4 S4 P. e+ L5 p; H. S( k                break;
* R7 G8 d* ]  Q; g) M             }
6 b, C; e6 T: ~4 Y4 ^& v: T             else
9 `9 R6 M+ h8 [5 l- f: O) K: G* T) @             {
( L9 J/ |3 v1 y& D                pre=cur;
: ]! K3 v5 y: r* g                cur=p;
7 u1 N# l# ~4 ]3 n4 _; m& Q' \" K& C             }! r- ]7 m" y! ]

( y5 u# O& n6 @. E4 c          }
0 v, C( h! ^0 e8 t          while(!s.empty())0 W3 C% w: y2 A) e9 j
         {
. Z8 C/ s0 l/ G) ?; y% f. {             cur=s.top();
+ A% k: P  u& c4 p3 U/ a             p=GetAdjVex(cur,pre);
- Y* T' j$ G- Z8 a4 O             if(tag[p]==0)9 R* r8 V" ?' N: X
            {7 U$ Q5 C  H0 P1 ^* Y
                  pre=cur;1 ?, D# {1 f9 N: t+ p
                  cur=p;& B7 H9 Z: ~* F/ Q: o
                  break;  f, ~2 c' e" w" G
            }
) A% s# r, w; M% i2 \             else2 N8 K" f; N& p$ n2 d9 D9 g
            {/ M8 b. f8 t1 e4 V: I) Y
                  pre=s.top();$ m+ I' W5 X' t* I: v
                  s.pop();
  D+ k" @& A. ]6 S/ o# m5 L             }/ a  ?- o5 d1 A. }

* O( F5 u" ~$ q          }
" u9 M% q5 w6 j. i& M4 @  g  K0 L
4 @. M' m( E9 W! k9 ^' D$ C/ d       }* q' h* ]7 G% Z% p8 d
}/ p- n# m. Y+ W$ m# K- J) H
}
! }: O1 S0 n, M( `, `. Ntemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()5 I2 Z( N! O7 ~' M5 ?& V% s
{
5 `& g4 O! _; v& | for(int i=0; i<vexNum; i++)
9 B& h5 k% F* L. h0 x/ n       tag=0;: @% U  B4 y" k. D$ s- ?# \
queue<int> q;- H! W# O& I0 n2 J
int tmp,t;2 H3 Z- a$ T7 ]
MultiAdjListNetworkArc<WeightType> *p;
2 p+ l* @! M7 }5 L" H7 b/ s# a2 A) p for(int i=0; i<vexNum; i++)
( v+ ?: ^; t/ z1 n: f) d: n {( O$ l! `6 b9 q2 x
      if(tag==0)
' o) a, j7 V; m+ m# P0 v) W) q       {
* c" e; @' {6 U" @7 J& ?% {' H          tag=1;
9 V8 n3 R5 e  p8 A' ^( Y          q.push(i);
. j1 u& ~5 u8 h0 o5 t          cout<<setw(3)<<vexTable.data;
5 ~8 d' b8 F1 b       }
% d9 E2 j' I) C% _8 F8 W       while(!q.empty()); f0 S' a7 Z" ^, j' K
      {+ h' T7 Y5 {( N3 f
         tmp=q.front();' Q; \; L# h+ [& h8 O
         q.pop();
2 ]+ I* {# B# Y$ b          p=vexTable[tmp].firstarc;: G& X7 ~! g* N1 R
         while(p!=NULL)- T, p* d' U3 A% V% N  ?
         {
" f" J+ C7 b# j, F* J4 t7 e             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
9 M1 p- W, p: m* f             if(tag[t]==0)
) Q& M5 d1 x- |5 }4 m$ y7 ^( D9 D  v             {
5 n7 z& E8 E( A9 t                   cout<<setw(3)<<vexTable[t].data;
2 [( a5 {- K. B( V                   tag[t]=1;
, ^9 w, p" T% W1 k                   q.push(t);
- m# s% ?' K5 q% g             }
, I8 p) b1 }( w; J9 a" |             p=NextArc(tmp,p);
7 f4 k3 K( [7 |          }
8 G% o$ }9 t4 k. ~  Z& }0 x       }+ @4 s+ H/ _! L
}& G# R" U* G4 w/ W
}
  Z. o  S! D1 R0 K. e; \template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()  }, M' E! ~% `7 W8 k1 f5 B
{
( h0 F( s& d5 I: ^5 Q, Q MultiAdjListNetworkArc<WeightType> *p;" P* }) v. m, F! p
cout << "无向图有" << vexNum << "个点，分别为:";
  i% k. h. p* h  h for (int i = 0; i < vexNum; i++)
* S9 \7 T/ B1 p6 y2 e1 Q! }       cout << vexTable.data << " ";
' M% Y* B4 d; ~% [5 D- w0 \ cout << endl;
0 B$ f, @8 P  t1 E8 M cout << "无向图有" << arcNum << "条边"<<endl;( I3 L, {2 g  L# R0 U5 L( Y: w  ^
for (int i = 0; i < vexNum; i++)# [% S; v) L. P' E- b) x0 s
{/ ?; T, }8 f% O
      cout<<"和" << vexTable.data << "有关的边:";: W! I- ?3 u1 t6 |6 v1 i- A- x
      p = vexTable.firstarc;5 k) Y5 @2 K7 ?
      while (p != NULL)# A1 |( T; k1 Y9 n
      {0 B+ \& Q7 H, y7 f
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";4 m- Q' i& l; _& B* Q8 z. y" e
         p=NextArc(i,p);; a3 z$ h2 q: M( l- G
      }1 W; E8 N9 Q, x+ f; l. p
      cout << endl;7 s) @: g$ H7 n& ^" s: V
}. t, C( m1 ^" b: k
}
- a, G8 ^/ U3 m4 _
+ z' P3 w8 [4 C; j' t. p8 p" ^5 s, e0 K, e
邻接多重表与邻接表的对比

$ b8 q" e! q+ A3 L# m* I邻接表链接
. X5 @2 l. ~$ R, N) \6 P在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
( E" A) M) `/ p8 ], g1 A8 E& e3 w6 K) H在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。2 B- u- ~" ~0 L9 v& r+ J0 o9 x6 y
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。: a2 @" K  T0 @0 y0 M9 J' w) G
————————————————
% M; h4 N6 K: ~5 w# I5 @" T版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
2 ~& @- r; b0 I原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
$ h3 R, T' S( P  N( S# `" ?# \
* f6 E( I, X+ c, X
: ^1 }4 ^# k9 i' L9 z2 p. B
/ w% M$ g1 L5 b0 ^1 Q( E: p- i' W0 z6 L
————————————————2 C; _4 F" q& A3 I7 j) t
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
7 Z* s7 X; b3 G( [' F原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
: a# L$ q  B9 V6 Z7 s) N
! M; S; ~8 C8 j' l+ h
2 \, O4 V2 I5 J/ p6 B/ B