logo资料库

地图着色贪心算法代码.doc

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.02M 资料格式：doc 举报 版权申诉
第1页 / 共5页
第2页 / 共5页
第3页 / 共5页
第4页 / 共5页
第5页 / 共5页
资料共5页，全文预览结束
    #include #include #include #define Max 50 using namespace std; //图的类 class Graph { public: //顶点信息 int n;//顶点 int e;//边 string vex[Max]; int Edge[Max][Max];//顶点与顶点之间的联系 Graph(int n0,int e0){n=n0;e=e0;}//构造函数 void Input(); int IsEdge(int v1,int v2);//判断 v1,v2 之间是否有边 int check(string a); //图的输入 }; class color_greedy; class subset { public: //子集类 friend class color_greedy; //char-greedy 是其友元类 int *newclr;//指向子集所包含的各个结点序号 int n; int color;//该子集所赋给的颜色值 //子集中结点个数 subset(int newcolor=0,int m=Max);//构造函数 ~subset(){delete newclr;}//析构函数 }; class color_greedy { public: //图的结点个数 Graph g;//要着色的图 subset *u;//子集集合 int *x; //各结点的着色值向量 int n ; int m ; //可选的 m 种颜色 color_greedy(int n0,int m0,int e0);//构造函数 ~color_greedy(){delete x; delete []u;}//析构函数 void greedy(subset &y );//贪心法找子集 y 中包含的结点 void Coloring ();//产生图的着色方案
    }; /*************************Graph.cpp*****************/ int Graph::check(string a) { for(int i=0;i>vex[i]; cout<<"这些省份分别是:"<
    for(i=0;i>a; fin>>b; p=check(a); q=check(b); Edge[p][q]=Edge[q][p]=1;//矩阵存储 cout<0) return 1; else return 0; } /*******************************subset.cpp***********************/ subset::subset(int newcolor,int m) { n=m; if(n>0) newclr=new int[n]; else newclr=0; color=newcolor; } /*****************************color_greedy.cpp********************/ color_greedy::color_greedy(int n0,int m0,int e0):g(n0,e0) { n=n0; m=m0; x=new int[n];//创建 x 向量 for(int i=0;i
    void color_greedy::greedy(subset &y) { int v,p=0,q=1,w; for(int i=0;i=0) { w=y.newclr[p];//取子集中一个结点 w if(g.IsEdge(v,w))break;//若 v 和 w 邻接，则 v 不能赋给该新颜色值 else p--;//继续判断 v 是否与子集中的下一个结点邻接 } if(p<0)//v 不与子集中任意结点邻接，则将结点 v 加入子集 { y.newclr[q]=v; q++; x[v]=y.color; } } } y.n=q;//子集的大小为 q } void color_greedy::Coloring()//产生图的着色方案，并得到所有的着色子集集合 u { int r; for(int k=1;k<=m;k++)//最多使用 m 种颜色 { u[k-1].color=k;//赋给子集一个新的颜色值 greedy(u[k-1]);//使用贪心法找子集 u[k-1] for(int j=0;j
    break; if(j>=n)break;//所有结点都分配了颜色，退出循环 } system("pause"); system("cls"); cout<
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料