第5次实验-实验报告

附件2：

北京理工大学珠海学院实验报告

ZHUHAI CAMPAUS OF BEIJING INSTITUTE OF TECHNOLOGY

班级 软工3班 学号 140202031009 姓名 郑志峰 指导教师 何春香 成绩

实验题目 图及其应用 实验时间 2015/6/21

一、实验目的、意义

（1）熟悉图的邻接矩阵的表示方法；

（2）掌握建立图的邻接矩阵算法；

（3）掌握图的基本运算，熟悉对图遍历算法；

（4）加深对图的理解，逐步培养解决实际问题的编程能力

二、实验内容及要求

说明1：学生在上机实验时，需要自己设计出所涉及到的函数，同时设计多组输入数据并编写主程序分别调用这些函数，调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果，加深对有关算法的理解。

具体要求：

（1）建立图的邻接矩阵；

（2）对其进行深度优先及广度优先遍历。

（3）最小生成树（克鲁斯卡尔算法）

扩展要求（选做）：

（1）最小生成树（普里姆算法）

（2）拓扑排序和关键路径

（3）最短路径

（4）判断有向图是否存在回路

（5）判断无向图是否是树

（6）判断无向图是否为连通图

三、实验所涉及的知识点

1.图的邻接矩阵的建立；

2.图的基本操作

3.图的深搜和广搜

1

4.链式队列的应用

5.输入流和输出流的使用

四、实验记录

(调试过程及调试中遇到的问题及解决办法，其他算法的存在与实践等。)

五、实验结果及分析

（所输入的数据及相应的运行结果，运行结果要有提示信息，运行结果采用截图方式给出。）

#include<iostream>

using namespace std;

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<iomanip>

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define MAX_NAME 10

#define MAX_VERTEX_NUM 26

typedef int Status;

typedef int Boolean;

typedef char VertexType[MAX_NAME];

typedef int QElemType;

Boolean visite[MAX_VERTEX_NUM];

typedef struct{

VertexType vexs[MAX_VERTEX_NUM]; int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vexnum; int arcnum;

}MGraph;

typedef struct QNode{

QElemType data; QNode *next;

}*QueuePtr;

typedef struct{

QueuePtr front; 2

QueuePtr rear;

}LinkQueue;

int LocateVex(MGraph G, VertexType u){

}

void CreateUDN(MGraph &G){

}

void Display(MGraph G){

}

typedef struct

{

3 int i; for (i = 0; i < G.vexnum; i++) if (strcmp(u, G.vexs[i]) == 0) return i; return OVERFLOW; int i, j, k; VertexType v1, v2; cout << "请输入无向图G的顶点数："; cin >> G.vexnum; cout << "请输入无向图G的边数："; cin >> G.arcnum; cout << "请输入" << G.vexnum << "个顶点的值,按空格键隔开：" << endl; for (i = 0; i < G.vexnum; i++) cin >> G.vexs[i]; for (i = 0; i < G.vexnum; i++) for (j = 0; j < G.arcnum; j++) G.arcs[i][j] = 0; cout << "请输入" << G.arcnum << "条边的两个顶点,按空格键隔" << endl << "开顶点,按回车for (k = 0; k < G.arcnum; k++){ } cin >> v1 >> v2; i = LocateVex(G, v1); j = LocateVex(G, v2); G.arcs[i][j] = 1; G.arcs[j][i] = 1; 输入下一条边：" << endl; cout << G.vexnum << "个顶点" << G.arcnum << "条边的无向图," << endl << "顶点依次是：" for (int i = 0; i < G.vexnum; i++) cout << G.vexs[i] << " "; cout << endl; for (int i = 0; i < G.vexnum; i++){ } for (int j = 0; j < G.vexnum; j++) cout << setw(3) << G.arcs[i][j]; cout << endl; << endl << " ";

int adjvex;

int lowcost;

}minside[MAX_VERTEX_NUM];

int minimum(minside SZ, MGraph G)

{

int i = 0, j, k, min;

while (!SZ[i].lowcost)

i++;

min = SZ[i].lowcost;

k = i;

for (j = i + 1; j<G.vexnum; j++)

if (SZ[j].lowcost>0 && SZ[j].lowcost<min)

{

min = SZ[j].lowcost;

k = j;

}

return k;

}

void MiniSpanTree_PRIM(MGraph G, VertexType u)

{

int i, j, k;

minside closedge;

k = LocateVex(G, u);

for (j = 0; j<G.vexnum; ++j)

{

closedge[j].adjvex = k;

closedge[j].lowcost = G.arcs[k][j];

}

closedge[k].lowcost = 0;

printf("最小代价生成树的各条边为\n");

for (i = 1; i<G.vexnum; ++i)

{

k = minimum(closedge, G);

printf("(%s-%s)\n", G.vexs[closedge[k].adjvex], G.vexs[k]);

closedge[k].lowcost = 0;

for (j = 0; j<G.vexnum; ++j)

if (G.arcs[k][j]<closedge[j].lowcost)

{

closedge[j].adjvex = k;

closedge[j].lowcost = G.arcs[k][j];

}

}

}

void main(){

MGraph G;

4

} CreateUDN(G); Display(G); cout << endl << "Prim方法求最小生成树：" << endl; MiniSpanTree_PRIM(G, G.vexs[0]); system("pause"); int i; i = 0; 5