数据结构图的操作

实验7：图的操作算法

、实验目的

1.熟悉各种图的存储结构。

2.掌握图的各种搜索路径的遍历方法。

二、实验内容

1.设计一个有向图和一个无向图，任选一种存储结构，完成有向图和无向图的DFS（深度优先遍

历）和BFS（广度优先遍历）的操作。

算法：

#include<iostream>

#include<math.h>

#include<stdio.h>

#include<malloc.h>

#defineMAXV10

#defineINF980708

usingnamespacestd;

typedefintInfoType;

〃邻接矩阵

typedefstruct

（

intno;

InfoTypeinfo;

JVertexType;〃顶点类型

typedefstruct

（

intedges[MAXV][MAXV];

intn,e;

VertexTypevexs[MAXV];

}MatGr叩h;〃完整的图邻接矩阵类型

〃邻接表

typedefstructANode

（

intadjvex;

structANode*nextarc;

intweight;

}ArcNode;〃边结点类型

typedefstructVnode

InfoTypeinfo;

ArcNode*firstarc;

}VNode;〃邻接表的头结点类型

typedefstruct

(

VNodeadjlist[MAXV];

intn,e;

}AdjGraph;〃完整的图邻接表类型

typedefstruct

(

InfoTypedata[MAXV];

intfrontjear;

}SqQueue;〃队列

〃初始化队列

voidlnitQueue(SqQueue*&q)

(

q=(SqQueue*)malloc(sizeof(SqQueue));

q->front=q->rear=-l;

)

〃判断队列是否为空

boolQueueEmpty(SqQueue*q)

(

return(q->front==q->rear);

)

〃进队列

boolenQueue(SqQueue*&q,InfoTypee)

(

if(q->rear==MAXV)returnfalse;

q->rear++;

q->data[q->rear]=e;

returntrue;

)

〃出队列

booldeQueue(SqQueue*&q,InfoType&e)

(

if(q->front==q->rear)returnfalse;

q->front=(q->front+l)%MAXV;

e=q->data[q->front];

returntrue;

)

〃创建邻接表

voidCreateAdj(AdjGraph*&G,intA[MAXV][MAXV],intn,inte)

(

inti,j;

ArcNode*p;

G=(AdjGraph*)malloc(sizeof(AdjGraph));

for(i=0;i<n;i++)

G->adjlist[i].firstarc=NULL;

for(i=0;i<n;i++)

for(j=n-l;j>=0;j-)

if(A[i][j]!=O&&A[i][j]!=INF)

(

p=(ArcNode*)malloc(sizeof(ArcNode));

p->adjvex=j;

p->nextarc=G->adjlist[i].firstarc;

G->adjlist[i].firstarc=p;

)

G->n=n;G->e=e;

}

〃输出邻接表

voidDispAdj(AdjGraph*G)

(

cout<<”邻接表存储:"«endl;

inti;ArcNode*p;

for(i=0;i<G->n;i++)

(

p=G->adjlist[i].firstarc;

printf("%3d:uJ);

printf(“%3d[]・>));

while(p!=NULL)

(

printf("%3d[]->",p->adjvex);

p=p->nextarc;

)

cout«"A"«endl;

)

)

//DFS深度优先遍历

intvisited[MAXV]={0};

voidDFS(AdjGraph*G,intv)

(

ArcNode*p;

visited[v]=l;

cout«v;

p=G->adjlist[v].firstarc;

while(p!=NULL)

(

if(visited[p->adjvex]==O)

DFS(G,p->adjvex);

p=p->nextarc;

)

//BFS广度优先遍历

voidBFS(AdjGraph*G,intv)

(

intwzi;ArcNode*p;

SqQueue*qu;

InitQueue(qu);

intvisitedl[MAXV];

for(inti=0;i<G->n;i++)

visitedl[i]=O;

printf("%2d"zv);

visitedl[v]=l;

enQueue(qu,v);

while(!QueueEmpty(qu))

(

deQueue(qu,w);

p=G->adjlist[w].firstarc;

while(p!=NULL)

(

if(visitedl[p->adjvex]==O)

(

printf("%2d",p->adjvex);

visitedl[p->adjvex]=l;

enQueue(qu,p->adjvex);

)

p=p->nextarc;

)

)

cout«endl;

)

〃销毁邻接表

voidDestroyAdj(AdjGraph*&G)

(

inti;ArcNode*pre,*p;

for(i=0;i<G->n;i++)

(

pre=G->adjlist[i].firstarc;

if(pre!=NULL)

(

p=pre->nextarc;

while(p!=NULL)

{

free(pre);

pre=p;p=p->nextarc;

)

free(pre);

}

)

free(G);

)

〃创建邻接矩阵

voidCreatMat(MatGraph*&G,intnjnte)

(

inti,il,j,jl,numl,num2;

G=(MatGraph*)malloc(sizeof(MatGraph));

〃邻接矩阵初始化

for(i=0;i<n;i++)

(

for(j=0;j<n;j++)

G->edges[i][j]=O;

)

〃顶点信息

cout<<”请输入顶点编号”<<endl;

for(i=0;i<n;i++)

cin»G->vexs[i].no;

〃边信息

for(i=0;i<e;i++)

(

cout<<”请输入起始端点编号和终止端点编号"vvendl;

cin»il»jl;

for(j=0;j<n;j++)

(

if(G->vexs[j].no==il)

numl=j;

if(G->vexs[j].no==jl)

num2=j;

}

G->edges[numl][num2]=l;

)

G->n=n;G->e=e;

}

〃输出邻接矩阵

voidDispMatfMatGraph*G)

(

cout<<”邻接矩阵存储："<<endl;

cout«"\t\tn;

for(inti=0;i<G->n;i++)

cout«G->vexs[i].no«"\t";

cout«endl;

for(inti=O;i<G->n;i++)

(

cout«u\t"«G->vexs[i].no«"\t";

for(intj=O;j<G->n;j++)

cout«G->edges[i][j]«"\t";

cout«endl;

}

)

intmain()

(

intn,e,v,vl;

MatGraph*G;

AdjGraph*p;

cout<<”请输入顶点个数"<<endl;

cin»n;

cout<<”请输入边的个数"<<endl;

cin»e;

CreatMat(G,n,e);

DispMat(G);

CreateAdj(p,G・>edges,n,e);

DispAdj(p);

cout<<“进行DFS深度优先遍历，请输入初始点：”;

cin»v;

DFS(p,v);

cout«endl;

cout<<“进行BFS广度优先遍历，请输入初始点：

cin»vl;

BFS(P/vl);

coutvv"销毁图"<<endl;

DestroyAdj(p);

)

测试数据:

有向图：

13

无向图:

运行结果:

产输入顶点个数

请输入边的个数

请输入顶点编号

12345

请输入起始端点编号和终止端点编号

13

请输入起始端点编号和终止端点编号

14

请输入起始端点编号和终止端点编号

12

这输入起始端点编号和终止端点编号

43

请输入起始端点编号和终止端点编号

24

诂输入起始端点编号和终止端点编号

35

请输入起始端点编号和终止端点编号

邻接矩阵存储：

12345

01110

00010

00001

00100

01000

邻接表存储：

0:0[]->1[]->2[]->3[

1:1[]->3[]->*

邻接表存储：

0:0[]->1[]->2[]->3[]->

1：1[]->3[]->'

2:2[]->4[]->'

3:3[]->2[]->；

4:4[1[]->

进行DFS深度优先遍历,请输入初始点：1

1324

进行BFS广度优先遍历，请输入初始点：1

1324

销毁图

存在问题：无

2.求两点之间最短路径。

算法设计：

〃求两点之间最短路径。

#include<iostream>

#include<math.h>

#include<stdio.h>

#include<malloc.h>

#defineINF32767

#defineMAXV100

usingnamespacestd;

typedefcharInfoType;

〃以下定义邻接矩阵类型

typedefstruct

{intno;〃顶点编号

InfoTypeinfo;〃顶点其他信息

}VertexType;〃顶点类型

typedefstruct

{intedges[MAXV][MAXV];〃邻接矩阵数组

intn,e;〃顶点数，边数

VertexTypevexs[MAXV];〃存放顶点信息

}MatGraph;〃完整的图邻接矩阵类型

voidCreateMat(MatGraph&g,intA[MAXV][MAXV],intn,inte)〃创建图的邻接矩阵

(

inti,j;

g.n=n;gee;

for(i=0;i<g.n;i++)

for(j=O;j<g,n;j++)

g.edges[i][j]=A[i][j]；

)

voidDispMat(MatGraphg)〃输出邻接矩阵g

(

inti,j;

for(i=0;i<g.n;i++)

for(j=O;j<g.n;j++)

if(g.edges[i][j]!=INF)

printf("%4d",g.edges[i][j]);

else

printf("%4s"z"oo")；

cout«endl;

)

)

voidDispath(MatGraphgjntdist[],intpath[],intS[],intv)

〃输出从顶点v出发的所有最短路径

{intijk;

intapath[MAXV],d;〃存放一条最短路径(逆向)及其顶点个数

for(i=0;i<g.n;i++)〃循环输出从顶点v至i的路径

if(S[i]==l&&i!=v)

{coutvv”从顶点到顶点,,的路径长度为LvvdistUKc”路径为:";

d=0;apath[d]=i;〃添加路径上的终点

k=path[i];

if(k==-l)〃没有路径的情况

cout<<“无路径”<<endl;

else〃存在路径时输出该路径

{while(k!=v)

{d++;apath[d]=k;

k=path[k];

)

d++;apath[d]=v;〃添加路径上的起点

cout«apath[d];〃先输出起点

for(j=d-l;j>=O;j-)〃再输出其他顶点

cout«"/,«apath[j];

cout«endl;

)

)

)

voidDijkstra(MatGraphgjntv)//Dijkstra算法

{intdist[MAXV],path[MAXV];

intS[MAXV];//S[i]=l表示顶点i在S中,S[i]=O表示顶点i在U中

intMindis,i,j,u;

for(i=0;i<g.n;i++)

{dist[i]=g.edges[v][i];〃距离初始化

S[i]=0;〃S口置空

if(g.edges[v][i]<INF)〃路径初始化

path[i]=v;〃顶点v到顶点i有边时，置顶点i的前一•个顶点为v

else

path[i]=-l;〃顶点v到顶点i没边时，置顶点i的前一个顶点为；

}

S[v]=l;path[v]=O;〃源点编号v放入S中

for(i=O;i<g.n-l;i++)〃循环直到所有顶点的最短路径都求出

{Mindis=INF;〃Mindis置最大长度初值

for(j=O;j<g,n;j++)〃选取不在S中(即U中)且具有最小最短路径长度的顶点u

if(S[j]==O&&dist[j]<Mindis)

{u=j;

Mindis=dist[j];

)

S[u]=l;〃顶点u加入S中

for(j=O；j<g.n;j++)〃修改不在S中(即U中)的顶点的最短路径

if(S[j]==O)

if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j])

{dist[j]=dist[u]+g.edges[u][j];

path[j]=u;

)

)

Dispath(g,dist,path,S,v);〃输出最短路径

)

intmain()

(

MatGraphg;

intA[MAXV][MAXV]={

{0,4,INF,INF},

{INF,0,1,INF),

{4,INF,0,2),

{3,INF,INF,0});

intn=4,e=8;

CreateMat(g,A,n,e);〃建立《教程》中图8.35的邻接矩阵

cout«"SG的邻接矩阵:"<<endl;

DispMat(g);〃输出邻接矩阵

intv;

cout<<"输入一顶点："<<endl;

cin»v;

cout<<"从"vcvvc"顶点出发的最短路径如下:"<<en此；

Dijkstra(g,v);

测试数据:

图:

运行结果:

图G的邻接矩阵：

04ooCO

OO01CO

4OO02

3880

输入一顶点1

管

出

■的4m

QQ

u

旭

到

点DT

度

30g3泾30

《

旭

到

点

泾

点

31s度7301

o

泾

并

点

到

点

度

3顶2M830i2

存在问题：无

3、实现一个有向图的拓扑排序。

算法设计：

#include<iostream>

#include<math.h>

#include<stdio.h>

#include<malloc.h>

#defineMAXV10

#defineINF980708

usingnamespacestd;

typedefintInfoType;

〃邻接矩阵

typedefstruct

(

intno;

InfoTypeinfo;

JVertexType;〃顶点类型

typedefstruct

(

intedges[MAXV][MAXV];

intn,e;

VertexTypevexs[MAXV];

}MatGraph;〃完整的图邻接矩阵类型

〃邻接表

typedefstructANode

(

intadjvex;

structANode*nextarc;

intweight;

}ArcNode;〃边结点类型

typedefstructVnode

(

InfoTypeinfo;

intcount;

ArcNode*firstarc;

}VNode;〃邻接表的头结点类型

typedefstruct

(

VNodeadjlist[MAXV];

intn,e;

}AdjGraph;〃完整的图邻接表类型

〃创建邻接表

voidCreateAdj(AdjGraph*&GJntA[MAXV][MAXV]Jntnjnte)

(

intij;

ArcNode*p;

G=(AdjGraph*)malloc(sizeof(AdjGraph));

for(i=0;i<n;i++)

G->adjlist[i].firstarc=NULL;

for(i=0;i<n;i++)

for(j=n-l;j>=0;j-)

if(A[i][j]!=O&&A[i][j]!=INF)

(

p=(ArcNode*)malloc(sizeof(ArcNode));

p->adjvex=j;

p->nextarc=G->adjlist[i].firstarc;

G->adjlist[i].firstarc=p;

)

G->n=n;G->e=e;

}

〃输出邻接表

voidDispAdj(AdjGraph*G)

(

cout<<”邻接表存储：“<<endl;

inti;ArcNode*p;

for(i=0;i<G->n;i++)

(

p=G->adjlist[i].firstarc;

printf("%3d:"J);

printf("%3d[]->",i);

while(p!=NULL)

(

printf("%3d[]->"zp->adjvex);

p=p->nextarc;

)

cout«"A"«endl;

)

}

〃销毁邻接表

voidDestroyAdj(AdjGraph*&G)

(

inti;ArcNode*pre,*p;

for(i=0;i<G->n;i++)

(

pre=G->adjlist[i].firstarc;

if(pre!=NULL)

(

p=pre->nextarc;

while(p!=NULL)

(

free(pre);

pre=p;p=p->nextarc;

)

free(pre);

)

)

free(G);

)

〃创建邻接矩阵

voidCreatMat(MatGraph*&G,intn,inte)

(

inti,il,j,jl,numl,num2;

G=(MatGraph*)malloc(sizeof(MatGraph));

〃邻接矩阵初始化

for(i=0;i<n;i++)

(

for(j=0;j<n;j++)

G->edges[i][j]=O;

)

〃顶点信息

cout<<”请输入顶点编号”<<endl;

for(i=0;i<n;i++)

cin»G->vexs[i].no;

〃边信息

for(i=0;i<e;i++)

(

coutcc"请输入起始端点编号和终止端点编号"<<endl;

cin»il»jl;

for(j=0;j<n;j++)

(

if(G->vexs[j].no==il)

numl=j;

if(G->vexs[j].no==jl)

num2=j;

)

G->edges[numl][num2]=l;

)

G->n=n;G->e=e;

)

〃拓扑排序算法

voidTopSort(AdjGraph*G)〃拓扑排序算法

{intij;

intSt[MAXV],top=-l;〃栈St的指针为top

ArcNode*p;

for(i=0;i<G->n;i++)〃入度置初值0

G->adjlist[i].count=0;

for(i=0;i<G->n;i++)〃求所有顶点的入度

{p=G->adjlist[i].firstarc;

while(p!=NULL)

{G->adjlist[p->adjvex].count++;

p=p->nextarc;

)

)

for(i=0;i<G->n;i++)〃将入度为0的顶点进栈

if(G->adjlist[i].count==0)

{top++;

St[top]=i;

)

while(top>-l)〃栈不空循环

{i=St[top];top-;〃出栈一个顶点i

printf("%d"J);〃输出该顶点

p=G->adjlist[i].firstarc;〃找第一个邻接点

while(p!=NULL)