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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
9 K5 h: `* Q. Y/ [; Udata域存储有关顶点的信息；* Y( F" G+ C" _: G
firstarc域是链接指针，指向第一条依附于该顶点的边。
% T' \8 `8 G9 p所有的顶点结点组成一个顺序表。

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;2 g6 c- B3 w; q
for(int v=0; v<vexNum; v++)
% t. M# x3 T, A( t {" |+ K  T# k6 z; |
      if(tag[v]==0)
: I0 e0 r: K0 W% @( N6 \* d8 I          DFS1(v);# r9 M! X$ R8 ]! @" B
}/ W2 U& I: ]/ d% _. m. H, {8 J
}- o" Z( ^/ v$ p* ?, P
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()6 T. @8 u$ e% x, W, A
{* F; G7 z' \: e5 y4 j
stack<int> s;
! Y4 y2 X) ?: \0 h int tmp;6 n2 {1 b0 C3 C# r% s/ M5 j. w
MultiAdjListNetworkArc<WeightType> *p,*q;( e% C3 E' b1 N$ k- ]( k
for(int i=0; i<vexNum; i++)9 I- G" y2 u, }, Z6 |( {: k/ ~
      tag=0;  K0 s+ [1 }  F; J- L9 }
for(int i=0; i<vexNum; i++)* i) H9 N! }8 Q2 H1 O$ F) H  K" R1 A3 W
{
+ V& s4 `0 C) X+ }9 D; }9 A" T  a0 f       tmp=i;2 }7 |* y+ K) P( F4 L$ n
      while(tag[tmp]==0||!s.empty())9 y$ L/ H4 ]# `; X8 X
      {! D2 i3 o, I; _" ?
         p=vexTable[tmp].firstarc;5 ~) T7 P( g/ L& x
         while(tag[tmp]==0)
1 v2 F" b9 r' b/ t# Y          {
. I2 ]6 Z( F" w5 B4 F9 k             s.push(tmp);
" A( p) X( {' C1 E, T* y             cout<<setw(3)<<vexTable[tmp].data;$ t4 E* \/ j: @
            tag[tmp]=1;$ A& @6 A- n7 ~; t$ \1 b. S
            p=vexTable[tmp].firstarc;& Q% a4 ^. f3 g- @5 d) z4 k
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for9 t4 E: |4 o! `2 r" T
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);, E9 r0 b4 U, c
            //cout<<" 1st    tmp="<<tmp<<endl;
# d3 D9 S( B" t          }" B  W: @$ C. d7 ^
         if(!s.empty())0 z' `7 X& h  A4 J
         {0 f0 D; ]5 z4 r& \
            tmp=s.top();
+ B+ F' n* N7 b4 E( z! h             s.pop();
' Q- \( U0 K* y9 `( L* T( \2 e             q=vexTable[tmp].firstarc;; J/ B& R+ t9 o# r
            int t=tmp;
8 h) b  x* {3 c% J% t             while(q&&tag[tmp]!=0)
5 E. E1 Q' A! e             {7 Z+ R. }6 e0 I  A2 C8 H
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);* s9 R, k; B9 L! G, T$ c: R
                  //cout<<" 2nd    tmp="<<tmp<<endl;
+ t. ~- m9 q6 I1 p6 F                   q=NextArc(t,q);
& B) f9 S+ S5 C" T3 _; f" D             }
: ]  ]' d! j: W: z9 h             if(tag[tmp]==0)
9 }8 x# r2 l2 U8 t/ N                   s.push(t);0 g, a+ ^+ B1 W
            ///1、对应上面连通分支只有1个点的情况8 n( D7 A: g' h- n0 S- @
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
1 o0 ]8 K7 |) Q+ A5 V% i             ///tmp要么等于找到的第一个未访问节点，/ x  M4 M) B9 P* w  Q
            ///要么等于与t相连最后一个点（已被访问过）
1 l* V/ z: O  m             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点- o, b) g  ~1 p! b3 e( h& n( `7 d
         }
8 |8 q- o# F. |. X4 D, ~; T       }3 `% d) T! X! }  h4 H: ^* @
}! A; R/ c" j1 F9 Q4 Z  x9 r3 ~8 _
}
6 q& T5 q' |9 ]7 h. `//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-13 h7 V9 ^* M. `' J9 Q3 J/ r
template<class ElemType, class WeightType> int) a7 J5 X6 h9 g9 ^( P5 ~1 Z4 v2 q
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)9 B$ E2 p, a& M. X7 ?
{
- U$ M! j+ E" \, I if(head==pre); e, W, f+ A; Q: w" w
      return -1;) f# G8 C3 U2 m3 v$ t8 A. i& _: k

( w6 V6 C2 O8 r+ b  u MultiAdjListNetworkArc<WeightType> *p;# X: j5 u) ~! w( g
p=vexTable[head].firstarc;
6 x; m) B8 n2 S$ c if(pre==-1&&p!=NULL). g# F1 S3 {; s- ]' e9 r2 J8 j9 W
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
  R$ r! L1 I% @8 g5 h$ P4 } //pre!=-1&&p!=NULL
% K+ I7 {8 Z1 j( v while(p!=NULL)
- L. m3 \0 M! u5 |1 J8 Y. W {
: ]) f+ V2 V- b9 g       if(p->adjVex1==head && p->adjVex2!=pre)
$ R. A& r% v' O4 l' p          p=p->nextarc1;
5 u) K' O9 I. O3 d( q6 i       else if(p->adjVex2==head && p->adjVex1!=pre)
5 Y3 x3 i- ?6 ?/ i0 r5 v+ x          p=p->nextarc2;: I6 h8 p4 B$ O; K0 z+ N$ q+ u
      else if(p->adjVex1==head && p->adjVex2==pre)" D4 v8 W7 m: F) p% v% ?" A" Q" ^
      {  c2 F0 S( `9 d4 t" h6 j: G
         p=p->nextarc1;
: l+ B6 y3 Z0 b* w( J          break;0 x0 `, y% O) Q' O
      }
% g' g; Q& F6 n       else if(p->adjVex2==head && p->adjVex1==pre)
2 N; \! k7 r* R5 V1 L       {$ R, _: y7 C" W2 J; ^, F
         p=p->nextarc2;
, v3 z5 Y; _1 J2 B+ {/ G          break;
' P1 R! L* i+ F# R6 F" G       }
& h9 ^. G4 |8 I }
* ~) s" f5 v' z if(p!=NULL)9 S; a) N) d/ T- m1 ?! n
{1 x# M6 C, @3 r3 {, x# h& w
      return p->adjVex1==head?p->adjVex2:p->adjVex1;& B# C* q! M0 P1 N# {) s
}0 ^/ g. X& Q1 J
else
: y) j2 V3 H' R# p       return -1;
5 g- q' R( Q, q- Z' R$ |' c5 F}
+ S: S' C! x+ }. c% D, e- j  W9 T/ E& I4 S( v
% e7 @! t$ C/ H, t% e5 c- e
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()( @% ?& p, J# m$ o: q. g/ Y
{
% W. L2 v) O8 l+ ^0 y. a) [* y stack<int> s;
7 p6 V; y: h, o+ A int p,cur,pre;
& b/ i  ]2 Q8 p4 y+ X3 l$ e //MultiAdjListNetworkArc<WeightType> *p,*q;
0 P6 ~' {+ A1 e% z3 k4 S3 y for(int i=0; i<vexNum; i++) tag=0;//初始化2 N$ i: w  A' I" I  A6 h5 B
' h" D, ?7 ?% l! `! N/ S9 R
for(int i=0; i<vexNum; i++); H6 Y# _1 V$ T1 k7 A) O% E9 @
{7 E. p, B4 R0 i. X' g
      cur=i;pre=-1;
  T+ ]  X/ j6 ]       while(tag[cur]==0||!s.empty())
( b& l  a" W2 I  \+ f, _       {6 r: t6 i9 G( _- ]) H
         while(tag[cur]==0)/ e/ _/ r! j: m" k0 i/ _) B
         {, R; G3 I, l+ f" R- g  L3 x$ I
            cout<<vexTable[cur].data<<"  ";" w2 O6 q2 C& ^1 Y$ x" l* ^) o
            s.push(cur);
! B% H1 F; m7 H% j             tag[cur]=1;
; ?4 B3 i& |( i0 M5 b' a+ H             //初次访问，标记入栈* _# Z- I/ w( l% j
: \" O# a7 O( T% q/ @- q
            p=GetAdjVex(cur,pre);//p是cur的连通顶点
, Z+ t8 l/ ~- y! l( @$ A& i             if(p==-1)
& U. ^. t, C' q# ?! v+ _# J; u             {( K. o8 a' }! d3 |
               pre=cur;s.pop();
( P1 w7 I% F: _0 A                break;  y5 E6 i- }' o% b% F; o
            }% T9 m  N# ^: Z. B( X
            else! d0 E5 W) r. W) i
            {8 i" J- J6 k" S' P' s- f6 \/ i
               pre=cur;
# B5 n) c, w8 [" A9 l! p                cur=p;
. a- \& X4 b# x& T             }
. X2 ^4 S! O+ m9 _4 g- C5 N1 `9 r' p" v, e, m
         }
; X* X8 U9 `" G- u6 ?( u, M. Z          while(!s.empty())
8 d6 F2 J  J+ f! M0 n& i          {
; Z. @. x% h+ b/ e* i6 X             cur=s.top();" E- n( q3 Q  o% s1 f
            p=GetAdjVex(cur,pre);
2 ~1 K( R" Z6 p, z" }; ]" i3 n             if(tag[p]==0)& X1 j2 }5 y. }5 f0 S# D
            {9 z; G. }6 s+ C$ w1 x
                  pre=cur;7 X) x% @) M0 q+ i  L
                  cur=p;$ E, v" d# c; h/ |
                  break;2 e/ P4 A, }# j1 E& V6 o
            }0 E+ s/ C$ r8 C
            else
) I2 [: h" s: ~" w7 v/ h$ Z2 L             {# p. a+ p* g: t! r- l' @3 f' W! ^
                  pre=s.top();
" P3 @2 G* ~. Z1 f. W, T3 }2 M                   s.pop();, G( b* M! n* }, h5 d
            }
/ ~5 D+ D! E$ C0 u- P4 X9 g: X+ n+ F% C
         }
) d* V" u+ t* R1 b: [. T( G, J! f4 B" G7 C4 _4 \! V
      }
( `  K5 {5 t4 j9 `9 L% c' R }2 Z, G' q7 Z8 L2 b
}
9 H+ ~2 X( H8 dtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
5 r# ^) }0 t) j6 e! u! x{
) R& V+ [# S+ l7 r7 \ for(int i=0; i<vexNum; i++)  _: O9 d4 o% n* z5 g& G. ^
      tag=0;
( J) g4 N! T) R  N: C queue<int> q;2 ~' d; v3 n1 E
int tmp,t;' L2 ]( a* i. Y0 ]0 S% \4 {
MultiAdjListNetworkArc<WeightType> *p;
! j% G" ~8 ?6 t8 y; |4 r for(int i=0; i<vexNum; i++)
4 }8 v# U2 q1 X. U6 Z! s1 W) ? {
: I# p0 j3 h8 I       if(tag==0); x% v4 W3 b% @: ?+ Q
      {; d; C# b+ I" r, I. k4 X
         tag=1;3 t. O9 l( g, |0 T% I% q! {% w8 P
         q.push(i);- {2 d8 f8 w9 `* Y; W8 p9 t& X% H
         cout<<setw(3)<<vexTable.data;
- D( U7 q2 M4 }8 L! M2 J       }7 Y' u1 e9 i# w3 h3 }# r: l! M
      while(!q.empty())4 k3 L4 W+ _# c3 s) |
      {, |1 e+ N$ m+ t8 O, d- k. I
         tmp=q.front();( G+ O% j7 K: x$ ?# Q8 d- A
         q.pop();
# k( Q4 M- U9 y3 @. ^, P          p=vexTable[tmp].firstarc;" D* _! w7 O1 P) x
         while(p!=NULL)- O9 E, L: m9 S
         {( q8 L. Q2 I" E% h+ ]+ V
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
$ E3 h8 o, O7 b( e; \2 @0 B4 e             if(tag[t]==0)4 W5 E# [" n* _/ n" S
            {+ u! w# v; D& K( m+ g
                  cout<<setw(3)<<vexTable[t].data;
1 ?0 b/ q4 e6 P  V7 o                   tag[t]=1;
1 a) r6 w9 X, {/ J                   q.push(t);
0 l2 w+ R) h! A) V* J+ l             }
' j, r- P9 r' s/ t4 T5 \7 b) [             p=NextArc(tmp,p);
6 u( f# R, k1 L8 y& z* r0 _% R8 G2 i          }
8 @7 F/ Z2 t) f! R       }) A6 Z+ N* K! Q
}! m* i0 a1 z$ `$ B, q
}
+ L2 x# ^+ Q8 ]3 g* }1 j% ~) J4 Ltemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
& ]1 W* c; X, d{
# [. a' _  k' a' f9 m1 y MultiAdjListNetworkArc<WeightType> *p;
, R3 G/ O- W  A$ Q  o cout << "无向图有" << vexNum << "个点，分别为:";
- L4 W, t" O! d5 o# ~/ a5 \+ p& k; s8 ] for (int i = 0; i < vexNum; i++)8 b& S) R( R9 p3 O/ o
      cout << vexTable.data << " ";
- M: D& I2 G3 b! N cout << endl;- O; F5 C; F/ A% s! o
cout << "无向图有" << arcNum << "条边"<<endl;
8 O/ F6 G  E- s. H9 @( d for (int i = 0; i < vexNum; i++)) Z+ ~9 e( e7 B, i& Y
{
7 y4 E: X. Q2 Z6 ~- E2 ?1 `3 H$ |       cout<<"和" << vexTable.data << "有关的边:";; n% I/ A# W% O, Q# P8 F
      p = vexTable.firstarc;1 K3 l  `) _2 N4 i, B
      while (p != NULL)
: W- Y4 J2 \& y6 m       {9 J  l+ l! ~0 G% P
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";+ u. V2 f" B3 O0 Z5 ~) \$ h
         p=NextArc(i,p);" Q1 V. Z6 a1 u
      }' r$ I# F2 [6 L4 Z) i* N
      cout << endl;9 X+ _$ z5 `( ?
}
& f8 B: J1 x7 n$ V; V$ a! _}! g* p, A3 S! S/ v

9 q8 @9 \( C' d8 r
" L1 G/ c( M4 D" L1 a1 _0 S邻接多重表与邻接表的对比. e5 ]0 H: x6 V% W

0 j3 k& u# r) E9 l8 y1 S邻接表链接
& [! @5 ^5 Z0 p, n: W8 M在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。0 u2 L8 K1 m0 p- Y- Z8 e* h% A
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。+ _* N( x! f# X  G- j
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
$ O6 \9 |* T9 k8 D" o4 E————————————————
" S5 [7 q  G: w版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。, s- P2 a: D. F3 ^
原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669585 `5 Q- g9 q1 i1 l. U# X
( X- V" N; O7 O; Q
* M. [; f7 ^2 S2 g& g  a. A
9 ~+ b: F0 I) i
3 k3 y& x, l" M+ p8 W
————————————————, L9 ~9 m9 |( l0 z
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
3 n& Y( f: g2 D( C0 g# t原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958) x0 N' d: |$ T  z
' f7 L" L4 L0 L6 Z
- E* S/ {/ L" Y; \* y+ B% m! |