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;
}

#include<iostream> #include<queue> using namespace std; #define MAXNUM 100 char visited1[MAXNUM]; typedef struct{ char vexs[MAXNUM]; //顶点 int arcs[MAXNUM][MAXNUM];//边 int vexnum,arcnum; } AMGraph; int LocateVex(AMGraph G,char v){ for(int i = 0; i < G.vexnum; i++){ if(G.vexs[i] == v)return i; } return -1; } int CreateUNG(AMGraph &G){ char v1,v2; cout<<"请输入顶点数和边数："; cin>>G.vexnum>>G.arcnum; cout<<"请依次输入顶点："; for(int i = 0; i < G.vexnum; i++)cin>>G.vexs[i]; for(int j = 0; j < G.vexnum; j++) for(int i = 0; i < G.vexnum; i++) G.arcs[j][i] = 0; //初始化邻接矩阵 cout<<"请依次输入邻边："<<endl; for(int k = 0; k < G.arcnum; k++){ cin>>v1>>v2; int i = LocateVex(G,v1); int j = LocateVex(G,v2); G.arcs[i][j] = 1; G.arcs[j][i] = 1; } return 1; } void DFT_AM(AMGraph G,int i){ //深度优先遍历邻接矩阵 cout<<G.vexs[i]; visited1[i] = 1; for(int j = 0; j < G.vexnum; j++){ if(G.arcs[i][j] == 1 && !visited1[j])DFT_AM(G,j); } } void BFT_AM(AMGraph G, int i) { //广度优先遍历邻接矩阵 queue<int> Q; //定义队列Q Q.push(i); //将起始顶点入队 visited1[i] = 1; //标记为已访问 while (!Q.empty()) { //重复步骤2-3，直到队列为空 int cur = Q.front(); //取出队首元素 Q.pop(); //出队 cout << G.vexs[cur]; //访问该顶点 for (int j = 0; j < G.vexnum; j++) { if (G.arcs[cur][j] == 1 && !visited1[j]) { //遍历该顶点的邻接点，将未访问的邻接点入队 Q.push(j); visited1[j] = 1; //标记为已访问 } } } } int main(){ AMGraph G; CreateUNG(G); for(int j = 0; j < G.vexnum; j++){ //输出邻接矩阵 for(int i = 0; i < G.vexnum; i++) cout<<G.arcs[j][i]<<" "; cout<<endl; } cout<<endl<<"输出深度优先序列："; DFT_AM(G,0); cout << endl << "输出广度优先序列："; for (int i = 0; i < MAXNUM; i++) visited1[i] = 0; //重置visited1数组 BFT_AM(G, 0); } 请改良此代码

以下是对代码的改良建议：

1. 在定义结构体时，使用结构体名称作为前缀，提高可读性。

2. 使用枚举类型来定义遍历方法，提高可读性。

3. 将遍历方法的参数从顶点序号改为顶点名称，提高可读性。

4. 在遍历时，将访问过的顶点入栈或入队，不必使用全局变量visited1。

5. 将创建图的函数返回值改为bool类型，表示创建是否成功。

6. 在输入邻边时，应该检查输入的两个顶点是否合法，避免数组越界。

下面是改良后的代码：

#include<iostream>
#include<stack>
#include<queue>

using namespace std;

#define MAXNUM 100

typedef struct AMGraph{
    char vexs[MAXNUM]; //顶点
    int arcs[MAXNUM][MAXNUM];//边
    int vexnum,arcnum;
} AMGraph;

enum TraverseMethod{
    DEPTH_FIRST_TRAVERSE,
    BREADTH_FIRST_TRAVERSE
};

int LocateVex(AMGraph G, char v){
    for(int i = 0; i < G.vexnum; i++){
        if(G.vexs[i] == v) return i;
    }
    return -1;
}

bool CreateUNG(AMGraph &G){
    char v1,v2;
    cout<<"请输入顶点数和边数：";
    cin>>G.vexnum>>G.arcnum;
    if(G.vexnum <= 0 || G.arcnum <= 0) return false;
    cout<<"请依次输入顶点：";
    for(int i = 0; i < G.vexnum; i++) cin>>G.vexs[i];
    for(int j = 0; j < G.vexnum; j++){
        for(int i = 0; i < G.vexnum; i++) G.arcs[j][i] = 0; //初始化邻接矩阵
    }
    cout<<"请依次输入邻边："<<endl;
    for(int k = 0; k < G.arcnum; k++){
        cin>>v1>>v2;
        int i = LocateVex(G,v1);
        int j = LocateVex(G,v2);
        if(i == -1 || j == -1){
            cout << "输入的边不合法，请重新输入！" << endl;
            k--;
            continue;
        }
        G.arcs[i][j] = 1;
        G.arcs[j][i] = 1;
    }
    return true;
}

void Traverse_AM(AMGraph G, char v, TraverseMethod method){
    bool visited[MAXNUM] = {false};
    stack<int> S;
    queue<int> Q;

    int i = LocateVex(G, v);
    if(i == -1) return;

    if(method == DEPTH_FIRST_TRAVERSE){ //深度优先遍历邻接矩阵
        S.push(i);
        visited[i] = true;
        while(!S.empty()){
            int cur = S.top();
            S.pop();
            cout << G.vexs[cur];
            for(int j = G.vexnum - 1; j >= 0; j--){
                if(G.arcs[cur][j] == 1 && !visited[j]){
                    S.push(j);
                    visited[j] = true;
                }
            }
        }
    }
    else if(method == BREADTH_FIRST_TRAVERSE){ //广度优先遍历邻接矩阵
        Q.push(i);
        visited[i] = true;
        while(!Q.empty()){
            int cur = Q.front();
            Q.pop();
            cout << G.vexs[cur];
            for(int j = 0; j < G.vexnum; j++){
                if(G.arcs[cur][j] == 1 && !visited[j]){
                    Q.push(j);
                    visited[j] = true;
                }
            }
        }
    }
}

int main(){
    AMGraph G;
    if(CreateUNG(G)){
        for(int j = 0; j < G.vexnum; j++){ //输出邻接矩阵
            for(int i = 0; i < G.vexnum; i++) cout<<G.arcs[j][i]<<" ";
            cout<<endl;
        }

        cout<<endl<<"输出深度优先序列：";
        Traverse_AM(G, G.vexs[0], DEPTH_FIRST_TRAVERSE);

        cout << endl << "输出广度优先序列：";
        Traverse_AM(G, G.vexs[0], BREADTH_FIRST_TRAVERSE);
    }

    return 0;
}