我在代码里面写了注释，这里就不多废话了。

一：图的广度优先遍历：

public String breadthFirstTraverse(int StartIndex) {//为什么不直接用数组，我想是因为遍历的结果要建立在上一次遍历的结果上面，广度遍历需要存储上一次的结果，这样在之后才能正常进行广度遍历。String result = "";CircleObjectQueue tempQueue = new CircleObjectQueue();//创建一个栈存储int numNodes = fgh.GetRows();//获取图的节点个数Integer tempStart = new Integer(StartIndex);//包装StartIndextempQueue.enqueue(tempStart);//存储包装后的tempStartboolean[] IndexJudge = new boolean[fgh.GetRows()];//判断节点是否被遍历的数组int tempIndex;//标记节点位置要用Integer tempOut = (Integer)tempQueue.dequeue();//从栈中释放出来，根据栈是否为空，就可以判断所有节点是否遍历完成tempIndex = tempOut.intValue();IndexJudge[tempIndex] = true;//true表示当前节点已经被遍历result += tempIndex+" ";//		System.out.println("分解");while(tempOut!=null) {//节点从0开始的好处，就是之后不需要进行多余的变换，直接用就可以了。tempIndex = tempOut.intValue();//获得节点编号int[][] numMartrix = fgh.getData();for(int i = 0;i<fgh.GetRows();i++) {//遍历当前节点和其他节点是否邻接,节点从0开始！！！！！！if(numMartrix[tempIndex][i] == 0) {continue;//两个节点之间不连通，直接跳过。}if(IndexJudge[i] == true) {continue;//当前节点已经遍历过，直接跳过}IndexJudge[i] = true;result += i+" ";tempQueue.enqueue(new Integer(i));//当前节点遍历后变成true,当节点编号写入result当中，入栈}tempOut = (Integer)tempQueue.dequeue();}return result;}

二：图的深度优先遍历：

	public String depthFirstTraversal(int StartIndex) {//图的深度优先遍历，很多步骤和图的广度优先遍历相同，就不重复说了，只说一些稍微不同的地方。String result = "";ObjectStack tempStack = new ObjectStack();boolean[] IndexJudge =new boolean[fgh.GetRows()];//为了严谨，就以包装类放入栈当中(本来这个栈也是要来存Object类型的)Integer tempStart = new Integer(StartIndex);Integer tempOut;int tempIndex = StartIndex;IndexJudge[tempIndex] = true;result += tempIndex+" ";tempStack.enstack(tempStart);int flag;//标记该节点下面是否还有节点，根据不同情况分别处理while(true) {//和广度优先遍历不同，只要找到符合的，就直接往下了，不再在同一层耽搁，之后再回溯回来重新查找直到完毕。flag = -1;int[][] numMatrix = fgh.getData();for(int i = 0;i<fgh.GetRows();i++) {if(numMatrix[tempIndex][i]==0) {continue;}if(IndexJudge[i]==true) {//这里原来出了逻辑问题，方框里面应该是i，不该是tempIndex，不然一直不对。continue;}result += i+" ";IndexJudge[i] = true;tempStack.enstack(new Integer(i));flag = i;break;//找到一个点满足就终止循环，并且还要把该节点存入栈中方便以后回溯。}if(flag == -1) {//这种情况表示找不到之后的点了，当前这条路已经走到了尽头，进行回溯if(tempStack.isEmpty()==true) {break;//while结束，所有节点遍历完毕。}tempOut = (Integer)tempStack.destack();tempIndex = tempOut.intValue();}else {tempIndex = flag;//表示从当前这个节点开始查询起。}}return result;}

三：m点着色问题：

相邻点颜色不能相同。其中最麻烦的应该是颜色数组这一部分，这里染色的本质就是为colorArray数组赋值操作，存入不同的值代表不同的颜色。检测颜色相同与否时，就可以通过比较colorArray数组来进行判断。

//以下是m点着色问题的代码。检测的话还是和上面一样，如果不连通就不用管了，同一条上的两端点颜色必须不同。public void Mcoloring(int NumColors) {int NumNodes = fgh.GetRows();int[] ColorScheme = new int[NumNodes];Arrays.fill(ColorScheme, -1);Mcoloring(NumColors,0,ColorScheme);}//先染色进行初始化。public void Mcoloring(int numColors,int CurrentNumNodes,int[] ColorArray) {//按顺序来分别是：颜色数量，已染色的节点数，颜色数组int NumNodes = fgh.GetRows();if(CurrentNumNodes >= NumNodes) {System.out.println("得到："+Arrays.toString(ColorArray));return;}for(int i = 0;i<numColors;i++) {//先通过for循环遍历，因为初始化了colorArray数组全为一，之后如果有相同的，则说明相邻的节点颜色相同，则跳过。ColorArray[CurrentNumNodes] = i;//每个点的标号都在这个数组当中。if(!McoloringConflict(CurrentNumNodes+1,ColorArray)) {Mcoloring(numColors,CurrentNumNodes+1,ColorArray);}}}//颜色碰撞检测public boolean McoloringConflict(int CurrentNumNodes,int[] ColorArray) {//现在点的个数  ， 现在染色的情况for(int i = 0;i<CurrentNumNodes-1;i++) {if(fgh.getValue(CurrentNumNodes-1, i)==0) {continue;}if(ColorArray[CurrentNumNodes-1] == ColorArray[i]) {//如果和相邻那个点的颜色相同，则跳过。相当于这个color数组里存的是每一个编号。return true;}}return false;}

结合之前的代码，目前图的相关代码如下：

package graph;import java.util.Arrays;import matrix.*;//这就是那个矩阵的基础运算的包，是我自己写的，不是java自带的。
import stack.*;
import queue.*;public class Graph {IntMatrix fgh;public Graph(int paralength) {fgh = new IntMatrix(paralength,paralength);}//创建一个方形矩阵。public Graph(IntMatrix para) {fgh = new IntMatrix(para);}//利用矩阵创建图public Graph(Graph para) {fgh = new IntMatrix(para.fgh);}//利用图来进行复制。public Graph(int[][] temp) {fgh = new IntMatrix(temp);}public String toString() {String result = "连通矩阵如下:\r\n"+fgh;return result;}public boolean getConnectivity() throws Exception{//终于懂了，获取连通性的方法，分别以单个节点(M0)，一个距离(M1)，两个距离(M2)。。等等。。因为如果最后不连通的话，这些相加起来绝对为0（如果不懂建议看看离散数学）//总体思路就是遍历每一种可能，发现有0的存在说明这张图不连通(这里是有向图的思路，无向图差不多)//首先获取一个单位矩阵IntMatrix tempMatrix = new IntMatrix(fgh.GetRows(),fgh.GetRows());//中间矩阵IntMatrix tempfgh = IntMatrix.getIdentityMatrix(fgh.GetRows());//接下来需要检测连通性，还需要这里的fgh,经过节点数-1次循环相加后得到最后的矩阵(为了之后的0的判断)for(int i = 0;i<fgh.GetRows();i++) {tempMatrix.add(tempfgh);tempfgh = IntMatrix.Multiple(tempfgh, fgh);//多算了一次，没有影响，因为最后结果是不包含多出来的这一次的。}//最后的矩阵得出来了，接下来就非常简单了，直接冒泡遍历查询矩阵中是否有0的存在即可。for(int i = 0;i<tempMatrix.GetRows();i++) {for(int j = 0;j<tempMatrix.GetRows();j++) {if(tempMatrix.getValue(i, j) == 0) {return false;}}}return true;}public String breadthFirstTraverse(int StartIndex) {//为什么不直接用数组，我想是因为遍历的结果要建立在上一次遍历的结果上面，广度遍历需要存储上一次的结果，这样在之后才能正常进行广度遍历。String result = "";CircleObjectQueue tempQueue = new CircleObjectQueue();//创建一个栈存储int numNodes = fgh.GetRows();//获取图的节点个数Integer tempStart = new Integer(StartIndex);//包装StartIndextempQueue.enqueue(tempStart);//存储包装后的tempStartboolean[] IndexJudge = new boolean[fgh.GetRows()];//判断节点是否被遍历的数组int tempIndex;//标记节点位置要用Integer tempOut = (Integer)tempQueue.dequeue();//从栈中释放出来，根据栈是否为空，就可以判断所有节点是否遍历完成tempIndex = tempOut.intValue();IndexJudge[tempIndex] = true;//true表示当前节点已经被遍历result += tempIndex+" ";//		System.out.println("分解");while(tempOut!=null) {//节点从0开始的好处，就是之后不需要进行多余的变换，直接用就可以了。tempIndex = tempOut.intValue();//获得节点编号int[][] numMartrix = fgh.getData();for(int i = 0;i<fgh.GetRows();i++) {//遍历当前节点和其他节点是否邻接,节点从0开始！！！！！！if(numMartrix[tempIndex][i] == 0) {continue;//两个节点之间不连通，直接跳过。}if(IndexJudge[i] == true) {continue;//当前节点已经遍历过，直接跳过}IndexJudge[i] = true;result += i+" ";tempQueue.enqueue(new Integer(i));//当前节点遍历后变成true,当节点编号写入result当中，入栈}tempOut = (Integer)tempQueue.dequeue();}return result;}public String depthFirstTraversal(int StartIndex) {//图的深度优先遍历，很多步骤和图的广度优先遍历相同，就不重复说了，只说一些稍微不同的地方。String result = "";ObjectStack tempStack = new ObjectStack();boolean[] IndexJudge =new boolean[fgh.GetRows()];//为了严谨，就以包装类放入栈当中(本来这个栈也是要来存Object类型的)Integer tempStart = new Integer(StartIndex);Integer tempOut;int tempIndex = StartIndex;IndexJudge[tempIndex] = true;result += tempIndex+" ";tempStack.enstack(tempStart);int flag;//标记该节点下面是否还有节点，根据不同情况分别处理while(true) {//和广度优先遍历不同，只要找到符合的，就直接往下了，不再在同一层耽搁，之后再回溯回来重新查找直到完毕。flag = -1;int[][] numMatrix = fgh.getData();for(int i = 0;i<fgh.GetRows();i++) {if(numMatrix[tempIndex][i]==0) {continue;}if(IndexJudge[i]==true) {//这里原来出了逻辑问题，方框里面应该是i，不该是tempIndex，不然一直不对。continue;}result += i+" ";IndexJudge[i] = true;tempStack.enstack(new Integer(i));flag = i;break;//找到一个点满足就终止循环，并且还要把该节点存入栈中方便以后回溯。}if(flag == -1) {//这种情况表示找不到之后的点了，当前这条路已经走到了尽头，进行回溯if(tempStack.isEmpty()==true) {break;//while结束，所有节点遍历完毕。}tempOut = (Integer)tempStack.destack();tempIndex = tempOut.intValue();}else {tempIndex = flag;//表示从当前这个节点开始查询起。}}return result;}//以下是m点着色问题的代码。检测的话还是和上面一样，如果不连通就不用管了，同一条上的两端点颜色必须不同。public void Mcoloring(int NumColors) {int NumNodes = fgh.GetRows();int[] ColorScheme = new int[NumNodes];Arrays.fill(ColorScheme, -1);Mcoloring(NumColors,0,ColorScheme);}//先染色进行初始化。public void Mcoloring(int numColors,int CurrentNumNodes,int[] ColorArray) {//按顺序来分别是：颜色数量，已染色的节点数，颜色数组int NumNodes = fgh.GetRows();if(CurrentNumNodes >= NumNodes) {System.out.println("得到："+Arrays.toString(ColorArray));return;}for(int i = 0;i<numColors;i++) {//先通过for循环遍历，因为初始化了colorArray数组全为一，之后如果有相同的，则说明相邻的节点颜色相同，则跳过。ColorArray[CurrentNumNodes] = i;//每个点的标号都在这个数组当中。if(!McoloringConflict(CurrentNumNodes+1,ColorArray)) {Mcoloring(numColors,CurrentNumNodes+1,ColorArray);}}}//颜色碰撞检测public boolean McoloringConflict(int CurrentNumNodes,int[] ColorArray) {//现在点的个数  ， 现在染色的情况for(int i = 0;i<CurrentNumNodes-1;i++) {if(fgh.getValue(CurrentNumNodes-1, i)==0) {continue;}if(ColorArray[CurrentNumNodes-1] == ColorArray[i]) {//如果和相邻那个点的颜色相同，则跳过。相当于这个color数组里存的是每一个编号。return true;}}return false;}//对以上的程序进行测试。。public static void main(String[] args) {//先测试无向图int[][] temp = {{0,1,1,0},{1,0,0,0},{1,0,0,1},{0,0,1,0}};Graph test = new Graph(temp);boolean result=true;try {result = test.getConnectivity();} catch (Exception e) {// TODO Auto-generated catch blocke.printStackTrace();}System.out.println(result);System.out.println(test.breadthFirstTraverse(0));//因为for循环那里是按照从0开始的，所以这里会有一定的顺序，不过不影响，最后的结果是正确的。System.out.println(test.depthFirstTraversal(0));test.Mcoloring(2);}}