一、 实验目的
（1）掌握图的邻接矩阵和邻接表存储结构。
（2）熟练图的邻接表的基本运算。
（3）加深图的深度优先遍历算法和广度优先遍历算法的理解
二、 实验要求
有下图所示的带权有向图及其对应的邻接矩阵,编写一个程序exp7-1.c,实现图的各种基本运算和下面main函数中的每一步功能。
（1）依据所给的邻接矩阵，创建图的邻接表存储，并输出邻接表结构；
（2）输出从顶点0出发的一个深度优先遍历序列
（3）输出从顶点0出发的一个广度优先遍历序列
（4）销毁图的邻接表。
三、实验环境
Windows+DEV C++( 或者其他编译工具)
四、实验步骤及结果
1.类型声明
typedef char VertexType[10];//顶点的数据类型
//声明邻接矩阵类型
typedef struct vertex//顶点
{
int adjvex;//邻接点域
VertexType data;//顶点信息
} VType;//顶点的类型
typedef struct graph//图表
{
int n,e;//顶点数、边数
VType vexs[MAXV];//存放顶点信息
int edges[MAXV][MAXV];//邻接矩阵数组
} MatGraph;//完整的图邻接矩阵类型
//声明邻接表类型
typedef struct ANode//边结点
{
int adjvex;//该边的邻接点编号
int weight;//该边的相关信息，例如权值（这里用整型表示）
struct ANode *nextarc;//指向下一条边的指针
} ArcNode;//边结点的类型
typedef struct Vnode //头结点
{
VertexType data;//顶点信息
ArcNode *firstarc;//指向第一个边结点
} VNode;// 邻接表的头结点类型
typedef struct
{
int n,e;//图中顶点数n和边数e
VNode adjlist[MAXV];//邻接表的头结点数组
} AdjGraph;2.图的基本运算在链式存储结构上的实现
void DestroyGraph(AdjGraph *&g)//销毁邻接表运算算法
{
int i;
ArcNode *pre,*p;
for (i=0;i<g->n;i++)// 遍历所有的单链表
{
pre=g->adjlist[i].firstarc;//p指向第i个单链表的头结点
if (pre!=NULL)
{
p=pre->nextarc;
while (p!=NULL) //释放第i个单链表的所有边结点
{
free(pre);
pre=p;p=p->nextarc;
}
free(pre);//释放头结点数组
}
}
free(g);
}
void DispGraph(AdjGraph *g)//输出邻接表g运算算法
{
ArcNode *p;
int i;
for (i=0;i<g->n;i++)
{
printf(" [%2d]",i);
p=g->adjlist[i].firstarc;
if (p!=NULL)
printf("→");
while (p!=NULL)
{
printf("%d(%d)",p->adjvex,p->weight);
p=p->nextarc;
}
printf("\n");
}
}3. 程序exp7-1.c的设计，及完成实验要求中的功能
#include <iostream>
using namespace std;
#include <stdlib.h>
#define MAXV 100//定义最大顶点数
#define INF 32767//定义无穷大
#include <stdio.h>
int visited[MAXV];//访问标志数组
int visited1[MAXV];
typedef char VertexType[10];//顶点的数据类型
//声明邻接矩阵类型
typedef struct vertex//顶点
{
int adjvex;//邻接点域
VertexType data;//顶点信息
} VType;//顶点的类型
typedef struct graph//图表
{
int n,e;//顶点数、边数
VType vexs[MAXV];//存放顶点信息
int edges[MAXV][MAXV];//邻接矩阵数组
} MatGraph;//完整的图邻接矩阵类型
//声明邻接表类型
typedef struct ANode//边结点
{
int adjvex;//该边的邻接点编号
int weight;//该边的相关信息，例如权值（这里用整型表示）
struct ANode *nextarc;//指向下一条边的指针
} ArcNode;//边结点的类型
typedef struct Vnode //头结点
{
VertexType data;//顶点信息
ArcNode *firstarc;//指向第一个边结点
} VNode;// 邻接表的头结点类型
typedef struct
{
int n,e;//图中顶点数n和边数e
VNode adjlist[MAXV];//邻接表的头结点数组
} AdjGraph;
void CreateGraph1(MatGraph &G,int A[][MAXV],int n,int e)
//建立邻接矩阵运算算法
{
int i,j;
G.n=n;G.e=e;
for (i=0;i<n;i++)
for (j=0;j<n;j++)
G.edges[i][j]=A[i][j];
}
void DestroyGraph1(MatGraph G)//销毁邻接矩阵运算算法
{}
void DispGraph1(MatGraph 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("%4d",G.edges[i][j]);
else
printf("%4s","∞");
printf("\n");
}
}
int Degree1(MatGraph G,int v)//有向图邻接矩阵顶点度运算算法
{
int i,d1=0,d2=0,d;
if (v<0 || v>=G.n)
return -1;
for (i=0;i<G.n;i++)
if (G.edges[v][i]>0&&G.edges[v][i]<INF)
d1++;
for (i=0;i<G.n;i++)
if (G.edges[i][v]>0&&G.edges[i][v]<INF)
d2++;
d=d1+d2;
return d;
}
void DFS1(MatGraph G,int v)//邻接矩阵存储的深度优先遍历序列
{
int w;
printf("%d",v);
visited1[v]=1;
for (w=0;w<G.n;w++)
if (G.edges[v][w]!=0&&G.edges[v][w]!=INF&&visited1[w]==0)
DFS1(G,w);
}
void BFS1(MatGraph G,int v)//邻接矩阵存储的广度优先遍历序列
{
int i,w;
int Qu[MAXV],front=0,rear=0;
for (i=0;i<G.n;i++) visited1[i]=0;
printf("%d",v);
visited1[v]=1;
rear=(rear+1)%MAXV;
Qu[rear]=v;
while (front!=rear)
{
front=(front+1)%MAXV;
w=Qu[front];
for (i=0;i<G.n;i++)
if (G.edges[w][i]!=0&&G.edges[w][i]!=INF&&visited1[i]==0)
{
printf("%d",i);
visited1[i]=1;
rear=(rear+1)%MAXV;
Qu[rear]=i;
}
}
}
void CreateGraph(AdjGraph *&g,int A[][MAXV],int n,int e)//建立邻接表运算算法
{
int i,j;
ArcNode *p;
g=(AdjGraph *)malloc(sizeof(AdjGraph));//动态分配空间
g->n=n;g->e=e;
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 (A[i][j]>0&&A[i][j]<INF)//存在一条边<i,j>
{
p=(ArcNode *)malloc(sizeof(ArcNode));//创建一个结点p
p->adjvex=j;//存放邻接点
p->weight=A[i][j];//存放权
p->nextarc=g->adjlist[i].firstarc;//采用头插法插入结点p
g->adjlist[i].firstarc=p;
}
}
void DestroyGraph(AdjGraph *&g)//销毁邻接表运算算法
{
int i;
ArcNode *pre,*p;
for (i=0;i<g->n;i++)// 遍历所有的单链表
{
pre=g->adjlist[i].firstarc;//p指向第i个单链表的头结点
if (pre!=NULL)
{
p=pre->nextarc;
while (p!=NULL) //释放第i个单链表的所有边结点
{
free(pre);
pre=p;p=p->nextarc;
}
free(pre);//释放头结点数组
}
}4.实验结果截图
如需源文件，请私信作者，无偿
