数据结构图实验报告-(2).doc

一、实验目得与要求
（1)掌握图得相关概念，包括图,有向图,无向图，完全图，子图,连通图,度,入度，出度,简单回路与环等定义.
（2）重点掌握图得各种存储结构，包括邻接矩阵与邻接表等。
(3）重点掌握图得基本运算，包括创建图,输出图,深度优先遍历,广度优先遍历等.
（4）掌握图得其她运算　,包括最小生成树,最短路径，拓扑排序与关键路径等算法。
(5)灵活运用图这种数据结构解决一些综合应用问题。
二、实验内容与方法
（1）实验内容:
１、编写一个程序alｇo8-1、cpp，实现不带权图与带权图得邻接矩阵与邻接表得相互转换算法、输出邻接矩阵与邻接表得算法，并在此基础上设计一个程序exp8—１、cpｐ实现如下功能:
①建立如图1所示得有向图G得邻接矩阵,并输出;
②由有向图Ｇ得邻接矩阵产生邻接表,并输出;
③再由②得邻接表产生对应得邻接矩阵,并输出。
1
5
6
9
7
5
8
4
5
3
0
1
5
2
4
3

图1
2、编写一个程序ａlgo8－2、cpp，实现图得遍历运算,并在此基础上设计一个程序ｅxp8－2、cpp完成如下功能：
①输出图1所示得有向图Ｇ从顶点0开始得深度优先遍历序列（递归算法）；
②输出图１所示得有向图G从顶点0开始得深度优先遍历序列（非递归算法);
③输出图1所示得有向图G从顶点0开始得广度优先遍历序列。
３、设计一个程序exp8－3、cpp,采用邻接表存储图，并输出图8、1(a）中从指定顶点1出发得所有深度优先遍历序列。
(2)实验方法:
1、综合运用课本所学得知识，用不同得算法实现在不同得程序功能.
2、结合指导老师得指导，解决程序中得问题，正确解决实际中存在得异常情况，逐步改善功能。
3、根据实验内容，编译程序。
三、实验环境：
Winｄows　7,Visuａl　C＋+6、0
三、实验过程描述
文件ｇraph、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;
ArcNode* firstarc;
}VNode;

typedef VNode AdjList[MAXV];

typedef struct
{
AdjList adjlist;
int n,e;
}ALGraph;

#endif // GRAPH_H_INCLUDED

VertexType vexs[MAXV];
}MGraph;

//以下定义邻接表类型
typedef struct ANode
{
int adjvex;
struct ANode* nextarc;
InfoType info;
}ArcNode;

typedef int Vertex;

typedef struct VNode
{
Vertex data;
ArcNode* firstarc;
}VNode;

typedef VNode AdjList[MAXV];

typedef struct
{
AdjList adjlist;
int n,e;
}ALGraph;

#endif // GRAPH_H_INCLUDED

实验①
源程序。
一、输入如下所示程序;
//文件名: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");

DispMat1(g);
G = (ALGraph*)malloc(sizeof(ALGraph));
printf("图G得邻接矩阵转换成邻接表:\n");
MatToList1(g,G);
DispAdj1(G);
printf("图G得邻接表转换成邻接矩阵:\n");
ListToMat1(G,g1);
DispMat1(g1);

return 0;
}

//文件名: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++)
for(j=0; j<G->n; j++)
g、edges[i][j] = 0;

for(i=0; i<G->n; i++)
{
p = G->adjlist[i]、firstarc;
while(p!=NULL)
{
g、edges[i][p->adjvex] = 1;
p = p->nextarc;
}
}
g、n = G->n;
g、e = G->e;
}

void DispMat(MGraph g)
{
int i,j;
for(i=0; i<g、n; i++)
{
for(j=0; j<g、n; j++)
printf("%3d",g、edges[i][j]);
printf("\n");
}
}

void DispAdj(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",p->adjvex);
p = p->nextarc;
}
printf("\n");
}
}

//带权图得算法
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;
}
G->n = g、n;
G->e = g、e;
}

void ListToMat1(ALGraph *G, MGraph &g)
{
int i,j;
ArcNode *p;

for(i=0; i<G->n; i++)
for(j=0; j<G->n; j++)
if(i==j)
g、edges[i][j] = 0;
else
g、edges[i][j] = INF;

for(i=0; i<G->n; i++)
{
p = G->adjlist[i]、firstarc;
while(p!=NULL)
{
g、edges[i][p->adjvex] = p->info;
p = p->nextarc;
}
}
g、n = G->n;
g、e = G->e;
}

void DispMat1(MGraph g)
{
int i,j;
for(i=0; i<g、n; i++)
{
for(j=0; j<g、n; j++)
if(g、edges[i][j] == INF)
printf("%3s","∞");
else
printf("%3d",g、edges[i][j]);
printf("\n");
}
}

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");
}
}

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");
}
}

二、编译并链接程序;
三、运行程序，结果如下图:

实验
源程序
一、输入如下所示程序;
//文件名: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;
MGraph g;
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];
G = (ALGraph*)malloc(sizeof(ALGraph));
MatToList1(g,G);
printf("图G得邻接表:\n");
DispAdj1(G);
printf("从顶点0开始得DFS(递归算法):\n");
DFS(G,0);
printf("\n");
printf("从顶点0开始得DFS(非递归算法):\n");
DFS1(G,0);
printf("\n");
printf("从顶点0开始得BFS:\n");
BFS(G,0);
printf("\n");

returne 0;
}

//文件名: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)
DFS(G,p->adjvex);
p = p->nextarc;
}
}

void DFS1(ALGraph *G,int v) //非递归深度优先遍历
{
ArcNode *p;
ArcNode *St[MAXV];
int top = -1,w,i;
for(i=0; i<G->n; i++)
visited[i] = 0;
printf("%3d",v);
visited[v] = 1;
top++;
St[top] = G->adjlist[v]、firstarc;
while(top>-1)
{
p = St[top];
top--;
while(p!=NULL)
{
w = p->adjvex;
if(visited[w]==0)
{
printf("%3d",w);
visited[w] = 1;
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++)
visited[i] = 0;
printf("%3d",v);
visited[v] = 1;
rear = (rear+1) % MAXV;
queue[rear] = v;
while(front!=rear)
{
front = (front+1)%MAXV;
w = queue[front];
p = G->adjlist[w]、firstarc;
while(p!=NULL)
{
if(visited[p->adjvex]==0)
{
printf("%3d",p->adjvex);
visited[p->adjvex] = 1;
rear = (rear+1) % MAXV;
queue[rear] = p->adjvex;
}
p = p->nextarc;
}
}
printf("\n");
}

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;
}
G->n = g、n;
G->e = g、e;
}

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");
}
}

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++)
visited[i] = 0;
printf("%3d",v);
visited[v] = 1;
rear = (rear+1) % MAXV;
queue[rear] = v;
while(front!=rear)
{
front = (front+1)%MAXV;
w = queue[front];
p = G->adjlist[w]、firstarc;
while(p!=NULL)
{
if(visited[p->adjvex]==0)
{
printf("%3d",p->adjvex);
visited[p->adjvex] = 1;
rear = (rear+1) % MAXV;
queue[rear] = p->adjvex;
}
p = p->nextarc;
}
}
printf("\n");
}

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;
}
G->n = g、n;
G->e = g、e;
}

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");
}
}

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;
}
G->n = g、n;
G->e = g、e;
}

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");
}
}

二、对程序进行编译链接；
三、运行该程序,结果如图

实验③
源程序。
一、输入如下所示程序;
#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)
DFSALL(G,p->adjvex,path,d);
p = p->nextarc;
}
visited[v] = 0;
}

int main()
{
int path[MAXV],i,j,v=1;
MGraph g;
ALGraph *G;
g、n = 5;
g、e = 8;
int A[MAXV][MAXV] = {{0,1,0,1,1},{1,0,1,1,0},{0,1,0,1,1},
{1,1,1,0,1},{1,0,1,1,0}};
for(i=0;i<g、n;i++)
for(j=0;j<g、n;j++)
g、edges[i][j] = A[i][j];
MatToList(g,G);
for (i=0;i<g、n;i++)
visited[i] = 0;
printf("图G得邻接表: \n");
DispAdj(G);
printf("从顶点%d出发得所有深度优先序列:\n",v);
DFSALL(G,v,path,0);
printf("\n");

return 0;
}

void MatToList(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)
{
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 DispAdj(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",p->adjvex);
p = p->nextarc;
}
printf("\n");
}
}

if(visited[p->adjvex]==0)
DFSALL(G,p->adjvex,path,d);
p = p->nextarc;
}
visi