图实验报告

数据结构实验报告

实验四：图

专 业： 班 级： 姓 名： 学 号： 指导教师： 日 期：

一：实验目的：

（1）掌握图的存储思想及其存储实现。

（2）掌握图的深度、广度优先遍历算法思想及其程序实现。

（3）掌握图的常见应用算法的思想及其程序实现。 （4）理解有向无环图、最短路径等算法 二：实验内容：

以下实验内容，1和2为必做内容，3为选做内容。 1.有向图

（1）键盘输入数据，建立一个有向图的邻接表，并输出该邻接表。 （2）在有向图的邻接表的基础上计算各顶点的度，并输出。

（3）以有向图的邻接表为基础实现并输出它的拓扑排序序列。 （4）在主函数中设计一个简单的菜单，分别调试上述算法。 2.无向图

（1）建立一个无向图的邻接表，并输出该邻接表。 （2）采用邻接表存储实现无向图的深度优先遍历。。 （3）采用邻接表存储实现无向图的广度优先遍历。 （4）在主函数中设计一个简单的菜单，分别调试上述算法。 3.综合训练

最小生成树问题： 【问题描述】

若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。

【基本要求】

(1)利用PRIM算法求网的最小生成树。

(2)以文本形式输出生成树中各条边以及他们的权值. 【测试数据】 见下图：

【实现提示】

通信线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数。

【选作内容】

利用克鲁斯卡尔算法求网的最小生成树。

三、实验说明： 1.类型定义（邻接表存储） #define MAX_VERTEX_NUM 8 //顶点最大个数 typedef struct ArcNode {int adjvex;

struct ArcNode *nextarc; int weight; //边的权

}ArcNode; //表结点 #define VertexType int //顶点元素类型

typedef struct VNode

{int degree,indegree;//顶点的度，入度 VertexType data;

ArcNode *firstarc;

}VNode/*头结点*/,AdjList[MAX_VERTEX_NUM]; typedef struct{ AdjList vertices;

int vexnum,arcnum;//顶点的实际数，边的实际数 }ALGraph; 四、注意问题：

1.注意理解各算法实现时所采用的存储结构。 2.注意区别正、逆邻接。

五、概要设计

实验操作步骤（代码）

1. 有向图

#include #include #include

using namespace std;

#define Max 100 int n,m;

typedef struct Arc*link; struct Arc

{ char info[15]; int adjvex;

link nextarc;

点

//邻接点结构定义

//存储结点信息

//邻接点编号

//定义指针，指向下一个邻接

};

struct Vex { char info[15]; int indgree;

link firstarc;

}v[Max];

int find(char*str)

的顶点，并将其编号返回{ for(int i=1;i<=n;i++)

if(!strcmp(str,v[i].info))

return i;

}

void creat() {

//顶点结构定义

//顶点信息

//顶点入度

//定义指针，指向下一个邻接点

//在顶点集中查询信息为“str”

//返回编号

//创建邻接表

cout<<\"请 输 入 顶 点 总 数 :\"<>n;

//n记录顶点数

cout<<\"请 输 入 各 个 顶 点 的 元 素 信 息 :

\"<v[i].firstarc=NULL;

//初始化：每个顶点的指针（指

v[i].indgree=0;

//初始化：每个顶点的入度为0

for(int i=1;i<=n;i++) {

cin>>v[i].info;

//循环输入顶点信息

向下个顶点）为空

cout<<\"请 输 入 有 向 边 数 目 ：\"<>m;

//m记录边数

}

cout<<\"输 入 有 向 边 : 例（若a指向b，则输入a b）

\"<int tem[10][10];

for( i=1;i<=m;i++) {

char ss[15],tt[12]; cin>>ss>>tt;

//定义字符串ss，tt

int s=find(ss),t=find(tt); //记s为ss的编号，t为tt

的编号

v[t].indgree++;

//因为是前者指向后者

tem[i][i]=s; tem[i][i+1]=t;

（s指向t），所以后者的入度需要+1

link p=(link)malloc(sizeof(Arc)); //指针变量p申请空

间，空间大小为邻接点Arc的个数

strcpy(p->info,v[t].info); //将顶点信息复制入指针p指

向的info内容中

p->adjvex=t;

//t（被指的信息）赋给p指向的

邻接点编号

p->nextarc=v[s].firstarc;

}

v[s].firstarc=p;

cout<<\"该 邻 接 表 为 ：\"<for( i=1;i<=m;i++) { }

//根据刚才输入，输出邻接表

cout<for( i=1;i<=m;i++) {

//循环输出每个顶点的入度

cout<<\"第 \"<\"<cout<void update(int node)

//每输出一个顶点时要相应的

调用该函数，更新顶点入度信息 {

link p=v[node].firstarc;

//指针p为顶点元素信

息的指向下一个邻接点的指针

p=p->nextarc;

//p指向下一个邻接点的

v[p->adjvex].indgree--;

//则入度-1

while(p) {

if(v[p->adjvex].indgree>0)

//若此顶点入度>0

//当p非空

指针还原给先前的指针 } int main()

//主函数

}

{

if(lencout<<\"Input error!\"<creat();

for(int k=1;k<=n;k++)

for(int i=1;i<=n;i++) if(!v[i].indgree) {

rel[len++]=i; v[i].indgree=-1; update(i); }

cout<<\"该 拓 扑 排 序 为 : \"<else {

for(int i=0;icout<cout<}

cout<<\"\\n\"<} return 0;

}

2. 无向图 #include #include

int visited1[10]; int visited2[10];

typedef struct

元素，边元素，顶点个数，边数）{ int vexs[10]; int edges[10][10];

int n,e;

}MGraph;

//无向图结构定义（顶点

void CreateMGraph(MGraph *G) {

scanf(\"%d,%d\

//输入顶

printf(\"\\nPlease input vexs and edges!（用逗号隔开）\\n\");

int r[10][10]; int i,j,k,m,n;

点数和边数

for(i=0;in;i++)

//输入顶点

printf(\"\\nPlease input the vexs information! \\n\");

元素 { }

getchar();

scanf(\"%d\visited1[i]=0; visited2[i]=0;

for(i=0;in;i++)

//初始边集

合，均赋值为0

for(k=0;ke;k++)

//输入边集

printf(\"Please input 2 vexs of each edge ! eg. (i,j) \\n\"); { }

for(j=0;jn;j++) { }

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

合元素 {

getchar();

printf(\"Please input 第%d edge ! \\n\scanf(\"%d,%d\r[k][k]=m;

//用r[][]临时

存储输入的邻接表

r[k][k+1]=n;

G->edges[m-1][n-1]=1;

//已赋值过

的边，定义为1 }

printf(\"该邻接表为:\\n\"); for(k=0;ke;k++)

出 { printf(\"%d,%d\\n\ }

}

void DFSM(MGraph G,int i)

{

//邻接表输

//深度搜索定义

int j;

if(visited1[i]==0)

//若visited1为0，即

未搜索过的边元素 {

printf(\"V%d \visited1[i]=1;

//则输出顶点元素 //将搜索过的visiter1

定义为1 }

for(j=0;jif(G.edges[i][j]==1&&visited1[j]==0) //若边未搜索过且

顶点未搜索过

DFSM(G,j);

//则继续深度搜索，

实行递归 }

void BFSM(MGraph G,int k) {

int i,j,front,rear,q[10]; front=-1,rear=-1; if(visited2[k]==0)

//若visited2未0，即

//广度搜索定义

}

未搜索过的边元素 { }

rear=rear+1; q[rear]=k; while (rear!=front) { }

front=front+1; i=q[front]; for(j=0;jif(G.edges[i][j]==1&&visited2[j]==0) { }

printf(\"V%d \.vexs[j]); visited2[j]=1; rear=rear+1; q[rear]=j;

printf(\"V%d \ visited2[k]=1;

//输出顶点元素 //记visited2为1

}

void main() {

MGraph p;

CreateMGraph(&p);

//邻接表输入无向

printf(\"邻接矩阵建立无向图!\\n\"); printf(\"网络\\n\\n\"); int j;

//主函数

图及输出

printf(\"\\n\");

printf(\"从第i个进行 BFSM，Please input i : \\n\"); printf(\"从第i个进行 DFSM，Please input i : \\n\"); scanf(\"%d\--j;

printf(\"DFSM: \\n\"); DFSM(p,j);

//调用深度搜索函数

}

scanf(\"%d\--j;

printf(\"BFSM : \\n\"); BFSM(p,j); printf(\"\\n\");

//调用广度搜索函数