[春节整活]
QQ的一笔画红包有几个特性：
1.最大为5×5的点阵，所以可以把每个点从左到右，从上到下标为1-25号点
2.每两个点只能存在一条线
3.线可以被盖住（例如连接2-1-3，2-1的线会被后来的1-3的连接线盖住），对肉眼观察很不利，但是对代码来说没有影响
解题思路：
1.对于线较多的点阵，可以使用邻接矩阵来画无向无权图（线较少可以使用邻接表），由于最大只有25个点，不必要考虑内存开销，所以直接使用邻接矩阵了
2.若某个节点所连接的线数为奇数，即为起点/终点，为偶数即为经过的点。若所有节点所连接的线数都为偶数，即首尾相连，任意点都可为起点/终点
3.使用回溯算法，找出将全部线只走一遍的方案，即为点阵的解
邻接矩阵代码如下：
/** * 邻接矩阵 */public class DenseGraph { // 节点数 private int n; // 边数 private int m; // 是否为有向图 private boolean directed; // 图的具体数据 private boolean[][] g; //记录节点的线数量 private int[] line; //已连接数量 private int connected; //换行专用 private int lineFeed; // 构造函数 public DenseGraph(){ n = 26; m = 0; directed = false; // g初始化为n*n的布尔矩阵, 每一个g[i][j]均为false, 表示没有任和线 g = new boolean[n][n]; line=new int[n]; } //初始化点阵 private void initialization(){ //临时变量，保存每个节点连接节点的数量，以判断起点 int count=0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (g[i][j]) { count++; } } line[i]=count; count=0; } } // 返回节点个数 public int V(){ return n;} // 返回边的个数 public int E(){ return m;} // 向图中添加一个边 public void addEdge( int v , int w ){ assert v >= 0 && v < n ; assert w >= 0 && w < n ; if( hasEdge( v , w ) ) return; g[v][w] = true; if( !directed ) g[w][v] = true; m ++; } // 验证图中是否有从v到w的边 boolean hasEdge( int v , int w ){ assert v >= 0 && v < n ; assert w >= 0 && w < n ; return g[v][w]; } //开始运行 public void start(){ //初始化 this.initialization(); //输出邻接矩阵 this.print(); //寻找起点 int qsd=-1; for (int i = 0; i < line.length; i++) { if (line[i]%2!=0){ qsd=i; break; }else if (line[i]!=0){ qsd=i; } } //从起点开始回溯寻找路线 flashBack(qsd); } public boolean flashBack(int a){ //如果已经走过的线数量等于总线数量，说明寻路完成 if (connected==m){ System.out.print("路线:["+a+"] -> "); return true; }else { //遍历此点与全部节点的关系并按照以下执行 //1.如果两点之间有连接，假设此路线为正确路线，将此线改变为无连接，并开始从此点遍历 //2.如果最终无法走过全部线，则确定此路线不正确，回溯并将此线还原为连接，继续遍历 for (int i = 0; i < n; i++) { if (g[a][i]){ g[a][i]=false; g[i][a]=false; connected++; if (flashBack(i)){ lineFeed++; if (lineFeed%20==0) System.out.println(); System.out.print("["+a+"] -> "); return true; }else { connected--; g[a][i]=true; g[i][a]=true; } } } return false; } } //输出邻接矩阵 public void print(){ System.out.println("边共:"+m+"条"); System.out.print("邻接矩阵 "); for (int i = 1; i < n; i++) { System.out.print(i+" \t"); } System.out.println(); for (int i = 1; i < n; i++) { System.out.print(i+" \t"); for (int j = 1; j < n; j++) { System.out.print(g[i][j]+" \t"); } System.out.println(); } }}
使用方法：
创建对象(new)
添加边(addEdge)
开始运行(start)
对于线非常多的图，一条一条添加线依然很麻烦，有没有更好的办法呢？
