一、实验目的和要求
（1）掌握图的相关概念，包括图，有向图，无向图，完全图，子图，连通图，度，入度，出度，简单回路和环等定义。
（2）重点掌握图的各种存储结构，包括邻接矩阵和邻接表等。
（3）重点掌握图的基本运算，包括创建图，输出图，深度优先遍历，广度优先遍历等。 （4）掌握图的其他运算 ，包括最小生成树，最短路径，拓扑排序和关键路径等算法。 （5）灵活运用图这种数据结构解决一些综合应用问题。
二、实验内容和方法
(1)实验内容：
1、编写一个程序algo8-1.cpp，实现不带权图和带权图的邻接矩阵与邻接表的相互转换算法、输出邻接矩阵与邻接表的算法，并在此基础上设计一个程序exp8-1.cpp实现如下功能：
①建立如图1所示的有向图G的邻接矩阵，并输出； ②由有向图G的邻接矩阵产生邻接表，并输出； ③再由②的邻接表产生对应的邻接矩阵，并输出。
图1
2、编写一个程序algo8-2.cpp，实现图的遍历运算，并在此基础上设计一个程序exp8-2.cpp完成如下功能：
①输出图1所示的有向图G从顶点0开始的深度优先遍历序列（递归算法）； ②输出图1所示的有向图G从顶点0开始的深度优先遍历序列（非递归算法）； ③输出图1所示的有向图G从顶点0开始的广度优先遍历序列。
3、设计一个程序exp8-3.cpp,采用邻接表存储图，并输出图8.1（a）中从指定顶点1出发的所有深度优先遍历序列。
1 4 5 6 5 3 5 3 0 7 5 1 9 8 2 4
(2)实验方法：
1、综合运用课本所学的知识，用不同的算法实现在不同的程序功能。
2、结合指导老师的指导，解决程序中的问题，正确解决实际中存在的异常情况，逐步改善功能。
3、根据实验内容，编译程序。
三、实验环境：
Windows 7，Visual C++6.0
三、实验过程描述
文件graph.h中定义了图的邻接矩阵表示类型和邻接表表示类型，该头文件在以下三个实验中都会使用到。其代码如下：
#ifndef GRAPH_H_INCLUDED #define GRAPH_H_INCLUDED
typedef 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
#include
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.edges[i][j] = A[i][j]; printf(\有向图G的邻接矩阵：\\n\ //文件名：algo8-1.cpp #include #include //不带权图的算法 void MatToList(MGraph g, ALGraph *&G) { int i,j; ArcNode *p; G = (ALGraph*)malloc(sizeof(ALGraph)); for(i=0; i 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 void DispAdj1(ALGraph *G) { int i; ArcNode *p; for(i=0; i p = G->adjlist[i].firstarc; printf(\ while(p!=NULL) { printf(\ p = p->nextarc; } printf(\ }