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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：1 N% x T7 H4 L9 L( @
data域存储有关顶点的信息；
6 _2 y( m# o/ B% U* `) y$ ofirstarc域是链接指针，指向第一条依附于该顶点的边。
9 n4 S5 m4 Q; z& E; {2 D* I( n. V所有的顶点结点组成一个顺序表。

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;) v: ]  F2 y" _5 ]( i0 I) p* c% A
for(int v=0; v<vexNum; v++)
3 _2 y1 w+ H$ R0 y* F' \ {
) T' c9 A  K7 {& x, p3 ^       if(tag[v]==0)  R/ L+ F0 ^8 L: m$ Z, L8 A+ O8 [
         DFS1(v);7 I5 c+ ?* U5 x* o1 E6 ]0 ?& p# @
}  c* s4 n$ D* h" l- b; D' m
}
- u! U# n7 {' L! v6 E1 H: m8 P3 d. vtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()$ g/ k( O+ G) j
{! d: }$ e/ K8 _8 G. x
stack<int> s;
, d" |6 I* d' ]  S. U int tmp;1 o5 {6 w5 H4 l% }: E' _8 j: a2 m
MultiAdjListNetworkArc<WeightType> *p,*q;$ f4 G/ i2 g# _0 Q1 M% T6 \
for(int i=0; i<vexNum; i++)3 K& i5 K  H9 a% a3 V
      tag=0;
5 _7 C/ Z/ b- r" ~1 O3 S4 t for(int i=0; i<vexNum; i++)2 C* o" S( g# B$ v; ~3 I
{
* a( `& U6 w# S- ^! ?       tmp=i;
3 Y7 h3 e  R6 z5 e4 M" o       while(tag[tmp]==0||!s.empty())
; M( _7 \% E- O2 M       {
* H& a) }: A9 U; _; e& q& C          p=vexTable[tmp].firstarc;5 u4 d5 e6 S* U+ \7 O' ]
         while(tag[tmp]==0)
) y0 M% s# C1 T" h' q, c          {
% C2 |" d+ H  X1 f" I             s.push(tmp);
! f2 W0 S1 Y* }2 r) _( m- ~2 U! j             cout<<setw(3)<<vexTable[tmp].data;
: i* x  N5 a" h3 z             tag[tmp]=1;
9 o4 T, }( \3 u  Y& c1 [! a7 e+ G             p=vexTable[tmp].firstarc;
/ h/ r0 N2 k7 x0 ]7 P" n             if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for
* k3 y+ {3 y( i2 l& s3 [' k  d% ^             tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
0 i6 Y/ }6 f% Q# u* u% O& t             //cout<<" 1st    tmp="<<tmp<<endl;) k! z' k1 L& Z, G& o% J' B$ z" S* j- s
         }
+ w! d( {2 \) s! Z; s$ j) t          if(!s.empty())- ?/ r1 k' s2 C5 U& x
         {! |: z0 C0 K% `
            tmp=s.top();* p: s5 N& [. d1 g/ p, f: f# S9 i( a& m
            s.pop();1 J  F9 L! r: a
            q=vexTable[tmp].firstarc;2 {: M& Y/ n$ f4 T" A, g$ C2 L
            int t=tmp;7 p( ~- U6 E& I
            while(q&&tag[tmp]!=0)2 Y* r. H& t. ~5 U) E, v
            {
$ @* |: r& J: v& X2 {8 C                   tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);/ C2 t$ l# _+ f
                  //cout<<" 2nd    tmp="<<tmp<<endl;8 |* }1 f: i+ h3 _) J' U
                  q=NextArc(t,q);' k/ @0 `6 E% G4 b
            }
  r+ D- j' V/ A9 B6 ^             if(tag[tmp]==0)
$ _6 d7 X, @, M6 V                   s.push(t);8 h7 J" @( P( ]$ }: K3 |2 ^; r
            ///1、对应上面连通分支只有1个点的情况8 p5 Q% u5 d# E
            ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈% G+ x2 R* r4 E' m- C
            ///tmp要么等于找到的第一个未访问节点，$ j. @, H; L! q
            ///要么等于与t相连最后一个点（已被访问过）
2 N9 e) D& `% s9 w  V             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
9 B" V8 I( s# Q! c, ~2 |          }
5 D5 B4 B/ ]2 D* c# q       }
9 P3 Z" ]" M6 j }" Y7 Z1 f' M% |$ N1 G6 p- n# b
}5 c# {3 t7 ?+ W
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1
1 D5 o' V3 x8 g) o: l+ G# n5 _! [template<class ElemType, class WeightType> int
# Q. M  N4 i2 c3 H% o- bMultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
0 I  _% ]- a* O! k{
+ B$ M: T. B$ h& |; o if(head==pre)9 o  R( u, e, A$ T7 T, R) r
      return -1;- W5 ~, c) u: A  A+ ~! E# i' p, _

- N9 [1 b6 |4 z* o0 Z' j8 Y MultiAdjListNetworkArc<WeightType> *p;' ?8 b# ~% B4 c2 z' O  z  U
p=vexTable[head].firstarc;
9 S- P* T: b$ a9 d if(pre==-1&&p!=NULL)
7 ~( b: e  x2 i0 \/ T! L3 W, p" S       return p->adjVex1==head?p->adjVex2:p->adjVex1;
) s' d% h% `+ B* B+ | //pre!=-1&&p!=NULL! U5 s1 I1 v  G/ e4 O3 [/ U9 P
while(p!=NULL)
* j! g3 Z- [, H {9 M5 W- G2 A! r$ i
      if(p->adjVex1==head && p->adjVex2!=pre)
- m$ z* K8 @" C8 H) X          p=p->nextarc1;
6 p/ N' e6 V9 e- S       else if(p->adjVex2==head && p->adjVex1!=pre)  x4 b% Y- w4 O( T
         p=p->nextarc2;
5 _& G- B6 e/ u, j5 C4 b6 a       else if(p->adjVex1==head && p->adjVex2==pre)
, y# B4 B2 `3 V: K  U% w. J       {% j2 N3 {6 n2 J- h' M, n) T9 F
         p=p->nextarc1;
; H1 V* y3 k* p2 _* r          break;1 W+ U( k* \% Z, R' W( M4 V8 Z
      }
3 G1 o7 \: }2 ?3 p2 e3 J       else if(p->adjVex2==head && p->adjVex1==pre)$ E9 H8 F1 g5 B+ ^
      {; J0 ~0 D2 ~/ E; A9 M+ C8 o% L
         p=p->nextarc2;
2 r3 ]+ Y/ U& ?% A) K7 U          break;
" ]+ ]# E( Y% b/ m0 X8 [+ X       }
' K) g1 Z$ h# N5 D" P, O }# l/ K9 ?% ^$ r# E6 W2 g7 M
if(p!=NULL)" i5 `$ ^! V) V
{
4 q. `6 A" r# k3 j9 V; o       return p->adjVex1==head?p->adjVex2:p->adjVex1;
2 z+ L0 Z* C. W1 ` }( c9 k: J7 b  w- K, O: F
else
2 Z+ q4 G, K' |$ E/ t       return -1;2 }- X" P+ g  `/ p* U8 ^0 v  o
}
0 y" N  c/ R3 Z3 \2 R
8 B% o; W" f2 a2 u. M8 ^0 v5 e5 `1 g: z5 z8 p; J$ ^
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
; ?1 C% W8 ~$ J" U{
1 e  ~" [: c" w! o* U stack<int> s;- ^' U# D; @( K8 A
int p,cur,pre;
7 s' z7 P: {& N) w  _/ X' [  } //MultiAdjListNetworkArc<WeightType> *p,*q;$ l; e6 |& `$ O, q6 K( s2 f0 |
for(int i=0; i<vexNum; i++) tag=0;//初始化6 X8 p1 p  ~* c- z& b

% X7 ^+ y' q' U, x# L, y5 {0 D for(int i=0; i<vexNum; i++)
$ z" D, w3 ?5 A7 s& ^ {
8 @. k; V9 Z5 T6 M0 Z6 A9 W! u& l4 O4 \       cur=i;pre=-1;
, A! ~2 p0 F  y$ {, Y8 v7 ^) r6 x2 s       while(tag[cur]==0||!s.empty())
1 [/ V# Y; y7 s: O& O, }! ~       {
8 k/ }/ m7 K' l# @; |( L1 U' ^          while(tag[cur]==0)# s! M! q1 K9 ^+ h' w% ]/ ]
         {
6 Q3 v% G4 z* E# S' e5 R- ]8 j             cout<<vexTable[cur].data<<"  ";
! {4 G: t, ~! x$ n8 R- S8 }# M             s.push(cur);
5 N4 ^( H2 r$ A7 x5 K+ t             tag[cur]=1;
/ S0 q1 `1 O7 i. j: l$ _9 q             //初次访问，标记入栈. Y/ @" h) P$ ~' u( W1 e

  q: H# y- \! ~: E0 }6 N4 X" p3 ?             p=GetAdjVex(cur,pre);//p是cur的连通顶点
0 C$ D5 A0 x0 O9 ]6 q             if(p==-1)4 x# p. k8 G0 ]7 H3 i7 K4 r2 J
            {
* [/ ?1 ~% n$ @; [& ^                pre=cur;s.pop();
- L3 z- V7 ]( `6 m( V) m7 I                break;/ b0 g* Z7 n5 d0 A' ?
            }
  d$ X# h: x; |( c$ K8 Z; o: C1 d             else  x4 z& s2 F4 n0 T5 j: W
            {
$ ~% }( h1 A& r2 y6 ^2 ?                pre=cur;
0 U5 P; h4 V% V$ v                cur=p;
) D6 {1 @% E$ J" x             }
) F. `% D$ u& H: r
/ R7 V4 F8 F) k; j          }
+ m6 N' I$ Z5 l* H4 B3 n8 a9 U& U) }          while(!s.empty())
. }- z) z" _9 p5 x" {$ |! Q% ]* p          {  R+ o/ F& @5 X% F' X( [6 M. s' m' J
            cur=s.top();
5 _0 ~2 @! Z3 ~5 q             p=GetAdjVex(cur,pre);8 Z$ n' @& ?. F5 t" Y$ `
            if(tag[p]==0)
; @2 O0 y; }" M; i( E% S) a             {
# I/ S9 o8 |: b                   pre=cur;* b: m4 m1 I$ Q# E6 `) M  _
                  cur=p;
: T7 ~0 V7 }, k4 L7 u) U                   break;( ]8 P% j& ?7 f8 t; W1 z! R
            }
9 n! H& ]1 t( z! V$ E             else
6 ~' w! `; M. ~: o1 t% t             {
8 s% M: `- x3 }9 L                   pre=s.top();- a/ z  \& w/ V; N3 W# s
                  s.pop();
3 O  I8 g  U( s7 o! k  j7 B, A             }
5 ^! [& a* T/ N# s
5 J3 l3 I5 X1 N! C7 K# c          }/ P, ?3 f; L. e1 `( o7 x3 r' ]1 O7 `* Z
5 O) K% Q2 Y0 I+ [
      }
( D( q& `% d6 q- Q7 H; Z4 F }/ w, X/ \* d3 ~4 {
}
4 R; b7 t) _  j7 D7 D! etemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()- r8 a& L4 o' q
{* c. O7 s+ e  I/ Q
for(int i=0; i<vexNum; i++)0 i& n  S7 W) I: T. d4 [% v
      tag=0;
# l: s8 ?% X3 {0 x) h" q( Z/ ?# p queue<int> q;
  j. p' {. o2 v  R. o int tmp,t;0 R8 l: e2 s+ W6 f! @+ x
MultiAdjListNetworkArc<WeightType> *p;( ]- j  J6 }. r0 i
for(int i=0; i<vexNum; i++)
# n! P: N: g# [, g+ e/ E* ~. S {
) m. {) ?* W' L       if(tag==0); Q, T9 w! V. v
      {
, z( N. f) ~' B6 y8 u  [, d4 c8 B6 b          tag=1;
3 h( c/ G: u# E" K          q.push(i);
' `* `2 A/ ?: K" c          cout<<setw(3)<<vexTable.data;
+ R# V( ]( W, W1 N       }3 y- j( r4 q1 q9 _  f8 S9 p
      while(!q.empty())
; o- S& r; H, _2 @2 n. v       {$ o1 M8 H* [" d. N: u
         tmp=q.front();$ ?4 P2 g& u9 F: Q: T
         q.pop();
) g: g) r% B, ^( P; P          p=vexTable[tmp].firstarc;
) h. e& q8 w8 }3 q  }          while(p!=NULL)' m! u  }/ I0 X( |
         {9 R6 O$ f+ p( v# D; `
            t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);: o3 w/ S9 O( `3 N1 L
            if(tag[t]==0)0 ~# h0 D# i, u  K4 F8 g
            {
3 n* F* c& c5 h7 U5 p, B* U                   cout<<setw(3)<<vexTable[t].data;
, s- N- D2 {( x                   tag[t]=1;
- x" b1 e1 i  q9 O9 i. b7 H                   q.push(t);# e9 W! m( h/ L) \) u* H% \
            }
; ?6 N2 X% R  g9 y& F: s+ h& e& r             p=NextArc(tmp,p);
3 L8 A! z) M6 k          }
) v, W" S# ]* e, U* ~) D       }
* h% A, }0 S5 I' C. {; Y }9 D% F$ K* p8 E0 _3 Y; M
}* R5 T( a* Q7 ]. r5 f9 }
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()0 R" D! p" A! X$ j, S/ k
{' X. `5 R  `; T7 y
MultiAdjListNetworkArc<WeightType> *p;
/ T$ I) @! S4 j8 w cout << "无向图有" << vexNum << "个点，分别为:";
; Y5 O1 L  ]8 z- Z3 P  D) U for (int i = 0; i < vexNum; i++)
5 ?& X6 s  P3 P       cout << vexTable.data << " ";1 r, ]8 N" }) t) t: `' i
cout << endl;  {  o6 r/ x7 }; E9 t6 A: G
cout << "无向图有" << arcNum << "条边"<<endl;# O& b$ _- M+ b) G7 C7 t
for (int i = 0; i < vexNum; i++): N$ v5 v3 Z- U/ I8 f5 x8 e" [" C
{' V  N6 D# `- V: Y6 q' I/ S
      cout<<"和" << vexTable.data << "有关的边:";2 C# e* t% @8 }. f! V4 ~
      p = vexTable.firstarc;3 i. `- m+ m+ M( b
      while (p != NULL)6 Q3 K3 w0 {$ w5 j1 ]4 B9 \
      {
- z4 T; x% _/ _5 P! L3 y) S          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
$ |( S3 ?3 i' |( f& O6 ^          p=NextArc(i,p);
' ]! a" Q7 ~9 }2 H6 a7 K       }
( V/ o+ r) ~5 Z+ ~2 F+ S! k9 b8 _       cout << endl;+ t. U1 E& P! F+ d7 e$ o
}/ j3 t5 d0 I( K0 h
}* O7 |+ ]5 u) Q. C/ o

- [. {& E3 T" B4 C9 v2 m* d
  T" [5 ~# `: N; K邻接多重表与邻接表的对比7 f5 N1 S$ m8 B
/ f' L% Z/ w: ^1 B5 P5 ^8 W
邻接表链接) ~# |7 @9 \: c# U; k  }, H+ \
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
. [8 \$ u% `" h' o2 C在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
( M# W! M9 J% i! h# I; v为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
& ?4 T  Y" n- P. G; I8 a0 I4 B————————————————1 e" i4 F3 @$ E+ F
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。1 v3 B8 v* X% j4 K: b6 d: u
原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669584 @4 J7 u9 r2 u$ U
' A& b9 e& @( [; R! _
& B  y7 }& I3 Y  P7 [
% O+ S# J+ _0 e: j5 y$ j( |

' q' [' V% `& W- l& \8 u+ k! W% b————————————————
; H+ {5 t4 q5 F% \% |+ d版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
+ l, k' [+ K6 l原文链接：https://blog.csdn.net/qq_43413403/article/details/1057669585 l+ B% E' n  p; [1 Y, @
* K5 ?8 m* Y: Y5 h( h/ o

/ v* K' P# y3 m+ n. P