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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
' n4 {9 x D5 P& kdata域存储有关顶点的信息；8 D9 V9 D0 G9 Z9 E. Q% W" M
firstarc域是链接指针，指向第一条依附于该顶点的边。& p. e+ ]# t$ ]' E" I
所有的顶点结点组成一个顺序表。

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;. _" c8 `/ O' F/ n9 y
for(int v=0; v<vexNum; v++)
8 ~9 E  X1 f) b6 ^ {) ^/ {  U- L7 J( c' v- `
      if(tag[v]==0)( x9 K* @. a( w: C* e
         DFS1(v);
1 T( a! Y& ]! T1 h- Q! r9 H9 h }
1 C: ~5 E, E4 Y; h* I% G' M- S}* o% w+ }7 l5 C+ @
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
' _7 B/ p9 f/ Q( V7 s5 S{) H- e" L* R( g
stack<int> s;
! T/ J2 B, u9 C2 u: H$ N int tmp;
( T1 u) w* V' V, @0 ^' [" x* ` MultiAdjListNetworkArc<WeightType> *p,*q;% y! E' h9 z5 R4 i! d
for(int i=0; i<vexNum; i++): B$ {/ Y: I) ?; r" n  Q0 r
      tag=0;# t5 W7 P' X' g1 f1 f' r5 _2 z3 ?- K
for(int i=0; i<vexNum; i++)& ~: R$ x: U& _' G5 c  V% q+ |
{, P6 w" V1 c  q8 o9 Z* O* K& o) S
      tmp=i;3 K2 t" k' T7 y7 I
      while(tag[tmp]==0||!s.empty())
3 s; \4 o+ R, a; c9 j) E& {       {
; L5 j$ i+ Z8 X1 j; A7 d1 l, z3 A5 L          p=vexTable[tmp].firstarc;4 e7 i3 \1 [$ W  D- Z
         while(tag[tmp]==0)# U! P& L: r: A" Q4 ^! J
         {: p% l% e% H+ E: D4 `( ?
            s.push(tmp);  b, E# h4 j. T3 \# R
            cout<<setw(3)<<vexTable[tmp].data;- V+ N# w& W6 C$ `
            tag[tmp]=1;
3 }6 V  w  J" P7 k! P3 ?; _8 h  P             p=vexTable[tmp].firstarc;
* x. m( t4 H: i- b6 t             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for; x" V1 `) V' R7 t0 W+ R& `: S
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
( @$ ^7 m- J0 i1 X( t             //cout<<" 1st    tmp="<<tmp<<endl;
; ~- J% p" P& Y" g8 u! ^, n          }
; v- E, s! C$ n          if(!s.empty())* H" H3 x' }  k, ^% }( x, y
         {0 P% O4 @5 w$ O9 B; k0 w
            tmp=s.top();
) g5 O( ]3 W6 D5 p9 O" H             s.pop();
+ J4 e8 Y2 r1 t2 y0 X+ ~             q=vexTable[tmp].firstarc;
% G) g) h3 ]  D/ N             int t=tmp;  L0 N8 _# t# f$ G: i
            while(q&&tag[tmp]!=0)
) C* o0 j5 w0 Q% D             {
. Z& G3 k9 g: ~! m) q                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);& |2 Z  q* L" u" n
                  //cout<<" 2nd    tmp="<<tmp<<endl;
9 j2 D) q. |6 Q1 T# L% W5 [; Z                   q=NextArc(t,q);
, ~' [' E, R/ n6 z6 P/ m6 z. \             }
" C( z% Z; s* d' O! `+ i9 ]             if(tag[tmp]==0), b1 r; B- d0 @  q
                  s.push(t);
" T4 R: C+ O' E) b. H& M" K             ///1、对应上面连通分支只有1个点的情况: z, [+ `7 L) V, p
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈6 m0 C; U& O2 `! {5 v
            ///tmp要么等于找到的第一个未访问节点，
3 O* ~" g: z# k& S8 \' L3 L             ///要么等于与t相连最后一个点（已被访问过）+ i  f3 m5 M, J% }8 f9 {. C" H+ y6 X
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
" S4 {2 Q, d. V! k7 V: s          }
: E/ C( E; J8 i, ]. S! O* h       }; w9 o/ @& y2 O
}
( A, f1 L" Z8 m& R/ j}
4 Y! o2 g- b1 Q+ \//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
, L- t' _* h( H6 i/ _4 vtemplate<class ElemType, class WeightType> int
: e" K$ ~; R: ^' U$ R9 vMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
& I6 c, b2 \7 q; T" z' r{* D9 I9 i7 f6 E7 t( d1 G
if(head==pre)
. s( E7 M" g! D       return -1;
/ n3 O. [/ c3 U+ K9 `0 N0 Z6 e5 k* P+ T4 }* J
MultiAdjListNetworkArc<WeightType> *p;, R, \& s- R8 K. k+ r9 S, Y
p=vexTable[head].firstarc;+ ?4 s9 S4 N: N
if(pre==-1&&p!=NULL)
$ Q1 @1 y- R5 v2 S4 r4 f       return p->adjVex1==head?p->adjVex2:p->adjVex1;% v: `: g/ g( j$ V& h
//pre!=-1&&p!=NULL
) _2 M% l( V/ l& U: y, i1 X while(p!=NULL)4 k6 c: \6 f+ X
{
) Y7 z* F+ v0 }8 N% T1 e       if(p->adjVex1==head && p->adjVex2!=pre)- Q7 b/ ]6 I( u% l
         p=p->nextarc1;
* G  d+ c' {) f  r% L       else if(p->adjVex2==head && p->adjVex1!=pre)
2 {7 P+ o) Y1 I/ l- _          p=p->nextarc2;
& u% @2 ]7 f* |" G# o5 X1 p       else if(p->adjVex1==head && p->adjVex2==pre)) T; A- d; t& B- i* w
      {
$ R$ p8 o$ S2 ~5 Q' |* {          p=p->nextarc1;  z$ D1 m( D* g
         break;
3 Y* M  v& l, T# G       }
" y$ ~, V* o: n# @8 B2 ?6 b       else if(p->adjVex2==head && p->adjVex1==pre)
1 @" w7 D2 R2 l+ c% ^( l8 Q$ H8 w       {
" y  x% B; Q/ j4 t4 w2 E0 v1 e8 ?          p=p->nextarc2;
4 J) a2 a% e& z3 B$ P4 y          break;
/ u, M& ~1 _$ `& H2 I$ g       }6 E/ q! n7 S7 E6 l; b% Q$ D! I
}
) b% N" j/ n/ F, I if(p!=NULL)- g& ^0 |& Q" {; k( j
{
9 ^& e$ O# }4 P0 O4 d       return p->adjVex1==head?p->adjVex2:p->adjVex1;
  u' `$ O) I6 N5 o( K3 x }& ~7 H/ M, Y- ]5 V
else
' Z( c- y' D) b+ s" D% y. U       return -1;
& c( M) \2 G& H" _8 B$ a7 T}
" ^( q+ W, n2 N  }' X1 m: J( l7 ?* v- J0 C
3 _1 w) Q" [- \7 `; [# \# Z' @% o' {
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
9 s, A, p& O) P& E& f+ b, r{
; c) O- Q8 k1 f stack<int> s;
  q# F) P. o7 u" W8 u0 C int p,cur,pre;
" l  ]/ O2 Z# S" e+ p0 j //MultiAdjListNetworkArc<WeightType> *p,*q;
- g6 z3 q. _7 p7 @" J, H" F for(int i=0; i<vexNum; i++) tag=0;//初始化
$ R9 N. P$ i& y6 r1 M- Q# h% \% v7 |$ e% L7 ~
for(int i=0; i<vexNum; i++)4 P& C$ V- B3 X% G
{
6 g" D" a; S6 i5 M- u       cur=i;pre=-1;
) X7 I& k1 g' K  h, M       while(tag[cur]==0||!s.empty())
/ L7 @( H# F& ^5 ?" w- Y       {2 l8 `6 t8 ?3 z0 u8 |* y
         while(tag[cur]==0)
+ F, w$ j) r$ [# X1 g, b% o          {
! e) _3 {; l  b7 E             cout<<vexTable[cur].data<<"  ";
7 v8 g: K% |# e( T2 }1 w9 c             s.push(cur);
9 o7 R0 a' v5 T$ s$ ?8 t! r# j- }             tag[cur]=1;: L8 t) l' ^6 ^' x" U0 Y3 Q
            //初次访问，标记入栈
4 _& ^8 k# i& ^+ M7 O1 K" f
            p=GetAdjVex(cur,pre);//p是cur的连通顶点7 L: P: j$ _' K2 h
            if(p==-1)
$ Z' \% a7 j0 ~# r             {6 u8 S* i# o" c3 D! T) W* J& l9 D
               pre=cur;s.pop();) A' O9 n( t" \2 K. U9 P
               break;
& u% e+ m# C. I* u+ d             }7 G  W7 y  |' P! r! T+ U: k
            else7 U, w! q/ i, i* J& i
            {
/ s9 F2 M1 w0 R$ ^, |6 r  ~                pre=cur;, @; y" Y; ~- L: q$ g8 R
               cur=p;
# R$ V7 w' s* k7 I2 S% [9 l             }
6 i# D0 K" S% s; g' G
% m- W" z3 }$ A2 \1 S& M, S) d          }0 e1 ^' P& v7 ~; @4 |
         while(!s.empty())
" t) ~" U; i! E& h$ X9 |- C          {
; M/ I, A% ^- w6 v             cur=s.top();1 t0 C$ A/ Q8 l; C8 [
            p=GetAdjVex(cur,pre);! x+ [, a8 z' d: h0 K3 }) ~" N
            if(tag[p]==0)9 A" Q( P- R/ c# `8 M* V8 t* a) R
            {
6 R9 `, R, K% u7 o/ @; M. @9 h( S. {                   pre=cur;
* B3 c1 u" v' h6 r                   cur=p;
5 a$ V$ |3 C4 |! h" B! E0 y( @/ a' u                   break;7 p, x, }( E+ y" |
            }
8 z. x4 u' X8 Y. m# r6 W             else
& I9 n7 K5 o$ e8 ^" t2 N3 Q3 O* H             {
: a- g; x$ V. K                   pre=s.top();+ j& H# b4 l1 I7 U$ o
                  s.pop();" r0 M2 H) ?, H+ ?. S; [1 e
            }  B' z! u; E+ O2 l5 K2 P
0 f& s3 o/ l# W8 e, B, ]
         }6 ~2 c7 N  R, u0 a
& z+ k& V/ _+ O5 i; x7 J3 C$ o" W
      }- T8 K: R9 \" P* m3 M
}4 _  L$ I; J- l; E
}
" @: L- B/ h6 K" b/ |& Ktemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
8 X" u6 U/ L' P$ w1 D{
8 X1 G( s! H: X: u' R for(int i=0; i<vexNum; i++)
# \5 {3 I7 F6 _; i& c       tag=0;
' c- V8 D% A) `! M queue<int> q;; v$ M7 U5 J1 I4 s
int tmp,t;
9 P7 K4 `% L& W) A MultiAdjListNetworkArc<WeightType> *p;
7 X: ?' S0 w: z; D; B) L& _" Y4 } for(int i=0; i<vexNum; i++)
% U/ k  ]8 L" Z9 f+ J6 R {  J& x4 Z2 r8 N9 `2 Z
      if(tag==0)3 m# F' f0 L$ P+ x( I4 K
      {
) M, c- ^% I/ l0 v! [$ c) f) y( m          tag=1;
0 q1 [0 f* p8 ?3 r, k          q.push(i);+ \/ Y: Q& Z, E
         cout<<setw(3)<<vexTable.data;
8 @+ v1 U7 X0 _. j  }  e+ l       }7 }7 G- e* i2 J# E
      while(!q.empty())8 `: _! O8 O% a7 {; k6 p, z
      {
& j5 E. k( c6 `- @5 T5 ?          tmp=q.front();" o* p0 S8 B* ~3 O) r1 j
         q.pop();
% m& l% B  p! I$ u4 W3 O          p=vexTable[tmp].firstarc;
2 B- Z' f" h6 ~          while(p!=NULL)
8 J0 p" _, |* i% r          {
" U8 t6 L& h6 B7 ?" z" P8 i             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
) K: s& A% f/ a; O             if(tag[t]==0)
. t- `1 T# N8 U8 @  z: I" H             {5 Y- j0 U5 d3 p, H- Y4 O
                  cout<<setw(3)<<vexTable[t].data;
0 ]; d  ?) w5 k- h/ X                   tag[t]=1;1 F* _0 _0 {2 t
                  q.push(t);
! e1 M  W) H/ U* ?9 w             }
' }! p$ q8 v& w9 D( R4 i( H             p=NextArc(tmp,p);
& r: G; q' ~$ f          }
9 b6 N+ i3 ]6 C  f/ j: X; ]       }2 B0 d, ^4 g3 b; N: s
}
/ o: \9 \& n+ N! ^0 o& R" U}; L/ R6 _* W3 |  Z, ~$ L
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()$ T  @3 x2 |/ N/ z2 G( f: K
{
) R8 n* R% S+ } MultiAdjListNetworkArc<WeightType> *p;( U$ O* g2 t- A, T2 H& s  k! z
cout << "无向图有" << vexNum << "个点，分别为:";9 I4 u, {7 z1 s$ U1 _
for (int i = 0; i < vexNum; i++)
0 ^( ^# Y1 |- @4 D) N0 E8 B       cout << vexTable.data << " ";
1 B3 M$ A( `* P$ e cout << endl;% i6 i  k( k6 H5 e  S
cout << "无向图有" << arcNum << "条边"<<endl;+ R0 o& Z: |0 J1 p5 |7 @
for (int i = 0; i < vexNum; i++)6 u6 u0 m) o- y0 V( H/ Y& y) U4 B7 T7 ^
{1 q/ a5 L. n* G$ G
      cout<<"和" << vexTable.data << "有关的边:";; A2 ~- ^' u3 r8 k, Q
      p = vexTable.firstarc;5 h# w; [& r1 _  B+ f
      while (p != NULL)) B% Y- {' d2 k! Z; ~- x
      {
. \( Z) ^+ `- b: d: F          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
) k: l1 {4 }+ X7 R: r          p=NextArc(i,p);& `* L/ D2 Q* y) I" N
      }+ E* [! e, B" q6 h3 `1 A6 ]
      cout << endl;3 E) Q) c3 j$ u6 L' ^& a
}. |1 @# n! g: e
}
# f' B- w' B+ b$ D! a8 I. s) r, \& [7 d( g; H* t6 l+ z
1 p" q6 o# z" {8 I
邻接多重表与邻接表的对比
; K. [* |" m' Q6 j( ~3 d: p7 [: ]5 d- z- {$ z. p- g( n, y+ U' }: q
邻接表链接
1 _8 s/ s; k, Q+ A: G! _在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。1 [" r# V& m- q0 U. B8 ^6 a4 Y  `
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。+ q4 f# e+ O, _$ J4 [0 ?
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。! w* a$ T% ^( f' i% }, m. y1 i) \
————————————————
7 \( `4 r& }0 E% C版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。. K9 f4 T9 K. j" Z9 i, P! F3 O6 W
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958, i# i+ y) K1 I9 C
( }1 R! ~% _2 |1 s4 `

2 r2 k6 h8 `/ D9 \
& b# y' R. o4 J8 \6 ?% M4 V! W; Q) G9 y+ i
————————————————
4 v! H( R0 W: C& L. @/ |版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。8 z6 Q) ^" Q9 o2 v9 E
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
9 E, i3 M4 A3 H2 Q% O
6 z( W( G, C6 w- q% d5 p, Y5 U$ i$ ?# O0 G