数据结构课设———最小生成树问题代码+报告-创新互联

目录

题目： 

运行截图：

代码： 

报告截图：

  最小生成树问题设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。

#include#include#include#define MAX_VERTEX_NUM 20
#define OK 1
#define ERROR 0
#define MAX 1000
using namespace std;
typedef struct Arcell
{
    double adj;
}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];


typedef struct
{
    char vexs[MAX_VERTEX_NUM]; //节点数组
    AdjMatrix arcs; //邻接矩阵
    int vexnum,arcnum; //图的当前节点数和弧数
}MGraph;
typedef struct Pnode //用于普利姆算法
{
    char adjvex; //节点
    double lowcost; //权值
}Pnode,Closedge[MAX_VERTEX_NUM];//记录顶点集U到V-U的代价最小的边的辅助数组定义
typedef struct Knode//用于克鲁斯卡尔算法中存储一条边及其对应的2个节点
{
    char ch1; //节点1
    char ch2; //节点2
    double value;//权值
}Knode,Dgevalue[MAX_VERTEX_NUM];

int CreateUDG(MGraph & G,Dgevalue & dgevalue);
int LocateVex(MGraph G,char ch);
int Minimum(MGraph G,Closedge closedge);
void MiniSpanTree_PRIM(MGraph G,char u);
void Sortdge(Dgevalue & dgevalue,MGraph G);
void Adjacency_Matrix(MGraph G);
void Adjacency_List(MGraph G,Dgevalue dgevalue);

int CreateUDG(MGraph & G,Dgevalue & dgevalue)//构造无向加权图的邻接矩阵
{
    int i,j,k;
    cout<<"请输入城市个数及其之间的可连接线路数目：";
    cin>>G.vexnum>>G.arcnum;
    cout<<"请输入各个城市名称(分别用一个字符代替)：";
    for(i=0;i>G.vexs[i];
    for(i=0;i>dgevalue[k].ch1 >>dgevalue[k].ch2 >>dgevalue[k].value;
        i = LocateVex(G,dgevalue[k].ch1);
        j = LocateVex(G,dgevalue[k].ch2);
        G.arcs[i][j].adj = dgevalue[k].value;
        G.arcs[j][i].adj = G.arcs[i][j].adj;
    }
    return OK;
}
int LocateVex(MGraph G,char ch) //确定节点ch在图G.vexs中的位置
{
    int a ;
    for(int i=0; i";
		for(j=0;j";
			else if(dgevalue[j].ch1!=G.vexs[i]&&dgevalue[j].ch2==G.vexs[i])
				cout<";
		cout<<"\b\b  "<dgevalue[j].value)
            {
                temp = dgevalue[i].value;
                dgevalue[i].value = dgevalue[j].value;
                dgevalue[j].value = temp;
                ch1 = dgevalue[i].ch1;
                dgevalue[i].ch1 = dgevalue[j].ch1;
                dgevalue[j].ch1 = ch1;
                ch2 = dgevalue[i].ch2;
                dgevalue[i].ch2 = dgevalue[j].ch2;
                dgevalue[j].ch2 = ch2;
            }
        }
    }
}
void MiniSpanTree_PRIM(MGraph G,char u)//普里姆算法求最小生成树
{
    int i,j,k;
    Closedge closedge;
    k = LocateVex(G,u);
    for(j=0; j>s;
  switch(s)
  {
  case 1:
   cout<<"用邻接矩阵存储为："<>u;
   MiniSpanTree_PRIM(G,u);
   break;
  default:
	  cout<<"输入有误!";
   break;
  }
  cout<>y;
  if(y=='n')
   break;
 }
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧