題目：Bandwidth

題意：給出一個n（n≤8）個結點的圖G和一個結點的排列，定義結點i的帶寬b(i)為i和相鄰結點在排列中的最遠距離，而所有b(i)的最大值就是整個圖的帶寬。 給定圖G，求出讓帶寬最小的結點排列。

思路：

（1）處理輸入：將給出的字符串用二維數組表示成圖

（2）標準的回溯dfs，將給出的結點進行全排列，篩選最小帶寬。

（3）剪枝：在進行排列時，當前的結點如果與之前的結點的距離大于當前的最優值，則無需再遞歸排列，因為此序列已經不可能為最優解了。剪掉。

參考：入門經典-例題7-6-P197

代碼：

#include <iostream>#include <stdio.h>#include <string.h>using namespace std;char str[100];int g[30][30],visit[30],ans,number;int PRt[10];void dfs(int steps, int seq[]){    if(steps == number){//滿足個數        int maxv = 0;        for(int i=0;i<number;i++)//進行尋找本次排列的帶寬            for(int j=i+1;j<number;j++)                if(g[seq[i]][seq[j]]) maxv = max(maxv,j-i);        if(ans > maxv){//保留最大值            ans = maxv;            for(int i=0;i<number;i++) prt[i] = seq[i];//保存序列        }        return;    }    for(int i=0;i<26;i++){        if(visit[i]){            int ok = 1;            for(int j=0;j<steps;j++)//判斷當前結點與之前的結點距離，如果大于當前最優值，就無需再遞歸排列了，剪枝                if(g[i][seq[j]])//存在邊                    if(steps-j > ans){ok = 0;break;}//如果大于最優解即跳出            if(ok){                seq[steps] = i;                visit[i] = 0;                dfs(steps+1,seq);                visit[i] = 1;            }        }    }return ;}int main(){    while(scanf("%s",str)!=EOF && str[0] != '#'){        int i=0;        memset(g,0,sizeof(g));        memset(visit,0,sizeof(visit));        while(str[i]!='/0'){//處理輸入，用二維數組g表示出來圖            if(str[i] == ':'){                int s = str[i-1] - 'A';                visit[s] = 1;                i++;                while(str[i] != ';' && str[i] != '/0'){                    g[s][str[i] - 'A'] = 1;                    g[str[i] - 'A'][s] = 1;                    visit[str[i] - 'A'] = 1;                    i++;                }            }            else i++;        }        number = 0;        for(int i=0;i<26;i++) if(visit[i]) number++;//計算結點個數        ans = 99999999;        int temp[10];        dfs(0,temp);        for(int i=0;i<number;i++) printf("%c ",prt[i]+'A');        printf("-> %d/n",ans);    }return 0;}