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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：0 `# t, y$ ^1 P3 f' {. V; h
data域存储有关顶点的信息；
8 i$ D* {; Y! y" y' u; \) afirstarc域是链接指针，指向第一条依附于该顶点的边。
# z( B" B8 K% g: e( l- m所有的顶点结点组成一个顺序表。

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;
: O9 r* P6 H& [ for(int v=0; v<vexNum; v++)
5 B0 F9 b* O# U( Y7 B6 g; h* w! ] {6 W, ^; U, d0 B, H( \
      if(tag[v]==0)& M. m$ m! M6 W! @
         DFS1(v);
# s0 X  e; A: K* G- O4 a( s }) f7 Y' o9 K) e
}
8 T+ b! m1 E& a/ r# _% k( B% Mtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
. t  y, H) @4 v9 [' `0 ^{* N5 c1 B( O+ M. g; K
stack<int> s;0 B4 p" W1 p1 S) t3 W2 K: T5 r
int tmp;: I5 F: Q* m3 ^$ z8 K
MultiAdjListNetworkArc<WeightType> *p,*q;9 _" P2 T3 i; v) [* q: l
for(int i=0; i<vexNum; i++)
5 ~% j0 |- T: v, v* M4 L* Y       tag=0;
: ^' T' c: n, `* Z for(int i=0; i<vexNum; i++)5 h* @1 j4 k& v) k
{( w. e5 [' H4 M, M- {1 [
      tmp=i;  ?4 }- {+ K% S/ O$ Z7 }- c$ ?' _0 P
      while(tag[tmp]==0||!s.empty())# O! b3 B" f8 F  o2 u
      {
3 j, y6 u+ E7 a9 y! d1 ~9 |( z: J- `          p=vexTable[tmp].firstarc;  j3 k. L/ x' `6 Y# K. w5 e
         while(tag[tmp]==0)! j. t1 F. R$ w. ]1 }; {
         {6 u$ \$ z' O; U" I7 N% C( e- m; R2 [
            s.push(tmp);5 o5 N2 ~) o- u, O3 g/ o/ `0 a$ v
            cout<<setw(3)<<vexTable[tmp].data;$ u8 p( `: p2 @7 B: B5 Z" ^- |0 c
            tag[tmp]=1;
! Z! Y9 Q: C. b5 J             p=vexTable[tmp].firstarc;; u: B' m7 |9 c+ ^  W/ G) H
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for  ^. \3 P2 t: w; N/ b. p0 Z- J) `
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
6 v) p, z( _8 p             //cout<<" 1st    tmp="<<tmp<<endl;
3 r+ T* {. l- {          }
: h( R7 y. k) c- \2 H9 t! E          if(!s.empty())
, L4 j& @+ u" a: Q0 M' n% w; S          {
; |* x! ?+ J% s2 T1 S. D* ^             tmp=s.top();
2 U% j& x* \4 W             s.pop();
& R; |0 U1 H" Z( X# v. t% V             q=vexTable[tmp].firstarc;
; s3 ]7 v( v: b6 p             int t=tmp;) V0 T* T( O# k  v# s$ A- }0 h7 _( n
            while(q&&tag[tmp]!=0)4 R( j+ |& K6 p  b: K
            {
+ W8 |6 ], V  l) Q1 j                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
- o9 k6 |% I- K3 R3 P3 _7 K                   //cout<<" 2nd    tmp="<<tmp<<endl;
6 A* s0 _0 |5 {: Q+ G1 Y                   q=NextArc(t,q);
9 I1 C3 {+ q" u             }: S& b7 C% i& S; x5 C; L& |
            if(tag[tmp]==0)
7 P3 ~3 d) v, t5 W                   s.push(t);
2 m; |/ P2 d* M' J1 K             ///1、对应上面连通分支只有1个点的情况# I% @# \+ {6 u# S' L; F
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈# S7 T4 X) w: p2 N- I
            ///tmp要么等于找到的第一个未访问节点，2 [) X. W- q5 F+ t6 C* r( Z5 o
            ///要么等于与t相连最后一个点（已被访问过）
  _2 ?. z. D# i+ F' |4 V0 i             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
- \: Z4 P3 _# x          }
1 ~, W: R+ c" k9 T6 M       }
9 F- [1 G$ P* r3 W) E/ ^7 N- L }/ R% F% ?% H/ V4 G" P% L0 U) P
}9 Y2 W& [- @8 W& Z5 r, G6 X
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
2 o3 `2 E& V- @& n+ F, ztemplate<class ElemType, class WeightType> int
/ c, K$ J' R5 X* r) ~6 ?9 o  S) WMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
( T+ y" Y" p5 D) G{
3 u1 ?  ]* X; a- F1 n if(head==pre)
6 g7 n$ ^/ F" \% R  y. h4 l       return -1;
! n8 E. j) E5 J: \8 i. U) z8 Q" k( Z
MultiAdjListNetworkArc<WeightType> *p;
4 o' M. f; @0 i! r. {0 L% W% w$ i p=vexTable[head].firstarc;
' ]5 J, H, M0 u if(pre==-1&&p!=NULL)' W& E9 V4 u* R2 F/ K/ y/ i+ N
      return p->adjVex1==head?p->adjVex2:p->adjVex1;& R( b0 n+ s7 H. V
//pre!=-1&&p!=NULL
6 {5 f: b: d7 n. E% R while(p!=NULL)
$ K! f4 M, r, l+ e  f {
$ W7 H; E" `. ]/ t  ]       if(p->adjVex1==head && p->adjVex2!=pre)4 N9 \  @4 m  E' R
         p=p->nextarc1;
# b2 G6 i. }0 d+ R, I       else if(p->adjVex2==head && p->adjVex1!=pre)7 e& t# Y2 {6 \0 D9 U" C
         p=p->nextarc2;$ N( S6 @- ^) k, D9 q
      else if(p->adjVex1==head && p->adjVex2==pre)
# h- Z% @0 P; s+ I2 T       {5 r- y& j# y( d4 c/ \  o& _
         p=p->nextarc1;2 R0 L6 ?, p. }- ?: m; h
         break;
. I/ Y; j; l6 X7 ~; X  l1 C' \; X       }
- k7 F7 }8 g: Q, C) T( g# j0 Y+ e       else if(p->adjVex2==head && p->adjVex1==pre)
' X9 @  k9 |( m- I. R& t       {) A! v3 _  @0 t+ A8 l# m7 c2 H  \
         p=p->nextarc2;
, l' N! F( H2 W7 U          break;  L3 M1 v, i% i) J
      }
0 T- L; [8 ^  j3 E' z5 g }( u4 q3 F' d. t$ @: g5 W$ Q
if(p!=NULL)
8 F. u" x( A0 Q2 H, r, `% y# y' M {7 }: m; \) }' \) S) T4 N* ^1 K
      return p->adjVex1==head?p->adjVex2:p->adjVex1;5 V! F7 u' z4 K) X8 }6 s( J$ `' X
}( h, U5 J9 q8 S) [/ V
else/ ^# W, c9 E4 }! c$ P8 I* X4 Q6 k! P
      return -1;. d2 X. v. Y# C. N
}
3 v! C8 R1 K1 S8 H& Y8 ]9 V& ~, }# ^, s  M, A

" j- v  d/ S/ ^# x3 b. Ytemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()4 M2 c9 H* w2 y* ?, o! Z/ m9 m9 q
{4 D  s9 q- A; f1 O" _& i
stack<int> s;( M  D# C& G. l: r3 I: W6 D* ]
int p,cur,pre;" ?: F% D& z* S& I3 b
//MultiAdjListNetworkArc<WeightType> *p,*q;/ l9 \3 W3 H% z& Y4 J) Z" D
for(int i=0; i<vexNum; i++) tag=0;//初始化
& x+ Q! {. G+ D# [3 Q8 J  T2 l4 T0 q
! @) i- W9 V3 Q6 N for(int i=0; i<vexNum; i++)
6 ~. X, K) E- _# [' X: V {' z- W3 x/ T1 R) s6 T2 L9 `+ }) Q
      cur=i;pre=-1;
$ a, M2 d# r3 |5 X# v7 E       while(tag[cur]==0||!s.empty())
, P- \+ B/ D: W0 L6 S' j3 [6 h       {" c# j) S; f% N
         while(tag[cur]==0)
0 v# U5 m6 U) T$ b: c          {
& a) u) B2 w- `, R/ X- Y: U% z             cout<<vexTable[cur].data<<"  ";" g% x8 N' b8 V6 w
            s.push(cur);6 E; Z9 N) K: K3 \* U
            tag[cur]=1;
5 y4 h) b3 U4 {. K, w, A. F             //初次访问，标记入栈% f, c, @2 Q4 o, O3 ?# [) {% ^
5 e6 H  V/ `! q0 x
            p=GetAdjVex(cur,pre);//p是cur的连通顶点9 V0 o  Q" P' Y2 E1 g  F, }
            if(p==-1)
5 q; C, k& {/ T# P( K+ `             {
( V2 K. Z  m! |  W) ]$ _& ~                pre=cur;s.pop();
4 z$ t) i* s) G  ~, B) F" C! F                break;. T$ t* ?, H- }8 S1 k
            }) L. ~. v2 b" e' r- N6 e4 }
            else* \" X: h4 @& x' G7 W1 q
            {
6 @7 Y" j9 P" ?                pre=cur;
! u4 i1 w& l* u8 Y) ~                cur=p;" D$ T% g* Z: c6 n
            }3 F9 W  X/ E  E' B: D
) |# K+ R9 U5 X; T4 ?! S
         }
+ A  u# V7 T* i' b* }! ^! i9 w3 i5 ~          while(!s.empty())
! w) y$ o( {. h& ^  {          {
+ t( ~0 E& n7 f% T. k. }, a             cur=s.top();& m' H) z7 L. u% ]7 @! L1 U% J' R! o
            p=GetAdjVex(cur,pre);
' i! |! I' B8 q) E# c2 H             if(tag[p]==0)
' K. u$ x% }7 B1 I, t1 P$ O             {
- z) |# j0 a5 B+ K                   pre=cur;
8 P/ s# ]) l* c) h9 j; ?; u) m- R                   cur=p;5 {) g" i1 V! C  \9 s
                  break;
2 {7 U1 {2 n7 z  l$ N5 a             }
& B' j: m3 X. V) z4 F/ \9 X             else3 [7 X4 ?7 v! g. G/ J
            {- H: v" `: M+ g# @# u2 o( E
                  pre=s.top();+ L6 k$ S8 x& Y: [! z! W8 r
                  s.pop();
# L  D3 J; [, V. h8 g9 P             }
! f! }5 Q6 X' K9 u. t) c* I
9 Z1 F; D* {! r, \% p' Y' c          }% M% ]; G  C- J/ h' s0 {
: G+ B0 U$ U# j1 N
      }
4 l: ^- X  V" W3 P% n }
- O2 ]7 d# u9 q! w" g% [}
8 T# Y3 ]+ m- X6 Y/ n# N% [# xtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS(). o' _. {2 l) z% I
{1 Z0 k" a! |7 b& Q% g6 B
for(int i=0; i<vexNum; i++)' o: @$ f4 x$ g' g& _/ D
      tag=0;
. r2 h) `6 |2 z3 |4 P, n4 D queue<int> q;
: o. b8 F3 a, z2 g' {' |$ n int tmp,t;
' Y7 J6 O8 Q! f, s% N) l MultiAdjListNetworkArc<WeightType> *p;
2 B9 S! g% n3 S for(int i=0; i<vexNum; i++)2 J! E& l" }- o! n% N
{
4 \& C5 {9 K# o+ G5 Y, u- X       if(tag==0)
+ V& U1 Y2 D$ @6 e2 ~/ k       {
8 c9 m3 {7 _$ c; n2 V0 Z" I5 E$ o- s          tag=1;
: ^0 R1 c% Z: Y9 P  w3 }          q.push(i);
1 f8 ~! b- w; Z( W8 Y          cout<<setw(3)<<vexTable.data;# i& X  w, T& }6 k& N
      }
" i" x# `3 P1 N; V! S7 ~       while(!q.empty())
5 S& u8 }2 n% m$ p9 C- n% c8 G! k# J       {
5 o/ a9 A. b* s) P% v          tmp=q.front();
; ^$ x4 r) y/ r( A* i7 t! g& t2 R          q.pop();+ z' ?$ h- V( d( x
         p=vexTable[tmp].firstarc;
+ B+ h+ P0 f7 P' E) F          while(p!=NULL)
1 i, Z2 M6 ^; T; O9 }" Y5 c# {          {
9 g4 M& x+ _- ?" ^             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);3 X- V+ M& j9 e. |3 Z& I  h& u  Q$ g
            if(tag[t]==0)2 m0 \7 s) z' d/ z4 d. e  K
            {: W* C8 C, z6 F% H( C2 N- Q* R; f
                  cout<<setw(3)<<vexTable[t].data;+ F9 R! q1 @8 T+ \
                  tag[t]=1;% x" |* J7 z! j$ d
                  q.push(t);
" D% T7 q+ V4 e  V, x- q             }' q  {' C; l0 B- a3 e
            p=NextArc(tmp,p);0 x! R, ?: w$ F; ^4 N) a% G6 x
         }
; k2 z# L% W8 u: ^" G' i( Y6 m) D       }
# O3 L7 @' i, {! j6 M  P$ T7 e& X }
+ r( l' M+ [' p, L}3 n8 N7 E: c- ]
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
5 G7 T/ X/ [6 u0 s& F1 L4 Q# ]{  ^3 S$ `5 G- @$ T7 N0 `* ^
MultiAdjListNetworkArc<WeightType> *p;) b8 o$ O5 o- Z3 }# T
cout << "无向图有" << vexNum << "个点，分别为:";
8 f, f! t# n# L, t1 @ for (int i = 0; i < vexNum; i++)9 \3 A* V5 E& U# Q6 r! {8 p3 l
      cout << vexTable.data << " ";  V, Q7 g# Q9 I
cout << endl;
6 w- d9 w- O# f0 l cout << "无向图有" << arcNum << "条边"<<endl;
: H! s4 w; v; a1 X9 `( \% I: g for (int i = 0; i < vexNum; i++)2 l& f1 d/ q5 o6 p' U
{
# n* i) v8 `0 a$ P       cout<<"和" << vexTable.data << "有关的边:";
0 }- I8 {4 O: z) w: u! l" A* e       p = vexTable.firstarc;
, N& D. U% a& Y% `  ?3 s       while (p != NULL)
+ o6 B: v* K9 R) G6 e7 k5 O       {( {" a4 |- M: U2 u$ M% }" V4 M; F
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
6 o  T! a" r0 e% E  E$ x/ h          p=NextArc(i,p);  M7 C' `3 R- J) \; e9 f: d
      }' K, l4 [- N4 D0 i* {/ ?: _3 B
      cout << endl;
- {( \/ d' w. h. \# H }+ V9 f2 ?9 A5 w. L! a1 P/ s! U
}* S1 Y9 s" H! M; F. l( H

3 r8 d( i7 c; i  A( y! B
2 Q/ w% |& C9 d' ^* P& _6 H, I邻接多重表与邻接表的对比
) @- D2 X. D2 _' \( ~3 A+ i2 [* N  w6 K3 s9 Q7 x% y5 U" y5 e: s  V
邻接表链接: V/ `' k. J: x, b; A4 j
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。' o: s) @6 h. x) ?! ^/ p6 }
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。* B. O1 |% R( T
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
. b5 U& R( d5 {; t; k————————————————
$ ?# e' S: ]) f5 Z3 C1 Z版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
, ?* |* t# F  ?8 k6 ]$ ~! b原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
) D3 j& V; c& h
2 A5 i( [5 @& F% u  a. `+ c
% l- c  Z" @% G
* _; T5 J, j) j5 ?/ P  V0 ]/ b4 z9 J9 V+ q' d
————————————————
0 [& V- q& n; G5 I  X版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
( j/ w9 {& x4 B7 `) \" x% G原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
6 a" p2 c" c3 k4 X/ A- U6 b% c# N5 g6 ?1 r+ M) |6 V$ W2 Z5 e

2 z. G% ?* h4 Z. Z. f) v& p