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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
- c8 T0 u" Y4 j6 S/ M j! H) V: {data域存储有关顶点的信息；
; O7 b# i5 H& y! t5 Rfirstarc域是链接指针，指向第一条依附于该顶点的边。! N9 R; [* _3 j/ A. B& f9 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;$ B4 P! f1 x8 R' J
for(int v=0; v<vexNum; v++)
$ @& t0 ?. f) o* I; I {: ?. c6 I, S9 @$ {# R
      if(tag[v]==0)
$ k3 @1 _. R4 U          DFS1(v);
: h# A6 y, q* |1 i }
, m* ^, i% @# n+ C  o" _* D}
+ a# N" Z+ J) @template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
4 R' X  X  R$ b1 y{1 c7 K9 k3 [% T! j; H  k# \* R
stack<int> s;( V" t7 [0 K$ U1 D
int tmp;# w5 s% D: m9 _% O
MultiAdjListNetworkArc<WeightType> *p,*q;
4 A, U6 ]9 i; l9 H for(int i=0; i<vexNum; i++)
0 r  M5 B6 K+ o1 U$ ]       tag=0;% Z' O2 t! W. V3 u
for(int i=0; i<vexNum; i++)" M6 k: I4 C8 }' A% j
{/ q1 o5 Z/ m; G- i& I5 G/ g
      tmp=i;
# i- o! @/ I$ [- y5 r# i( v       while(tag[tmp]==0||!s.empty())
, p1 ^5 ]1 c" r/ [8 v6 {/ V/ V       {
. ]  Y/ r: s& L9 z# [          p=vexTable[tmp].firstarc;5 k) ?+ N# u$ P' m% k, i4 N
         while(tag[tmp]==0)
% N) l7 ~3 ]! @" C/ z  E+ i: n          {9 g3 d- ^; D# T1 [* d
            s.push(tmp);! q3 _( e+ L2 x$ ~
            cout<<setw(3)<<vexTable[tmp].data;2 E3 Q! k8 y$ `
            tag[tmp]=1;8 n) d1 C  U& Z
            p=vexTable[tmp].firstarc;+ j+ O! U5 L. y  s2 ]! ?& k
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
( S3 r) G( I' a$ t" T# X             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
: X$ M* J) ?& E3 k$ D' U             //cout<<" 1st    tmp="<<tmp<<endl;) v0 H7 A5 q3 c3 w) [, V: b5 [
         }* j) x: ~6 C0 ^3 L# D1 a$ @
         if(!s.empty())
9 W$ f& D, ]  H4 B6 P1 x          {; h# @9 H- B* {
            tmp=s.top();0 z& e. L, [, e& z7 m
            s.pop();
7 ]* u- `! W& |# ?1 ]             q=vexTable[tmp].firstarc;
( s+ N+ h: B" D7 J8 x) R5 i             int t=tmp;
% {- @* w' S3 K+ G0 K  h             while(q&&tag[tmp]!=0)
2 R8 R  M6 g% D) Z             {, z/ D7 D8 M/ X" Y
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);. D4 E6 E1 f. |  W: q
                  //cout<<" 2nd    tmp="<<tmp<<endl;6 `, C! o' J9 [- x& v5 G. ^* h
                  q=NextArc(t,q);* S+ p$ Q. X* B: n3 W- D3 m
            }7 D( U  @8 F" I7 Z
            if(tag[tmp]==0)6 q! ]$ f: v* F% D, ?: O/ Y
                  s.push(t);
9 t) G2 R: ~$ J$ C/ D6 @             ///1、对应上面连通分支只有1个点的情况
5 X6 X% \% f+ L8 @1 B             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈5 ?) Z5 Z, {, t6 q2 _  z. q9 b
            ///tmp要么等于找到的第一个未访问节点，
1 Y% U' t+ j; T% v/ F             ///要么等于与t相连最后一个点（已被访问过）* ]; B2 |  Z( c' ~# c! E: T
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
# _( \/ ?- r8 Z3 T  C          }( }* l$ X# u  x: u7 k! d0 R
      }
$ Z* P8 ^6 J2 t }
; z8 P( x8 b6 ~}2 T7 b3 ?0 [) C3 V6 e' f% [3 L
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1. H& H, @. S# U. C1 w$ G% [( \
template<class ElemType, class WeightType> int
9 t) O" k9 g: X! P6 NMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)7 o# b, A! K& S. n! T3 c
{. d+ g" L/ }6 x) ~$ R& c; L, {
if(head==pre)4 Q: u6 B1 G$ B: w! W, }
      return -1;
: H% o/ {$ O2 Y. X0 k% w- t+ y) |3 l; ]& m" L  W! X6 q; v
MultiAdjListNetworkArc<WeightType> *p;/ H) J8 b1 |+ Z1 y2 L. ^
p=vexTable[head].firstarc;
& D( N5 v* E9 u8 n if(pre==-1&&p!=NULL)2 _# E2 ^! N, a% I3 S+ I4 A% n$ i7 q( H) c
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
4 O" z, m3 s: n; p) M; \0 j8 G% S //pre!=-1&&p!=NULL" E; _5 i7 b# l$ h' L8 H
while(p!=NULL)! S* y- I5 u+ N8 E  |9 O) ^# k' Y" l' M
{) j6 ]6 [- O- s1 m
      if(p->adjVex1==head && p->adjVex2!=pre)' ~4 e. W* ~$ b: e0 ~+ c% z5 W
         p=p->nextarc1;5 ]  T! W) p( o" @4 v
      else if(p->adjVex2==head && p->adjVex1!=pre)- ]* l6 X9 y8 s; U+ y: q7 f
         p=p->nextarc2;
) r% y0 c0 C" ]3 o- l$ F: X  m       else if(p->adjVex1==head && p->adjVex2==pre)
, _; g( S0 t7 G* D       {
9 \% a# ]  G6 {$ |' m, g! ?          p=p->nextarc1;& X( M" @1 n: O
         break;: Y4 f+ H2 g2 f1 |" }4 j! ]/ E* E
      }
' n0 o5 W  R. ?7 M- a- x# k+ G       else if(p->adjVex2==head && p->adjVex1==pre)* E+ b2 d1 Q: ~3 q
      {
9 z1 L( M# c- s% L          p=p->nextarc2;! A  m; r% [& f3 j7 Q/ r
         break;
+ e, w/ H: z9 R5 @9 f4 t+ _4 j       }! n* v3 n4 _8 E2 L
}% ?, Q& n0 `- V
if(p!=NULL)+ b% @" T7 F( l) U+ g
{: p$ F  |5 v$ P* ~8 F+ C9 u- O
      return p->adjVex1==head?p->adjVex2:p->adjVex1;* y3 d. j5 A/ ^3 r. J
}+ n" F- B# D2 U% D2 s5 W
else" A) z. R& k/ J! |: K+ c
      return -1;
- ]  I! e) |! e4 }2 b}
+ ~* d9 b9 v$ P$ x! a% ^' n0 L7 h. x* M; j) s

3 k9 K* M. u6 t, S' otemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
! t4 d+ Z! k: p7 _{
& E5 d, `# g0 B/ f stack<int> s;9 ~1 \4 j4 B, a8 Q8 {5 b
int p,cur,pre;
; ~* ^: \! a% {1 R' S1 E //MultiAdjListNetworkArc<WeightType> *p,*q;
$ w+ K- K! R5 @6 l) N for(int i=0; i<vexNum; i++) tag=0;//初始化# u$ A6 D" L9 X+ L! a0 Q
$ u; h% \8 [) F+ H
for(int i=0; i<vexNum; i++)) x9 U9 B. `% _, u
{
6 w' }! k% S: O  r3 {  A       cur=i;pre=-1;
9 N) Z0 \$ q! b       while(tag[cur]==0||!s.empty())
+ G7 b6 b: j+ A: A/ K% N( z       {1 U+ V. }, A9 a2 ]1 t
         while(tag[cur]==0)
& a* E- j0 `! d- u% I" B* s          {- T% p( }# V' a6 x2 Y' f  v
            cout<<vexTable[cur].data<<"  ";
9 I) R5 Z7 W, F9 @5 t2 N( L0 w             s.push(cur);
2 O3 r7 Z: h6 R! a% j5 \7 g8 S, V7 D             tag[cur]=1;
; _  a+ C( t- d8 U             //初次访问，标记入栈
" D! q9 a& s& _0 X8 X& K  U2 g4 H1 I8 r
            p=GetAdjVex(cur,pre);//p是cur的连通顶点0 P; n+ |% ]! k3 o
            if(p==-1)+ Z6 j& Z/ R8 \# m0 t" _( {: L
            {
/ X) n" b, n  x% S& Z+ Q                pre=cur;s.pop();
2 `, s7 C5 P' y- W                break;! e' A5 n: |/ Y* k/ Z: O
            }0 ^0 G0 J9 ^9 r% `0 [+ V  |
            else
# r6 G, r( e5 k+ i             {$ m* R8 _* w; H7 U: Z/ _7 v: ]7 Y
               pre=cur;  i1 D) W) B/ a, h
               cur=p;
0 S/ H" F  s9 n7 J9 j; j             }5 S$ _. E* G* V7 d8 P- o1 e' P+ d

7 E/ T. V6 }& {6 x. X          }
  i( C# o( `$ r. I1 i          while(!s.empty())& \6 x7 @! ~5 T* R. A+ @
         {
- |% ~/ I! n; o             cur=s.top();  Q3 ^2 S& d$ a0 P+ m, D8 S
            p=GetAdjVex(cur,pre);( ?2 l. m/ H) n9 e6 c6 D7 R
            if(tag[p]==0)
& w3 D+ M. p8 u$ L2 Y  t9 u: B7 q             {% b6 O  P% x8 O, i. I3 _, @! G+ w
                  pre=cur;
5 {0 ?4 M- T% X5 @) Q6 A+ l; p                   cur=p;
/ o+ g( q* c! F% U. _                   break;  o" E9 i' M8 B2 m1 C" q$ n# O
            }
% G2 g- K; ^! E1 W6 G, p             else
0 V0 ~' N$ @1 n$ m9 [, V7 A8 p             {
% g5 J, F* [7 |/ E% h9 w$ s                   pre=s.top();1 X, Q& X8 B/ Z6 W$ X
                  s.pop();1 U. C3 J9 f, W! ?
            }, x) H0 Q0 v% ]0 v
# E$ c$ Q6 l: C1 Y; Q# m2 g
         }3 A4 N! z4 H1 A; |. I

# S8 E0 ^9 x4 a) D& m) _- ]  |       }8 O8 z; W/ ]) w( K2 ]3 I
}
6 \7 U2 e& t8 B/ V/ N* o# J}
3 E) e  o5 ~0 D+ K, a  U) Ytemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
6 L. p! R* v% d{. U% W+ [' o$ @# C- ^
for(int i=0; i<vexNum; i++)1 r4 |. X/ i$ v
      tag=0;; G; {) S: X; R* B8 Z, O, p& j1 ]0 |
queue<int> q;% o  O, g/ G1 R3 \
int tmp,t;" k; X& U% r% ]& T7 p3 Q* Y
MultiAdjListNetworkArc<WeightType> *p;1 `! ^! |: f$ e
for(int i=0; i<vexNum; i++)
6 L3 S- {* _$ Q7 ~& i+ L, Y {% B6 d8 V. m' c& Y' a% Y
      if(tag==0)
, B8 p& l0 B$ _6 `7 g$ K       {  z. K8 |, D; Y# D6 K9 _$ |- [
         tag=1;6 ~! ~# F. h0 D. M/ \. @! J
         q.push(i);0 m0 y" u9 d; C! H# t) @) X, K4 W
         cout<<setw(3)<<vexTable.data;7 {/ `6 V6 U1 V& n! `$ {9 {
      }) \  N3 M0 Z" q4 l( Q: L( O! m
      while(!q.empty())" I$ i7 A; F% {. O) W  W9 n, n, i
      {
# H/ B( S$ S1 C, m+ N0 J          tmp=q.front();, Q* n! x) |' v3 C/ u
         q.pop();5 c' s6 ?  M  N5 r- U' E' k
         p=vexTable[tmp].firstarc;2 q4 u) E9 G# [6 {7 o
         while(p!=NULL)* K8 l4 C3 i8 k- W& [. J1 N3 }8 [) n
         {
! w6 S7 R. }. o4 J. A             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
$ i* l* E8 F) W& y% s             if(tag[t]==0)
' T& Z' s2 n. [% K4 s* C             {' Y7 w5 f# ^1 @2 F( k5 V
                  cout<<setw(3)<<vexTable[t].data;  m: Y0 a# o1 t% m& V
                  tag[t]=1;
/ t, a0 T- ]1 {3 T" @                   q.push(t);1 K$ p! V+ ?- n( `4 f2 v
            }
+ m9 v; m: J: l" q+ V             p=NextArc(tmp,p);' E2 z* t0 q6 W4 C4 D5 |+ W6 a; |
         }
, A1 f! l5 V3 M; K       }, @2 X1 I* |9 l/ e- O" f/ P% e
}
# c5 Z+ r" N# j0 E. a* @}# |* K8 y- z4 {4 P- |  Z8 n
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()$ x! ^# c9 s" S; o1 m" W- ~  K
{
8 H/ h! }! d7 n9 z* U- Q2 R MultiAdjListNetworkArc<WeightType> *p;
! {' b5 D& z# D) `3 A cout << "无向图有" << vexNum << "个点，分别为:";
9 K6 A3 O, M) d4 N( m" w' r for (int i = 0; i < vexNum; i++)  E; C1 U3 P; u5 c1 C
      cout << vexTable.data << " ";
2 _2 b& v) ]+ d" k" V" e  ] cout << endl;" w' B6 `: J; Q) D+ b/ G
cout << "无向图有" << arcNum << "条边"<<endl;
. [9 |: E3 F& |2 e# e for (int i = 0; i < vexNum; i++)
8 v1 z9 H( Z/ ?6 Z4 j$ | {
% }- |. N: s2 f; g       cout<<"和" << vexTable.data << "有关的边:";
2 ^% @" J; S! i       p = vexTable.firstarc;% A6 v- Z) x: g6 D. t; u
      while (p != NULL)
$ Q$ A3 R% ~- C) v* Z       {
  k# ^( Z% @! ^          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
  E4 F0 C' O7 I, ]3 I; ]1 e          p=NextArc(i,p);
7 b! z# X2 q3 u  B" N       }- p  d# D  W$ g8 t" W6 p; N
      cout << endl;
, m" T, ?' }. m3 w4 {6 {) t! O( r) a# R }( r2 m1 [$ R" ^& m$ n8 j
}
$ z9 H, O! q4 F- f0 U
7 I2 L7 R/ ?: g9 Z" j: p& t" O
; f9 v# m8 l2 T( N# I0 ?邻接多重表与邻接表的对比6 U0 h6 I  v1 x/ V2 q5 n

( i9 q  q7 b* X9 V$ G( Q- F0 _# x邻接表链接
4 b; L& O* C* k% N4 b在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
3 ]* m. Z* ~0 A5 ?在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。+ q3 }/ O1 R1 R5 n! B
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
  i% q$ R! \8 c, w6 A4 o3 f————————————————; r7 R: `: F' K4 ^1 v3 _
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。8 m1 A( X+ W, W
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958* V7 }3 E: W& i6 G  N) [$ l

# U" M9 V: w: p0 I: y# ?* l3 k  K

9 O! m: u7 ?, g& c
; {6 P7 l" ?. ~5 l! ]9 N1 W2 V————————————————, N$ \+ K* V, u1 I
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
& O4 k% X0 y  @- t原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
9 U% Q2 O" A$ _: K  I
* N0 F+ l3 D! ?  t% Q
) V" M2 c% u: E* [8 ?! P# M8 l) g