邻接多重表存储无向图以及有关操作(五)

p=p->ilink;

}

else

{

if(!visited[p->ivex])

DFS(p->ivex);

p=p->jlink;

}

}

}

//广度优先遍历

void BFS_Traverse()

{

for(int i=0;i

visited[i]=false;

for(i=0;i

if(!visited[i])

BFS(i);

cout<

}

void BFS(int v)

{

visited[v]=true;

cout<

EBox *p;

int pos;

queue qu;

qu.push(v);

while(!qu.empty())

{

pos=qu.front();

qu.pop();

p=adjmulist[pos].firstedge;

while(p)

{

if(p->ivex == pos)

{

if(!visited[p->jvex])

{

visited[p->jvex]=true;

cout<jvex].data<<" ";

qu.push(p->jvex);

}

p=p->ilink;

}

else

{

if(!visited[p->ivex])

{

visited[p->ivex]=true;

cout<ivex].data<<" ";

qu.push(p->ivex);

}

p=p->jlink;

}

}

}

}

void Mark_Unvisited()

{

//置边的访问标志为未访问

int i;

EBox *p;

for(i=0;i

{

p=adjmulist[i].firstedge;

while(p)

{

p->mark=0;

if(p->ivex == i)

p=p->ilink;

else

p=p->jlink;

}

}

}

void Display()

{

//输出邻接多重表

int i;

EBox *p;

Mark_Unvisited();

cout<<"顶点为：";

for(i=0;i

cout<

cout<

cout<<"总共有"<

for(i=0;i

{

p=adjmulist[i].firstedge;

while(p)

{

if(p->ivex == i)

{

if(!p->mark)

{

cout<jvex].data<

p->mark=1;

}

p=p->ilink;

}

else

{

if(!p->mark)

{

cout<jvex].data<<"--"<ivex].data<

p->mark=1;

}

p=p->jlink;

}

}

}

}

};

文件"main.cpp"

#include "graph.h"

#include

#include

using namespace std;

int main()

{

AMLGraph G;

G.CreateUDG_AML();

string v,v1,v2;

cout<<"输入顶点名称，将输出其相邻顶点：";

cin>>v;

G.Find_Neighbour(v);

cout<

cout<<"邻接多重表结构："<

G.Display();

cout<<"深度优先遍历序列：";

G.DFS_Traverse();

cout<<"广度优先遍历序列：";

G.BFS_Traverse();

cout<<"输入你要插入的新的边的两个顶点的名称：";

cin>>v1>>v2;

if(G.Insert_Arc(v1,v2))

{

cout<<"插入成功"<

G.Display();

cout<<"插入后深度优先遍历序列为：";

G.DFS_Traverse();

cout<<"插入后广度优先遍历序列为：";

G.BFS_Traverse();

}

cout<<"输入你要删除的边的另个顶点的名称：";

cin