基本概念
邻接：如果两个顶点被同一条边连接，就称这两条边是邻接的。
路径：路径是边的序列。
连通图：如果至少有一条路径可以连接起图中的所有顶点，就称图为连通图。
极大连通子图：非连通图中包含几个连通图，其中包含最多顶点的称为极大连通子图。
一般用两种方法表示图：邻接矩阵和邻接表。（如果两个顶点被同一条边连接就称这两个顶点是邻接的）。
邻接矩阵：使用二维数组表示各顶点之间是否有边，可以约定0表示没有边连接，1表示有边连接。
邻接表：邻接表是一个链表数组，每个单独的链表表示有哪些顶点与当前顶点邻接（形式上很像哈希表中处理冲突的链地址法）。将与顶点v邻接的顶点存放在一个单独的链表中，再使顶点v包含指向这个链表的指针即可。可以使用Map存储邻接表，HashMap<T, Map<T, double>>。
其中，B——>C——>D只是表示A的邻接顶点是B，C，D并不是B指向C，C指向D。
邻接矩阵和邻接表的比较
设图G含有n个顶点e条边，下面比较邻接矩阵和邻接表的存储结构。
空间性能比较
邻接矩阵是一个n*n的矩阵，存储了所有可能的边，所以空间代价是O(n^2)。邻接表是对所有顶点的存储和边的存储，所以其空间代价是O(n+e)。
时间性能比较
图算法中查找某顶点的邻接顶点是常见操作，如果使用邻接矩阵，就需要遍历此顶点对应的一行数组元素，平均查找次数为O(n)。如果使用邻接表，只需要查找顶点对应的邻接表，平均查找次数是O(e/n)。
小结
总之，邻接表是图的标准存储方式，而邻接矩阵的存储方式便于编程。当图是稀疏图时，边的数量远小于顶点的数量，使用邻接矩阵的话，会导致存储空间的极大浪费，并且查找效率也更低下，此时采用邻接表的方法。当图是稠密图时，为了便于编程，可以使用邻接矩阵的方法。
顶点的表示
顶点类的实现对深搜、广搜以及迪杰斯特拉算法的实现具有重要的作用，这里给出顶点类的具体实现，其中有两个标志字段，标识顶点是否已被访问(搜索算法中使用)和顶点是否已加入集合S(迪杰斯特拉算法中使用)，代码如下：
1 class Vertex{ 2 char label;//顶点标签 3 boolean wasVisited;//顶点访问标记 4 boolean insertedIntoS;//迪杰斯特拉算法中，表示此顶点是否已加入集合S中。 5 public Vertex(char label){ 6 this.label=label; 7 wasVisited=false; 8 insertedIntoS=false; 9 } 10 }
深度优先搜索
深度优先搜索是图的一种搜索算法，从起始顶点开始想着距离顶点“更远”的方向搜索可以到达的顶点。深搜使用栈来完成，利用栈来“记住”访问过的顶点，以栈空作为搜索结束的条件。步骤如下：
1)从搜索从起始顶点开始，将顶点标记为已访问，并入栈
2）如果栈顶元素有邻接顶点并且未被访问，将顶点标记为已访问，输出顶点标签并入栈，直到不满足前述条件转3。
3）如果栈不空，将栈顶元素出栈，转2
4）最后栈空时，搜索结束。
5）//将顶点访问标记重置为false，便于下次搜索使用
总结：
每次出栈时，就到达离起始点“较远”的一个顶点，通过比较每次出栈时顶点与起始点的距离可以得到图中
离起始点“最远”的顶点
每次入栈时，就是访问了一个顶点，所以入栈时，将顶点输出，最终就得到了深度优先搜索的访问序列。
任意时刻，栈的内容是从起始顶点到栈顶顶点所经过的所有顶点，也就是一条路径。
代码实现如下：
1 /* 2 深度优先搜索使用栈来完成，使用栈来“记住”访问过的顶点，以栈空作为搜索结束的条件，步骤如下 3 1)从搜索从起始顶点开始，将顶点标记为已访问，并入栈 4 2）如果栈顶元素有邻接顶点并且未被访问，将顶点标记为已访问，输出顶点标签并入栈，直到不满足前述条件转3。 5 3）如果栈不空，将栈顶元素出栈，转2 6 4）最后栈空时，搜索结束。 7 5）//将顶点访问标记重置为false，便于下次搜索使用 8 9 总结： 10 每次出栈时，就到达离起始点“较远”的一个顶点，通过比较每次出栈时顶点与起始点的距离可以得到图中 11 离起始点“最远”的顶点 12 每次入栈时，就是访问了一个顶点，所以入栈时，将顶点输出，最终就得到了深度优先搜索的访问序列。 13 任意时刻，栈的内容是从起始顶点到栈顶顶点所经过的所有顶点，也就是一条路径。 14 */ 15 public void dfs(){//从起始点0(A)开始搜索 16 System.out.println("dfs:"); 17 Stack<Integer> stack=new Stack<>(); 18 vertexArray[0].wasVisited=true; 19 stack.push(0); 20 System.out.print(vertexArray[0].label); 21 int adjNumber=-1; 22 while (!stack.isEmpty()){ 23 adjNumber=getAdjUnvisitedVertex(stack.peek());//得到栈顶元素的下一个未被访问的邻接点 24 if(adjNumber==-1){ 25 stack.pop();//栈顶元素没有邻接点，访问到距离起始点较远的顶点 26 } 27 else { 28 vertexArray[adjNumber].wasVisited=true; 29 System.out.print("\t" + vertexArray[adjNumber].label); 30 stack.push(adjNumber);//将栈顶元素的未被访问的邻接点入栈 31 32 } 33 } 34 //将访问标记重置为false，便于下次搜索使用 35 for (int i = 0; i <nVertexs ; i++) { 36 vertexArray[i].wasVisited=false; 37 } 38 }
深度优先搜索得到距离起始点最远的顶点，然后再不能前进的时候返回。使用深度优先搜索可以解决迷宫问题。
广度优先搜索
图的广度优先搜索使用队列来实现，与深度优先搜索类似，以队空作为搜索结束的条件，任意时刻，
队列中的顶点是那些已经被访问过，其邻接点还未被访问过的顶点。步骤如下：
1)将起始顶点标记为已访问，并将其入队。
2）如果队不空，得到队首元素所有未被访问过的顶点，将其标记为已访问，输出对应标签，最后依次入队
3）如果队首元素邻接顶点全部入队，将队首元素出队，得到新的队首元素，转2
4）最后队空时，搜索结束。
5）将访问标记重置为false，便于下次搜索使用
代码实现如下：
1 public void bfs2(){ 2 Queue<Integer> queue=new LinkedList<>(); 3 vertexArray[0].wasVisited=true; 4 System.out.print("\nbfs:" + "\n" + vertexArray[0].label); 5 queue.add(0);//将起始点入队 6 int adjNumber=-1; 7 while (!queue.isEmpty()){ 8 while ((adjNumber=getAdjUnvisitedVertex(queue.peek()))!=-1){//队首顶点的未被访问的邻接顶点 9 vertexArray[adjNumber].wasVisited=true; 10 System.out.print("\t" + vertexArray[adjNumber].label); 11 queue.add(adjNumber);//队首元素未访问过的邻接点入队 12 } 13 queue.remove(); 14 } 15 //将访问标记重置为false，便于下次搜索使用 16 for (int i = 0; i <nVertexs ; i++) { 17 vertexArray[i].wasVisited=false; 18 } 19 }
迪杰斯特拉算法
Dijkstra算法用于求单源点最短路径问题，问题描述如下：给定的带权有向图G=(V,E)和源点v，求从v到G中其余各顶点的最短路径。
算法描述
设D(v)是从源点s到顶点v的距离
I(v,w)是从顶点v到顶点w的距离
如两顶点之间无边，就认为两点之间距离为正无穷(或者赋给一个很大的值)。
算法如下：
1.设S={s},以集合S存放已经找到源点到其的最短路径的顶点，初始状态下，S中只包含源点s。对不再S中的每一个顶点，另D(v)=I(s,v)。
对那些与s不邻接的顶点赋值为∞。
2.找到不在集合S中的顶点，比较其D(v)值，得到具有最小值的节点w，如果D(w)=∞，说明已经得到了所有源点可以到达的顶点，算法结束。否则，将w加入集合S中，表示已找到源点到w的最短路径，然后对不在集合S的其余顶点，利用w更新D(v)：
D(v)=min([D(v),D(w)+I(w,v)])
重复2，知道所有顶点都在S中。
算法实现
使用DistPar类来保存从源点到此顶点的最短距离以及最短路径上的父顶点，DistPar[] dist，，具体实现如下：
class DistPar{//保存从源点到此顶点的最短距离以及最短路径上的父顶点 int distance;//最短距离 int parentVertexindex;//父顶点 public DistPar(int distance,int parentVertexindex){ this.distance=distance; this.parentVertexindex=parentVertexindex; }
求dist数组中离源点最近的顶点，并且是未加入集合S中的顶点，getMin实现如下：
//要求邻接矩阵中使用1e6(infinity)表示两顶点不邻接，没有边连接。 /* 求dist数组中离源点最近的顶点，并且是未加入集合S中的顶点。 */ public int getMin(DistPar[] dist,int len){ int minValue=(int)1e6;// int minIndex=-1; for (int i = 1; i <len ; i++) { if(!vertexArray[i].insertedIntoS&&dist[i].distance<minValue){ minIndex=i; minValue=dist[i].distance; } } return minIndex; }
根据刚加入S的顶点，更新dist,已经标记为加入集合S的顶点不用更新，adjustDist实现如下：
/* 根据刚加入S的顶点，更新dist,已经标记为加入集合S的顶点不用更新 */ public void adjustDist(DistPar[] dist,int len,int insertedVertexIndex){ for (int i = 0; i <len ; i++) { if(!vertexArray[i].insertedIntoS&&adjMat[insertedVertexIndex][i]+dist[insertedVertexIndex].distance <dist[i].distance){ dist[i].distance=adjMat[insertedVertexIndex][i]+dist[insertedVertexIndex].distance; dist[i].parentVertexindex=insertedVertexIndex; } } }
算法收敛条件有两个，图中所有顶点已加入S中或者getMin得到的最小值是∞，说明已经没有源点可到达的顶点，算法主体实现如下：
1 //迪杰斯特拉算法:求解单源最短路径问题，求图中某点v到其余顶点的最短路径。 2 public void dijkstra(int sourceVertexIndex){ 3 DistPar[] dist=new DistPar[nVertexs]; 4 int insertedIntoVertexs=0; 5 vertexArray[sourceVertexIndex].insertedIntoS=true;//把源点加入集合S中 6 ++insertedIntoVertexs;//对集合S中顶点数量计数 7 for (int i = 0; i <nVertexs; i++) { 8 int temp=adjMat[sourceVertexIndex][i]; 9 dist[i]=new DistPar(temp,sourceVertexIndex);//把与源点邻接的各顶点的权值拷贝到dist中 10 } 11 int minIndex=-1; 12 while (insertedIntoVertexs<nVertexs){//源点可以到达所有其他顶点，将这些顶点加入集合S 13 minIndex=getMin(dist,nVertexs);//得到集合S外的顶点中，源点可到的距离最短的顶点索引 14 if(minIndex==-1){//除S外，已经没有源点可到的顶点，算法结束 15 System.out.println("no more reachable vertexs"); 16 break; 17 } 18 else { 19 ++insertedIntoVertexs;//计数，表示向S中加入一个顶点 20 vertexArray[minIndex].insertedIntoS=true;//将顶点标记为已加入集合S 21 adjustDist(dist,nVertexs,minIndex); 22 } 23 } 24 System.out.println("迪杰斯特拉算法已完成"); 25 //算法结束，重置顶点加入S标志，便于下次使用 26 for (int i = 0; i <nVertexs ; i++) { 27 vertexArray[i].insertedIntoS=false; 28 } 29 }
Dijkstra应用实例
完整程序(dfs、bfs、Dijkstra)
1 import java.util.LinkedList; 2 import java.util.Queue; 3 import java.util.Stack; 4 5 /** 6 * Created by hfz on 2016/8/24. 7 */ 8 public class graph { 9 private int MAX_VERTEXS=20;//最多顶点数 10 private Vertex[] vertexArray;//存储顶点的数组 11 private int[][] adjMat;//邻接矩阵 12 private int nVertexs;//图中当前顶点数量 13 14 public graph(){ 15 vertexArray=new Vertex[MAX_VERTEXS]; 16 adjMat=new int[MAX_VERTEXS][MAX_VERTEXS]; 17 nVertexs=0; 18 for (int i = 0; i <MAX_VERTEXS ; i++) { 19 for (int j = 0; j <MAX_VERTEXS ; j++) { 20 adjMat[i][j]=(int)1e6; 21 } 22 } 23 } 24 25 public void addVertex(char label){ 26 vertexArray[nVertexs++]=new Vertex(label); 27 } 28 /* 29 根据顶点的label，按照字母顺序，将节点以0，1.。。n-1简单编号，利用这些编号创建边和求解未被访问的 30 邻接顶点。起始点对应编号是0 31 */ 32 public void addEdge(int start,int end){ 33 adjMat[start][end]=1; 34 adjMat[end][start]=1; 35 } 36 37 public void addEdge(int start,int end,int weight){ 38 adjMat[start][end]=weight; 39 } 40 41 //得到相邻的未被访问的顶点索引值(根据字母序将标签分别映射为0,1...n-1) 42 public int getAdjUnvisitedVertex(int v){ 43 for (int i = 0; i <nVertexs ; i++) { 44 if(adjMat[v][i]==1&&vertexArray[i].wasVisited==false){ 45 return i; 46 } 47 } 48 return -1; 49 } 50 51 /* 52 深度优先搜索使用栈来完成，使用栈来“记住”访问过的顶点，以栈空作为搜索结束的条件，步骤如下 53 1)从搜索从起始顶点开始，将顶点标记为已访问，并入栈 54 2）如果栈顶元素有邻接顶点并且未被访问，将顶点标记为已访问，输出顶点标签并入栈，直到不满足前述条件转3。 55 3）如果栈不空，将栈顶元素出栈，转2 56 4）最后栈空时，搜索结束。 57 5）//将顶点访问标记重置为false，便于下次搜索使用 58 59 总结： 60 每次出栈时，就到达离起始点“较远”的一个顶点，通过比较每次出栈时顶点与起始点的距离可以得到图中 61 离起始点“最远”的顶点 62 每次入栈时，就是访问了一个顶点，所以入栈时，将顶点输出，最终就得到了深度优先搜索的访问序列。 63 任意时刻，栈的内容是从起始顶点到栈顶顶点所经过的所有顶点，也就是一条路径。 64 */ 65 public void dfs(){//从起始点0(A)开始搜索 66 System.out.println("dfs:"); 67 Stack<Integer> stack=new Stack<>(); 68 vertexArray[0].wasVisited=true; 69 stack.push(0); 70 System.out.print(vertexArray[0].label); 71 int adjNumber=-1; 72 while (!stack.isEmpty()){ 73 adjNumber=getAdjUnvisitedVertex(stack.peek());//得到栈顶元素的下一个未被访问的邻接点 74 if(adjNumber==-1){ 75 stack.pop();//栈顶元素没有邻接点，访问到距离起始点较远的顶点 76 } 77 else { 78 vertexArray[adjNumber].wasVisited=true; 79 System.out.print("\t" + vertexArray[adjNumber].label); 80 stack.push(adjNumber);//将栈顶元素的未被访问的邻接点入栈 81 82 } 83 } 84 //将访问标记重置为false，便于下次搜索使用 85 for (int i = 0; i <nVertexs ; i++) { 86 vertexArray[i].wasVisited=false; 87 } 88 } 89 90 /* 91 图的广度优先搜索使用队列来实现，与深度优先搜索类似，以队空作为搜索结束的条件，任意时刻， 92 队列中的顶点是那些已经被访问过，其邻接点还未被访问过的顶点。步骤如下： 93 1)将起始顶点标记为已访问，并将其入队。 94 2）如果队不空，得到队首元素所有未被访问过的顶点，将其标记为已访问，输出对应标签，最后依次入队 95 3）如果队首元素邻接顶点全部入队，将队首元素出队，得到新的队首元素，转2 96 4）最后队空时，搜索结束。 97 5）将访问标记重置为false，便于下次搜索使用 98 */ 99 public void bfs(){ 100 Queue<Integer> queue=new LinkedList<>(); 101 vertexArray[0].wasVisited=true; 102 System.out.print("\nbfs:" + "\n" + vertexArray[0].label); 103 queue.add(0);//将起始点入队 104 int adjNumber=-1; 105 while (!queue.isEmpty()){ 106 adjNumber=getAdjUnvisitedVertex(queue.peek());//队首顶点的未被访问的邻接顶点 107 if(adjNumber==-1){ 108 queue.remove();//队首元素的所有邻接点入队之后，队首元素出队。 109 } 110 else { 111 vertexArray[adjNumber].wasVisited=true; 112 System.out.print("\t" + vertexArray[adjNumber].label); 113 queue.add(adjNumber);//队首元素未访问过的邻接点入队 114 } 115 } 116 //将访问标记重置为false，便于下次搜索使用 117 for (int i = 0; i <nVertexs ; i++) { 118 vertexArray[i].wasVisited=false; 119 } 120 } 121 //简洁版本 122 public void bfs2(){ 123 Queue<Integer> queue=new LinkedList<>(); 124 vertexArray[0].wasVisited=true; 125 System.out.print("\nbfs:" + "\n" + vertexArray[0].label); 126 queue.add(0);//将起始点入队 127 int adjNumber=-1; 128 while (!queue.isEmpty()){ 129 while ((adjNumber=getAdjUnvisitedVertex(queue.peek()))!=-1){//队首顶点的未被访问的邻接顶点 130 vertexArray[adjNumber].wasVisited=true; 131 System.out.print("\t" + vertexArray[adjNumber].label); 132 queue.add(adjNumber);//队首元素未访问过的邻接点入队 133 } 134 queue.remove(); 135 } 136 //将访问标记重置为false，便于下次搜索使用 137 for (int i = 0; i <nVertexs ; i++) { 138 vertexArray[i].wasVisited=false; 139 } 140 } 141 142 //迪杰斯特拉算法:求解单源最短路径问题，求图中某点v到其余顶点的最短路径。 143 public void dijkstra(int sourceVertexIndex){ 144 DistPar[] dist=new DistPar[nVertexs]; 145 int insertedIntoVertexs=0; 146 vertexArray[sourceVertexIndex].insertedIntoS=true;//把源点加入集合S中 147 ++insertedIntoVertexs;//对集合S中顶点数量计数 148 for (int i = 0; i <nVertexs; i++) { 149 int temp=adjMat[sourceVertexIndex][i]; 150 dist[i]=new DistPar(temp,sourceVertexIndex);//把与源点邻接的各顶点的权值拷贝到dist中 151 } 152 int minIndex=-1; 153 while (insertedIntoVertexs<nVertexs){//源点可以到达所有其他顶点，将这些顶点加入集合S 154 minIndex=getMin(dist,nVertexs);//得到集合S外的顶点中，源点可到的距离最短的顶点索引 155 if(minIndex==-1){//除S外，已经没有源点可到的顶点，算法结束 156 System.out.println("no more reachable vertexs"); 157 break; 158 } 159 else { 160 ++insertedIntoVertexs;//计数，表示向S中加入一个顶点 161 vertexArray[minIndex].insertedIntoS=true;//将顶点标记为已加入集合S 162 adjustDist(dist,nVertexs,minIndex); 163 } 164 } 165 System.out.println("迪杰斯特拉算法已完成"); 166 //算法结束，重置顶点加入S标志，便于下次使用 167 for (int i = 0; i <nVertexs ; i++) { 168 vertexArray[i].insertedIntoS=false; 169 } 170 } 171 //要求邻接矩阵中使用1e6(infinity)表示两顶点不邻接，没有边连接。 172 /* 173 求dist数组中离源点最近的顶点，并且是未加入集合S中的顶点。 174 */ 175 public int getMin(DistPar[] dist,int len){ 176 int minValue=(int)1e6;// 177 int minIndex=-1; 178 for (int i = 1; i <len ; i++) { 179 if(!vertexArray[i].insertedIntoS&&dist[i].distance<minValue){ 180 minIndex=i; 181 minValue=dist[i].distance; 182 } 183 } 184 return minIndex; 185 } 186 187 /* 188 根据刚加入S的顶点，更新dist,已经标记为加入集合S的顶点不用更新 189 */ 190 191 public void adjustDist(DistPar[] dist,int len,int insertedVertexIndex){ 192 for (int i = 0; i <len ; i++) { 193 if(!vertexArray[i].insertedIntoS&&adjMat[insertedVertexIndex][i]+dist[insertedVertexIndex].distance 194 <dist[i].distance){ 195 dist[i].distance=adjMat[insertedVertexIndex][i]+dist[insertedVertexIndex].distance; 196 dist[i].parentVertexindex=insertedVertexIndex; 197 } 198 } 199 } 200 public static void main(String[] args){ 201 graph gra=new graph(); 202 gra.addVertex('A');//0 203 gra.addVertex('B');//1 204 gra.addVertex('C');//2 205 gra.addVertex('D');//3 206 gra.addVertex('E');//4 207 gra.addEdge(0, 1); 208 gra.addEdge(0, 3); 209 gra.addEdge(1, 2); 210 gra.addEdge(3, 4); 211 gra.dfs(); 212 System.out.println("\n" + "******************"); 213 graph graph2=new graph(); 214 graph2.addVertex('A'); 215 graph2.addVertex('B'); 216 graph2.addVertex('C'); 217 graph2.addVertex('D'); 218 graph2.addVertex('E'); 219 graph2.addVertex('F'); 220 graph2.addVertex('G'); 221 graph2.addVertex('H'); 222 graph2.addVertex('I'); 223 graph2.addEdge(0, 1); 224 graph2.addEdge(0, 2); 225 graph2.addEdge(0, 3); 226 graph2.addEdge(0, 4); 227 graph2.addEdge(1, 5); 228 graph2.addEdge(3, 6); 229 graph2.addEdge(5, 7); 230 graph2.addEdge(6, 8); 231 graph2.dfs(); 232 System.out.println("\n" + "******************"); 233 graph2.bfs(); 234 graph2.bfs2(); 235 System.out.println("\n" + "******迪杰斯特拉************"); 236 graph graph3=new graph(); 237 graph3.addVertex('A'); 238 graph3.addVertex('B'); 239 graph3.addVertex('C'); 240 graph3.addVertex('D'); 241 graph3.addVertex('E'); 242 graph3.addEdge(0, 1, 50); 243 graph3.addEdge(0, 3, 80); 244 graph3.addEdge(1, 2, 60); 245 graph3.addEdge(1, 3, 90); 246 graph3.addEdge(2, 4, 40); 247 graph3.addEdge(3, 2, 20); 248 graph3.addEdge(3, 4, 70); 249 graph3.addEdge(4, 1, 50); 250 graph3.dijkstra(0); 251 252 graph graph4=new graph(); 253 graph4.addVertex('A'); 254 graph4.addVertex('B'); 255 graph4.addVertex('C'); 256 graph4.addVertex('D'); 257 graph4.addVertex('E'); 258 graph4.addEdge(0, 1, 4); 259 graph4.addEdge(1, 0, 4); 260 graph4.addEdge(0, 2, 5); 261 graph4.addEdge(2, 0, 5); 262 graph4.addEdge(2, 1, 3); 263 graph4.addEdge(1, 2, 3); 264 graph4.addEdge(1, 3, 1); 265 graph4.addEdge(3, 1, 1); 266 graph4.addEdge(3, 2, 2); 267 graph4.addEdge(2, 3, 2); 268 graph4.addEdge(3, 4, 2); 269 graph4.addEdge(4, 3, 2); 270 graph4.addEdge(4, 2, 20); 271 graph4.addEdge(2, 4, 20); 272 graph4.dijkstra(4); 273 } 274 } 275 276 class DistPar{//保存从源点到此顶点的最短距离以及最短路径上的父顶点 277 int distance;//最短距离 278 int parentVertexindex;//父顶点 279 public DistPar(int distance,int parentVertexindex){ 280 this.distance=distance; 281 this.parentVertexindex=parentVertexindex; 282 } 283 } 284 class Vertex{ 285 char label;//顶点标签 286 boolean wasVisited;//顶点访问标记 287 boolean insertedIntoS;//迪杰斯特拉算法中，表示此顶点是否已加入集合S中。 288 public Vertex(char label){ 289 this.label=label; 290 wasVisited=false; 291 insertedIntoS=false; 292 } 293 }
参考：Java数据结构和算法 第二版 Robert Lafore，数据结构（C++版）第二版 王红梅