一、实验目的和要求（1）掌握图的相关概念，包括图，有向图，无向图，完全图，子图，连通图，度，入度，出度，简单回路和环等定义。

（2）重点掌握图的各种存储结构，包括邻接矩阵和邻接表等。

（3）重点掌握图的基本运算，包括创建图，输出图，深度优先遍历，广度优先遍历等。

（4）掌握图的其他运算 ，包括最小生成树，最短路径，拓扑排序和关键路径等算法。

（5）灵活运用图这种数据结构解决一些综合应用问题。

二、实验内容和方法(1)实验内容：1、编写一个程序algo8-1.cpp ，实现不带权图和带权图的邻接矩阵与邻接表的相互转换算法、输出邻接矩阵与邻接表的算法，并在此基础上设计一个程序exp8-1.cpp 实现如下功能：①建立如图1所示的有向图G 的邻接矩阵，并输出； ②由有向图G 的邻接矩阵产生邻接表，并输出； ③再由②的邻接表产生对应的邻接矩阵，并输出。

图12、编写一个程序algo8-2.cpp ，实现图的遍历运算，并在此基础上设计一个程序exp8-2.cpp 完成如下功能：①输出图1所示的有向图G 从顶点0开始的深度优先遍历序列（递归算法）； ②输出图1所示的有向图G 从顶点0开始的深度优先遍历序列（非递归算法）； ③输出图1所示的有向图G 从顶点0开始的广度优先遍历序列。

3、设计一个程序exp8-3.cpp,采用邻接表存储图，并输出图8.1（a ）中从指定顶点1出发的所有深度优先遍历序列。

156 97584530 1 52 43(2)实验方法：1、综合运用课本所学的知识，用不同的算法实现在不同的程序功能。

2、结合指导老师的指导，解决程序中的问题，正确解决实际中存在的异常情况，逐步改善功能。

3、根据实验内容，编译程序。

三、实验环境：Windows 7，Visual C++6.0三、实验过程描述文件graph.h中定义了图的邻接矩阵表示类型和邻接表表示类型，该头文件在以下三个实验中都会使用到。

其代码如下：#ifndef GRAPH_H_INCLUDED#define GRAPH_H_INCLUDEDtypedef int InfoType;#define MAXV 100 //最大顶点个数#define INF 32767 //INF表示无限大//以下定义邻接矩阵类型typedef struct{int no;InfoType info;}VertexType;typedef struct{int edges[MAXV][MAXV];int n,e;VertexType vexs[MAXV];}MGraph;//以下定义邻接表类型typedef struct ANode{int adjvex;struct ANode* nextarc;InfoType info;}ArcNode;typedef int Vertex;typedef struct VNode{Vertex data;实验①源程序。

一、输入如下所示程序；//文件名：exp8-1.cpp#include <stdio.h>#include <malloc.h>#include "graph.h"extern void MatToList1(MGraph, ALGraph* &);extern void ListToMat1(ALGraph*, MGraph&);extern void DispMat1(MGraph);extern void DispAdj1(ALGraph*);int main(){int i,j;MGraph g,g1;ALGraph *G;int A[MAXV][6] = {{0,5,INF,7,INF,INF},{INF,0,4,INF,INF,INF},{8,INF,0,INF,INF,9},{INF,INF,5,0,INF,6},{INF,INF,INF,5,0,INF},{3,INF,INF,INF,1,0}};g.n = 6;g.e = 10;for(i=0; i<g.n; i++)for(j=0; j<g.n; j++)g.edges[i][j] = A[i][j];printf("有向图G的邻接矩阵：\n");//文件名：algo8-1.cpp#include <stdio.h>#include <malloc.h>#include "graph.h"//不带权图的算法void MatToList(MGraph g, ALGraph *&G){int i,j;ArcNode *p;G = (ALGraph*)malloc(sizeof(ALGraph));for(i=0; i<g.n; i++)for(j = g.n-1; j>=0; j--)if(g.edges[i][j]!=0){p = (ArcNode*)malloc(sizeof(ArcNode));p->adjvex = j;p->nextarc = G->adjlist[i].firstarc;G->adjlist[i].firstarc = p;}G->n = g.n;G->e = g.e;}void ListToMat(ALGraph *G,MGraph &g){int i,j;ArcNode *p;for(i=0; i<G->n; i++)void DispAdj1(ALGraph *G){int i;ArcNode *p;for(i=0; i<G->n; i++){p = G->adjlist[i].firstarc;printf("%3d:",i);while(p!=NULL){printf("%3d(%d)",p->adjvex,p->info);p = p->nextarc;}printf("\n");}二、编译并链接程序；三、运行程序，结果如下图：实验○2源程序一、输入如下所示程序；//文件名：exp8-2.cpp#include <stdio.h>#include <malloc.h>#include "graph.h"extern void MatToList1(MGraph, ALGraph *&); extern void DispAdj1(ALGraph *G);extern void DFS(ALGraph *G,int v);extern void DFS1(ALGraph *G,int v);extern void DFS2(ALGraph *G,int v);extern void BFS(ALGraph *G,int v);int main(){int i,j;//文件名：algo8-2.cpp#include <stdio.h>#include <malloc.h>#include "graph.h"int visited[MAXV];void DFS(ALGraph *G,int v) //递归深度优先遍历{ArcNode *p;visited[v] = 1;printf("%3d",v);p = G->adjlist[v].firstarc;while(p!=NULL){if(visited[p->adjvex]==0)top++;St[top] = G->adjlist[w].firstarc;break;}p = p->nextarc;}}printf("\n");}void BFS(ALGraph *G,int v){ArcNode *p;int queue[MAXV],front = 0,rear = 0;int visited[MAXV];int w,i;for(i=0;i<G->n;i++)void MatToList1(MGraph g, ALGraph *&G){int i,j;ArcNode *p;G = (ALGraph*)malloc(sizeof(ALGraph));for(i=0; i<g.n;i++)G->adjlist[i].firstarc = NULL;for(i=0; i<g.n; i++)for(j=g.n-1; j>=0; j--)if(g.edges[i][j]!=0 && g.edges[i][j]!=INF){p = (ArcNode*)malloc(sizeof(ArcNode));p->adjvex = j;p->info = g.edges[i][j];p->nextarc = G->adjlist[i].firstarc;G->adjlist[i].firstarc = p;}二、对程序进行编译链接；三、运行该程序，结果如图实验③源程序。

一、输入如下所示程序；#include <stdio.h>#include <malloc.h>#include "graph.h"extern void MatToList(MGraph,ALGraph *&); extern void DispAdj(ALGraph *);int visited[MAXV];void DFSALL(ALGraph *G,int v,int path[],int d) {ArcNode *p;visited[v] = 1;path[d] = v;d++;if(d==G->n){for(int k=0;k<d;k++)printf("%2d",path[k]);printf("\n");}p = G->adjlist[v].firstarc;while(p!=NULL){if(visited[p->adjvex]==0)if(visited[p->adjvex]==0)DFSALL(G,p->adjvex,path,d);p = p->nextarc;}visited[v] = 0;}p = (ArcNode*)malloc(sizeof(ArcNode));p->adjvex = j;p->nextarc = G->adjlist[i].firstarc;G->adjlist[i].firstarc = p;}G->n = g.n;G->e = g.e;二、对程序进行编译链接；三、运行该程序，结果如图。