实验内容
1、编写一个程序graph.cpp,设计带权图的邻接矩阵与邻接表的创建和输出运算,并在此基础上设计一个主程序exp8-1.cpp完成以下功能。
(1)建立如图8.54所示的有向图G的邻接矩阵,并输出之。
(2)建立如图8.54所示的有向图G的邻接表,并输出之。
(3)销毁图G的邻接表。
2、编写一个程序travsal.cpp实现图的两种遍历运算,并在此基础上设计一个程序exp8-2.cpp完成以下功能。
(1)输出如图8.54的有向图G从顶点0开始的深度优先遍历序列(递归算法)。
(2)输出如图8.54的有向图G从顶点0开始的深度优先遍历序列(非递归算法)。
(3)输出如图8.54的有向图G从顶点0开始的广度优先遍历序列。
代码实现
1、
#include <iostream>
#include <malloc.h>
#define INF 32767 //定义无穷大
#define MAXV 100 //最大顶点个数
typedef char InfoType;
//定义邻接矩阵类型
typedef struct
{
int no;
InfoType info;
}VertexType;
typedef struct
{
int edges[MAXV][MAXV];
int n,e;
VertexType vexs[MAXV];
}MatGraph;
//定义邻接表类型
typedef struct ANode
{
int adjvex;
struct ANode *nextarc;
int weight;
} ArcNode;
typedef struct Vnode
{
InfoType info;
int count;
ArcNode *firstarc;
}VNode;
typedef struct
{
VNode adjlist[MAXV];
int n,e;
}AdjGraph;
//邻接矩阵的基本运算:
//创建邻接矩阵
void CreateMat(MatGraph &g,int A[MAXV][MAXV],int n,int e)
{
int i,j;
g.n=n;g.e=e;
for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++)
g.edges[i][j]=A[i][j];
}
//输出邻接矩阵
void DispMat(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");
}
}
//邻接表的基本运算:
//创建邻接表
void CreateAdj(AdjGraph *&G,int A[MAXV][MAXV],int n,int e)
{
int i,j;
ArcNode *p;
G=(AdjGraph *)malloc(sizeof(AdjGraph));
for(i=0;i<n;i++)
G->adjlist[i].firstarc=NULL;
for(i=0;i<n;i++)
{
for(j=n-1;j>=0;j--)
{
if(A[i][j]!=0&&A[i][j]!=INF)
{
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=j;
p->weight=A[i][j];
p->nextarc=G->adjlist[i].firstarc;
G->adjlist[i].firstarc=p;
}
}
}
G->n=n;G->e=n;
}
//输出邻接表
void DispAdj(AdjGraph *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->weight);
p=p->nextarc ;
}
printf("^\n");
}
}
//销毁邻接表
void DestroyAdj(AdjGraph *&G)
{
int i;
ArcNode *pre,*p;
for(i=0;i<G->n;i++)
{
pre=G->adjlist[i].firstarc;
if(pre!=NULL)
{
p=pre->nextarc ;
while(p!=NULL)
{
free(pre);
pre=p;p=p->nextarc ;
}
free(pre);
}
}
free(G);
}
int main()
{
MatGraph g;
AdjGraph *G;
int A[MAXV][MAXV]={{0,1,0,1,0,0},
{0,0,1,0,0,0},
{1,0,0,0,0,1},
{0,0,1,0,0,1},
{0,0,0,1,0,0},
{1,0,0,0,1,0}};
int n=6,e=10;
CreateMat(g,A,n,e);
printf("图G的邻接矩阵:\n");
DispMat(g);
CreateAdj(G,A,n,e);
printf("图G的邻接表:\n");
DispAdj(G);
DestroyAdj(G);
return 1;
}
结果截图:
2、
#include<stdio.h>
#include<malloc.h>
#define MAXV 100
//以下定义邻接矩阵类型
typedef struct
{
int no; //顶点编号
int info; //顶点其余的信息
}VertexType;
typedef struct
{
int edges[MAXV][MAXV]; //邻接矩阵
int n,e; //顶点数,弧数
VertexType vexs[MAXV]; //存放顶点信息
}MGraph;
//一下定义邻接表类型
typedef struct ANode //弧的节点结构类型
{
int adjvex; //该弧的终点位置
struct ANode *nextarc;
int info; //弧的相关信息
} ArcNode;
typedef struct Vnode //邻接表头结点类型
{
int data; //顶点信息
ArcNode *firstarc; //指向第一条弧
}VNode;
typedef VNode AdjList[MAXV];
typedef struct
{
AdjList adjlist;
int n,e;
}ALGraph;
int visited[MAXV];
//递归深度优先遍历
void DFS(ALGraph *G,int v)
{
ArcNode *p;
visited[v]=1;
printf("%3d",v);
p=G->adjlist[v].firstarc;
while(p)
{
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,i,w;
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)
{
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 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)
{
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 DispAdj(ALGraph *G) //输出邻接表
{
int i;
ArcNode *p;
for(i=0;i<G->n;i++)
{
p=G->adjlist[i].firstarc;
if(p) printf("%3d:",i);
while(p)
{
printf("%3d->",p->adjvex);
p=p->nextarc;
}
printf("\n");
}
}
void MatToList(MGraph g,ALGraph *&G) //将邻接矩阵 g 转换为邻接表 G
{
int i,j,n=g.n;
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
for(i=0;i<n;i++)
G->adjlist[i].firstarc=NULL;
for(i=0;i<n;i++)
for(j=n-1;j>=0;j--)
if(g.edges[i][j])
{
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=n;
G->e=g.e;
}
int main()
{
int i,j;
MGraph g;
ALGraph *G;
int A[MAXV][6]={
{0,5,0,7,0,0},
{0,0,4,0,0,0},
{8,0,0,0,0,9},
{0,0,5,0,0,6},
{0,0,0,5,0,0},
{3,0,0,0,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));
MatToList(g,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");
}
结果截图: