一.概述

图可以使用两种存储结构，分别是邻接矩阵和邻接表。

邻接矩阵以矩阵的形式存储图所有顶点间的关系。邻接矩阵具有以下特点：

1，邻接矩阵是正矩阵，即横纵维数相等。 3，如果是无权图，则1代表有边，0代表无边，矩阵的对角线都是0；如果是有权图，矩阵点数值可以是权值4，如果是无向图，那么矩阵是对称矩阵；如果是有向图则不一定。 4，邻接矩阵表示图的关系非常清晰，但消耗空间较大。

邻接表是以一组链表来表示顶点间关系，有以下特点:

1，邻接表示一个由链表组成的数组 2，图中的每一个顶点都有一个链，数组的大小等于图中顶点的个数。 3，无向图的链的第一个元素是本顶点，后继分别连接着和这个顶点相连的顶点；有向图的链第一个顶点是本顶点，后继是以本顶点为起点的边的终点。 4，如果是有权图，可以在节点元素中设置权值属性 

5，邻接链表关系表示不如邻接矩阵清晰，数据结构相对复杂，但节省空间。

二.邻接矩阵

假设有图形结构如下：

1.建树

/** * 这个类代表一条边，有起始节点和终止节点，以及边的长度 */ public class Edge { String beginCity; String endCity; int cost; public Edge(String beginCity, String endCity, int cost) { super(); this.beginCity = beginCity; this.endCity = endCity; this.cost = cost; } } public class Graph { int size; int[][] matrix; String[] cityArray; /** * * @param cityArray * 代表所有的城市信息 * @param edges * 代表所有的边 * @param direction * true代表构建有向图，false代表无向图 */ public Graph(String[] cityArray, Edge[] edges, boolean direction) { this.cityArray = cityArray; this.size = cityArray.length; matrix = new int[size][size]; for(int i=0;i<size;i++) { for(int j=0;j<size;j++) { if(i==j) { matrix[i][j] = 0; }else { matrix[i][j] = Integer.MAX_VALUE; } } } for (Edge e : edges) { int begin = findIndex(e.beginCity, cityArray); int end = findIndex(e.endCity, cityArray); matrix[begin][end] = e.cost; if (!direction) { matrix[end][begin] = e.cost; } } } /** * 找出指定数组中某个元素的位置，如果找不到，则返回-1 */ public int findIndex(String city, String[] cityArray) { for (int i = 0; i < cityArray.length; i++) { if (city.equals(cityArray[i])) return i; } return -1; } public void print() { for (int i = 0; i < matrix.length; i++) { int[] ii = matrix[i]; System.out.print(cityArray[i] + " "); for (int j : ii) { System.out.printf("%-16d", j); } System.out.println(); } } }

测试代码如下：

public class Test { public static void main(String[] args) { Graph graph = createGraph(false); System.out.println("图的矩阵如下："); graph.print(); } /** * * @param direction * 是否生成有向图 * @return */ public static Graph createGraph(boolean direction) { String[] citys = new String[] { "北京", "上海", "广州", "重庆", "武汉", "南昌" }; List<Edge> edgeList = new ArrayList<>(); edgeList.add(new Edge("北京", "广州", 10)); edgeList.add(new Edge("北京", "上海", 11)); edgeList.add(new Edge("上海", "南昌", 6)); edgeList.add(new Edge("广州", "重庆", 14)); edgeList.add(new Edge("广州", "武汉", 9)); edgeList.add(new Edge("重庆", "武汉", 20)); edgeList.add(new Edge("武汉", "北京", 13)); edgeList.add(new Edge("武汉", "南昌", 12)); edgeList.add(new Edge("南昌", "广州", 18)); Edge[] edgeArray = new Edge[edgeList.size()]; return new Graph(citys, edgeList.toArray(edgeArray), true); } }

执行结果：

图的矩阵如下： 北京  0               11              10              2147483647      2147483647      2147483647       上海  2147483647      0               2147483647      2147483647      2147483647      6                广州  2147483647      2147483647      0               14              9               2147483647       重庆  2147483647      2147483647      2147483647      0               20              2147483647       武汉  13              2147483647      2147483647      2147483647      0               12               南昌  2147483647      2147483647      18              2147483647      2147483647      0   

注意：

我们这里表示节点时，只是用了一个String代表一个节点，如果是复杂的节点，比如

public class City{     String name; //城市名字 double gdp; //城市GDP ...... }

我们只需要将 Edge类改为

public class Edge { City beginCity; City endCity; int cost; ...... }

同时将Graph类中的 String[] cityArray 修改为 City[] cityArray，还有其他的修改都类似

2.深度优先级遍历

在类Graph中添加dfs()方法

public class Graph { int size; int[][] matrix; String[] cityArray; ....... /** * 对图执行深度优先级遍历 * * @param start * 遍历其实节点 * @param visit * 保存所有节点的遍历状态 */ public void dfs(int start, int[] visit) { // 访问当前节点 System.out.print(cityArray[start] + " "); visit[start] = 1; for (int i = 0; i < visit.length; i++) { if (matrix[start][i] > 0 && visit[i] == 0) { dfs(i, visit); } } } }

测试如下：

public class Test { public static void main(String[] args) { Graph graph = createGraph(false);              System.out.println("深度优先遍历顺序如下："); int[] visit = new int[graph.size];              graph.dfs(0, visit);        }

运行结果如下：

深度优先遍历顺序如下： 北京 上海 广州 重庆 武汉 南昌

3.广度优先级遍历

在类Graph中添加bfs()方法

public class Graph { int size; int[][] matrix; String[] cityArray; ....... /** * 对图执行广度优先级遍历 *  * @param start *            遍历开始节点 */ public void bfs(int start) { int visit[] = new int[size]; int[] queue = new int[size]; int front = -1; int tail = -1; // 根节点入队 tail = (tail + 1) % queue.length; queue[tail] = start; visit[start] = 1; while (front != tail) { // 根节点出队 front = (front + 1) % queue.length; int index = queue[front]; // 访问出队节点 System.out.print(cityArray[index] + "  "); for (int i = 0; i < cityArray.length; i++) { if (matrix[index][i] != 0 && visit[i] == 0) { // 下一个节点入队 tail = (tail + 1) % queue.length; queue[tail] = i; visit[i] = 1; } } } } }

测试如下：

public class Test { public static void main(String[] args) { Graph graph = createGraph(false); System.out.println("广度优先遍历顺序如下："); graph.bfs(0); } }

运行结果如下：

广度优先遍历顺序如下： 北京  上海  广州  重庆  武汉  南昌  

注意：

        在进行广度优先级遍历时，这个有个坑，一开始我是在节点离开队列时，给此节点打上访问标志（visit[i] = 1），这样做有什么问题呢？

    在进行广度优先级遍历时，重庆和广州的遍历顺序在武汉的前面，重庆和武汉都指向武汉，当遍历广州节点时，执行如下代码:

                    for (int i = 0; i < cityArray.length; i++) { if (matrix[index][i] != 0 && visit[i] == 0) { // 下一个节点入队 tail = (tail + 1) % queue.length; queue[tail] = i; visit[i] = 1; } }

武汉的visit状态为0，故武汉入队列，但武汉的visit状态没变

当遍历重庆节点时，武汉的visit == 0，故武汉节点又进队里，这样就重复访问了武汉

所以：不能在节点出队列时才修改Visit状态，应该在节点入队列时设置 visit[i] =1

4.Prim算法--最小生成树

public class Test { public static void main(String[] args) { Graph graph = createGraph(false); int sum = prim(graph, 0); System.out.println("最小路径总长度是：" + sum); } /** * * @param direction * 是否生成有向图 * @return */ public static Graph createGraph(boolean direction) { String[] citys = new String[] { "北京", "上海", "广州", "重庆", "武汉", "南昌" }; List<Edge> edgeList = new ArrayList<>(); edgeList.add(new Edge("北京", "广州", 10)); edgeList.add(new Edge("北京", "上海", 11)); edgeList.add(new Edge("上海", "南昌", 6)); edgeList.add(new Edge("广州", "重庆", 14)); edgeList.add(new Edge("广州", "武汉", 9)); edgeList.add(new Edge("重庆", "武汉", 20)); edgeList.add(new Edge("武汉", "北京", 13)); edgeList.add(new Edge("武汉", "南昌", 12)); edgeList.add(new Edge("南昌", "广州", 18)); Edge[] edgeArray = new Edge[edgeList.size()]; return new Graph(citys, edgeList.toArray(edgeArray), true); } public static int prim(Graph graph, int start) { if (graph != null) { int size = graph.size; int[] lowCost = new int[size]; int[] visit = new int[size]; // 初始化lowCost数组 for (int i = 0; i < size; i++) { lowCost[i] = graph.matrix[start][i]; } // 对进树节点的操作 StringBuilder builder = new StringBuilder(); builder.append(graph.cityArray[start]).append(" "); visit[start] = 1; int sum = 0; // 起始节点不需要找，所以我们总共要找(size-1)个节点，故这里n从1开始 for (int n = 1; n < size; n++) { int min = Integer.MAX_VALUE; int k = -1; // 选出下一个进树的节点 for (int i = 0; i < size; i++) { if (visit[i] == 0 && lowCost[i] < min) { min = lowCost[i]; k = i; } } builder.append(graph.cityArray[k]).append(" "); visit[k] = 1; sum += min; // 更新剩下节点的lowCost for (int i = 0; i < size; i++) { if (visit[i] == 0 && graph.matrix[k][i] < lowCost[i]) { lowCost[i] = graph.matrix[k][i]; } } } System.out.println("Prim 数的构造顺序如下："); System.out.println(builder.toString()); return sum; } return 0; } }

运行结果如下：

Prim 数的构造顺序如下： 北京 广州 武汉 上海 南昌 重庆  最小路径总长度是：50 

5.Dijkstra--最短路径算法

public class Test { public static void main(String[] args) { Graph graph = createGraph(false); int[] dist = new int[graph.size]; int[] path = new int[graph.size]; djst(graph, 0, dist, path); for(int i=0;i<graph.size;i++) { printPath(path, i); System.out.println(); } } /** * * @param direction * 是否生成有向图 * @return */ public static Graph createGraph(boolean direction) { String[] citys = new String[] { "北京", "上海", "广州", "重庆", "武汉", "南昌" }; List<Edge> edgeList = new ArrayList<>(); edgeList.add(new Edge("北京", "广州", 10)); edgeList.add(new Edge("北京", "上海", 11)); edgeList.add(new Edge("上海", "南昌", 6)); edgeList.add(new Edge("广州", "重庆", 14)); edgeList.add(new Edge("广州", "武汉", 9)); edgeList.add(new Edge("重庆", "武汉", 20)); edgeList.add(new Edge("武汉", "北京", 13)); edgeList.add(new Edge("武汉", "南昌", 12)); edgeList.add(new Edge("南昌", "广州", 18)); Edge[] edgeArray = new Edge[edgeList.size()]; return new Graph(citys, edgeList.toArray(edgeArray), true); } /** * * @param graph * @param start * @param dist * 各个节点到起始节点start的最短距离 * @param path * 各个节点到起始节点start的路径的前一个节点 */ public static void djst(Graph graph, int start, int[] dist, int[] path) { int size = graph.size; int[][] matrix = graph.matrix; int[] visit = new int[size]; // 初始化数组path和dist for (int i = 0; i < size; i++) { dist[i] = matrix[start][i]; if (matrix[start][i] < Graph.MAX) { path[i] = start; } else { path[i] = -1; } } // 前面的for循环将起始节点的path值设为了start // 这里将起始节点的前一个节点为-1 // 整个Djst算法结束后，只有起始节点的path值为-1 path[start] = -1; visit[start] = 1; // 起始节点不需要找，所以我们总共要找(size-1)个节点，故这里n从1开始 for (int n = 1; n < size; n++) { int min = Graph.MAX; int k = -1; // 找出下一个节点 for (int i = 0; i < size; i++) { if (visit[i] == 0 && dist[i] < min) { k = i; min = dist[i]; } } visit[k] = 1; // 找到了最短的节点之后，更新剩下节点的dist距离 for (int i = 0; i < size; i++) { if ((visit[i] == 0) && (dist[k] + matrix[k][i] < dist[i])) { dist[i] = dist[k] + matrix[k][i]; path[i] = k; } } } } /** * 打印出起始结点到每个节点的路径 path[]数组中保存了一棵双亲存储结构的树，默认输出的是叶子节点到根节点路径， * * 我们使用了一个栈，从而实现了逆向输出。 * */ public static void printPath(int[] path, int target) { // int[] stack = new int[path.length]; int pos = -1; int index = target; while (index != -1) { stack[++pos] = index; index = path[index]; } while (pos!=-1) { System.out.print(stack[pos--] + " "); } } }

结果如下：

0 0 1 0 2 0 2 3 0 2 4 0 1 5

注意：Graph.MAX 代表两节点没直接相连时的无穷大距离，一开始我设置的数值是 Graph.MAX  = Integer.Max_Value，但是有一个错误，当执行到

// 找到了最短的节点之后，更新剩下节点的dist距离 for (int i = 0; i < size; i++) { if ((visit[i] == 0) && (dist[k] + matrix[k][i] < dist[i])) { dist[i] = dist[k] + matrix[k][i]; path[i] = k; } } matrix[k][i]的值可能是 Integer.Max_Value,当和dist[k]相加时，得到的结果超过了Int的表示范围， 从而结果是是负数，当然结果就会有错误

故正确设置 Graph.MAX = Integer.Max_Value >>1

6.佛洛依德Floyd --最短路径算法

public class Test { public static void main(String[] args) { Graph graph = createGraph(false); int[][] dist2 = new int[graph.size][graph.size]; int[][] path2 = new int[graph.size][graph.size]; floyd(graph, dist2, path2); for (int i = 0; i < graph.size; i++) { System.out.println(dist2[0][i]); } printFloydPath(path2, 0, 4); } public static void floyd(Graph graph, int[][] dist, int[][] path) { if (graph != null) { int size = graph.size; // 初始化矩阵 path和dist for (int i = 0; i < size; i++) { for (int j = 0; j < size; j++) { path[i][j] = -1; dist[i][j] = graph.matrix[i][j]; } } /** * 下面这个三层循环是本运算的主要操作，完成了以K为中间节点对所有(i,j)进行检测和修改 */ for (int k = 0; k < size; k++) for (int i = 0; i < size; i++) for (int j = 0; j < size; j++) { if (dist[i][k] + dist[k][j] < dist[i][j]) { dist[i][j] = dist[i][k] + dist[k][j]; path[i][j] = k; } } } } /** * 打印两个节点之前的中间节点 * * @param path * @param start * @param end */ public static void printFloydPath(int[][] path, int start, int end) { if (path[start][end] != -1) { int mid = path[start][end]; System.out.println(mid); printFloydPath(path, start, mid); printFloydPath(path, mid, end); } } }

结果如下：

0 11 10 24 19 17 节点0到节点4之间的节点有： 2

二.邻接表

假设有图形结构如下：

源码如下：

/** * 这个类代表一条边，有起始节点和终止节点，以及边的长度 * * 这是从用户角度来看图，用户只知道这种形式的边，不涉及任何指向下一条边的指针 */ public class Edge { String beginCity; String endCity; int cost; public Edge(String beginCity, String endCity, int cost) { super(); this.beginCity = beginCity; this.endCity = endCity; this.cost = cost; } } /** * Arc弧线，代表着下一层的小弟 * target 下一层的小弟是谁 * next 指向下一层的指针 * cost 和下一层的等级差距 * */ public class Arc { String target; Arc next; int cost; public Arc(String target, Arc next, int cost) { super(); this.target = target; this.next = next; this.cost = cost; } } /** * 类Node(value,firstAct) 代表着某个部门， value是这位部门老大的信息,firstAct代表着这个部门老大下面的小弟， * * 类Act代表着一个小弟，类Act中的target 和类Node的value是相同性质的数据， * 只不过value代表老大的个人信息，target代表小弟的个人信息 * * 老大和小弟唯一不同的是：老大没有 cost属性，因为老大是食物链顶端 * * 一个层的小弟在另一个层中就是老大，所以一个小弟的target 肯定会等于某个老大的target * */ public class Node { String value; Arc firstAct; public Node(String value, Arc firstAct) { super(); this.value = value; this.firstAct = firstAct; } public void addNode(String target, int cost) { if (target != null) { if (firstAct == null) { firstAct = new Arc(target, null, cost); } else { // 找到此链表的最后一个节点 Arc arc = firstAct; while (arc.next != null) { arc = arc.next; } arc.next = new Arc(target, null, cost); } } } public static final String TAG_ARROW = "->"; @Override public String toString() { // 无论怎样，就算这个部门没有小弟，至少还有个光杆司令 StringBuilder builder = new StringBuilder(); builder.append(value).append(TAG_ARROW); if (firstAct != null) { Arc arc = firstAct; while (arc != null) { builder.append(arc.target).append(TAG_ARROW); arc = arc.next; } } String str = builder.toString(); return str.substring(0, str.lastIndexOf(TAG_ARROW)); } }

/** * 邻接表表示图型结构可以这样理解： Graph代表一个公司老总，Node就代表一个部门， 老总直接管理着很多个部门 * * 类Node(value,firstAct) 代表着某个部门， value是这位部门老大的信息,firstAct代表着这个部门老大下面的小弟， * * 类Act代表着一个小弟，类Act中的target 和类Node的value是相同性质的数据， * 只不过value代表老大的个人信息，target代表小弟的个人信息 * * 老大和小弟唯一不同的是：老大没有 cost属性，因为老大是食物链顶端 * */ public class Graph { String[] cityArray; Node[] nodeArray; int size; /** * 这是完全模拟从用户角度来建图的过程，用户只知道提供所有城市和城市之间的简单连线， 而我们要做的事，就是将用户提供的这种简单数据变成具有逻辑的结构 * */ public Graph(String[] cityArray, Edge[] edges, boolean direction) { if (cityArray != null && cityArray.length > 0 && edges != null && edges.length > 0) { this.cityArray = cityArray; this.size = cityArray.length; nodeArray = new Node[size]; for (int i = 0; i < nodeArray.length; i++) { nodeArray[i] = new Node(cityArray[i], null); } for (Edge e : edges) { int index = findIndex(e.beginCity, cityArray); nodeArray[index].addNode(e.endCity, e.cost); if (!direction) { index = findIndex(e.endCity, cityArray); nodeArray[index].addNode(e.beginCity, e.cost); } } /** * 注意1 */ } } /** * 找出指定数组中某个元素的位置，如果找不到，则返回-1 */ public int findIndex(String city, String[] cityArray) { for (int i = 0; i < cityArray.length; i++) { if (city.equals(cityArray[i])) return i; } return -1; } public void print() { for (Node node : nodeArray) System.out.println(node); } public void dfs(int start, int[] visit) { Node node = nodeArray[start]; visit[start] = 1; // 接下來是访问节点操作 System.out.print(node.value + " "); Arc arc = node.firstAct; while (arc != null) { int index = findIndex(arc.target, cityArray); if (visit[index] == 0) dfs(index, visit); arc = arc.next; } } /** * 对图执行广度优先级遍历 * * @param start * 遍历开始节点 */ public void bfs(int start) { int visit[] = new int[size]; int[] queue = new int[size]; int front = -1; int tail = -1; // 根节点入队 tail = (tail + 1) % queue.length; queue[tail] = start; visit[start] = 1; while (front != tail) { // 根节点出队 front = (front + 1) % queue.length; int index = queue[front]; // 访问出队节点 System.out.print(cityArray[index] + " "); Arc arc = nodeArray[index].firstAct; while (arc != null) { int ii = findIndex(arc.target, cityArray); if (visit[ii] == 0) { // 下一个节点入队 tail = (tail + 1) % queue.length; queue[tail] = ii; visit[ii] = 1; } arc = arc.next; } } } }

测试代码如下：

public class Test { public static void main(String[] args) { Graph graph = createGraph(true); //建立有向图 System.out.println("图的矩阵如下："); graph.print(); System.out.println("深度优先遍历顺序如下："); int[] visit = new int[graph.size]; graph.dfs(0, visit); System.out.println(""); System.out.println("广度优先遍历顺序如下："); graph.bfs(0); } public static Graph createGraph(boolean direction) { String[] citys = new String[] { "北京", "上海", "广州", "重庆", "武汉", "南昌" }; List<Edge> edgeList = new ArrayList<>(); edgeList.add(new Edge("北京", "上海", 11)); edgeList.add(new Edge("北京", "广州", 10)); edgeList.add(new Edge("上海", "南昌", 6)); edgeList.add(new Edge("广州", "重庆", 14)); edgeList.add(new Edge("广州", "武汉", 9)); edgeList.add(new Edge("重庆", "武汉", 20)); edgeList.add(new Edge("武汉", "北京", 13)); edgeList.add(new Edge("武汉", "南昌", 12)); edgeList.add(new Edge("南昌", "广州", 18)); Edge[] edgeArray = new Edge[edgeList.size()]; return new Graph(citys, edgeList.toArray(edgeArray), direction); } }

执行结果：

图的矩阵如下： 北京->上海->广州 上海->南昌 广州->重庆->武汉 重庆->武汉 武汉->北京->南昌 南昌->广州 深度优先遍历顺序如下： 北京 上海 南昌 广州 重庆 武汉 广度优先遍历顺序如下： 北京 上海 广州 南昌 重庆 武汉

注意1处：这里有一个问题，这里是基于对“边”的遍历，然后挨个插入到适当的部门当中去，这里就要求，边数组必须是排好序的， 比如 citys= {"北京","上海", "广州", "重庆", "武汉", "南昌" },edges 中的边必须是 先(北京，上海)，再(北京，广州)

当我们建立有向图时，“边数组”有序，就没问题，但是如果建立的是无向图，比如本地，如果建立无向图，由于“南昌”的序号最后面，故边（南昌--广州）最后添加，但是人家广州的序号很靠前啊，原本打印“南昌“为首的那条链表，顺序应该是 

南昌->上海->广州->武汉

但实际情况是：

南昌->上海->武汉->广州

所以，如果建成无向图，还需要对每条链表进行排序，让序号小的排在前面