数学建模社区-数学中国

标题: 图的存储结构——邻接多重表（多重邻接表）的实现 [打印本页]

作者: 杨利霞 时间: 2020-4-26 15:26
标题: 图的存储结构——邻接多重表（多重邻接表）的实现

图的存储结构——邻接多重表（多重邻接表）的实现
7.2 图的存储结构

7.2.3 邻接多重表（多重邻接表）Adjacency Multilist
邻接多重表的类定义
邻接多重表的顶点结点类模板
邻接多重表的边结点类模板
邻接多重表的类模板
邻接多重表与邻接表的对比
7.2.3 邻接多重表（多重邻接表）Adjacency Multilist

在无向图的邻接表中可以看到，每一条边（vi,vj）在邻接表中有两个边结点：一个在顶点vi的边链表中，表示(vi,vj)；一个在顶点vj的边链表中，表示(vj,vi)。
在较复杂的问题中，有时需要给被处理的边加标记（如访问标志或删除标志等），若用邻接表表示，则需要同时给表示某一条边的两个边结点加标记，而这两个结点又不在同一个边链表中，所以处理会很不方便。若改用邻接多重表作为无向图的存储表示，则可简化上述问题的处理。

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：( A( w3 k2 P' `/ o6 @. A
data域存储有关顶点的信息；
+ ]- v% y+ n1 m/ U6 {) c& g; Lfirstarc域是链接指针，指向第一条依附于该顶点的边。1 S' W3 u$ B' G! y/ U) Z0 _* E; T3 ?
所有的顶点结点组成一个顺序表。

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;0 M6 P$ f1 @/ N- I2 S" N8 N  ^
for(int v=0; v<vexNum; v++)
' D3 b+ T$ {7 v+ g' L6 V. D2 e$ n {
3 A, _* b& Z- Q1 e" U4 }       if(tag[v]==0)" ~  Y* s; H8 \5 x% `1 x
         DFS1(v);
, r$ u" i7 h* F }
: c  T( X! ^9 \- E5 P}
9 _/ G3 M% l* c8 L8 p' Rtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()  Z9 }( ^) S) p7 a
{8 R; G9 ~% a9 J$ q, s+ f
stack<int> s;7 d; C7 J7 b' _
int tmp;5 Z) U- Z5 U$ z
MultiAdjListNetworkArc<WeightType> *p,*q;% T$ K$ Q5 m9 x5 ^6 t
for(int i=0; i<vexNum; i++)
1 O$ x8 u( ]- u( t       tag=0;0 h6 U/ ]) i" f5 }# |+ C+ R
for(int i=0; i<vexNum; i++)
2 i" ]8 l6 q+ D- Q) E {& j2 S" Q$ m8 l* f+ x
      tmp=i;- y. S- P9 d7 |2 Z% R
      while(tag[tmp]==0||!s.empty())+ ?. V6 r" K4 u# P
      {6 `; O4 p! p& ]+ t& ~: r& B0 X
         p=vexTable[tmp].firstarc;- b) \, G- V6 q2 h' G/ i. B2 ^
         while(tag[tmp]==0). O- l% b5 K$ H4 I
         {; A: t9 N* i" R; r% H  h
            s.push(tmp);  |7 x9 k: N) ^' ]# ^2 h1 {9 B& R
            cout<<setw(3)<<vexTable[tmp].data;0 ~' @+ |" T6 z' J
            tag[tmp]=1;
6 ~* }) d; i: E             p=vexTable[tmp].firstarc;+ l4 D, p3 U2 p) b8 X- o
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for( W$ y! m% s* O
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);' c4 a, H1 I3 ?9 e& I  E
            //cout<<" 1st    tmp="<<tmp<<endl;/ L9 L) C" B- @8 {6 P5 M6 V0 Z
         }
. v' l' B( \7 E5 D! }; w          if(!s.empty()), \5 O+ t4 F% g. n8 l1 E
         {' G5 H9 n/ C6 z  ?& R
            tmp=s.top();
9 Z) P/ ~5 X  a2 U9 _6 u             s.pop();3 L- p4 T, L8 z
            q=vexTable[tmp].firstarc;7 I& L2 Z& u2 a, J& L/ e3 h8 a1 ?
            int t=tmp;/ f( ]6 L, Q6 ]
            while(q&&tag[tmp]!=0)9 v; g+ h& a4 m7 f; i; d% E+ B" ^! e
            {% j0 c" x. I% P9 }( O* M3 o
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
. O, v& J; H' v+ w* @0 W: r) @                   //cout<<" 2nd    tmp="<<tmp<<endl;
9 A) S9 Y; I; K1 h- z( G                   q=NextArc(t,q);" o1 f0 `3 ]8 h0 ?. f. u
            }
  N$ _# N- K* T$ C8 B: |             if(tag[tmp]==0)
5 h6 M9 z, @- o$ K6 ?# J                   s.push(t);
! T9 u% ^: t% f+ o) X: Z; H             ///1、对应上面连通分支只有1个点的情况
2 `; t7 `  r" m5 x; _) t             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈" z% n- U- }! E9 F, _- r6 E) c; \
            ///tmp要么等于找到的第一个未访问节点，+ u3 \* U1 _1 W, ]- v) u
            ///要么等于与t相连最后一个点（已被访问过）
+ L1 f0 K: t& T7 I+ J4 w, e             ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点2 V: K3 f9 G, w6 q" I1 ?
         }: O9 ^+ e% p. ]+ o: v3 s
      }% G$ y6 U( w# E0 O2 N/ X& u% z& ?9 W' v
}- k" h3 I! u8 h  @: z; b8 D& E
}2 F5 `, u) N$ T4 K
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1( T9 x# z6 W( _" O9 G0 T. f
template<class ElemType, class WeightType> int( e2 {: X: \4 @; d, y! S
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)/ M) d% p% V; c: M
{
if(head==pre)
9 G. y9 [3 o1 @3 [' f2 @. a       return -1;
) r" W( B8 ?' ^6 ^$ h- k8 F: |# b7 d
MultiAdjListNetworkArc<WeightType> *p;4 `* j. z; u& t# }# [0 n. H9 U
p=vexTable[head].firstarc;
+ `& f* G/ l$ M: k if(pre==-1&&p!=NULL)( x; P4 H( v+ N
      return p->adjVex1==head?p->adjVex2:p->adjVex1;8 w2 ?% c* ^1 o+ }, p0 Q& W  y
//pre!=-1&&p!=NULL( B7 P( g8 _  t6 H; u
while(p!=NULL)
# o* C, X$ o* B6 O" F$ f {
- Z- J; K* E! V) Z" a2 X       if(p->adjVex1==head && p->adjVex2!=pre)8 D# T7 j% `$ h
         p=p->nextarc1;
+ O0 ]: \4 r. H$ I7 `& `       else if(p->adjVex2==head && p->adjVex1!=pre)
: z+ f" a$ l. s* G; `          p=p->nextarc2;8 `7 ^% X2 ~, r* P6 A
      else if(p->adjVex1==head && p->adjVex2==pre)+ F9 R# Z( j! _  d
      {- M1 @  ]7 X  t
         p=p->nextarc1;7 ?9 ^$ `5 A7 @) t% P% b
         break;) n4 v, T* F% \3 d. k
      }
6 a9 X# {( ]& ~, g' j7 s       else if(p->adjVex2==head && p->adjVex1==pre)
" S- o& ]0 R/ i3 L/ I& h5 y       {
( M/ [! c: r: P0 R3 S) g$ h' L& [          p=p->nextarc2;( E# a" u$ T* Z9 R
         break;% {1 i) V: I1 @" f
      }) _, e2 Q& i: e
}
# t; ?! E- {! ]% t0 V  _ if(p!=NULL)
* R5 Y) V. r0 g# Y# H; O4 u {5 j2 n8 p; a: Y3 \, N/ t2 T' d  k1 F
      return p->adjVex1==head?p->adjVex2:p->adjVex1;) O! ^; \- }9 Y/ Z
}
/ O5 `9 E$ m0 c else) B5 s% ]/ V  h# T% p" l
      return -1;
+ q3 `. s* {0 [! P3 ]}
! r6 l9 s0 v) x- H/ a% L9 H6 t
+ X3 V9 I6 x8 n/ D: N0 A$ @9 n, f: U+ _
0 a, R+ v6 K/ }. v1 ~template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()" \( e6 D- B$ P% ]
{
& ]7 ~+ S6 |  ]8 k. I; y9 F stack<int> s;
2 v  A1 y4 |9 \/ M5 R1 q int p,cur,pre;
% ^4 J3 s: \0 p! O# n //MultiAdjListNetworkArc<WeightType> *p,*q;) m# j- d$ }" q/ L
for(int i=0; i<vexNum; i++) tag=0;//初始化4 w7 y, x- Z& S: U+ P7 H9 A- B( {% C

; q$ T# R4 g2 t. W! M: O4 I for(int i=0; i<vexNum; i++)
7 ]/ E) v4 B4 J+ {6 j& | {
# @; k( t- e  D8 I! ^, e       cur=i;pre=-1;) a5 N+ C+ K8 S) D1 u
      while(tag[cur]==0||!s.empty())7 y, u/ X& ?) I# }& |( C0 o
      {
3 L! A: f  c! `$ Q3 W" J          while(tag[cur]==0)' L; y* C  n0 U! `
         {
, M* a8 ?$ p6 r6 i4 V             cout<<vexTable[cur].data<<"  ";
1 ]& K# _. {6 d, C0 [; c+ X             s.push(cur);
4 x0 E  c- G4 X6 p             tag[cur]=1;
4 q- e7 V1 |+ c! P1 ^% f7 |             //初次访问，标记入栈3 L; v( u/ }- e

# Y$ b8 ?3 c) y( {9 ?             p=GetAdjVex(cur,pre);//p是cur的连通顶点
% ~# j9 f4 c8 s) F7 r# [: U% M             if(p==-1)8 g# L7 q% c% Z8 f9 g) Q
            {
6 c5 [2 V3 j) X' Y+ E! \1 a+ l                pre=cur;s.pop();  y2 x8 z8 }9 N5 W
               break;
" Y- V8 N+ E1 i8 t$ L" `) ^6 _# O7 x             }5 N! |. S% ~; P7 w: a0 M
            else/ z* H% c9 h0 G; {, R
            {
% ]7 f& E. g0 @6 U6 q                pre=cur;
7 I: c- `1 d2 ^* O0 d                cur=p;9 ]0 q6 W; A4 d/ M% P" ~" x6 P
            }0 ]- [# r/ Y4 K4 x! h$ V$ w% s5 }

% \0 j9 [7 l9 M& v1 s' m          }
3 `# s9 B: p4 `4 E  l4 y          while(!s.empty())
+ a4 ]& `2 y; D7 Z4 O0 U          {# W. ~3 M: @: p7 `7 m; u
            cur=s.top();. s' Y7 L+ [: u  P% J" d
            p=GetAdjVex(cur,pre);0 t) e( ~  `0 l
            if(tag[p]==0)
& t, _) |/ C8 s" `             {
$ n4 u- `, }: i: o' J5 Z9 O$ L% i                   pre=cur;6 e4 T+ ?+ E' p. h/ ?
                  cur=p;! E1 X, |6 P" l5 Z: b. ?6 \3 ?% @
                  break;
& I* C: ?/ @; A8 H             }' _% n3 I+ p& T8 m% R
            else
, m; n. j. D# Z) z' d4 g             {; b  K5 g0 |! e! |
                  pre=s.top();
) _7 o. q" ]: _! ]                   s.pop();  R  Z, j: x' d  X& \/ |
            }9 W$ w3 ^5 W2 R* ~
2 Z5 ]2 z+ E& V( s5 h1 L
         }) Y; h! P4 Q+ U$ Z

% x* j7 a6 e, J4 E0 S2 [" c( X1 U       }. \4 F" E9 _2 Y  {" u* f" n
}# _0 @8 R) F8 h5 E2 X8 t. W5 V
}' W( V+ x) \' k, T
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()) ~9 E. C. \4 m6 M. X$ G5 O+ D3 t
{
- [8 i: j. e7 j3 l( N3 b- m for(int i=0; i<vexNum; i++)
; I% o+ ]2 h, d       tag=0;8 V# H9 O9 @# E/ P/ O1 S- S
queue<int> q;8 n% }  F% o* R3 T* q
int tmp,t;/ d) H( [9 ^7 l  X
MultiAdjListNetworkArc<WeightType> *p;
: I3 S! @* a- _+ E) q) p for(int i=0; i<vexNum; i++)
( Y- W) B1 k0 g2 e {
: S5 k  M2 O' _% Z, h       if(tag==0)
6 G' F3 O) z8 ^* T; w$ @1 ]       {6 N% H3 `6 S. o' d. Y; ^, `' W
         tag=1;+ q! S0 ~1 a* z) W3 f0 a% d1 a" ]3 \
         q.push(i);" C, Q. d4 v8 s5 h- b. X
         cout<<setw(3)<<vexTable.data;
9 n2 D7 [7 M- q  J       }( i  y  L/ X2 h. ?: s+ k
      while(!q.empty())6 T: e9 ?8 Y! z
      {% K6 U) P' i1 H$ e' V
         tmp=q.front();
5 l1 Q2 k9 I& E0 T8 I7 E          q.pop();
- x( d4 ]: w( i0 i! q( C1 ~- U% S, ?$ e          p=vexTable[tmp].firstarc;
" D, T4 x( `/ r0 ^, K          while(p!=NULL): Z$ J% |* X: l1 R% g# a
         {
8 g" h1 c2 n% _7 _2 }. o2 s             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
  o. i' P$ m9 l7 G% b# i7 q             if(tag[t]==0)
0 M: y1 R( K% _# q             {
4 X7 @' g2 B- k1 z' x$ ^                   cout<<setw(3)<<vexTable[t].data;
( r, f9 n& A0 w- _' G; B( W                   tag[t]=1;
. U! A1 l2 Y, v9 }! {! C: p                   q.push(t);
/ r# s# ]5 \# O4 ?             }
% H. k, R, U$ H8 n; ^; h: q             p=NextArc(tmp,p);
8 D1 K7 T: S5 ~3 S          }0 \0 E6 y. L+ Y
      }
7 Y1 [% |; ]- D; o0 d }
8 s( s7 w) [* g0 w& S}: R3 @, u/ N( I9 R4 p
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()1 T' d# W9 p  Q' C6 K- D! O
{: l# _- K9 G9 p0 {, Y) F
MultiAdjListNetworkArc<WeightType> *p;, k2 u& {* \" s! `5 g
cout << "无向图有" << vexNum << "个点，分别为:";
9 K7 @8 ?4 \( z& {* h$ T2 z for (int i = 0; i < vexNum; i++)
9 a8 F* D5 P/ H" `8 k: O: [3 H# U       cout << vexTable.data << " ";
* m& `4 S; v9 u% U5 g' N cout << endl;
, {2 r6 d' \: e% F( I cout << "无向图有" << arcNum << "条边"<<endl;! _& u! `, m6 ?/ r
for (int i = 0; i < vexNum; i++)% e: c% M8 T% d5 }1 A% `
{  e/ ~  c! N+ H+ ^$ H! S1 w
      cout<<"和" << vexTable.data << "有关的边:";. K. y: q" U; Q
      p = vexTable.firstarc;4 A: N$ [5 H& N: F1 J
      while (p != NULL)$ o# n5 B9 d2 ~, D5 h3 e
      {. b% C5 B2 B/ V2 ?, p" g
         cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
3 u+ y2 h7 h! Y: j7 ]$ ]0 g1 q          p=NextArc(i,p);+ I. Q4 c8 C9 P7 b2 z% I1 t
      }
9 u0 E6 V: _3 y0 r       cout << endl;
: l! l4 R% L( i }0 X8 Y$ j3 H' }. U+ U! E  s1 M
}
8 Y5 ^1 H& g* @& T( p/ K: d; Z
( `" v7 j# f& H, {2 w9 F- P1 m
& R/ b2 p" N- U0 ?# i5 |邻接多重表与邻接表的对比
1 A" k+ T. N- i% W+ c
1 j1 \5 v# B1 \* |" ]0 Y* Z+ ^4 k; Y邻接表链接
( Q" M7 O: E3 H# F2 R# d在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。
' A! o6 x5 p' F6 x在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。5 G  c" L+ |7 q0 H! x3 {
为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
) Z: b; ]) F+ I  T9 U/ I- L————————————————
& T" |. @+ M) z" X& g! B  c9 r版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。& @6 m; T3 i$ a  _4 x& O
原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
* ^: @4 U  n5 o6 u9 D1 [' f; }1 S7 Z% ?+ V; N9 ?* x; I% A
3 v) [% a! @- Q" F7 l
- k. ~% A4 Y) a% L: a
( U3 E, m+ U# l' T* m3 d/ c
————————————————1 A7 v$ ?1 E* N
版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
4 w6 K7 d  d* w  W+ j6 k原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958
* _9 i! h- G" w- N6 E1 t# W" A+ u2 Z+ t; a9 ?" x1 H, v

% `- D2 x1 Y  ?9 @" j) k& G

欢迎光临数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5