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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：6 b6 u; A5 ?) `4 |7 U1 L7 G
data域存储有关顶点的信息；0 z) ?+ _ T& H# z
firstarc域是链接指针，指向第一条依附于该顶点的边。
7 E3 J( P# {! e" c0 |6 q5 {, }所有的顶点结点组成一个顺序表。

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;
; w& c2 _) t9 w) \% c, |* i for(int v=0; v<vexNum; v++)3 B' V8 W0 l" W- C. W* E8 d
{
# S8 a3 y/ V9 Z2 ~       if(tag[v]==0)
/ a2 t" w. O0 g          DFS1(v);2 L. K" J4 Y# S6 h4 M! A- h
}
: {) ^) o, }# {" `: v7 U}" F' ]( q' s; V. N( _* ]3 X7 c
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
% N1 ?. r1 h- M: Q3 l6 w{
7 K8 W  L! n$ _) A2 \2 L) |9 N stack<int> s;( D- G6 m3 g- C
int tmp;
/ `/ P) c7 u: H* \  r+ P MultiAdjListNetworkArc<WeightType> *p,*q;
  G) L8 S/ W; P6 m for(int i=0; i<vexNum; i++)# }, ]5 x& m9 U+ g
      tag=0;
7 M# C" k! \- q" r/ v1 j8 | for(int i=0; i<vexNum; i++)7 K, j5 e2 m$ h) q9 e+ Q
{
0 p* i) I; H( {, I- }       tmp=i;
0 g$ _' X- n( w4 G$ Z* N; [* X8 d       while(tag[tmp]==0||!s.empty())
& \/ @" O6 [/ a) g6 \       {7 C. z9 C% o  D" ~" X( N
         p=vexTable[tmp].firstarc;
- O: f  E7 B( _8 ]3 ^* R          while(tag[tmp]==0)
( }4 i& h  ]) h2 a: v+ t5 M- r          {
2 [' h* T$ A- M; |3 j             s.push(tmp);
7 \, u! i/ |+ w& x             cout<<setw(3)<<vexTable[tmp].data;
) _) Q* T5 R, Y' _2 D             tag[tmp]=1;; k7 z" O- D/ n: ~$ _
            p=vexTable[tmp].firstarc;) h% j& @( {# f, c" X6 P' {
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
0 a$ V! r( Z4 ~             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);+ e9 {4 D) |. V  i, q4 \
            //cout<<" 1st    tmp="<<tmp<<endl;
1 [9 q. J( k- ]  I          }
6 o! i/ V* I% H0 g. ?8 L          if(!s.empty())
         {  ~7 E0 Q5 T& d- T
            tmp=s.top();
/ k7 j+ c0 X. x2 E  O7 E! D+ v/ |             s.pop();
6 f1 g8 j; |& \& e             q=vexTable[tmp].firstarc;: ]  |0 A4 R" v! `. {. I
            int t=tmp;
( N; q' H0 s, w2 _6 A: h             while(q&&tag[tmp]!=0)5 l9 |; T# _! N3 C; H' O4 Y! \
            {# s! z5 K) e# Y+ u1 F+ X$ [7 _) I
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);0 Y9 A; Z" n5 c. e5 ]1 i% ?0 \
                  //cout<<" 2nd    tmp="<<tmp<<endl;
& t. O' ]* j  ~/ Y6 L( c- N                   q=NextArc(t,q);. w4 f* I. X7 |9 x( c1 y
            }5 u# O1 _9 r0 _! k5 R
            if(tag[tmp]==0)
# a* t2 g7 c- g8 H9 d                   s.push(t);
+ o+ K- r! d2 L             ///1、对应上面连通分支只有1个点的情况
& k0 |$ G  Z' m6 F; B- ^, G. ]6 E             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
  q8 D  m& {0 B) p6 l             ///tmp要么等于找到的第一个未访问节点，
( ?- o# @6 y4 c) I: q" N8 U3 q( O7 L             ///要么等于与t相连最后一个点（已被访问过）% q: C" c& O$ g, q* a: j( W
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
+ G9 l" ^2 l. r% A          }3 W% V; g* S6 P- {' c& N
      }
# o- A7 e; i2 Z5 N1 u0 k1 I! B }
  T' I7 Z6 U& J* i}1 h6 k: [9 x! |! }
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-12 |2 H3 l" p4 T1 [
template<class ElemType, class WeightType> int  w+ }4 x7 }7 B+ F
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
. b2 ]. y2 @6 p, h( ~" }{
4 C  {6 O% X& B5 Y) C if(head==pre)9 \' E( a& s8 \( ?: W( L- L
      return -1;) }% B$ h+ ~5 I6 T
) k7 n+ ?5 I& l& E3 y9 ^! y5 P
MultiAdjListNetworkArc<WeightType> *p;# N) o0 j( A  k0 n
p=vexTable[head].firstarc;* K5 {% ^! u% Q, @+ ~! Q  j5 w
if(pre==-1&&p!=NULL)/ j) G2 [1 C, Y; u. f
      return p->adjVex1==head?p->adjVex2:p->adjVex1;9 _9 r3 P: {7 I  d
//pre!=-1&&p!=NULL0 j2 e/ @2 X6 R( s& U% ?8 P
while(p!=NULL)
& Q9 t$ O* Q7 Y! L {# l2 m8 V( |$ B: b) B# V
      if(p->adjVex1==head && p->adjVex2!=pre): G' a3 c, y) U5 a, F  L7 }
         p=p->nextarc1;
3 c: r5 n0 l/ k2 Y0 E( w) d" H8 t       else if(p->adjVex2==head && p->adjVex1!=pre)
5 W6 Z7 P7 t# }4 W          p=p->nextarc2;
2 F2 e* {5 V/ z$ q0 J- w; O; [       else if(p->adjVex1==head && p->adjVex2==pre)
! e8 h2 _9 m+ J  @$ m/ t( R1 p       {  ~9 T9 B* ]: m! @
         p=p->nextarc1;
0 G# o- k2 i+ P! N: k          break;5 G" s& I6 w0 |
      }
; q( b8 g0 @. T1 B$ Y0 I       else if(p->adjVex2==head && p->adjVex1==pre)
1 F/ L6 h+ O5 j  r" r" |. U) K       {
8 }# m& }# K) m& `1 D6 o          p=p->nextarc2;
; x3 H/ [0 m+ w5 l* ], O+ y" S          break;
7 b% T) A* R3 `; R4 B       }' y3 [' n+ M  a% q8 F
}& K5 _0 |8 b6 ^0 K4 t) c7 G
if(p!=NULL)8 p" {- D6 v2 Q+ I9 |, {
{$ @3 O: T) r3 v/ v/ c
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
+ r& L9 }" Y( s1 | }
$ o- A$ O0 N' j( ^. O+ T1 j else3 C  q8 _: }3 \, F! P9 k
      return -1;
6 w0 ]3 Q+ u( ~2 q7 J, j( y0 b$ I- \8 Y}$ E( y' c4 T1 D9 A7 W7 M

- f6 W* m* @6 B/ W! t- O
4 K" |. p; T+ E# U8 A: etemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()" I; _3 r0 ?' x4 i% o; M
{
/ e0 Z, p! f, R% ~ stack<int> s;! A  U! V# \- J) {0 ]' i
int p,cur,pre;
) P7 y3 P5 f6 K4 X- w+ s //MultiAdjListNetworkArc<WeightType> *p,*q;% |4 `; d% X7 n0 F
for(int i=0; i<vexNum; i++) tag=0;//初始化4 V; O- I0 A* k9 i5 R* A

. p6 _/ |0 v* m/ q/ I6 } for(int i=0; i<vexNum; i++)- z5 e  f- h& Q2 w1 b1 Y
{
9 Q7 i2 X- e( q       cur=i;pre=-1;& [& R2 U0 [. h# x5 _+ V% l9 C9 t$ G
      while(tag[cur]==0||!s.empty())
$ `) M; P! M9 H) v       {* H0 P- n  M$ m: l
         while(tag[cur]==0)
0 r9 a! n" l$ E. l* H          {
. y" d+ o* ~( l; I( G             cout<<vexTable[cur].data<<"  ";
  i4 d$ K6 u# h+ q+ M$ q6 K             s.push(cur);  Q# g4 d& d6 X' S
            tag[cur]=1;! l5 ?# h; Q1 ?
            //初次访问，标记入栈/ x4 Z1 ], P% |9 r1 F
* A! N$ l8 j+ Q# x/ ^2 D, r
            p=GetAdjVex(cur,pre);//p是cur的连通顶点
" k5 Z; ?$ Y) M) T( D. G             if(p==-1)
; _4 Y/ Y2 `/ h             {
. S6 `8 G6 j. s: Z, _& R, n                pre=cur;s.pop();
; y( t0 m& S+ Q/ Z                break;
# s- C7 j! Q& l6 t# `( x  U8 P             }( o9 R) \- N# z3 h1 l. T+ i
            else% y2 b" |! i8 H4 T2 n2 ]1 T
            {$ o* m2 C% l5 q7 ~
               pre=cur;/ K5 A9 l% B4 [5 v5 t& H; L1 c6 v
               cur=p;
( c4 |) I- K; B  e             }5 w7 {- R# I3 `* A
  J" `1 Y- R: ~& b% x" v1 r- V
         }
! p; c1 _( @: J+ |2 ^3 E; q7 H          while(!s.empty())  j% z! P$ l7 o
         {
6 L6 b" B; _& j5 e7 V4 @' R- s0 C" i             cur=s.top();
) v4 P) _/ ?; d, E) _/ k4 g& |             p=GetAdjVex(cur,pre);
; z+ u; e& Q  L. x             if(tag[p]==0)
" A, h2 C* P* r0 U8 B+ h/ n             {
) n3 j- ^4 b+ L* |; f' r                   pre=cur;
) B" F3 ?" @' z6 w' D                   cur=p;# [. j3 M! Y% n* W
                  break;3 J9 g$ Q1 P# w7 k! a7 Y
            }
& f, i/ o. P& p  M7 m             else! @. k/ O3 o2 ]( T: O
            {
3 U( U9 o- T  d: u% J% E                   pre=s.top();
- V/ V9 }# w$ c) w5 f                   s.pop();: |' D, A* Q: K% ^9 I% }) L
            }, m" C1 X9 i' J" y. L; C

$ r' \4 j9 n5 L" E7 ?; P. ~+ z. p          }& a; O! }4 |" @# G3 E
6 B0 k4 w+ r3 a5 E% |. c" ~  s) m( [
      }7 E  z: u: P5 U  J, `* u& l4 }
}, J/ u. q; b) d1 M
}
. S1 ?# H& K  Y. w( utemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()/ R9 }0 v7 O% b6 Y
{
" A9 ~" F6 L" X# z& J; k( j for(int i=0; i<vexNum; i++), h# p0 |8 c' z9 g; p$ j
      tag=0;
+ e, t+ m9 [8 P& E0 x4 t( S& K. r queue<int> q;
, E& _) `) Q; ? int tmp,t;
! u- H- o! q% E! {: [3 o; X MultiAdjListNetworkArc<WeightType> *p;, v# K0 S% p4 K+ I5 H$ `9 i
for(int i=0; i<vexNum; i++)9 b, {. e6 c/ A6 V6 x/ J# |7 j
{
" {; k; ~- t% r: @( |5 _       if(tag==0)
% v  j9 O2 s, T) ~7 X! K0 }       {$ d( r: |' |& y: G2 u# m* n
         tag=1;
. n+ o6 E# N) b$ H- C8 a          q.push(i);8 S- D5 J- c* {8 h, i, A: F
         cout<<setw(3)<<vexTable.data;
, g0 y8 y6 U$ Q$ S( S/ A       }
( Z/ T5 Y9 Z* V" C4 L       while(!q.empty())2 v! Y: R" ^+ }  I
      {
8 g1 K+ U$ F3 Y          tmp=q.front();
8 o/ D( @" `9 [          q.pop();5 y% U( T7 Z8 {3 J- \; x* G+ ^
         p=vexTable[tmp].firstarc;4 r' J- r6 L2 h* y% {7 k" w
         while(p!=NULL)
7 t% H& u4 n( B- p) }/ ]7 Q4 d2 y          {4 u' B; }0 V( z' V0 X8 r
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
0 p9 [1 @. C  V4 ]8 g8 q             if(tag[t]==0)0 Z+ ~% Z3 I0 S% F6 F2 C. P
            {' U, V5 V# H* b+ p5 L# W/ `
                  cout<<setw(3)<<vexTable[t].data;
/ \7 D/ P0 w2 E1 A5 S0 x& L; ~                   tag[t]=1;
( ]" \3 A; K2 f# A                   q.push(t);- J: ^4 I8 G( Z! G/ W. L8 O
            }
) ]1 F: ]( E( Q0 y* A             p=NextArc(tmp,p);
8 _5 K4 y4 ~5 Y% N          }
4 L% ~3 ]0 Q* n: K: `! C       }
- f  Q( B9 {3 W, w }
+ w" ]: [' B; H5 N}
9 ?& x7 c/ I( t- H# E6 Vtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
( Q6 i5 i3 c1 l& m, R  _{
' c" e! Q; J$ {& O( ]( X' N6 a MultiAdjListNetworkArc<WeightType> *p;
. e2 i+ D' v' J3 t7 h, X. a cout << "无向图有" << vexNum << "个点，分别为:";
/ N/ E: i. {  P/ ~: z for (int i = 0; i < vexNum; i++)
% i6 v8 c, n/ H6 W" Q0 d% R       cout << vexTable.data << " ";
; u1 v+ C5 _! V cout << endl;1 D; V" I3 n; E& S
cout << "无向图有" << arcNum << "条边"<<endl;
# r8 w/ R* o6 T; M5 D9 l for (int i = 0; i < vexNum; i++)$ ^: Y8 ]8 {; J" ^* d4 Z+ p/ _/ \
{2 \& H6 Q  E6 Z: ~2 ^6 d1 B7 t
      cout<<"和" << vexTable.data << "有关的边:";8 Q1 }9 `% l5 `
      p = vexTable.firstarc;  F$ L: x: O9 b" S4 p; S) B
      while (p != NULL)
- X) {4 \1 h! Q/ ]  |       {1 _+ i  J3 q5 ^% V2 c
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
3 D1 K3 U: G% k3 I# [: z' T% Y7 M          p=NextArc(i,p);
# z: }7 H# ~  \9 R4 s       }: t3 B9 K& T+ t. @. I3 u# i6 L1 F
      cout << endl;( V& m! F" Y, {: a4 K  e9 o! y
}9 ]. Q+ `* z# y4 G: d- g
}
) \$ T" t' Y2 F: M+ T3 `8 }) C& {  e
7 L+ X5 e" q5 M/ F& H7 {5 Z# L
邻接多重表与邻接表的对比
+ g( b% C4 {4 q1 L3 E% c# w& m; q. v
( A' k4 ]& M1 k% D  m" Y5 n  d邻接表链接
2 N, g* Q$ p- y5 D$ O; @9 Y/ L在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。  a& d( O8 U& v* d# j0 A+ g
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。2 O3 Z7 b8 P, [6 Y
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。- H6 P  o, v& a
————————————————
7 o! N. z5 J8 `版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
( u; d6 G' R+ o) W% E& ]原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669587 e0 w6 H9 x0 J( M

$ M2 l) J: l5 j; f5 }0 ~  m2 ^" x4 c' l! s# R' |

) l; J5 Z/ j' H" v9 v" x/ m/ V2 X+ d; ?: P5 s
————————————————+ h  h) m0 C, P0 H
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
% h6 y3 A! w5 W9 i7 k- B; M原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
" h4 N& V$ z% b4 y0 c* A+ a; e. ^4 v* c0 x4 T# W8 j: |
0 `/ K: \2 [( {/ q1 g! [