C/C++の宿題を片付けます 99代目

163 名前：デフォルトの名無しさん mailto:sage [2007/11/09(金) 21:33:34 ] [1] データ構造 [2] 問題文(含コード&リンク)： n個の頂点からなるグラフを、辺の両端の頂点に同じ色を塗らないようにし、すべての頂点を彩色するのに必要な色数を最小化する。 また、頂点iに接続する辺の数を頂点iの次数とよぶ。以下のアルゴリズムで作るように。 （１） �@頂点の次数を降順にソートする。 �A頂点1に色１を割り当てる �B頂点i=２、．．．nについて、隣接する頂点に割り当てられていない最小の色番号を頂点iに割り当てる。 （２）頂点iの隣接頂点に彩色された異なる色数を頂点iの飽和次数とする。 �@最大次数の頂点に色1を割り当てる �A飽和次数が最大の頂点を選ぶ。そのような頂点が複数ある場合は、 未彩色の部分グラフにおいて最大次数の頂点を選ぶ。 �B選んだ頂点に彩色可能な最小の色番号を割り当てる �C全頂点が彩色済みならば終了。そうでないなら�Aにもどる。 [3] 環境 　[3.1] OS： Linux　[3.2] コンパイラ名とバージョン： gcc　[3.3] 言語： C [4] 期限： 2007年11月10日24:00まで（出来れば21:00 [5] その他の制限： 関数と変数の定義 #include <stdio.h> #define TRUE 1 #define FALSE 0 #define MAX_N 2000 /*変数*/ int n; /*頂点数*/　　int m; /*辺数*/ double x[MAX_N],y[MAX_N]; /*各頂点の座標*/ int a[MAX_N][MAX_N]; /*隣接行列*/ int color[MAX_N]; /*色*/ int max_color; /*最大の色番号*/

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef