回溯法求问题的一个解时，只要搜索到问题的一个解就可结束。这种以深度优先方式系统搜索问题解的算法称为回溯法，它适用于求解组合数较大的问题。

C/C++:

图的m着色问题：

#include <iostream>

#define Max 15
using namespace std;
int vertexCount=0;
int color[Max]={0};
int arc[Max][Max]={0};
int visited[Max]={0};
void init()
{
cout<<"请输入定点数目：\n";
cin>>vertexCount;
int t;
cout<<"请输入边的数目：\n";
cin>>t;
for(int i=0;i!=t;++i)
{
cout<<"请输入第"<<i+1<<"条边：\n";
int a,b;
cin>>a>>b;
arc[a-1][b-1]=1;
arc[b-1][a-1]=1;
}
}
void DFSTraverse(int s)
{
if(visited[s]) return;
int t=1;
bool flag;
do{
flag=false;
for(int i=0;i!=vertexCount;++i)
{
if(arc[s][i]&&color[i]==t)
{
flag=true;
t++;
break;
}
}
}while(flag);
color[s]=t;
visited[s]=1;
for(int i=0;i!=vertexCount;++i)
{
if(arc[s][i]&&visited[i]==0)
DFSTraverse(i);
}
}
void show()
{
for(int i=0;i!=vertexCount;++i)
cout<<"顶点"<<i+1<<" 颜色"<<color[i]<<endl;
}
int main()
{
init();
for(int i=0;i!=vertexCount;++i)
DFSTraverse(i);
show();

}

Java：

图的m着色问题：


import java.util.Scanner;

public class Coloring {
    static int n, m;            // 图的顶点数，可用颜色数
    static boolean[][] a;       // 图的邻接矩阵
    static int[] x;             // 当前解
    static long sum;            // 当前已找到的可m着色方案数

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        System.out.println("输入图的顶点数，可用颜色数");
        n = s.nextInt();
        m = s.nextInt();
        x = new int[n + 1];
        a = new boolean[n + 1][n + 1];

        int xx, yy;

        while (true) {
            System.out.println("请输入相邻点对 x y");
            xx = s.nextInt();
            if (xx == -1)
                break;
            yy = s.nextInt();
            a[xx][yy] = true;
            a[yy][xx] = true;
        }

        System.out.println("可用方案数为：" + mColoring(m));

        s.close();
    }

    static long mColoring(int mm) {
        m = mm;
        sum = 0;
        backtrack(1);
        return sum;
    }

    private static void backtrack(int t) {
        if (t > n) { // 到达叶节点，表示该方案可行
            sum++;  // 可行解数量加1，并输出可行解
            System.out.print("方案" + sum + ":  ");
            for (int i = 1; i <= n; i++) {
                System.out.print(x[i] + "\t");
            }
            System.out.println();
        } else {
            for (int i = 1; i <= m; i++) {  //m叉树
                x[t] = i;
                if (ok(t))              // 继续遍历叶结点
                    backtrack(t + 1);
                x[t] = 0;
            }
        }
    }

    private static boolean ok(int k) {
        for (int j = 1; j <= n; j++) {
            if (a[k][j] && (x[j] == x[k])) //  a[k][j]：相邻接， x[j] == x[k] 同色
                return false;
        }
        return true;
    }
}

?旅行销售员问题：

import java.util.Arrays;
import java.util.Scanner;

/**
 *
 * @author 刘宁宁
 */

public class BBTSP {
static int n;       // 图G顶点数
    static int[] x;     // 当前解
    static int[] bestx; // 当前最优解
    static float bestc = Float.MAX_VALUE; // 当前最优值
    static float cc;    // 当前费用
    static float[][] a; // 图G的邻接矩阵

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        System.out.println("请输入顶点数");
        n = s.nextInt();

        init(n);
        input(s);
        print();
        s.close();
    }

    private static void input(Scanner s) {
        System.out.println("请输入相邻的两个点的编号和距离（输入-1结束）：");
        int xx, yy;
        while (true) {
            xx = s.nextInt();
            if (xx == -1)
                break;
            yy = s.nextInt();
            a[yy][xx] = a[xx][yy] = s.nextFloat();
        }
    }

    private static void print() {
        System.out.println("最短距离为：" + tsp(bestx));
        System.out.print("路径为：");
        for (int i = 1; i < x.length; i++) {
            System.out.print(bestx[i] + "\t");
        }

        System.out.println(1);
    }

    private static void init(int n) {
        x = new int[n + 1];
        bestx = new int[n + 1];
        a = new float[n + 1][n + 1];

        for (int i = 0; i < a.length; i++) {
            Arrays.fill(a[i], Float.MAX_VALUE);
        }
    }

    public static float tsp(int[] v) {
        // 置x为单位排列
        x = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            x[i] = i;
        }
        bestx = v;
        cc = 0;
        // 搜索x[2:n]的全排列
        backtrack(2); // 直接从第二个城市开始
        return bestc;
    }

    private static void backtrack(int i) { //这里的i代表第i步去的城市而不是代号为i的城市
        if (i == n) {
            // a[x[n - 1]][x[n]] < Float.MAX_VALUE 最后一个点和倒数第二个点是否有连通
            if (a[x[n - 1]][x[n]] < Float.MAX_VALUE && a[x[n]][1] < Float.MAX_VALUE &&
                    (bestc == Float.MAX_VALUE || cc + a[x[n - 1]][x[n]] + a[x[n]][1] < bestc)) {
                for (int j = 1; j <= n; j++) {
                    bestx[j] = x[j];
                }
                bestc = cc + a[x[n - 1]][x[n]] + a[x[n]][1];
            }
        } else {
            for (int j = i; j <= n; j++) {
                // 是否可进入x[i]子树
                if (a[x[i - 1]][x[j]] < Float.MAX_VALUE &&
                        (bestc == Float.MAX_VALUE || cc + a[x[i - 1]][x[j]] < bestc)) {// 搜索子树
                    swap(x, i, j);
                    cc += a[x[i - 1]][x[i]];
                    backtrack(i + 1);
                    cc -= a[x[i - 1]][x[i]];
                    swap(x, i, j);
                }
            }
        }
    }

    private static void swap(int[] x, int i, int j) {
        int temp = x[i];
        x[i] = x[j];
        x[j] = temp;
    } 
}