数学建模社区-数学中国

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

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

邻接多重表的类定义

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

对图中的每一个顶点用一个顶点结点表示，它有两个域组成，其中：8 \) O% j# l# l
data域存储有关顶点的信息；
6 n0 N- |0 b" C5 y7 |! @$ N8 I3 L, lfirstarc域是链接指针，指向第一条依附于该顶点的边。
1 z2 B j( y# h, s! r所有的顶点结点组成一个顺序表。

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;
% N" M, [4 Y9 P  k  a for(int v=0; v<vexNum; v++)
! O5 ~. a1 z3 j {" g$ V. n5 V5 Z2 f- C5 J) e1 }
      if(tag[v]==0)7 ^+ A# L, A9 B
         DFS1(v);
0 B/ N& t5 J+ I }
6 ^3 @: l0 ?% c; A8 f: o/ W5 O, p}( X! p# ^) ~+ y+ P3 ?
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS2()
/ L& ~% e& r$ M# B( t{% a# @" J* D+ P
stack<int> s;* ?2 B! t6 ?4 L6 A, i& a
int tmp;
' J# r1 a% r0 O5 `4 V MultiAdjListNetworkArc<WeightType> *p,*q;
7 U; ?  s, v/ C( f for(int i=0; i<vexNum; i++)
) Y% B: L2 A- \; Z8 E$ n       tag=0;* C; X2 ~4 S, @2 w8 w! T' M' l; O( s
for(int i=0; i<vexNum; i++)
: G, E* t& l1 `" n  i {
! u: ?# x' ^% _, G/ [       tmp=i;
" |- t) h. b/ P# S$ j       while(tag[tmp]==0||!s.empty())
" m& O7 u5 O9 u" n: T- F( b4 P       {/ [$ U2 o  i' d- }6 a- m
         p=vexTable[tmp].firstarc;
$ i9 C9 {3 z1 ?4 S& N7 j; Q  N          while(tag[tmp]==0)
' e- ?- Q* e5 q+ Y          {) A7 v& b% p( }# C0 |6 c
            s.push(tmp);- l6 l4 z; u0 ]! c% ~& [1 d
            cout<<setw(3)<<vexTable[tmp].data;
! h) x7 m9 }0 K( M& d             tag[tmp]=1;( h$ q6 h$ {7 p
            p=vexTable[tmp].firstarc;. q% w) {7 V1 Q$ a
            if(p==NULL) break;///该顶点没有边，连通分支结束（1个点）先出栈再跳出循环进入for( m4 f: u1 t5 u- e& r5 x
            tmp=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);
& ~& K8 y( w. V6 H4 n+ W             //cout<<" 1st    tmp="<<tmp<<endl;
- e! o; F/ O1 t          }
! ]3 \) ^& O6 J1 _  M9 x8 N& k          if(!s.empty())
5 p5 [( ~* k5 n# O4 s          {5 ~+ r2 M4 k9 X, q
            tmp=s.top();* o8 z/ j" {& ~& b
            s.pop();
, v; S/ m5 R5 N# N             q=vexTable[tmp].firstarc;
( M; h% u/ b( u; G/ v             int t=tmp;
! L1 Z" {+ Q* c1 s1 l9 s$ d             while(q&&tag[tmp]!=0)& k+ g4 P1 Q5 ^; B
            {% L$ C% t6 N2 Z2 S9 t' g1 |
                  tmp=(q->adjVex1==t?q->adjVex2:q->adjVex1);
* P. J+ L4 o: B5 Y* f9 D. ^6 C                   //cout<<" 2nd    tmp="<<tmp<<endl;
0 P' k0 ~8 v; h4 w: m  L% [! o                   q=NextArc(t,q);/ x  }. @3 j% w
            }
- z0 T7 H# W+ a; d" u9 O             if(tag[tmp]==0)
2 y, x. v' f* m/ C/ j                   s.push(t);. Q5 K# J2 a' y9 i) W9 W
            ///1、对应上面连通分支只有1个点的情况
7 X0 k" J, q9 e& i' }             ///2、t上的点都被访问过，此时tmp是t相连的最后一个点，用于跳过上面while，再次进行出栈
0 `9 X4 K7 {! r+ ^) f$ ~* _& a             ///tmp要么等于找到的第一个未访问节点，
* O& M- i; F0 P  K             ///要么等于与t相连最后一个点（已被访问过）+ I- P. [" N% T# N
            ///当连通图只有一个节点时，这时tmp=这个已访问的孤立节点
& I, @0 ]2 k5 Y4 n0 f9 `          }
2 X/ n+ \+ ]8 i; H0 g. C       }
/ M" q1 `, J- d5 S0 W" ]8 y, J }  s0 J9 V  v# F6 i& K+ L; G
}/ n$ _6 P# s- ?- y
//从顶点v出发的一个顶点u，返回v通往的下一个顶点；如果没有其它分支或者已经是最后一个连通点，返回-1；如果要取第一个顶点传入-1$ r: B0 }4 V* w6 r5 w
template<class ElemType, class WeightType> int6 F% H1 y% U8 p) \. ?
MultiAdjListNetwork<ElemType, WeightType>::GetAdjVex(int head,int pre)
) a! K( a2 h  b. i{# |/ U9 [5 ^  ~1 P# O% V
if(head==pre)
: X9 v4 {( \* r  T+ [6 F. f7 Q       return -1;
$ I2 T0 X! k! E2 G" g
( q, g5 e2 x( }3 t3 h MultiAdjListNetworkArc<WeightType> *p;
3 t. K$ M3 |0 R1 I7 c: N8 g' G p=vexTable[head].firstarc;
- s* X$ Y: f6 {. A: i+ E if(pre==-1&&p!=NULL): r& R; N, o# U$ _3 B4 d
      return p->adjVex1==head?p->adjVex2:p->adjVex1;
" \4 z# m7 A# ?6 x, E //pre!=-1&&p!=NULL! g3 c+ |, N# s% p! u
while(p!=NULL)
& v, R% s, W: O. y: c' U! z {% x: y6 C3 C' A
      if(p->adjVex1==head && p->adjVex2!=pre)) K, g9 Y+ m* D) c1 ?' Z# t
         p=p->nextarc1;  _9 ~; b& R, v  _
      else if(p->adjVex2==head && p->adjVex1!=pre)
! q' p1 u+ X! B  Z- e( r; I2 Y8 @9 l          p=p->nextarc2;3 z1 G7 x# k7 q8 \: O
      else if(p->adjVex1==head && p->adjVex2==pre)
) A1 N% J. P5 m4 J       {
" o' Z6 W; {# q  u          p=p->nextarc1;
2 y$ m2 r1 f; B: T, P( t6 O          break;9 ^, e! v) U5 s
      }' W! ]: s* K9 z. G
      else if(p->adjVex2==head && p->adjVex1==pre)
3 u% y- k( F6 d- x% ]( F0 h2 A" t       {
2 R( V3 Q. ]9 N6 l2 S; p# \          p=p->nextarc2;
- p( I5 i& Z( E- x          break;1 n3 v- C" K) w8 f
      }
/ l+ J# \: I" o( p! Y- s7 L }$ i% \# \  U( g6 ~% z2 W5 i
if(p!=NULL)) W# |- V1 Z, j
{
$ d) _/ `% B$ g8 B" H; _' D5 G       return p->adjVex1==head?p->adjVex2:p->adjVex1;$ P1 ?: K5 X. h0 ]( v" h
}
! O. j. ~: G& Z  ? else' D8 Q. C( i3 b: B" [* O
      return -1;
2 i. i1 p5 ]- k}
' l  d8 A9 z* b  U$ j2 a4 S' B
; V- B; z2 P. U( |3 ]
' y& H) F5 E6 h' p3 ~template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>:FS3()
' C5 o( R) f. s+ M( y{2 `* y( U8 v. @# F1 `. w  _
stack<int> s;
7 `$ W" P" j3 C int p,cur,pre;
- l( i. K! s- v  o //MultiAdjListNetworkArc<WeightType> *p,*q;) e$ U" G& y7 C% u# W, x
for(int i=0; i<vexNum; i++) tag=0;//初始化
* M& n  O# f3 C* \2 v) Q/ P" ?3 s( P5 P% q) B1 k7 o
for(int i=0; i<vexNum; i++)* t7 ], p5 i1 r) I$ F
{* s  [1 O( p. @& n( v3 b! D. L
      cur=i;pre=-1;
; H8 e. Y. U" D0 s       while(tag[cur]==0||!s.empty())) j: n7 [+ |5 j+ g! X
      {
7 T+ I3 q! ]) J, X* K( j          while(tag[cur]==0)
8 Y2 s- c+ `7 \1 n) ~/ ]          {$ A1 A) C) }1 w, b  ]3 [- z' c
            cout<<vexTable[cur].data<<"  ";' d- S3 X. y+ U! }3 R/ ^7 B' d
            s.push(cur);6 m% N8 u* g  S( G# }
            tag[cur]=1;
6 k  {* O3 @* k* Y$ \8 c" G             //初次访问，标记入栈+ e% d( ^# d# o

4 G! X2 p5 W3 z- e7 x             p=GetAdjVex(cur,pre);//p是cur的连通顶点: H; P3 |6 X% C* N
            if(p==-1)9 e% z: R' B9 L, L3 p
            {! X7 o/ v8 Q" V& W, z
               pre=cur;s.pop();5 F! \: y5 \  q: R* v& j5 T5 {
               break;# w7 y) R! x2 B: k$ C# ~- w" ?
            }
4 k" n4 A0 \0 Z4 P9 H             else& l$ T5 A" ^9 \, c* u1 S& r7 P& r
            {! D. c% ?, Z. N) C8 `2 O: f
               pre=cur;
# I8 r" v+ r, v, [5 ~; i                cur=p;6 J. k. L6 C) q2 M; g% u! t' D( i
            }
- S! P3 b0 ]6 l, w* W7 U, l* y- g2 x( @+ A  v. g) c
         }- N5 h8 L- Y4 c4 f/ Q
         while(!s.empty())4 z/ M9 c/ h6 S  I
         {- m$ s3 e& W- v- @" z5 e8 ]
            cur=s.top();
) Z! H4 l/ T7 g& O' q             p=GetAdjVex(cur,pre);' x% }. O, q% n( a' g3 F
            if(tag[p]==0)
2 e7 K7 ]" B1 q             {8 @+ P" U& I5 v' \3 q' a
                  pre=cur;7 C% g; y; v7 {
                  cur=p;
8 k  k7 O- Y7 {5 g* Z! [                   break;
2 o; n4 _6 L$ N. V: |5 M  @             }% P+ C3 I- y$ v. T$ s6 z( u
            else
, ]9 E5 i! ]& b2 K, h3 y             {
/ W0 |& S+ ?& A7 a' K7 ]+ P2 m                   pre=s.top();
( i/ Q1 v* T4 b  f3 H& U7 o& G+ r! m                   s.pop();
- s! a) x9 T( C% @- C1 M             }' P" Z& x+ X* g# w
+ U% z; Z$ I3 }
         }
! @1 Y8 d( j+ w  H: d, a2 O( d' D7 X0 S7 g) b
      }
0 d& }1 n1 C9 e+ B# e: I }6 Y* ]5 w. X" J# W" Z' ~
}! F1 _5 Z7 h# d& p
template<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::BFS()
: B0 H3 o0 ^, A% O{2 a3 m) [& c; }+ O) ?/ n
for(int i=0; i<vexNum; i++)7 `+ C; W) ?: s6 U
      tag=0;7 \+ I! A+ n" s; ?9 z8 F
queue<int> q;2 W) g3 s- p. [" d
int tmp,t;/ t- t8 Z2 E# c$ p' o- e3 R
MultiAdjListNetworkArc<WeightType> *p;, K8 J1 R' r- m& X6 ]% a
for(int i=0; i<vexNum; i++)) ?- \' K3 E) [
{& |' Q0 @( P, }* r- E
      if(tag==0)
3 m2 z9 p3 j  D       {
* V! X/ g2 @1 G4 g          tag=1;: J1 f' l9 X) @) T. m$ y' H+ K
         q.push(i);
9 I7 t5 g( ~0 t$ p7 k          cout<<setw(3)<<vexTable.data;
( D0 U& k, t& c  B9 e       }+ o$ J5 M9 c7 Y9 t4 a- k
      while(!q.empty())
- ^6 }  c" t) u9 z+ ?1 T0 I       {
. z9 w6 E& Z* O# e9 R) V          tmp=q.front();
6 l! b/ I* f; m3 Y          q.pop();% D+ z, o7 N7 U) M
         p=vexTable[tmp].firstarc;! I5 j1 {4 D( |( W- H% X
         while(p!=NULL)8 I4 ?" }7 G- P+ l8 w& i% C' i( c
         {
/ E* B( f5 [  N( U) z             t=(p->adjVex1==tmp?p->adjVex2:p->adjVex1);% S$ i* ?1 K( T# v: E  I$ y3 `
            if(tag[t]==0)4 r9 @# ^$ A; g: B4 h
            {/ ^) B  Z, Q( D& T( K* h) F
                  cout<<setw(3)<<vexTable[t].data;0 A8 i2 L- A+ [. j! W/ l) J+ S( Z+ y
                  tag[t]=1;
! Q% m/ i7 l0 L: o                   q.push(t);' t( C; ^: [+ B/ ?; T3 Z0 S: T5 W
            }
5 {* a: r/ d2 Z' @. O, ^' C& Z, `             p=NextArc(tmp,p);
6 P9 t5 Z) W/ ~. w: C2 S          }$ Z) ~0 K5 l3 C+ \& T
      }8 h, h9 ]1 B' z$ Z
}6 M7 p# }" w  _# f) t- J  H' v
}
* B) @$ k; Q0 k2 P. X" P8 e( t" o* rtemplate<class ElemType, class WeightType> void MultiAdjListNetwork<ElemType, WeightType>::Show()
& Z0 u& n+ {. T7 }6 Z{  s4 s2 m9 L9 l. G' ]3 I
MultiAdjListNetworkArc<WeightType> *p;4 J- C1 X- f& j4 ~7 y
cout << "无向图有" << vexNum << "个点，分别为:";% x0 }& N1 T# ^% h3 p( I
for (int i = 0; i < vexNum; i++)
% w/ l) K7 E. A/ d       cout << vexTable.data << " ";& g. d3 M$ z1 m! a& w  ^$ B; F1 g
cout << endl;
0 m. y, w+ K' K cout << "无向图有" << arcNum << "条边"<<endl;% F# G, Y  e! w8 ]1 p; C
for (int i = 0; i < vexNum; i++)
: J  O3 R0 z; I. z- x! o: ] {7 z* P- M2 N( k
      cout<<"和" << vexTable.data << "有关的边:";( E2 Z- B% J8 g: @( m
      p = vexTable.firstarc;
& w9 h' s7 O7 e2 |  q7 p       while (p != NULL)
7 Z0 R: e3 j& o       {
, G* j! k4 P% c* E$ [- R" _          cout << vexTable[p->adjVex1].data << "<--"<<p->weight<<"-->" << vexTable[p->adjVex2].data << ",";
. I% ?  E; d. i( m4 _: v) b          p=NextArc(i,p);% F& W0 f# V7 {
      }* U% ~& ^% r4 k+ m+ D# _7 i1 m
      cout << endl;
; T! V/ F. I3 p& @( c. W( W2 i }) p2 s% P* o  E/ [8 ?2 `! J5 `
}$ O7 `" G% h) d2 H: `: Z
; `+ z; j4 F7 j# p8 g" v5 _

" h) u2 \. L/ P* `" b邻接多重表与邻接表的对比
* ^' }* y; r) g' M2 L
# F/ E' Q2 [* D& k邻接表链接( u! q3 p! r1 Z& C% L4 S
在无向图的邻接多重表中，所需存储空间与表示无向图的邻接表相同。7 k0 Y$ l1 N% e- @) I6 M
在无向图的应用中，如果更加关注图的顶点，那么邻接表是不错的选择，但如果我们更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，那就意味着需要找到这条边的两个边表结点进行操作，若要删除某条边，需要对邻接表结构中相关的两个结点进行删除，显然这是比较繁琐的。
5 P) H7 M% V  f9 e! Q( D' m为了提高在无向图中操作顶点的效率，又有了邻接多重表的存储结构。邻接多重表与邻接表的区别在于，同一条边，在邻接多重表中要用两个结点表示，而在邻接表中只需要一个结点。此外，邻接多重表中增加了标志域用以标记该条边是否被搜索过，避免了同一条边的重复搜索。
* c2 d# L( I4 E9 v  b7 J) R6 z————————————————
6 k# a, |; y% ?" Z  h1 |版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
5 t* u3 t. U& U9 J- ~原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958# r2 D4 ^, \' h

% u- {2 u: P: {- h' c' _1 Y% B# I# J" r, D

! @5 c. d) r' @1 U7 V' U" x  U/ C; Q: |: N8 L1 L. c( |
————————————————
" p6 A$ d2 j! J( i版权声明：本文为CSDN博主「lseaJK」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
2 O) _$ }# H4 _" u: g, b原文链接：https://blog.csdn.net/qq_43413403/article/details/105766958+ @, {& B; z& P7 e4 P( A

! m$ G" }5 @5 O7 H. o- v; h: ]) ]# g/ R" M  C

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