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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：
- N" ?. H- x! Z" mdata域存储有关顶点的信息；9 t m9 P* i. d( ]7 L8 Y, U& P
firstarc域是链接指针，指向第一条依附于该顶点的边。3 p4 U9 m7 V8 a( g0 ^0 ?4 E
所有的顶点结点组成一个顺序表。

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;
; L0 n* _2 l. V; h) u1 r for(int v=0; v<vexNum; v++)) d! t# b/ }+ w# {2 c
{& h( ~- K9 e9 B( z' f/ U
      if(tag[v]==0)
$ J' \5 U! g2 @% L  y: l, K$ ]; y          DFS1(v);$ ?' J- @) y/ X8 i
}9 @4 M7 m2 {, ^) y
}
; {- s  j. ^" ytemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
# q; [* h. y. n+ L7 J7 A{- f7 W7 a1 Y! v  R, U* U
stack<int> s;
  Y/ r; {" {$ Z+ H& T, m int tmp;
& d8 X$ T1 w' @ MultiAdjListNetworkArc<WeightType> *p,*q;5 w; u4 t- w; U
for(int i=0; i<vexNum; i++)
5 n) {6 i( d4 o5 x3 r) k7 Z$ o: B       tag=0;
4 X# ?& {# N+ ^0 W' h! u8 ] for(int i=0; i<vexNum; i++)
/ L7 K2 s( \3 X8 z6 @+ f {( |8 F5 r$ N" u# X# v
      tmp=i;
8 B3 a7 z! _. N+ F6 G; T* @       while(tag[tmp]==0||!s.empty())7 a$ y, Y. N( F7 P2 U0 D
      {5 W* |6 A3 |6 r/ R6 z; Y
         p=vexTable[tmp].firstarc;
. R* t. [( ]7 ?          while(tag[tmp]==0). w2 u3 L; i8 M9 E
         {# k, y' }$ |6 T' V
            s.push(tmp);
* I7 U' s; e! \; l             cout<<setw(3)<<vexTable[tmp].data;4 I* Z# j# i& G$ V2 t% ~1 ~
            tag[tmp]=1;0 ^( O, ^3 k4 M# B
            p=vexTable[tmp].firstarc;9 \4 _8 y0 Z* }) G6 w( K
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for' g& @% \! P$ P" k) i- M6 b- Y
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
' _% ?% J& O: [             //cout<<" 1st    tmp="<<tmp<<endl;
6 n9 Y+ J8 N/ r; j' c& f5 A          }" r  `! z2 y9 n8 o- W1 t( I$ \
         if(!s.empty())
  \2 ]( b* B  y0 o: d8 u# g. N          {
) v! h" D" R- q             tmp=s.top();
* z9 k/ @; v1 J9 X" L$ J4 K8 \             s.pop();
! J; q8 ]; d1 D) R             q=vexTable[tmp].firstarc;( d& M. |# v0 c% C, F! A( `: k
            int t=tmp;' @' s" i) N6 h& h5 w3 W
            while(q&&tag[tmp]!=0)
2 w) r- O  Q- P# d$ u3 }* L) [             {% P% m7 V$ V8 D1 B
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
. C" f* O) s  q                   //cout<<" 2nd    tmp="<<tmp<<endl;
9 p+ T3 u, a9 x                   q=NextArc(t,q);
3 A2 u8 Q( \1 }) b* i             }* e$ t1 s2 \8 ]- B
            if(tag[tmp]==0)3 d+ ]4 \" E; D
                  s.push(t);' S) z  ~6 n  l( T, F! `
            ///1、对应上面连通分支只有1个点的情况
" O( n5 g& S# y% v9 m1 H; n             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈8 O* W$ B* I& \) F% t
            ///tmp要么等于找到的第一个未访问节点，$ l2 y( z5 O2 B: R$ R3 z
            ///要么等于与t相连最后一个点（已被访问过）/ Y, G4 d0 b( B8 s2 B# Y5 o
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
+ v3 F2 w+ K* u% ~8 X8 M          }& o' l' v5 c/ H9 d% p
      }
: d2 o- c6 l9 X( u) G9 J/ [ }
# _+ n+ N6 V. j% k! \}
1 ^6 h+ u) O" m. H  C2 `. H/ d& S//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
$ p9 V1 ?# e; Qtemplate<class ElemType, class WeightType> int
. U" j! }+ Q- g2 o* z; FMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
/ \) w# {  z' M5 ]* [# e( t{
% |2 r, E- U$ R; ? if(head==pre), s5 D, |, P* X
      return -1;& S7 z1 o# X' w. F$ P

% ^5 ]3 t0 u- A MultiAdjListNetworkArc<WeightType> *p;; z: k3 N6 P, ?- g( Q8 k3 @, }
p=vexTable[head].firstarc;# g! S7 W# y- X- F, \8 @7 f
if(pre==-1&&p!=NULL)
/ D% z+ {0 w* R2 }1 J$ i       return p->adjVex1==head?p->adjVex2:p->adjVex1;
- C# D$ G8 A& P" c, _3 k //pre!=-1&&p!=NULL" U# Y' {4 t. m6 O' X1 _& {
while(p!=NULL)$ M/ m0 U* M" T
{3 k, e& V) `6 C; s, u
      if(p->adjVex1==head && p->adjVex2!=pre)
% J: {2 w- p% ~          p=p->nextarc1;8 C2 x( C: T# {) e# [! V
      else if(p->adjVex2==head && p->adjVex1!=pre)
  ?; @% H/ h8 e6 s. d) I          p=p->nextarc2;. `1 C* S' U0 R2 F
      else if(p->adjVex1==head && p->adjVex2==pre)
( \7 ^  l! W$ u$ l/ {, ?( s       {- m, b4 A7 z, ~" z
         p=p->nextarc1;
2 x! o/ N0 u1 V- Y% B/ K          break;- h: n) v( H  j1 N5 U
      }  p. A$ v% s& {- M6 ?
      else if(p->adjVex2==head && p->adjVex1==pre)
- Q9 U. t8 B8 c- O5 P       {
$ t2 s/ F9 h4 c0 O( a- Q5 r          p=p->nextarc2;3 Q1 k" B1 W8 [% F  G1 i% B3 ?
         break;: x: Q3 w0 |+ I! k8 s2 ^
      }
5 Z% t! ^. c3 c: R4 @4 ` }
9 X* g6 t7 N+ k; O if(p!=NULL)7 u  W  _& s! J
{5 L2 r/ W3 K0 Y. r1 ], z
      return p->adjVex1==head?p->adjVex2:p->adjVex1;) Q# ?5 o" r6 J( V! z" o
}
+ `1 B$ n7 l( c. b( K- q6 Y  u/ v% R else  p+ R3 }" M. |8 i9 |* n
      return -1;) @1 `; ^* i! [& Y) r: Z( O1 ~
}
9 r7 z3 Y3 K' q$ n; J, j
" y" s1 Q* J/ U- z" @: ?
0 H( g+ N$ d" |* c6 U/ z' l- ptemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()5 z3 D  h" F4 _
{0 A7 u3 p+ O7 G0 Y  T" Y
stack<int> s;
6 M( m) _- |- \. O4 \# w9 ? int p,cur,pre;
$ X5 V) g, c) d7 i- k8 O //MultiAdjListNetworkArc<WeightType> *p,*q;6 S6 C& F" P, j  j$ M
for(int i=0; i<vexNum; i++) tag=0;//初始化
' U3 u0 Y5 E: N' J/ K3 Q3 l6 M! k9 k) C4 B  q3 s! m6 d
for(int i=0; i<vexNum; i++)
3 z! D  {4 e. |5 Y5 O! y+ ]) A {, F* J; g& ]; @, h" A2 x) I0 ]. g
      cur=i;pre=-1;
7 A: ?5 b6 ]5 H0 \       while(tag[cur]==0||!s.empty()); g* [( Z) W$ F- h3 H5 x& N4 _9 c8 ?
      {8 o& V8 |* [7 k$ a# _; K9 H
         while(tag[cur]==0)0 i$ h$ i% e6 B5 o& ]+ e% f: K
         {7 H* H# k$ n) `3 j( U
            cout<<vexTable[cur].data<<"  ";% A. b% d- Z/ \2 D4 ]6 r
            s.push(cur);
/ t$ S7 U1 x  H" K# W( Y! |1 i0 s             tag[cur]=1;8 q, F/ B$ t: O( D$ w  z
            //初次访问，标记入栈
3 r8 O' n+ L$ @1 t5 G4 y( S
7 M6 F$ Q1 ~4 _* B& C7 y& J             p=GetAdjVex(cur,pre);//p是cur的连通顶点; ]8 u3 U' Y( s- X& R0 b6 e" `0 ?
            if(p==-1)
& R- D" R4 p; S, ?             {
- }. z; I+ x6 V! n' K                pre=cur;s.pop();) p' j; `9 f( }- B5 D
               break;" `% i4 p' l. i; e
            }5 o$ Q7 V, v; R* T* ~0 ^5 j* C/ W
            else8 u+ [! ~1 _( m2 c# C3 \
            {
, }. u7 e/ G& v                pre=cur;, u( l- L4 {2 w/ X) _, h
               cur=p;
- [" F, s, h& z  A             }
* r! q& w1 h4 u, T3 L& M- _- H# J7 k8 E8 F; x- ?
         }% ~4 U4 Q: `3 i4 ^2 I% }% F' \
         while(!s.empty())
& c( @9 R- a: k0 Z          {
) e. H4 K2 L/ P/ W- H2 ~             cur=s.top();
4 }) U0 K5 I/ ~& C/ u             p=GetAdjVex(cur,pre);# I8 S8 v9 {! c. \0 O
            if(tag[p]==0)/ c3 n$ W3 ~' }4 w) ?; W) r
            {3 ?) J' V- Y  @7 {! m2 R2 r
                  pre=cur;
( G# o% ^$ _1 G: T& J                   cur=p;3 E5 V9 S3 @6 N& |6 y9 j: C
                  break;
% q! e& D! q" h' s             }
7 r2 F( X; X  d; p9 ?3 g  R7 y             else' ?3 O- f$ P9 T6 Z! K3 `5 p
            {
4 Y, D8 N( q, K+ h                   pre=s.top();, i7 o% j' E* i6 h: g
                  s.pop();
% F% G4 I* }; w6 b" O+ I' W5 s5 T             }: _( e1 Q5 _7 {% S
- k& U' N# s0 k; f) u
         }$ n/ w  Z% l6 I0 e6 n$ d
# O4 p7 W" V' n4 k1 W
      }
5 f2 d" W, B3 P& D }( ?, e* D+ @6 |2 ?; T0 x# |0 l
}
& q0 ^! _$ s+ etemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
# O5 W0 S3 Z% n7 L. ]$ x+ Y( I{
6 P7 K. ?$ U) k- J% U" o for(int i=0; i<vexNum; i++)" ~" L. n! l, Z; H+ O) s( E: _4 n/ C
      tag=0;
& A! l  q8 Z: ~& z' b queue<int> q;' I6 l5 q  n: O/ k5 _, K. I$ `9 ]
int tmp,t;, ~0 f) o; s' i6 B% x
MultiAdjListNetworkArc<WeightType> *p;
2 D5 e4 @2 j+ P0 b& t( c7 k- ^ for(int i=0; i<vexNum; i++)
& l" p' i6 Q5 ~, e$ `5 n {- m/ y3 P1 m" g6 X) r3 d* S
      if(tag==0)
7 k) x% [; \5 X% j5 t       {3 d; p4 `! z) [! b* U) s' q1 k& [
         tag=1;4 x% f( u3 d; A1 @2 Z6 L
         q.push(i);
) A! [* `2 r- J, E1 j          cout<<setw(3)<<vexTable.data;$ V# L4 C0 v+ M& q+ i
      }
% Y; O$ `* b0 n) V% O- z       while(!q.empty())
+ l) x  Q+ K, G9 F, X       {
3 S5 E2 O6 w; O          tmp=q.front();
/ ?) G' E* N/ Z, V1 {          q.pop();- a; w+ y4 \- F5 S
         p=vexTable[tmp].firstarc;
6 T2 X# z1 ]. o; S- U% a/ y0 J          while(p!=NULL)0 X( {+ Y6 B% R
         {( m' I6 E, B# {: k6 Q: d9 ^
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
            if(tag[t]==0)
  d+ r& s2 g& X' `# b5 E! k) u             {  q: T8 I# m5 Q4 K7 J6 T
                  cout<<setw(3)<<vexTable[t].data;+ ^  t1 o$ T( ~8 _' v0 K! q
                  tag[t]=1;
; g, [9 B6 L4 A9 d! k; \                   q.push(t);
7 f" z& T. b* q- t* u$ h  V             }& p$ T7 @2 ~1 n' P0 I6 e
            p=NextArc(tmp,p);
: R3 ]7 J2 R9 p2 p          }
% }' H( p8 b! X       }8 A# \- f0 r$ f1 }
}
; {: @) J/ V7 w1 e}' B. L" g" r) ?; M6 L5 o6 Y
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()) B- n8 j' K7 {( X% p- i+ O; L
{' m% K& J+ Y0 X0 o
MultiAdjListNetworkArc<WeightType> *p;
: s/ u2 m! C( l5 a5 f cout << "无向图有" << vexNum << "个点，分别为:";' I  d3 f* I; F9 c
for (int i = 0; i < vexNum; i++)
/ _- T) c/ t1 Q" {9 Z! j5 v       cout << vexTable.data << " ";) x+ b; a- r/ T# J9 |- Z
cout << endl;
$ _( l% a1 X4 G0 g+ P: N& z cout << "无向图有" << arcNum << "条边"<<endl;! w/ D7 F5 ^  M: z1 c& @5 c; j' a
for (int i = 0; i < vexNum; i++)9 J. z' n% ?8 L; E: i7 p: z) K# W
{
! v' F8 Z7 w, h3 S% ?       cout<<"和" << vexTable.data << "有关的边:";' K( ^$ ^8 ~/ g( e
      p = vexTable.firstarc;: B9 Y/ o) |+ s
      while (p != NULL)
# o1 t0 v' E) s' [8 v$ M; }% R" b       {
8 F1 f  W$ t) f5 r9 e/ F          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";; G7 x0 r1 H: N2 E5 r4 a
         p=NextArc(i,p);5 F2 q+ J8 D# `1 P" r
      }
% B* w- ^( G6 S% l       cout << endl;
* }# x. ^1 B) g+ I* E: Y }
/ E2 v4 Y" L9 m. t}
& Q5 U8 `! l& i( }/ t" u5 _
5 t: Z# M- t6 z" r5 q; S9 V% j
& o; l9 V3 v5 C邻接多重表与邻接表的对比0 K4 d+ f, }2 r1 `5 x

% M- q2 p  F+ i$ ?, f邻接表链接
/ _, o, L* a5 H0 G- v0 b. n在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。2 _1 X* x9 I# |$ i
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
: Y' |( {8 q. [  N8 V为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
  t6 o4 F  y$ }0 S( {- A3 R————————————————6 C. p: b2 {& W5 F
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
* U7 e" _3 P2 Z$ a( R原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958% T) ]2 L0 e3 {7 q/ T9 c

) l6 E* F9 Z5 |& D* J0 e
- K3 \: p6 w8 G* a" U  I( Q) ]8 c! K% T; b1 E( x) `  q: y
( L7 j/ q. T9 C0 |
————————————————
3 [) s% @% A' x7 R  r4 z# `版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
1 \1 p6 q( ^  R& Q0 l原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
1 B0 S- F' D$ [1 d3 B
9 g9 {  k5 _$ C0 c. @9 V5 X9 y. H! @. i& S  `7 B4 x) m& z- M6 _