至今不明白原理
無(wú)向圖中，如果任意邊數(shù)大于3的環(huán)，至少存在一條邊連接環(huán)中不相鄰的某兩
個(gè)點(diǎn)，則稱此圖為弦圖(Chordal Graph)，所以說(shuō)這里的算法就是
第一步：給節(jié)點(diǎn)編號(hào)
設(shè)已編號(hào)的節(jié)點(diǎn)集合為A，未編號(hào)的節(jié)點(diǎn)集合
1 /*
2 無(wú)向圖中，如果任意邊數(shù)大于3的環(huán)，至少存在一條邊連接環(huán)中不相鄰的某兩
3 個(gè)點(diǎn)，則稱此圖為弦圖(Chordal Graph)
4 */
5 #include <iostream>
6 using namespace std;
7 int n,m;
8 bool map[1001][1001];
9 bool used[1001];
10 int seta[1001];
11 void number()
12 {
13 memset(used,0,sizeof(used));
14 used[1]=1;
15 seta[n]=1;
16 for(int num=n-1;num>=1;--num)
17 {
18 int Max=0;
19 int p=0;
20 for(int i=1;i<=n;++i)
21 if(!used[i])
22 {
23 int sum=1;
24 for(int k=n;k>=num;--k)
25 if(map[i][seta[k]])
26 sum++;
27 if(sum>Max)
28 {
29 Max=sum;
30 p=i;
31 }
32 }
33 seta[num]=p;
34 used[p]=1;
35 }
36 }
37 bool check()
38 {
39 int setc[1001];
40 for(int i=1;i<n;++i)
41 {
42 int x=seta[i];
43 int k=0;
44 for(int j=i+1;j<=n;++j)
45 {
46 int y=seta[j];
47 if(map[x][y])
48 setc[k++]=y;
49 }
50 if(k>1)
51 {
52 for(int j=1;j<k;j++)
53 if(!map[setc[0]][setc[j]])return 0;
54 }
55 }
56 return true;
57 }
58 int main()
59 {
60 int a,b;
61 while(scanf("%d%d",&n,&m)&&n)
62 {
63 memset(map,0,sizeof(map));
64 for(int i=1;i<=m;++i)
65 {
66 scanf("%d%d",&a,&b);
67 map[b][a]=map[a][b]=1;
68 }
69 //編號(hào)
70 number();
71 if(check())printf("Perfect\n\n");
72 else printf("Imperfect\n\n");
73 }
74 return 0;
75 }
為B
開(kāi)始時(shí)A為空，B包含所有節(jié)點(diǎn)。
for num=n-1 downto 0 do
{
在B中找節(jié)點(diǎn)x，使與x相鄰的在A集合中的節(jié)點(diǎn)數(shù)最多，將x編號(hào)為num，
并從B移入A
}
第二步：檢查
for num=0 to n-1 do
{
對(duì)編號(hào)為num的節(jié)點(diǎn)x，設(shè)所有編號(hào)大于num且與x相鄰的節(jié)點(diǎn)集合為C，
在集合C中找出編號(hào)最小的節(jié)點(diǎn)y，如果集合C中存在不等于y的節(jié)點(diǎn)z，
且y與z間沒(méi)有邊，則此圖不是弦圖，退出。
}
檢查完了，則此圖是弦圖。