图的建立以及应用(BFS,DFS,Prim)

关于带权无向图的一些操作

题目:根据图来建立它的邻接矩阵,通过邻接矩阵转化为邻接表,对邻接表进行深度优先访问和广度优先访问,最后用邻接矩阵生成它的最小生成树;

1.输入一个带权无向图(如下面图1和图2)的顶点数、边数、各条边信息(两个顶点和权值),建立该图的邻接矩阵结构,输出该邻接矩阵。

​ 图1 图2

2.将上述无向图邻接矩阵转换为邻接表结构,输出该邻接表;

3.根据该邻接表对无向图进行深度优先遍历序列和广度优先遍历序列,并输出遍历结果;

4.用prim算法实现构造该带权无向图的最小生成树,并将该最小生成树的各条边信息输出。

一些注意

程序用文件读入,使用前应写好读入文件;

初始工作(所有的结构体定义和函数声明)

结构体定义

# include <stdio.h>
# include <stdlib.h>
# define MAX 20
#define  MAXV  20	//最大顶点个数
#define VertexType int //存放顶点信息
#define QElemType int
typedef  int  VetexType;
int visited[MAX];
typedef struct ArcNode		//弧结点类型定义
{
int  adjvex;		//该弧的弧头
int weight;
struct  ArcNode  *nextarc;		//指向另一个弧结点的指针
}ArcNode;
typedef  struct  VNode		//邻接表头结点类型定义
{
VetexType  data;		//顶点信息
int adv;
ArcNode  *firstarc;		//指向第一个依附于该顶点的弧的指针
} AdjList[MAX];
typedef  struct		//图定义
{
AdjList  vertices;		//邻接表定义
int  vexnum, arcnum;		//顶点数和弧数
}ALGraph;
typedef  struct
{
int  adj;
int weight;			//顶点关系(0或1)
//	InfoType  info;	//该弧或边的相关信息
} AdjMatrix[MAXV][MAXV];
typedef  struct		//图的定义
{
AdjMatrix  arcs;				//邻接矩阵
int  vexnum, arcnum;			//顶点数,弧数
VertexType vexs[MAXV];		//存放顶点信息
} MGraph;
//队列的定义
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct {
QueuePtr front;
QueuePtr rear;
}LinkQueue;
//辅助数组定义
struct mini{
int adjvex;
int lowcost;
}mini,closedge[MAXV];

函数声明

void creatMG(MGraph *G);
void outMG(MGraph *G);
void Transition(MGraph *G1,ALGraph *G2);
void outALGraph(ALGraph *G);
void DFSTraverse(ALGraph *G);
void BFSTraverse(ALGraph G);
void DFS(ALGraph *G,int v);
void visit(int v,ALGraph *G);
void InitQueue(LinkQueue *Q);
void EnQueue(LinkQueue *Q,QElemType e);
void DeQueue(LinkQueue *Q,int *e);
int QueueEmpty(LinkQueue Q);
void MiniSpanTree(MGraph G,int u);

具体的函数实现

//创造邻接矩阵
void creatMG(MGraph *G){
int i, j, k,n,w,e;
FILE *fp1;
fp1=fopen("text2.txt","r");//第一组数据打开text1, 第二组数据打开text2;
if(!fp1)
{
printf("can't open file\n");
return ;
}
//	printf("输入顶点数和边数\n");
fscanf(fp1,"%d%d", &n, &e);	//输入顶点数n,边数e
G->arcnum =e;G->vexnum=n;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
{
G->arcs[i][j].adj=0;
G->arcs[i][j].weight=1000;//假设最大权值不会超过一千
}
for(k=1; k<=e; k++)	//勾画各条边
{
//	printf("输入边(vi, vj)的顶点号vi, vj以及权值w\n ");
fscanf(fp1,"%d%d%d", &i, &j,&w);		//输入一条边的两个顶点编号i,j
G->arcs[i][j].adj=1;
G->arcs[j][i].adj=1;
G->arcs[i][j].weight=w;
G->arcs[j][i].weight=w;
}	//若是网,可让G[i][j]=w,w也需提前输入
} //creat_Mg
void outMG(MGraph *G){//输出邻接矩阵
int i, j;
for(i=1; i<=G->vexnum; i++)		//矩阵原样输出
{
printf("\n");
for(j=1; j<=G->vexnum; j++)
printf("%5d", G->arcs[i][j].adj);
}
//输出所存在的边
for(i=1; i<=G->vexnum; i++)
{
for(j=1; j<=G->vexnum; j++)
{
if(G->arcs[i][j].adj!=0)
//	printf("\n存在边( %d, %d )",i,j);
printf("\n存在边( %d, %d )它的权值为%d",i,j,G->arcs[i][j].weight);
}
}
printf("\n");
} //out_Mg
//邻接矩阵转化成邻接表
void Transition(MGraph *G1,ALGraph *G2){
int i,j;
ArcNode *p;
G2->arcnum=G1->arcnum;//点和边的数值相同
G2->vexnum=G1->vexnum;
for(i=1;i<=G2->vexnum;i++){
G2->vertices[i].data=i;
G2->vertices[i].adv=i;
G2->vertices[i].firstarc =NULL;//每个结点是首地址指向NULL
for(j=1;j<=G2->vexnum;j++){
if(G1->arcs[i][j].adj){
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=j;
p->weight=G1->arcs[i][j].weight;//保存权重
p->nextarc=G2->vertices[i].firstarc;//头插入到后面
G2->vertices[i].firstarc =p;
}
}
}
}
void outALGraph(ALGraph *G){ //输出邻接表
int i;
ArcNode *p;
for(i=1;i<=G->vexnum;i++){
printf("%d",G->vertices[i].adv);
p=G->vertices[i].firstarc;
while(p){//依次输出与该点相互邻接的点
printf("->%d",p->adjvex);
p=p->nextarc;
}
printf("\n");
}
}
//DFS
void DFSTraverse(ALGraph *G){
int i;
for(i=0;i<=G->vexnum;i++){
visited[i]=0;
}
for(i=1;i<=G->vexnum;i++){//防止不是连通图
if(!visited[i]){
DFS(G,i);
}
}
}
void DFS(ALGraph *G,int v){//深度优先遍历
ArcNode *p;
visited[v]=1;
visit(v,G);
for(p=G->vertices[v].firstarc;p;p=p->nextarc){//依次经过每个结点
if(!visited[p->adjvex]) DFS(G,p->adjvex);//未访问测访问
}
}
void BFSTraverse(ALGraph G) { //广度优先遍历
LinkQueue Q;
ArcNode *p;
int v,u;
for(v=0;v<=G.vexnum;v++){
visited[v]=0;//初始化
}
InitQueue(&Q);
for(v=1;v<=G.vexnum;v++){
if(!visited[v]){
visited[v]=1;
visit(v,&G);
EnQueue(&Q,v);
while(QueueEmpty(Q)){
DeQueue(&Q,&u);
for(p=G.vertices[u].firstarc;p;p=p->nextarc){
if(!visited[p->adjvex]){
visited[p->adjvex]=1;//新访问的点标记
visit(p->adjvex,&G);//访问
EnQueue(&Q,p->adjvex);//新点入队
}
}
}
}
}
}
void visit(int v,ALGraph *G){//访问点信息的函数
printf("%d\n",G->vertices[v].data);
}
void InitQueue(LinkQueue *Q){//队列初始化
Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
Q->front->next=NULL;//首尾都指向NULL
}
void EnQueue(LinkQueue *Q,int e){//入队
QueuePtr p;
p=(QueuePtr)malloc(sizeof(QNode));
p->data=e;
p->next=Q->rear->next;
Q->rear->next=p;//插入队中
Q->rear=p;
}
void DeQueue(LinkQueue *Q,int *e){//出队
QueuePtr p;
if(Q->front==Q->rear) return ;//队列为空
p=Q->front->next;
*e=p->data;
Q->front->next=p->next;
if(Q->rear==p) Q->rear=Q->front;//此时只有一个元素
}
int QueueEmpty(LinkQueue Q){
if(Q.front==Q.rear) return 0;//为空
return 1;
}
//构造最小生成树
void MiniSpanTree(MGraph G,int u){//u为顶点,表示从第几个顶点开始构造最小生成树
int j,i,k,a,min=1000;
k=u;
for(j=0;j<=G.vexnum;j++){
closedge[j].lowcost=1000;
}
for(j=1;j<G.vexnum;j++){
if(j!=k){
closedge[j].adjvex=u;
closedge[j].lowcost=G.arcs[k][j].weight;
}
}
closedge[k].lowcost=0;
for(i=2;i<=G.vexnum;i++){
for(a=1;a<=G.vexnum;a++){
if(closedge[a].lowcost<min&&closedge[a].lowcost!=0){
min=closedge[a].lowcost;
k=a;
}
}
min=1000;
printf("点%d到点%d,权值为%d\n",closedge[k].adjvex,k,closedge[k].lowcost);
closedge[k].lowcost=0;
for(j=1;j<=G.vexnum;j++){
if(G.arcs[k][j].weight<closedge[j].lowcost){//printf("-");
closedge[j].adjvex=k;
closedge[j].lowcost=G.arcs[k][j].weight;
}
}
}
}

main函数

//主函数
int main(){
MGraph G1;
ALGraph G2;
creatMG(&G1);
printf("输出邻接矩阵\n");
outMG(&G1);
Transition(&G1,&G2);
printf("输出邻接表\n");
outALGraph(&G2);
printf("输出深度优先排序\n");
DFSTraverse(&G2);
printf("输出广度优先排序\n");
BFSTraverse(G2);
printf("输出最小生成树\n");
MiniSpanTree(G1,1);
return 0;
}

一下是测试用例以及结果

第一组数据:

图的样子

邻接矩阵

各个点之间的权值

邻接表

DFS和BFS

最小生成树

博客园精华区
我还没有学会写个人说明!
上一篇

神州租车18亿港元卖身,陆正耀的资本游戏走向终结

你也可能喜欢

评论已经被关闭。

插入图片