数据结构实验七 图及图的操作实验(2)

E->nextarc=adjlist[j-1].firstarc;

adjlist[j-1].firstarc=E;

}

}

创建有向网邻接表算法：

template<class T>

void Mgraph<T>::creatGraphH(T a[],int n,int e){

Edge *E;

vertexNum=n;

arcNum=e;

for (int i=0;i<vertexNum;i++)

{

adjlist[i].vex=a[i];

adjlist[i].firstarc=NULL;

}

int j,w;

for (int k=0;k<arcNum;k++)

{

cout<<"请输入第"<<k+1<<"条弧的信息（格式为：起点

";

cin>>i>>j>>w;

E=new Edge;

E->value=w;

E->adjvertex=j-1;

E->nextarc=adjlist[i-1].firstarc;

adjlist[i-1].firstarc=E;

}

}

（3）输出邻接表结果算法

template<class T>

void Mgraph<T>::printGraph(){

for (int i=0;i<vertexNum;i++)

{

Edge *p;

cout<<i<<" ";

p=adjlist[i].firstarc;

while(p)

{

cout<<p->adjvertex<<" ";

p=p->nextarc;

}

cout<<endl;

} 终点 权值）

数据结构实验七 图及图的操作实验

}

测试结果粘贴如下：

void main()

{

int a[5]={1,2,3,4,5};

Mgraph<int> graph1(a,5,5);

graph1.printGraph();

int visited[5]={0};

graph1.DFS(2,visited);

}

3、图的遍历递归算法

（1）（存储结构为邻接表）深度优先遍历算法

递归算法：

template<class T>

void Mgraph<T>::DFS(int v,int visited[]){

if(v>vertexNum){ cout<<"顶点数处错误"<<endl; exit(0);}

Edge *p;

int j;

cout<<adjlist[v].vex<<" ";

visited[v]=1;

p=adjlist[v].firstarc;

while (p!=NULL) //依次搜索顶点v的邻接点j {

j=p->adjvertex;

if (visited[j]==0) DFS(j,visited);

p=p->nextarc;

数据结构实验七 图及图的操作实验

}

}

测试结果粘贴如下：

有向网的测试结果：

无向网的测试结果：

数据结构实验七 图及图的操作实验

（2）广度优先遍历算法

非递归算法

template <class T>

void Graph<T>::BFS(int v,int visited[]){

if (v>vertexNum){ cout<<"元素不存在！"<<endl; exit(0);} /*构造队列*/

int front=-1;

int rear=-1;

int Queue[MaxSize];

//////////////////

cout<<vertex[v]<<" ";

visited[v]=1;

Queue[++rear]=v;

while (front!=rear)

{

v=Queue[++front]; //将队头元素出队并送到v中

for (int j=0; j<vertexNum; j++)

if (arc[v][j]==1 && visited[j]==0 ){

cout<<vertex[j]<<" ";

visited[j]=1;

Queue[++rear]=j;//进队

}

}

}

测试结果粘贴如下：

void main(){

int a[5]={1,2,3,4,5};

Mgraph<int> graph1(a,5,5);

graph1.printGraph();

int visited[5]={0};

graph1.BFS(2,visited);

}

有向网的测试结果：

数据结构实验七 图及图的操作实验

无向网的测试结果：

三、 实验心得（含上机中所遇问题的解决办法，所使用到的编程技巧、创新

点及编程的心得）