关于带权无向图的一些操作
题目:根据图来建立它的邻接矩阵,通过邻接矩阵转化为邻接表,对邻接表进行深度优先访问和广度优先访问,最后用邻接矩阵生成它的最小生成树;
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
最小生成树