数据结构与算法实验报告-图

沈 阳 工 程 学 院

学 生 实 验 报 告

（课程名称： 数据结构与算法 ）

实验题目： 图

班 级 网络本112班 学 号 2011414217姓 名 樊 鹏 鹏 地 点 F 6 0 6 指导教师 吕 海 华、祝 世 东 实 验 日 期 : 2012 年 11 月 18 日

一、实验目的 1．掌握图的基本存储方法。 2．掌握有关图的操作算法并用高级语言实现。 3．熟练掌握图的两种搜索路径的遍历方法。 4．掌握图的有关应用。 二、实验环境 Turbo C或是Visual C++ 三、实验内容与要求 实验1 建立无向图的邻接矩阵或邻接表存储并输出 本题给出了一个无向图的邻接矩阵存储表示，在此基础上稍加改动就可以实现有向图、无向图和有向网的邻接矩阵表示。 实验2 建立图的邻接矩阵或邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历 图的广度优先遍历用非递归方法很容易理解，非递归方法需要辅助队列Q以及出队、入队函数。 四、实验过程及结果分析 1、无向图的邻接矩阵的创建和遍历 #include #include #define MAX_NUM 20 #define OK 1 #define ERROR -1 #define MaxVertexNum 20 //最大顶点数，应由用户定义 #define OK 1 #define ERROR -1 typedef char VertexType; //顶点类型应由用户定义 typedef int EdgeType; //边上的权值类型应由用户定义 //定义图的种类类型，yxt有向图，yxw有向网，wxt无向图，wxw无向网 typedef enum{yxt,yxw,wxt,wxw} GraphKind; 1

typedef struct { VertexType vexs[MaxVertexNum]; //顶点表 //邻接矩阵，可看作边表,如果是无权图，1：相邻，0：不相邻 EdgeType edges[MaxVertexNum][MaxVertexNum]; int n; int e; //图中当前的顶点数和边数 GraphKind gkind; //图的种类标示 }MGraph; int i=0,j=0,k=0; char v1,v2;//弧的两个结点 //函数声明 int creatWxw(MGraph *G); int creatYxt(MGraph *G); int creatYxw(MGraph *G); int creatWxt(MGraph *G); //输出函数 int printGraph(MGraph *G) { printf(\"*********************\\n\"); int i,j; for(i=0;in;i++) { for(j=0;jn;j++) printf(\"%4d\ printf(\"\\n\"); } printf(\"*********************\\n\"); return OK; } //========================创建无向网========================= int creatWxw(MGraph *G) { int w;//权值 printf(\"输入图的结点数：\\n\"); scanf(\"%d\2

printf(\"输入图的边数：\\n\"); scanf(\"%d\ getchar();//接收scanf的回车符 //输入结点 printf(\"输入结点，用大写字母标示(要求第一个顶点是A)，如：A：\\n\"); for(i=0;in;i++) { scanf(\"%c\ } getchar();//接收scanf的回车符 //初始化邻接矩阵 for(i=0;in;i++) for(j=0;jn;j++) G->edges[i][j]=0; //输入边连接的两个结点 printf(\"输入弧和权值：\\n\"); for(k=0;ke;k++) { //i,j作为矩阵的行和列 scanf(\"%c%c%d\getchar(); i=v1-'A'; j=v2-'A'; G->edges[i][j]=w; G->edges[j][i]=w; } return OK; } //========================创建无向图========================= int creatWxt(MGraph *G) { printf(\"输入图的结点数：\\n\"); scanf(\"%d\ printf(\"输入图的边数：\\n\"); scanf(\"%d\ getchar();//接收scanf的回车符 //输入结点 3

printf(\"输入结点，用大写字母标示(要求第一个顶点是A)，如：A：\\n\"); for(i=0;in;i++) { scanf(\"%c\ } getchar();//接收scanf的回车符 //初始化邻接矩阵 for(i=0;in;i++) for(j=0;jn;j++) G->edges[i][j]=0; //输入边连接的两个结点 printf(\"输入弧：\\n\"); for(k=0;ke;k++) { //i,j作为矩阵的行和列 scanf(\"%c%c\getchar(); i=v1-'A'; j=v2-'A'; G->edges[i][j]=1; G->edges[j][i]=1; } // printGraph(G); return OK; } //========================创建有向图========================= int creatYxt(MGraph *G) { printf(\"输入图的结点数：\\n\"); scanf(\"%d\ printf(\"输入图的边数：\\n\"); scanf(\"%d\ getchar();//接收scanf的回车符 //输入结点 printf(\"输入结点，用大写字母标示(要求第一个顶点是A)，如：A：\\n\"); for(i=0;in;i++) { 4

scanf(\"%c\ } getchar();//接收scanf的回车符 //初始化邻接矩阵 for(i=0;in;i++) for(j=0;jn;j++) G->edges[i][j]=0; //输入边连接的两个结点 printf(\"输入弧：\\n\"); for(k=0;ke;k++) { //i,j作为矩阵的行和列 scanf(\"%c%c\getchar(); i=v1-'A'; j=v2-'A'; G->edges[i][j]=1; } return OK; } //========================创建有向网========================= int creatYxw(MGraph *G) { int w;//权值 printf(\"输入图的结点数：\\n\"); scanf(\"%d\ printf(\"输入图的边数：\\n\"); scanf(\"%d\ getchar();//接收scanf的回车符 //输入结点 printf(\"输入结点，用大写字母标示(要求第一个顶点是A)，如：A：\\n\"); for(i=0;in;i++) { scanf(\"%c\ } getchar();//接收scanf的回车符 //初始化邻接矩阵 for(i=0;in;i++) 5

for(j=0;jn;j++) G->edges[i][j]=0; //输入边连接的两个结点 printf(\"输入弧和权值：\\n\"); for(k=0;ke;k++) { //i,j作为矩阵的行和列 scanf(\"%c%c%d\getchar(); i=v1-'A'; j=v2-'A'; G->edges[i][j]=w; } return OK; } int main() { MGraph G; int a; printf(\"====================\\n\"); printf(\" 选择0:有向图\\n\"); printf(\" 选择1:有向网\\n\"); printf(\" 选择2:无向图\\n\"); printf(\" 选择3:无向网\\n\"); printf(\"====================\\n\"); printf(\"选择图的种类:\"); printf(\"\\n\"); scanf(\"%d\ while(a!=5) { switch(a) { case 0: creatYxt(&G);printGraph(&G);break; case 1: creatYxw(&G);printGraph(&G);break; case 2: creatWxt(&G);printGraph(&G);break; case 3: creatWxw(&G);printGraph(&G);break; default:return ERROR; } 6

printf(\"\\n继续操作请输入，否则请按5退出：\\n\"); scanf(\"%d\ } } 无向图运行结果如下图： 2、图的深度优先遍历 #include #include #define MAX_NUM 20 #define OK 1 #define ERROR -1 typedef int ElemType; typedef char VertexType; typedef struct ArcNode { //定义弧结点 ElemType data; ArcNode *nextarc; }ArcNode,*ArcLink; 7

typedef struct VNode { //定义顶点结点 VertexType data; ArcLink firstarc; }VNode,AdjList[MAX_NUM]; //定义图typedef struct typedef struct{ AdjList vdata; int vexnum,arcnum; }ALGraph; //为深度优先遍历进行类型设置 typedef enum{FALSE,TRUE}Boolean;//FALSE为0，TRUE为1 Boolean visited[MAX_NUM]; //访问标志向量是全局量 //========================深度优先遍历======================= void DFS(ALGraph *G,int i) { //以vi为出发点对邻接表表示的图G进行深度优先搜索 ArcNode *p=NULL; printf(\"visit 顶点：%c\\n\访问顶点vi visited[i]=TRUE; //标记vi已访问 p=G->vdata[i].firstarc; //取vi边表的头指针,找和点vi连接的弧结点 while(p!=NULL) {//依次搜索vi的邻接点vj，这里j=p->nextarc->data if (!visited[p->data])//若vi尚未被访问 DFS(G,p->data);//则以Vj为出发点向纵深搜索 p=p->nextarc; //找vi的下一邻接点 } }//DFS void DFSTraverse(ALGraph *G) { //深度优先遍历以邻接表表示的图G，而以邻接矩阵表示G时，算法完全与此相同 int i; for(i=0;ivexnum;i++) visited[i]=FALSE; //标志向量初始化 for(i=0;ivexnum;i++) if(!visited[i]) //vi未访问过 8

DFS(G,i); //以vi为源点开始DFS搜索 }//DFSTraverse //========================构建图的邻接表====================== int Creategraph(ALGraph &G,int n){ ArcLink p; int e,i; char v,w; for(i=0;idata=(int)(w-'A'); printf(\"%d\\n\ p->nextarc=G.vdata[(int)(v-'A')].firstarc; G.vdata[(int)(v-'A')].firstarc=p; p=(ArcLink)malloc(sizeof(ArcNode)); p->data=(int)(v-'A'); p->nextarc=G.vdata[(int)(w-'A')].firstarc; G.vdata[(int)(w-'A')].firstarc=p; } G.vexnum=n; G.arcnum=e; return OK; } //=========================输出邻接表======================== int printGraph(ALGraph G){ printf(\"===============================\\n\"); ArcLink p; 9

int i; for(i=0;inextarc){ printf(\"-->\"); printf(\"%d\} printf(\"\\n\"); } printf(\"===============================\\n\"); return OK; } //主函数 int main() { ALGraph G; int n; printf(\"请输入你要构建的无向图的顶点个数:\\n\"); scanf(\"%d\Creategraph(G,n); printf(\"深度优先遍历：\\n\"); DFSTraverse(&G); printf(\"\\n你所构建的无向图的邻接表如下所示:\\n\"); printGraph(G); return OK; } 深度优先遍历的运行结果： 10

图1 图2 图的广度遍历： #include #include 11

#include #define MAX_NUM 20 #define OK 1 #define ERROR -1 #define QUEUEMAX 20 typedef int ElemType; typedef char VertexType; typedef struct ArcNode//定义弧结点 { ElemType data1; ArcNode *nextarc; }ArcNode,*ArcLink; typedef struct VNode//定义顶点结点 { VertexType data; ArcLink firstarc; }VNode,Adjlist[MAX_NUM]; typedef struct { Adjlist vdata; int vexnum,arcnum; }ALGraph; ALGraph G; typedef enum{FALSE,TRUE}Boolean;//FALSE为0，TRUE为1 Boolean visited[MAX_NUM]; //访问标志向量是全局量 typedef struct{ int data[QUEUEMAX]; int front;//头指针 int rear;//尾指针 }CirQueue; //置队列空 void InitQueue(CirQueue *Q) { 12

Q->front=Q->rear=0; } //判队空 int QueueEmpty(CirQueue *Q) { return(Q->front==Q->rear); } //判队满 int IsFull(CirQueue *Q) { return Q->rear==QUEUEMAX-1+Q->front; } //入队 void EnQueue(CirQueue *Q,int k) { if (IsFull(Q)) { printf(\"队列已满\"); //上溢,退出运行 exit(1); } Q->data[Q->rear]=k; //新元素插入队尾 Q->rear=(Q->rear+1)%QUEUEMAX; //循环意义下将尾指针加1 } //出队 int DeQueue(CirQueue *Q) { int temp; if(QueueEmpty(Q)) { printf(\"队列为空\");//下溢,退出运行 exit(1); } temp=Q->data[Q->front]; Q->front=(Q->front+1)%QUEUEMAX; //循环意义下的头指针加1 return temp; } //=======================构建图的邻接表====================== int Creategraph(ALGraph &G,int n) { 13

ArcLink p; int e,i; char v,w; for(i=0;idata1=(int)(w-'A'); printf(\"%d\\n\p->nextarc=G.vdata[(int)(v-'A')].firstarc; G.vdata[(int)(v-'A')].firstarc=p; p=(ArcLink)malloc(sizeof(ArcNode)); p->data1=(int)(v-'A'); p->nextarc=G.vdata[(int)(w-'A')].firstarc; G.vdata[(int)(w-'A')].firstarc=p; } G.vexnum=n; G.arcnum=e; return OK; } //=======================输出邻接表========================== int printGraph(ALGraph G) { ArcLink p; int i; for(i=0;inextarc) { printf(\"-->\"); printf(\"%d\14

} printf(\"\\n\"); } return OK; } //========以vk为源点对用邻接表表示的图G进行广度优先搜索======== void BFS(ALGraph *G,int k) { int i; CirQueue Q; ArcLink p; InitQueue(&Q); //队列初始化 //访问源点vk printf(\"顶点：%c \ visited[k]=TRUE; EnQueue(&Q,k); //vk已访问，将其人队。（实际上是将其序号人队） while(!QueueEmpty(&Q)) / /队非空则执行 { i=DeQueue(&Q); //相当于vi出队 p=G->vdata[i].firstarc; //取vi的边表头指针 while(p)//依次搜索vi的邻接点vj(令p->adjvex=j) { if(!visited[p->data1]) { //若vj未访问过 printf(\"顶点：%c \访问vj visited[p->data1]=TRUE; EnQueue(&Q,p->data1);//访问过的vj人队 } p=p->nextarc;//找vi的下一邻接点 } } } void BFSTraverse(ALGraph *G) { int i; for(i=0;ivexnum;i++) visited[i]=FALSE; //标志向量初始化 for(i=0;ivexnum;i++) 15

if(!visited[i]) //vi未访问过 BFS(G,i); //以vi为源点开始BFS搜索 } //=========================主函数=========================== int main() { ALGraph G; int n; printf(\"请输入你要构建的无向图的顶点个数:\"); scanf(\"%d\Creategraph(G,n); printf(\"广度优先遍历的序列为:\\n\"); BFSTraverse(&G); printf(\"\\n你所构建的无向图的邻接表如下所示:\\n\"); printf(\"***************************\\n\"); printGraph(G); printf(\"***************************\\n\"); return OK; } 图的广度遍历结果如下: 16

17

五、成绩评定 出 勤 内 容 格 式 创 新 效 果 总 评 优 良 中 及格 不及格 指导教师： 年 月 日

18