壹、 ? 設計任務考慮壹個多叉路口，如作圖所示，在這個路口中，***有五條道路相交，其中C和E是單行線，其他為雙行線。提出的任務是：為這個路口設計壹個安全有效的交通燈管理系統。
、
二、 ? 問題分析
首先需要分析壹下所有車輛的行駛路線的沖突問題。這個問題可以歸結為對車輛的可能行駛方向作某種分組，對分組的要求是使任壹個組中各個方向行駛的車輛可以同時安全行駛而不發生碰撞。根據這個路口的實際情況可以確定13個可能通行方向：A→B，A→C，A→D，?B→A，B→C，B→D，?D→A，D→B，D→C，?E→A，E→B，E→C，?E→D。
為了敘述方便，我們下面把A→B簡寫成AB，並且用壹個小橢圓把它框起來，在不能同時行駛的路線間畫壹條連線(表示它們互相沖突)，便可以得到圖所示的圖式。
這樣做就把要解決的問題借助圖的模型變成了另壹個抽象問題：要求將圖1.2中的結點分組，使有線相連(互相沖突)的結點不在同壹個組裏。如果把上圖中的壹個結點理解為壹個國家，結點之間的連線看作兩國有***同邊界，上述問題就變成著名的“著色問題”：即求出要幾種顏色可將圖中所有國家著色，使得任意兩個相鄰的國家顏色都不相同。通過上面的分析，我們就獲得了該交通管系統的數學模型，這樣就可以用轉變為計算機可以解決的問題了。
三、 ? 算法和數據結構的設計
圖的結構體包含成員：頂點、邊、頂點個數
頂點也是壹個結構體，包含成員：名字、所塗顏色
typedef?struct?//頂點結構
{
char?name[30];?//名字
int?color;//所塗顏色
}VexType;
typedef?struct//圖的結構
{
VexType?dingdian[MAX];?//頂點信息
AdjType?bian[MAX][MAX];//邊信息
int?n;//圖的頂點個數
}GraphMatrix;
四、 ? 程序的實現
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define?MAX?100
typedef?struct?//頂點結構
{
char?name[30];?//名字
int?color;//所塗顏色
}VexType;
typedef?int?AdjType;
typedef?struct
{
VexType?dingdian[MAX];?//頂點信息
AdjType?bian[MAX][MAX];//邊信息
int?n;//圖的頂點個數
}GraphMatrix;
int?empty(GraphMatrix?*?pG)//判斷集合V1是否為空
{
int?i;
for(i=0;i<pG->n;i++)
? if(pG->dingdian[i].color==0)
?return?0;
return?1;
}
int?buxianglin(GraphMatrix?*?pG,int?index,int?color)//判斷第index個頂點是否與集合NEW中每個頂點不相鄰
{
int?i;
for(i=0;i<pG->n;i++)
{
? if(pG->dingdian[i].color!=color)//第i個頂點不在NEW中
?continue;
? if(pG->bian[index][i]==1)//第index個頂點與第i個頂點（在集合NEW中)相鄰
?return?0;
}
return?1;//執行至此，說明第index個頂點與集合NEW中每個頂點都不相鄰
}
int?colorup(GraphMatrix?*?pG)//用貪心法給圖*pG染色，並返回顏色數目
//邏輯上認為有壹個集合V1,圖*pG的任壹頂點v屬於V1當且僅當v.color等於0
//邏輯上認為有壹個集合NEW，圖*pG的任壹頂點v屬於NEW當且僅當v.color等於當前color
{
int?color=0,i;
while(!empty(pG))//當集合V1不空時
{
? color++;
? for(i=0;i<pG->n;i++)
? {
?if(pG->dingdian[i].color!=0)//第i個頂點不屬於V1
continue;
?if(buxianglin(pG,i,color))//第i個頂點與集合NEW中每個頂點不相鄰
pG->dingdian[i].color=color;//將第i個頂點加入NEW中
? }
}
return?color;
}
void?Output(GraphMatrix?*?pG)
{
int?i,j;
printf("Result\ncertex?color\n");
for(i=0;i<pG->n;i++)
{
? printf("%6s,%5d",pG->dingdian[i].name,pG->dingdian[i].color);
? putchar('\n');
}
printf("The?relation?of?all?the?borders");
putchar('\n');
for(i=0;i<pG->n;i++)
{
? for(j=0;j<pG->n;j++)
?printf("%2d",pG->bian[i][j]);
? putchar('\n');
}
}
GraphMatrix?*createaGraph()
{
int?i,j;
GraphMatrix?*?pG=(GraphMatrix?*)malloc(sizeof(GraphMatrix));
pG->n=13;
strcpy(pG->dingdian[0].name,"AB");
strcpy(pG->dingdian[1].name,"AC");
strcpy(pG->dingdian[2].name,"AD");
strcpy(pG->dingdian[3].name,"BA");
strcpy(pG->dingdian[4].name,"BC");
strcpy(pG->dingdian[5].name,"BD");
strcpy(pG->dingdian[6].name,"DA");
strcpy(pG->dingdian[7].name,"DB");
strcpy(pG->dingdian[8].name,"DC");
strcpy(pG->dingdian[9].name,"EA");
strcpy(pG->dingdian[10].name,"EB");
strcpy(pG->dingdian[11].name,"EC");
strcpy(pG->dingdian[12].name,"ED");
for(i=0;i<pG->n;i++)
{
? pG->dingdian[i].color=0;
? for(j=0;j<pG->n;j++)
?pG->bian[i][j]=0;
}
pG->bian[0][4]=pG->bian[0][5]=pG->bian[0][6]=pG->bian[0][9]=pG->bian[1][5]=pG->bian[1][6]=pG->bian[1][7]=pG->bian[1][9]=pG->bian[1][10]=pG->bian[2][9]=pG->bian[2][10]=pG->bian[2][11]=pG->bian[4][0]=pG->bian[4][7]=pG->bian[4][10]=pG->bian[5][0]=pG->bian[5][1]=pG->bian[5][6]=pG->bian[5][10]=pG->bian[5][11]=pG->bian[6][0]=pG->bian[6][1]=pG->bian[6][5]=pG->bian[6][10]=pG->bian[6][11]=pG->bian[7][1]=pG->bian[7][4]=pG->bian[7][11]=pG->bian[9][0]=pG->bian[9][1]=pG->bian[9][2]=pG->bian[10][1]=pG->bian[10][2]=pG->bian[10][4]=pG->bian[10][5]=pG->bian[10][6]=pG->bian[11][2]=pG->bian[11][5]=pG->bian[11][6]=pG->bian[11][7]=1;
return?pG;
}
void?main()
{
GraphMatrix?*?pG=createaGraph();
int?color=colorup(pG);
printf("Used?%d?color.\n",color);
Output(pG);
free(pG);
}
五、 ? 程序的調試與計算的結果分析
、