問題介紹
地圖著色問題是一個抽象的圖形學問題，用程式實作對各個區域進行著色，并且相鄰區域所用的顏色不同，同時保證顏色的總數最少，那么就是如何將這些抽象的問題進行資料化，如何將程式所需要的功能模擬著色在計算機中編程實作，
問題解決
先將每個城市與城市分界線進行數字化，將每個城市的地圖顏色設為初始值0即為白色，在回圈中判斷目前城市的顏色和與當前城市有分界線的城市是否存在顏色相同，如果存在就將數字加一（改變顏色），
流程圖
初始化模塊
typedef structArcNode
{
int x; // 表示與當前頂點所表示城市相鄰的省份的位置資訊
struct ArcNode *next; // 指向下一個弧結點
}ArcNode; // 表示城市之間相鄰關系的弧結點
typedef struct
{
char *name; // 頂點所表示的城市的名稱
int color; // 城市的顏色，用數字表示不同的顏色
ArcNode *firstnext; // 指向第一個弧
}City[13];
著色模塊
for(i=1;i<=13;i++)
{
city[i].color=0;
}
for(i=1;i<=13;i++)
{
j=1;
p=city[i].firstnext;
while(p!=NULL)
{
while(p!=NULL&&j!=city[p->x].color)
{
p=p->next;
}
if(p!=NULL)
j++;
}
city[i].color=j;
}
輸出模塊
for(i=1;i<=13;i++)
{
printf("%s:",city[i].name);
printf("%d\n",city[i].color);
}
詳細代碼
#include <stdio.h>
#include <stdlib.h>
typedef struct ArcNode{
int x; // 表示與當前頂點所表示城市相鄰的省份的位置資訊
struct ArcNode *next;
}ArcNode; // 表示城市之間相鄰關系的弧結點
typedef struct{
char *name; // 頂點所表示的城市的名稱
int color;
ArcNode *firstnext; // 指向第一個弧
}City[13];
int main()
{
City city;
int i,j;
ArcNode
*p,*hu1,*hu2,*hu3,*hu4,*hu5,*hu6,*hu7,*hu8,*hu9,*hu10,*hu11,*hu12,*hu13,*hu14,*hu15,*hu16,*hu17,*hu18;
ArcNode *hu19,*hu20,*hu21,*hu22,*hu23,*hu24,*hu25,*hu26,*hu27,*hu28,*hu29,*hu30,*hu31,*hu32,*hu33,*hu34,*hu35;
ArcNode *hu36,*hu37,*hu38,*hu39,*hu40,*hu41,*hu42,*hu43,*hu44,*hu45,*hu46,*hu47,*hu48,*hu49,*hu50,*hu51,*hu52;
ArcNode *hu53,*hu54,*hu55,*hu56,*hu57,*hu58,*hu59,*hu60,*hu61,*hu62;//宣告表示城市頂點的資訊
hu1=(ArcNode *)malloc(sizeof(ArcNode));
hu2=(ArcNode *)malloc(sizeof(ArcNode));
hu3=(ArcNode *)malloc(sizeof(ArcNode));
hu4=(ArcNode *)malloc(sizeof(ArcNode));
hu5=(ArcNode *)malloc(sizeof(ArcNode));
hu6=(ArcNode *)malloc(sizeof(ArcNode));
hu7=(ArcNode *)malloc(sizeof(ArcNode));
hu8=(ArcNode *)malloc(sizeof(ArcNode));
hu9=(ArcNode *)malloc(sizeof(ArcNode));
hu10=(ArcNode *)malloc(sizeof(ArcNode));
hu11=(ArcNode *)malloc(sizeof(ArcNode));
hu12=(ArcNode *)malloc(sizeof(ArcNode));
hu13=(ArcNode *)malloc(sizeof(ArcNode));
hu14=(ArcNode *)malloc(sizeof(ArcNode));
hu15=(ArcNode *)malloc(sizeof(ArcNode));
hu16=(ArcNode *)malloc(sizeof(ArcNode));
hu17=(ArcNode *)malloc(sizeof(ArcNode));
hu18=(ArcNode *)malloc(sizeof(ArcNode));
hu19=(ArcNode *)malloc(sizeof(ArcNode));
hu20=(ArcNode *)malloc(sizeof(ArcNode));
hu21=(ArcNode *)malloc(sizeof(ArcNode));
hu22=(ArcNode *)malloc(sizeof(ArcNode));
hu23=(ArcNode *)malloc(sizeof(ArcNode));
hu24=(ArcNode *)malloc(sizeof(ArcNode));
hu25=(ArcNode *)malloc(sizeof(ArcNode));
hu26=(ArcNode *)malloc(sizeof(ArcNode));
hu27=(ArcNode *)malloc(sizeof(ArcNode));
hu28=(ArcNode *)malloc(sizeof(ArcNode));
hu29=(ArcNode *)malloc(sizeof(ArcNode));
hu30=(ArcNode *)malloc(sizeof(ArcNode));
hu31=(ArcNode *)malloc(sizeof(ArcNode));
hu32=(ArcNode *)malloc(sizeof(ArcNode));
hu33=(ArcNode *)malloc(sizeof(ArcNode));
hu34=(ArcNode *)malloc(sizeof(ArcNode));
hu35=(ArcNode *)malloc(sizeof(ArcNode));
hu36=(ArcNode *)malloc(sizeof(ArcNode));
hu37=(ArcNode *)malloc(sizeof(ArcNode));
hu38=(ArcNode *)malloc(sizeof(ArcNode));
hu39=(ArcNode *)malloc(sizeof(ArcNode));
hu40=(ArcNode *)malloc(sizeof(ArcNode));
hu41=(ArcNode *)malloc(sizeof(ArcNode));
hu42=(ArcNode *)malloc(sizeof(ArcNode));
hu43=(ArcNode *)malloc(sizeof(ArcNode));
hu44=(ArcNode *)malloc(sizeof(ArcNode));
hu45=(ArcNode *)malloc(sizeof(ArcNode));
hu46=(ArcNode *)malloc(sizeof(ArcNode));
hu47=(ArcNode *)malloc(sizeof(ArcNode));
hu48=(ArcNode *)malloc(sizeof(ArcNode));
hu49=(ArcNode *)malloc(sizeof(ArcNode));
hu50=(ArcNode *)malloc(sizeof(ArcNode));
hu51=(ArcNode *)malloc(sizeof(ArcNode));
hu52=(ArcNode *)malloc(sizeof(ArcNode));
hu53=(ArcNode *)malloc(sizeof(ArcNode));
hu54=(ArcNode *)malloc(sizeof(ArcNode));
hu55=(ArcNode *)malloc(sizeof(ArcNode));
hu56=(ArcNode *)malloc(sizeof(ArcNode));
hu57=(ArcNode *)malloc(sizeof(ArcNode));
hu58=(ArcNode *)malloc(sizeof(ArcNode));
hu59=(ArcNode *)malloc(sizeof(ArcNode));
hu60=(ArcNode *)malloc(sizeof(ArcNode));
hu61=(ArcNode *)malloc(sizeof(ArcNode));
hu62=(ArcNode *)malloc(sizeof(ArcNode));
city[1].name="蘇州市";
hu1->x=2;
hu2->x=8;
hu3->x=7;
city[1].firstnext=hu1;//聲名表示城市之間相鄰的弧
hu1->next=hu2;
hu2->next=hu3;
hu3->next=NULL;
city[2].name="無錫市";
hu4->x=3;
hu5->x=7;
hu6->x=1;
city[2].firstnext=hu4;
hu4->next=hu5;
hu5->next=hu6;
hu6->next=NULL;
city[3].name="常州市";
hu7->x=4;
hu8->x=5;
hu9->x=2;
hu10->x=7;
city[3].firstnext=hu7;
hu7->next=hu8;
hu8->next=hu9;
hu9->next=hu10;
hu10->next=NULL;
city[4].name="鎮江市";
hu12->x=6;
hu13->x=7;
hu14->x=3;
hu11->x=5;
city[4].firstnext=hu12;
hu12->next=hu13;
hu13->next=hu14;
hu14->next=hu11;
hu11->next=NULL;
city[5].name="南京市";
hu15->x=6;
hu16->x=10;
hu18->x=3;
hu17->x=4;
city[5].firstnext=hu15;
hu15->next=hu16;
hu16->next=hu18;
hu18->next=hu17;
hu17->next=NULL;
city[6].name="揚州市";
hu19->x=7;
hu20->x=9;
hu21->x=10;
hu22->x=5;
hu23->x=4;
city[6].firstnext=hu19;
hu19->next=hu20;
hu20->next=hu21;
hu21->next=hu22;
hu22->next=hu23;
hu23->next=NULL;
city[7].name="泰州市";
hu24->x=8;
hu26->x=1;
hu27->x=2;
hu28->x=3;
hu29->x=4;
hu30->x=6;
hu60->x=9;
city[7].firstnext=hu24;
hu24->next=hu26;
hu26->next=hu27;
hu27->next=hu28;
hu28->next=hu29;
hu29->next=hu30;
hu30->next=hu60;
hu60->next=NULL;
city[8].name="南通市";
hu32->x=1;
hu33->x=7;
hu57->x=9;
city[8].firstnext=hu32;
hu32->next=hu33;
hu33->next=hu57;
hu57->next=NULL;
city[9].name="鹽城市";
hu35->x=11;
hu38->x=6;
hu55->x=10;
hu58->x=8;
hu61->x=7;
city[9].firstnext=hu35;
hu35->next=hu38;
hu38->next=hu55;
hu55->next=hu58;
hu58->next=hu61;
hu61->next=NULL;
city[10].name="淮安市";
hu39->x=11;
hu40->x=12;
hu42->x=6;
hu43->x=5;
hu56->x=9;
city[10].firstnext=hu39;
hu39->next=hu40;
hu40->next=hu42;
hu42->next=hu43;
hu43->next=hu56;
hu56->next=NULL;
city[11].name="連云港市";
hu44->x=12;
hu45->x=13;
hu46->x=10;
hu47->x=9;
city[11].firstnext=hu44;
hu44->next=hu45;
hu45->next=hu46;
hu46->next=hu47;
hu47->next=NULL;
city[12].name="宿遷市";
hu48->x=13;
hu49->x=11;
hu50->x=10;
city[12].firstnext=hu48;
hu48->next=hu49;
hu49->next=hu50;
hu50->next=NULL;
city[13].name="徐州市";
hu51->x=11;
hu52->x=12;
city[13].firstnext=hu51;
hu51->next=hu52;
hu52->next=NULL;
for(i=1;i<=13;i++)
{
city[i].color=0;
}
for(i=1;i<=13;i++)
{
j=1;
p=city[i].firstnext;
while(p!=NULL)
{
while(p!=NULL&&j!=city[p->x].color)
{
p=p->next;
}
if(p!=NULL)
j++;
}
city[i].color=j;
}//分別為各城市著色
for(i=1;i<=13;i++)
{
printf("%s:",city[i].name);
printf("%d\n",city[i].color);
}//輸出各城市顏色資訊
printf("/n 0表示白色,1表示藍色,2表示紅色,3表示綠色,4表示黃色");
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/237642.html
標籤：其他
上一篇：2021計算機視覺-包攬所有前沿論文原始碼 -上半年
下一篇：數字邏輯期末知識點總結