无向图(使用邻接矩阵)

C语言数据结构实验,已经调试成功。直接复制即可运行。由于文库不支持C文件,所以将扩展名改为了TXT,可下载后直接将其改为C或cpp即可直接运行。

#include<stdio.h>
#include<stdlib.h>

#define MaxVertices 100 //假设包含100个顶点
#define MaxWeight 32767 //不邻接时为32767，但输出时用 "∞"

typedef struct //包含权的邻接矩阵的的定义
{int Vertices[MaxVertices]; //顶点信息的数组
int Edge[MaxVertices][MaxVertices]; //边的权信息的数组
int numV; //当前的顶点数
int numE; //当前的边数
}AdjMatrix;


void main()
{void CreateGraph(AdjMatrix*G);
void DispGraph(AdjMatrix G);
void Prim(AdjMatrix G); //最小生成树的普里姆算法;
AdjMatrix G;
CreateGraph(&G);
DispGraph(G);
Prim(G);
}

void CreateGraph(AdjMatrix*G) //图(带权)的产生函数(建立无(有)向图)
{int n,e,vi,vj,w,i,j;
printf("请输入图的顶点数和边数（以空格分隔）：");
scanf("%d%d",&n,&e);
G->numV=n;G->numE=e;
for(i=0;i<n;i++) //对图进行初始化
for(j=0;j<n;j++)
{if(i==j)
G->Edge[i][j]=0;
else
G->Edge[i][j]=32767;
}
for(i=0;i<n;i++)
for(i=0;i<G->numV;i++) //将顶点存入数组中
{printf("请输入第%d个顶点的信息(整型):",i+1);
scanf("%d",&G->Vertices[i]);
}
printf("\n");
for(i=0;i<G->numE;i++)
{printf("请输入边的信息i,j,w(以空格分隔):");
scanf("%d%d%d",&vi,&vj,&w); //建立有向图时只有此句
G->Edge[vi-1][vj-1]=w;
G->Edge[vj-1][vi-1]=w; //建立均向图片时要此句
}
}

void DispGraph(AdjMatrix G) //输出邻接矩阵的信息
{int i,j;
printf("\n输出顶点的信息（整型）:\n");
for(i=0;i<G.numV;i++)
printf("%8d",G.Vertices[i]);
printf("\n输出邻接矩阵:\n");
printf(" ");
for(i=0;i<G.numV;i++)
printf("%8d",G.Vertices[i]);
for(i=0;i<G.numV;i++)
{printf("\n%8d",i+1);
for(j=0;j<G.numV;j++)
{if(G.Edge[i][j]==32767) //无边时值为32767，但输出时为了方便输出 "∞"
printf("%8s", "∞");
else
printf("%8d",G.Edge[i][j]);
}
printf("\n");
}
}

typedef struct //定义最小生成树的带权边
{int begin,end;//边的起点和终点
int weight; //边的权值
}MinSpanTree;

void Prim(AdjMatrix G) //最小生成树的普里姆算法
{int n,j,k,v,min,m;
n=G.numV;
MinSpanTree e,mintree[100]; //mintree生成树数组
for(j=1;j
<n;j++) //初始化mintree
{mintree[j-1].begin=1; //将1并入U中
mintree[j-1].end=j+1;
mintree[j-1].weig

C语言数据结构实验,已经调试成功。直接复制即可运行。由于文库不支持C文件,所以将扩展名改为了TXT,可下载后直接将其改为C或cpp即可直接运行。

ht=G.Edge[0][j];
}
for(k=0;k<n-1;k++) //求第k+1条边
{min=MaxWeight;
for(j=k;j<n-1;j++)
if(mintree[j].weight<min)
{min=mintree[j].weight;m=j;}
e=mintree[m];mintree[m]=mintree[k];mintree[k]=e;
v=mintree[k].end;
for(j=k+1;j<n-1;j++) //在新顶点v并入U之后更新tree[n-1]
{int d=G.Edge[v-1][mintree[j].end-1];
if(d<mintree[j].weight)
{mintree[j].weight=d;
mintree[j].begin=v;
}
}
}
printf("最小生成树为：");
for(j=0;j<n-1;j++)
printf("\ni=%d,j=%d,weight=%d",mintree[j].begin,mintree[j].end,mintree[j].weight);
printf("\n");
}

本文来源：https://www.bwwdw.com/article/8u2q.html