void find_min_tree()// 求解最小生成树 { for (int i = 1; i <= G.vexnum; i++) { closeedges[i].end_ver = 1; closeedges[i].lowcost = G.arcs[1][i]; closeedges[i].flag = 0; } closeedges[1].flag = 1; int min; for (int i = 2; i <= G.vexnum; i++) { min = -1; for (int j = 1; j <= G.vexnum; j++) { if (closeedges[j].flag == 0 && (closeedges[j].lowcost > 0 && (min < 0 || closeedges[min].lowcost>closeedges[j].lowcost))) min = j; } closeedges[min].flag = 1; setlinecolor(GREEN); setlinestyle(PS_SOLID | PS_JOIN_BEVEL, 5); draw_arc(G.vexs[closeedges[min].end_ver], G.vexs[min], closeedges[min].lowcost); setlinecolor(RED); setlinestyle(PS_SOLID | PS_JOIN_BEVEL, 1); setfillcolor(MAGENTA); for (int i = 1; i <= G.vexnum; i++) { draw_vex(G.vexs[i], i); } Sleep(1000); for (int j = 2; j <= G.vexnum; j++) { if (closeedges[j].flag == 0 && (G.arcs[j][min] > 0 && (closeedges[j].lowcost < 0 || closeedges[j].lowcost > G.arcs[j][min]))) { closeedges[j].end_ver = min; closeedges[j].lowcost = G.arcs[j][min]; } } getchar(); } }

&&(min == -1 || closeedges[j].lowcost < closeedges[min].lowcost)) min = j; } closeedges[min].flag = 1; for (int j = 1; j <= G.vexnum; j ) { if (closeedges[j].flag == 0
&& G.arcs[min][j] < closeedges[j].lowcost) { closeedges[j].end_ver = min; closeedges[j].lowcost = G.arcs[min][j]; } } } }答：这里是求解最小生成树的算法。首先，初始化closeedges数组，将closeedges[i]的end_ver设置为1，lowcost设置为G.arcs[1][i]，flag设置为0；然后将closeedges[1].flag设置为1，进入循环，从closeedges数

相关问题

删除下列代码中的注释#include <iostream> #define MVNum 100//最大顶点数 using namespace std; typedef struct{ int vexs[MVNum];//顶点表 int arcs[MVNum][MVNum];//邻接矩阵 int vexnum,arcnum; }AMGraph; void Create_V(AMGraph &G,int name){ int pos=++G.vexnum; G.vexs[pos-1]=name;//存入点名 for(int i=1;i<=pos;i++){//点所在的行列清零 G.arcs[i-1][pos-1]=0; G.arcs[pos-1][i-1]=0; } } void Create_Arc(AMGraph &G,int h,int k){ G.arcs[h-1][k-1]=G.arcs[k-1][h-1]=1;//点与对称点都归1 } void Out_Graph(AMGraph G){ cout<<"0 ";//开头输出0 for(int i=1;i<G.vexnum;i++) cout<<G.vexs[i-1]<<" ";//输出所有点名 cout<<G.vexs[G.vexnum-1]<<endl; for(int i=1;i<=G.vexnum;i++){//输出所有弧 cout<<G.vexs[i-1]<<" "; for(int j=1;j<G.vexnum;j++){ cout<<G.arcs[i-1][j-1]<<" "; } cout<<G.arcs[i-1][G.vexnum-1]<<endl; } } void Calculate(int m,int n){ AMGraph G; G.vexnum=G.arcnum=0; for(int i=1;i<=m;i++) Create_V(G,i);//构造前n个顶点 for(int i=1;i<=n;i++){//构造n条边 int h,k; cin>>h>>k;//输入左右顶点 Create_Arc(G,h,k);//构造边 } int new_point;//新顶点 cin>>new_point; Create_V(G,new_point);//新顶点入图 Out_Graph(G);//输出图 } int main(){ int m,n; while(cin>>m>>n&&m!=0&&n!=0){//每次处理一行数据 Calculate(m,n); } return 0; }

以下是删除了注释的代码：

#include <iostream>
#define MVNum 100

using namespace std;

typedef struct{
int vexs[MVNum];
int arcs[MVNum][MVNum];
int vexnum,arcnum;
}AMGraph;

void Create_V(AMGraph &G,int name){
int pos=++G.vexnum;
G.vexs[pos-1]=name;
for(int i=1;i<=pos;i++){
G.arcs[i-1][pos-1]=0;
G.arcs[pos-1][i-1]=0;
}
}

void Create_Arc(AMGraph &G,int h,int k){
G.arcs[h-1][k-1]=G.arcs[k-1][h-1]=1;
}

void Out_Graph(AMGraph G){
cout<<"0 ";
for(int i=1;i<G.vexnum;i++) cout<<G.vexs[i-1]<<" ";
cout<<G.vexs[G.vexnum-1]<<endl;
for(int i=1;i<=G.vexnum;i++){
cout<<G.vexs[i-1]<<" ";
for(int j=1;j<G.vexnum;j++){
cout<<G.arcs[i-1][j-1]<<" ";
}
cout<<G.arcs[i-1][G.vexnum-1]<<endl;
}
}

void Calculate(int m,int n){
AMGraph G;
G.vexnum=G.arcnum=0;
for(int i=1;i<=m;i++) Create_V(G,i);
for(int i=1;i<=n;i++){
int h,k;
cin>>h>>k;
Create_Arc(G,h,k);
}
int new_point;
cin>>new_point;
Create_V(G,new_point);
Out_Graph(G);
}

int main(){
int m,n;
while(cin>>m>>n&&m!=0&&n!=0){
Calculate(m,n);
}
return 0;
}

// just for test，无向图，邻接矩阵，书上图 6.17(a) void CreateUDG_AMG_Test(AMGraph &g){ g.vexnum = 8; g.arcnum = 9; // vertices string temp[] = {"V1", "V2", "V3","V4", "V5", "V6","V7", "V8"}; for (int i=0; i<g.vexnum; i++){ g.vexs[i] = temp[i]; } // init arcs as 0 for (int j=0; j<g.vexnum; j++) for (int k=0; k<g.vexnum; k++){ g.arcs[j][k] = 0; } // arcs int arc_i[] = {0, 0, 1, 1, 2, 2, 3, 4, 5}; int arc_j[] = {1, 2, 3, 4, 5, 6, 7, 7, 6}; int i, j; for (int k=0; k<g.arcnum; k++){ i = arc_i[k]; j = arc_j[k]; g.arcs[i][j] = 1; g.arcs[j][i] = 1; } return; } // just for test，无向网，邻接矩阵，书上图 6.19 void CreateUDN_AMG_Test(AMGraph &g){ g.vexnum = 6; g.arcnum = 10; // vertices string temp[] = {"V1", "V2", "V3","V4", "V5", "V6"}; for (int i=0; i<g.vexnum; i++){ g.vexs[i] = temp[i]; } // init arcs as MaxInt for (int j=0; j<g.vexnum; j++){ for (int k=0; k<g.vexnum; k++){ g.arcs[j][k] = MaxInt; } } // arcs int arc_i[] = {0, 0, 0, 1, 1, 2, 2, 2, 3, 4}; int arc_j[] = {1, 2, 3, 2, 4, 3, 4, 5, 5, 5}; int weights[] = {6, 1, 5, 5, 3, 5, 6, 4, 2, 6}; int i, j; for (int k=0; k<g.arcnum; k++){ i = arc_i[k]; j = arc_j[k]; g.arcs[i][j] = weights[k]; g.arcs[j][i] = weights[k]; } return; } // just for test，有向网，邻接矩阵 void CreateDN_AMG_Test(AMGraph &g, int vexnum, int arcnum, string vertices[], int arc_i[], int arc_j[], int weights[]){ g.vexnum = vexnum; g.arcnum = arcnum; // vertices for (int i=0; i<g.vexnum; i++){ g.vexs[i] = vertices[i]; } // init arcs as MaxInt for (int j=0; j<g.vexnum; j++){ for (int k=0; k<g.vexnum; k++){ g.arcs[j][k] = MaxInt; } } // arcs int i, j; for (int k=0; k<g.arcnum; k++){ i = arc_i[k]; j = arc_j[k]; g.arcs[i][j] = weights[k]; } return; }如何根据这个来编写以邻接矩阵存储创建无向网

您可以使用 CreateUDN_AMG_Test 函数来创建邻接矩阵存储的无向网。该函数已经预设了一个无向网的顶点数、边数、顶点信息和边信息。您可以将它们存入 AMGraph 类型的变量 g 中，代码如下：

AMGraph g;
CreateUDN_AMG_Test(g);

这样，变量 g 中就存储了一个邻接矩阵存储的无向网，您可以使用 g 进行后续的操作。