图
一、图的基本概念
线性表和树两类数据结构，线性表中的元>素是“一对一”的关系，树中的元素是“一对多”的关系，本章所述的图结构中的元素则是“多对多”的关系。
图（Graph）是一种复杂的非线性结构，在图结构中，每个元素都可以有零个或多个前驱，也可以有零个或多个后继，也就是说，元素之间的关系是任意的。
无向图：
无向图是由顶点和边构成。
有向图：
有向图是由顶点和有向边构成。
完全图：
如果任意两个顶点之间都存在边叫完全图，有向的边叫有向完全图。如果无重复的边或者顶点到自身的边叫简单图。
图按照有无方向分为无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧尾和弧头之分。
图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。
图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度，有向图顶点分为入度和出度。
图上的边或弧上带权则称为网。
图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环，当中不重复叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称强连通分量。
无向图中连通且n个顶点n-1条边叫生成树。有向图中一顶点入度为0其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林。
二、java实现
1.定义邻接矩阵图结构
static final int MaxNum=20; //图的最大顶点数static final int MaxValue=65535; //最大值class GraphMaterix{int GType; //图的类型（0:无向图 1：有向图）int VertexNum;//顶点数量int EdgeNum; //边的数量char[] Vertex=new char[MaxNum]; //保存顶点信息int[][] EdgeWeight=new int[MaxNum][MaxNum];//保存权
2.创建图
在使用图结构之前。首先需要创建并初始化一个图。代码如下：
public static void creatGraph(GraphMatrix gm){int i,j,k;int weight; //权char startV,endV; //起始，终止顶点System.out.println("输入图中各顶点信息:");for(i=0;i<gm.VertexNum;i++){System.out.println("第"+(i+1)+"个顶点");gm.Vertex[i]=(input.next().toCharArray())[0];//保存到顶点数组中}System.out.println("输入各边的顶点及权值：");for(k=0;k<gm.EdgeNum;k++){System.out.println("第"+(k+1)+"条边");System.out.println("边的起点为：");startV=input.next().charAt(0);System.out.println("边的终点为：");endV=input.next().charAt(0);System.out.println("边的权值为：");weight=input.nextInt();for(i=0;gm.Vertex[i]!=startV;i++); //在顶点数组中查找起点位置for(j=0;gm.Vertex[j]!=endV;j++); //在顶点数组中查找终点位置gm.EdgeWeight[i][j]=weight;if(gm.GType==0){gm.EdgeWeight[j][i]=weight;}}}
时间复杂度O(n+n+e) 其中对邻接矩阵的初始化耗费了O(n)
3.清空图
清空图就是将图结构变成一个空图，这里只需要将矩阵中的各个元素设置为MaxValue即可。代码如下：
static void clearGragh(GraphMatrix gm){
for(int i=0;i<gm.VertexNum;i++)
for(int j=0;j<gm.VertexNum;j++)
gm.EdgeWeight[i][j]=gm.MaxValue; //清空矩阵
}c
4.显示图
显示图就是将图的邻接矩阵打印出来，用户可以通过邻接矩阵方便的了解图的顶点及边等结构的信息。显示图代码如下：
static void outGraph(GraphMatrix gm){
for(int i=0;i<gm.VertexNum;i++){
System.out.printf("\t%c",gm.Vertex[i]); //第一行输出顶点信息
}
System.out.println();
for(int i=0;i<gm.VertexNum;i++){
System.out.printf("%c",gm.Vertex[i]);
for(int j=0;j<gm.VertexNum;j++){
if(gm.EdgeWeight[i][j]==gm.MaxValue){
System.out.printf("\tZ");
}else{
System.out.printf("\t"+gm.EdgeWeight[i][j]);
}
}
System.out.println();
}
}
图的DFS和BFS
1.图的DFS:
即Breadth First Search,深度优先搜索是从起始顶点开始，递归访问其所有邻近节点，比如A节点是其第一个邻近节点，而B节点又是A的一个邻近节点，则DFS访问A节点后再访问B节点，如果B节点有未访问的邻近节点的话将继续访问其邻近节点，否则继续访问A的未访问邻近节点，当所有从A节点出去的路径都访问完之后，继续递归访问除A以外未被访问的邻近节点。
package DFS;
public class Graph {
private int vertexSize;
private int[] vertexs;
private int[][] matrix;
private static final int MAX_WEIGHT=1000;
private boolean[] isVisited;
public Graph(int vertexSize) {
this.vertexSize = vertexSize;
matrix=new int[vertexSize][vertexSize];
vertexs=new int[vertexSize];
for (int i=0;i<vertexSize;i++){
vertexs[i]=i;
}
isVisited=new boolean[vertexSize];
}
/*
* 获取出度
* */
public int getOutDegree(int index){
int degree=0;
for (int j=0;j<matrix[index].length;j++){
int weight=matrix[index][j];
if (weight!=0&&weight<MAX_WEIGHT){
degree++;
}
}
return degree;
}
/*
* 获取权值
* */
public int getWeight(int v1,int v2){
return matrix[v1][v2]==0?0:(matrix[v1][v2]==MAX_WEIGHT?-1:matrix[v1][v2]);
}
/*
* 获取第一个邻接点
* */
public int getFirstNeighbor(int index){
for (int j=0;j<vertexSize;j++){
if (matrix[index][j]>0&&matrix[index][j]<MAX_WEIGHT){
return j;
}
}
return -1;
}
/*
* 获取下一个邻接点
*
* */
public int getNextNeighbor(int v,int index){
for (int j=index+1;j<vertexSize;j++){
if (matrix[v][j]>0&&matrix[v][j]<MAX_WEIGHT){
return j;
}
}
return -1;
}
/*
* 图的深度优先遍历算法
*
* */
private void depthFirstSearch(int i) {
isVisited[i] = true;
int w = getFirstNeighbor( i );
while (w != -1) {
if (!isVisited[w]) {
System.out.println( "访问到了" +w + "顶点" );
depthFirstSearch(w);
}
w = getNextNeighbor( i, w );
}
}
/**
*功能描述
* @author SGJ
* @param
* @return
*/
public void depthFirstSearch() {
isVisited=new boolean[vertexSize];//所有点重置到没有访问的状态
for (int i=0;i<vertexSize;i++){
if (!isVisited[i]){
System.out.println( "访问到了" + i + "顶点" );
depthFirstSearch(i);
}
}
isVisited=new boolean[vertexSize];
}
public int[] getVertexs() {
return vertexs;
}
public void setVertexs(int[] vertexs) {
this.vertexs = vertexs;
}
public static void main(String[] args){
Graph graph=new Graph( 9 );
int [] a1 =new int[]{0,10,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,11,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT};
int [] a2 =new int[]{10,0,18,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,16,MAX_WEIGHT,12};
int [] a3 =new int[]{MAX_WEIGHT,MAX_WEIGHT,0,22,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,8};
int [] a4 =new int[]{MAX_WEIGHT,MAX_WEIGHT,22,0,20,MAX_WEIGHT,MAX_WEIGHT,16,21};
int [] a5 =new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,20,0,26,MAX_WEIGHT,7,MAX_WEIGHT};
int [] a6 =new int[]{11,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,26,0,17,MAX_WEIGHT,MAX_WEIGHT};
int [] a7 =new int[]{MAX_WEIGHT,16,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,17,0,19,MAX_WEIGHT};
int [] a8=new int[]{MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,16,7,MAX_WEIGHT,19,0,MAX_WEIGHT};
int [] a9=new int[]{MAX_WEIGHT,12,8,21,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,MAX_WEIGHT,0};
graph.matrix[0]=a1;
graph.matrix[1]=a2;
graph.matrix[2]=a3;
graph.matrix[3]=a4;
graph.matrix[4]=a5;
graph.matrix[5]=a6;
graph.matrix[6]=a7;
graph.matrix[7]=a8;
graph.matrix[8]=a9;
//System.out.println(graph.getOutDegree( 1 ));
//System.out.println(graph.getWeight( 0, 1));
graph.depthFirstSearch();
}
}
2.图的BFS:
即Breadth First Search，其主要思想是从起始点开始，将其邻近的所有顶点都加到一个队列（FIFO）中去，然后标记下这些顶点离起始顶点的距离为1.最后将起始顶点标记为已访问，今后就不会再访问。然后再从队列中取出最先进队的顶点A，也取出其周边邻近节点，加入队列末尾，将这些顶点的距离相对A再加1，最后离开这个顶点A。依次下去，直到队列为空为止。
/**
*图的广度优先遍历算法 (对外公开)
* @author SGJ
* @param
* @return
*/
public void broadFirstSearch(){
isVisited=new boolean[vertexSize];
for (int i=0;i<vertexSize;i++){
if (!isVisited[i]){
broadFirstSearch(i);
}
}
}
/**
*（内部代码） 广度优先遍历实现
* @author SGJ
* @param
* @return
*/
private void broadFirstSearch(int i){
int u,w;
LinkedList<Integer> que=new LinkedList( );
System.out.println("访问到了"+i+"顶点");
isVisited[i]=true;
que.add( i );
while(!que.isEmpty()){
u=que.removeFirst().intValue();
w=getFirstNeighbor( u );
while(w!=-1) {
if (!isVisited[w]) {
System.out.println("访问到了"+w+"顶点");
que.add( w );
isVisited[w] = true;
}
w=getNextNeighbor( u,w );
}
}
}
最小生成树
一、简介
- 什么是最小生成树
将一个有权图中的 所以顶点 都连接起来，并保证连接的边的 总权重最小，即最小生成树（mini spanning tree）问题。
例如，电子电路设计中，将所有组件的针脚连接在一起，且希望所使用的连线长度最短。 - 图示
如上图（这里借用的是《算法导论》一书中的图）所示，每条边上的数字表示权重。我们使用阴影边连接了所有的顶点，并保证了其总权重是最小的。
注意最小生成树可能并不是唯一的，例如上图中我们就可以将 (b, c) 边换成 (a, h) 边。
二、算法分析
怎么求解
解决最小生成树的问题通常有两种解法：Kruskal 算法和 Prim 算法。它们都属于 贪婪算法，即每次总是寻找局部最优解。下面我们以 Kruskal 算法为例分析和求解该问题。Kruskal 算法
第一步，我们找出 权重最短 的边，并将边的顶点合并到一颗树中，例如 (g, h)；
第二步，在剩余边中继续找出 权重最短 的边，并将边的顶点合并到一颗树中，例如 (c, i)；
重复第二步，直到所有的顶点都合并到同一颗树中。
注意，如果某条边的两个顶点已经在同一颗树中了，则跳过该边，因为加入该边将导致闭环（它的两个顶点已经在同一颗树中连接了，没必要再加这条边了）。
- 过程图解
根据上述过程，我们始终找寻当前满足要求且权重最小的边：
三、代码实现
好了，理论说了这么多看着也乏味，关键是代码要怎么写呢？
1. Edge 类
我们算法最后返回的结果其实就是一个 “边” 的集合。我们很容易想到我们需要一个类来表示图的边，它应该包含两个顶点和权重这些信息，且之后我们需要根据边的权重从小到大排序，所以 Edge 类还应该实现 Comparable 接口。
public class Edge implements Comparable<Edge> {
private Vertex start;
private Vertex end;
private int weight; // 权重
public Edge(Vertex start, Vertex end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
public Vertex getStart() {
return start;
}
public Vertex getEnd() {
return end;
}
@Override
public int compareTo(Edge other) {
return this.weight - other.weight;
}
}
2. Vertex 类
上面 Edge 类里有两个顶点，这个顶点类当然也是需要的。由于算法之后需要判断两个顶点是否在同一个树中，那么最简单的方式就是判断顶点目前所在的树的根结点是否相同即可。
所以我们需要通过 Vertex 类找到树的根结点，可以创建一个 TreeNode 类表示树的结点，然后 Vertex 类继承 TreeNode 类，因为顶点可以看作就是树中的一个叶子结点。
public class Vertex extends TreeNode {
private char value; // 顶点的值
public Vertex(char value) {
this.value = value;
}
public char getValue() {
return value;
}
public TreeNode getRoot() {
TreeNode root = this;
while (root.getParent() != null) {
root = root.getParent();
}
return root;
}
public void setRoot(TreeNode treeNode) {
getRoot().setParent(treeNode);
}
}
其父类为：
public class TreeNode {
protected TreeNode parent;
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
}
3. 场景类
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<Edge> edges = getTestData(); // 获取测试数据
List<Edge> result = miniSpanningTree(edges); // 得到最小生成树
printEdges(result); // 打印最小生成树的边
}
public static List<Edge> miniSpanningTree(List<Edge> edges) {
ArrayList<Edge> result = new ArrayList<>();
Collections.sort(edges); // 根据边权重从小到大排序
for (Edge edge : edges) {
Vertex u = edge.getStart();
Vertex v = edge.getEnd();
// 如果 u 和 v 已经在同一颗树里则跳过
if (u.getRoot() == v.getRoot()) {
continue;
}
result.add(edge);
// 将 u 和 v 放在同一颗树里
// 合并两个树最直接的办法就是使用一个新的根结点，然后连接两个子树
TreeNode newRoot = new TreeNode();
u.setRoot(newRoot);
v.setRoot(newRoot);
}
return result;
}
public static List<Edge> getTestData() {
ArrayList<Edge> list = new ArrayList<>();
Vertex[] vertexes = new Vertex[9];
for (int i = 0; i < vertexes.length; i++) {
// 'a' to 'i'
vertexes[i] = new Vertex((char) (i + 97));
}
list.add(new Edge(vertexes[0], vertexes[1], 4)); // a-b
list.add(new Edge(vertexes[0], vertexes[7], 8)); // a-h
list.add(new Edge(vertexes[1], vertexes[2], 8)); // b-c
list.add(new Edge(vertexes[1], vertexes[7], 11)); // b-h
list.add(new Edge(vertexes[2], vertexes[3], 7)); // c-d
list.add(new Edge(vertexes[2], vertexes[5], 4)); // c-f
list.add(new Edge(vertexes[2], vertexes[8], 2)); // c-i
list.add(new Edge(vertexes[3], vertexes[4], 9)); // d-e
list.add(new Edge(vertexes[3], vertexes[5], 14)); // d-f
list.add(new Edge(vertexes[4], vertexes[5], 10)); // e-f
list.add(new Edge(vertexes[5], vertexes[6], 2)); // f-g
list.add(new Edge(vertexes[6], vertexes[7], 1)); // g-h
list.add(new Edge(vertexes[6], vertexes[8], 6)); // g-i
list.add(new Edge(vertexes[7], vertexes[8], 7)); // h-i
return list;
}
public static void printEdges(List<Edge> edges) {
for (int i = 0; i < edges.size(); i++) {
Edge edge = edges.get(i);
System.out.println("(" + edge.getStart().getValue() + ", " + edge.getEnd().getValue() + ")");
}
}
}
4.执行结果
(g, h)
(c, i)
(f, g)
(a, b)
(c, f)
(c, d)
(a, h)
(d, e)
上面是普里姆算法的最小生成树
下面是克鲁斯卡尔算法的最小生成树：
图的邻接矩阵表示法（无向图，上三角矩阵）
int[][] arr = new int[][] {
{ -1, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 0, -1, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 0, -1, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 0, -1, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 0, -1, 10, 0, 0, 0 },
{ 0, 0, 0, 0, 0, -1, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 0, -1, 1, 6 },
{ 0, 0, 0, 0, 0, 0, 0, -1, 7 },
{ 0, 0, 0, 0, 0, 0, 0, 0, -1 }
};
1.普里姆算法（加点法）
需求：求出最小生成树的权值
输入参数：二维数组arr（邻接矩阵），列表list（存放已经被加入的点），整型sum（存放权值）
输出参数：整型数组parent
1）先找一个起点，这个起点为任意一点，放入list中
2）如果list中不包含全部节点，进入循环
1>遍历list中节点，查找不存在list中的邻接节点的最小值，记录下begin和end
2>将begin和end放入数组中，较小值节点赋值给较大值所在数组位置
3）返回parent
实现:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 普里姆（Prim）算法
*
* @author Xiong YuSong
* 2019/3/22 16:02
*/
public class Prim {
public static void main(String[] args) {
int[][] arr = new int[][]{
{-1, 4, 0, 0, 0, 0, 0, 8, 0},
{0, -1, 8, 0, 0, 0, 0, 11, 0},
{0, 0, -1, 7, 0, 4, 0, 0, 2},
{0, 0, 0, -1, 9, 14, 0, 0, 0},
{0, 0, 0, 0, -1, 10, 0, 0, 0},
{0, 0, 0, 0, 0, -1, 2, 0, 0},
{0, 0, 0, 0, 0, 0, -1, 1, 6},
{0, 0, 0, 0, 0, 0, 0, -1, 7},
{0, 0, 0, 0, 0, 0, 0, 0, -1}
};
List<Integer> list = new ArrayList<>();
//先将0放置在list中
list.add(0);
int begin = 0, end = 0, weight;
int[] parent = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
parent[i] = -1;
}
while (list.size() < arr.length) {
weight = Integer.MAX_VALUE;
for (Integer row : list) {
for (int i = 0; i < arr.length; i++) {
if (!list.contains(i)) {
if (i >= row + 1) {
if (arr[row][i] > 0 && arr[row][i] < weight) {
begin = row;
end = i;
weight = arr[row][i];
}
} else if (i <= row - 1) {
//我这里只用了上三角矩阵，所以这里需要画蛇添足写这一部分
if (arr[i][row] > 0 && arr[i][row] < weight) {
begin = row;
end = i;
weight = arr[i][row];
}
}
}
}
}
list.add(end);
parent[end] = begin;
}
System.out.println(Arrays.toString(parent));
}
}
2.克鲁斯卡尔算法（加边法）
需求：求出最小生成树的权值
构建类：Edge
输入参数：存放有Edge的列表list，并查集parent
输出参数：并查集parent（最小生成树的数组表现形式）
原理：贪心算法的实现，程序中使用了并查集（判断两个集合中是否存在相同的数据）这种特殊的数据结构，使用数组实现
1）创建一个三元组<起始点，终止点，权值>，将邻接矩阵中数据放入三元组中，再放入list中，根据权值进行排序
2）创建变量count=0，整型数组parent
3）如果list中还存在值，则进行循环
1>判断begin和end是否存在于不同的集合中（判断是否在同一棵树中，即判断当前节点在并查集parent中的根节点是否为同一个）
2>如果存在不同的集合中，则将较小值节点赋值给较大值所在数组位置，较小值节点为较大值节点的父节点
4）返回parent
实现:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
/**
* @author Xiong YuSong
* 2019/3/22 17:04
*/
class Edge implements Comparable<Edge> {
//起始点
private int begin;
//终止点
private int end;
//权值
private int weight;
public Edge(int begin, int end, int weight) {
this.begin = begin;
this.end = end;
this.weight = weight;
}
public int getBegin() {
return begin;
}
public void setBegin(int begin) {
this.begin = begin;
}
public int getEnd() {
return end;
}
public void setEnd(int end) {
this.end = end;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
@Override
public int compareTo(Edge o) {
if (o.weight > this.weight) {
return -1;
} else {
return 1;
}
}
}
public class Kruskal {
public static void main(String[] args) {
//默认以a为根节点的最小生成树
List<Edge> list = new ArrayList<>();
int[][] arr = new int[][]{
{-1, 4, 0, 0, 0, 0, 0, 8, 0},
{0, -1, 8, 0, 0, 0, 0, 11, 0},
{0, 0, -1, 7, 0, 4, 0, 0, 2},
{0, 0, 0, -1, 9, 14, 0, 0, 0},
{0, 0, 0, 0, -1, 10, 0, 0, 0},
{0, 0, 0, 0, 0, -1, 2, 0, 0},
{0, 0, 0, 0, 0, 0, -1, 1, 6},
{0, 0, 0, 0, 0, 0, 0, -1, 7},
{0, 0, 0, 0, 0, 0, 0, 0, -1}
};
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i][j] > 0) {
list.add(new Edge(i, j, arr[i][j]));
}
}
}
Collections.sort(list);
//数组中每一个节点都只知道他的父节点是什么，-1表示不存在父节点，0位置是根节点
int[] parent = new int[arr.length];
for (int i = 1; i < arr.length; i++) {
parent[i] = -1;
}
int m = 0, n = 0;
for (Edge edge : list) {
//寻找这两个点有没有相同的父节点
m = find(parent, edge.getBegin());
n = find(parent, edge.getEnd());
if (m != n && parent[edge.getEnd()]>0) { //如果相等则证明已经形成环路
parent[edge.getEnd()] = edge.getBegin();
}
}
System.out.println(Arrays.toString(parent));
}
private static int find(int[] parent, int ch) {
while (parent[ch] > 0) {
ch = parent[ch]; //这里一直在查找没有连线的点
}
return ch;
}
}
最短路径的概念
最短路径的问题是比较典型的应用问题。在图中，确定了起始点和终点之后，一般情况下都可以有很多条路径来连接两者。而边或弧的权值最小的那一条路径就称为两点之间的最短路径，路径上的第一个顶点为源点，最后一个顶点为终点。
图的最短路径的算法有很多，本文主要介绍狄克斯特拉（Dijkstra）提出的一种按照长度递增的次序产生的最短路径的算法。\
狄克斯特拉（Dijkstra）算法
package everyday;
public class Dijkstra {
/*
* 参数adjMatrix:为图的权重矩阵，权值为-1的两个顶点表示不能直接相连
* 函数功能：返回顶点0到其它所有顶点的最短距离，其中顶点0到顶点0的最短距离为0
* []P:为前驱顶点下标
*/
public int[] getShortestPaths(int[][] adjMatrix) {
//用来初始化
int[] result = new int[adjMatrix.length]; // 用于存放顶点0到其它顶点的最短距离
boolean[] used = new boolean[adjMatrix.length]; // 用于判断顶点是否被遍历
used[0] = true; // 表示顶点0已被遍历
int[] P = new int[adjMatrix.length];//为前驱顶点下标
for (int i = 1; i < adjMatrix.length; i++) {
result[i] = adjMatrix[0][i];
used[i] = false;
P[i] = -1;
}
for (int i = 1; i < adjMatrix.length; i++) {
int min = Integer.MAX_VALUE; // 用于暂时存放顶点0到i的最短距离，初始化为Integer型最大值
int k = 0;
for (int j = 1; j < adjMatrix.length; j++) { // 找到顶点0到其它顶点中距离最小的一个顶点
if (!used[j] && result[j] != -1 && min > result[j]) {
min = result[j];
k = j;
}
}
used[k] = true; // 将距离最小的顶点，记为已遍历
for (int j = 1; j < adjMatrix.length; j++) { // 然后，将顶点0到其它顶点的距离与加入中间顶点k之后的距离进行比较，更新最短距离
if (!used[j]) { // 当顶点j未被遍历时
// 首先，顶点k到顶点j要能通行；这时，当顶点0到顶点j的距离大于顶点0到k再到j的距离或者顶点0无法直接到达顶点j时，更新顶点0到顶点j的最短距离
if (adjMatrix[k][j] != -1 && (result[j] > min + adjMatrix[k][j] || result[j] == -1)) {
result[j] = min + adjMatrix[k][j];
P[j] = k;
}
}
}
}
System.out.println("路径:");
for (int i : P) {
System.out.print(+i + " ");
}
System.out.println();
return result;
}
public static void main(String[] args) {
Dijkstra test = new Dijkstra();
int[][] adjMatrix = {
{ 0, 1, 5, -1, -1, -1, -1, -1, -1 },
{ 1, 0, 3, 7, 5, -1, -1, -1, -1 },
{ 5, 3, 0, -1, 1, 7, -1, -1, -1 },
{ -1, 7, -1, 0, 2, -1, 3, -1, -1 },
{ -1, 5, 1, 2, 0, 3, 6, 9, -1 },
{ -1, -1, 7, -1, 3, 0, -1, 5, -1 },
{ -1, -1, -1, 3, 6, -1, 0, 2, 7 },
{ -1, -1, -1, -1, 9, 5, 2, 0, 4 },
{ -1, -1, -1, -1, -1, -1, 7, 4, 0 } };
int[] result = test.getShortestPaths(adjMatrix);
System.out.println("顶点0到图中所有顶点之间的最短距离为：");
for (int i = 0; i < result.length; i++)
System.out.print(result[i] + " ");
}
}
弗洛伊德(Floyd)算法
public class Floyd {
//矩阵大小 图中点数
int num ;
//距离矩阵
int distance[][] ;
//父母矩阵
int parent[][] ;
/*
* 构造方法
*/
public Floyd() {
super();
distance = new int[0][0];
parent = new int[0][0];
}
public Floyd(int[][] distance, int[][] parent) {
super();
this.distance = distance;
this.parent = parent;
}
public Floyd(int num) {
super();
this.num = num;
this.distance = new int[num][num];
this.parent = new int[num][num];
}
/*
* 初始化所有矩阵方法
*/
private void initialize() {
for(int i = 0 ; i < distance.length ; i++ ){
for(int j = 0 ; j < distance.length ; j++ ){
parent[i][j] = j ;
}
}
}
/*
* 三次循环找到所有最短路径
*/
public void findShort() {
//更新矩阵
initialize();
//三个循环 设定所有
for (int temp = 0; temp < distance.length; temp++) {
for (int i = 0; i < distance.length; i++) {
for (int j = 0; j < distance.length; j++) {
if (distance[i][temp]!= Integer.MAX_VALUE && distance[temp][j]!= Integer.MAX_VALUE) {
if (distance[i][j] > ( distance[i][temp] + distance[temp][j] )) {
distance[i][j] = ( distance[i][temp] + distance[temp][j] );//将两点间权值设更小一个
parent[i][j] = parent[i][temp];//路径设置为经过下标为temp的顶点
}
}
}
}
}
}
/*
* get set 方法
*/
public int[][] getDiatance() {
return distance;
}
public void setDiatance(int[][] diatance) {
this.distance = diatance;
}
public int[][] getParent() {
return parent;
}
public void setParent(int[][] parent) {
this.parent = parent;
}
}
另一个例子:
public class FloydAlgorithm {
public static int MaxValue = 100000;
public static int[][] path;
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("请输入顶点数和边数:");
//顶点数
int vertex = input.nextInt();
//边数
int edge = input.nextInt();
int[][] matrix = new int[vertex][vertex];
//初始化邻接矩阵
for (int i = 0; i < vertex; i++) {
for (int j = 0; j < vertex; j++) {
matrix[i][j] = MaxValue;
}
}
//初始化路径数组
path = new int[matrix.length][matrix.length];
//初始化边权值
for (int i = 0; i < edge; i++) {
System.out.println("请输入第" + (i + 1) + "条边与其权值:");
int source = input.nextInt();
int target = input.nextInt();
int weight = input.nextInt();
matrix[source][target] = weight;
}
//调用算法计算最短路径
floyd(matrix);
}
//非递归实现
public static void floyd(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
path[i][j] = -1;
}
}
for (int m = 0; m < matrix.length; m++) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
if (matrix[i][m] + matrix[m][j] < matrix[i][j]) {
matrix[i][j] = matrix[i][m] + matrix[m][j];
//记录经由哪个点到达
path[i][j] = m;
}
}
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix.length; j++) {
if (i != j) {
if (matrix[i][j] == MaxValue) {
System.out.println(i + "到" + j + "不可达");
} else {
System.out.print(i + "到" + j + "的最短路径长度是：" + matrix[i][j]);
System.out.print("最短路径为：" + i + "->");
findPath(i, j);
System.out.println(j);
}
}
}
}
}
//递归寻找路径
public static void findPath(int i, int j) {
int m = path[i][j];
if (m == -1) {
return;
}
findPath(i, m);
System.out.print(m + "->");
findPath(m, j);
}
}
拓扑排序
拓扑排序是针对有向无圈图的顶点的一种排序，使得如果存在一条从A到B的路径，那么在排序中A必定在B的前面。
一个简单的拓扑排序的方案(Kahn算法)是：先找出任意一个没有入边的顶点，然后打印该顶点，并将它及其边一起从图中剔除，然后对其余的部分继续这个操作。
方法实现:
实现原理：不断地做这样一件事，在余下的有向图中求取一个源（source）（PS：定义入度为0的顶点为有向图的源），它是一个没有输入边的顶点，然后把它和所有从它出发的边都删除。（如果有多个这样的源，可以任意选择一个。如果这样的源不存在，算法停止，此时该问题无解），下面给出《算法设计与分析基础》第三版上一个配图：
package com.liuzhen.chapterFour;
import java.util.Stack;
public class TopologicalSorting {
//方法1：基于减治法：寻找图中入度为0的顶点作为即将遍历的顶点，遍历完后，将此顶点从图中删除
/*
* 参数adjMatrix:给出图的邻接矩阵值
* 参数source:给出图的每个顶点的入度值
* 该函数功能：返回给出图的拓扑排序序列
*/
public char[] getSourceSort(int[][] adjMatrix,int[] source){
int len = source.length; //给出图的顶点个数
char[] result = new char[len]; //定义最终返回路径字符数组
int count = 0; //用于计算当前遍历的顶点个数
boolean judge = true;
while(judge){
for(int i = 0;i < source.length;i++){
if(source[i] == 0){ //当第i个顶点入度为0时，遍历该顶点
result[count++] = (char) ('a'+i);
source[i] = -1; //代表第i个顶点已被遍历
for(int j = 0;j < adjMatrix[0].length;j++){ //寻找第i个顶点的出度顶点
if(adjMatrix[i][j] == 1)
source[j] -= 1; //第j个顶点的入度减1
}
}
}
if(count == len)
judge = false;
}
return result;
}
/*
* 参数adjMatrix:给出图的邻接矩阵值
* 函数功能：返回给出图每个顶点的入度值
*/
public int[] getSource(int[][] adjMatrix){
int len = adjMatrix[0].length;
int[] source = new int[len];
for(int i = 0;i < len;i++){
//若邻接矩阵中第i列含有m个1，则在该列的节点就包含m个入度，即source[i] = m
int count = 0;
for(int j = 0;j < len;j++){
if(adjMatrix[j][i] == 1)
count++;
}
source[i] = count;
}
return source;
}
public static void main(String[] args){
TopologicalSorting test = new TopologicalSorting();
int[][] adjMatrix = {{0,0,1,0,0},{0,0,1,0,0},{0,0,0,1,1},{0,0,0,0,1},{0,0,0,0,0}};
int[] source = test.getSource(adjMatrix);
System.out.println("给出图的所有节点（按照字母顺序排列）的入度值：");
for(int i = 0;i < source.length;i++)
System.out.print(source[i]+"\t");
System.out.println();
char[] result = test.getSourceSort(adjMatrix, source);
System.out.println("给出图的拓扑排序结果：");
for(int i = 0;i < result.length;i++)
System.out.print(result[i]+"\t");
}
}
关键路径算法原理
对于一个活动来说，有活动的最早开始时间和最晚开始时间，比较这个活动的最早开始时间和最晚开始时间，如果最早开始时间和最晚开始时间相等，那么就意味着该活动是关键活动，活动间的路径为关键路径。如果不相等，那么这个活动就不是关键活动。
名词解释
- 事件的最早发生时间etv：即顶点v_kvk的最早发生时间
- 事件的最晚发生时间ltv：即顶点v_kvk的最晚发生时间，也就是每个顶点对应的事件最晚需要开始的时间，超过此时间将会延误整个工期。
- 活动的最早开工时间ete：即弧a_kak的最早发生时间
- 活动的最晚开工时间lte：即弧a_kak的最晚发生时间，也就是不推迟工期的最晚开工时间。
求关键路径的步骤
- 根据图的描述建立该图的邻接表
- 从源点v_0v0出发，根据拓扑序列算法求源点到汇点每个顶点的etv，如果得到的拓扑序列个数小于网的顶点个数，则该网中存在环，无关键路径，结束程序。
- 从汇点v_nvn出发，且ltv[n-1]=etv[n-1]，按照逆拓扑序列，计算每个顶点的ltv。
- 根据每个顶点的etv和ltv求每条弧的ete和lte，若ete=lte，说明该活动是关键活动。
代码实现
边表节点：
public class EdgeNode {
public int adjevex;
public int weight;
public EdgeNode next;
public EdgeNode(int adjevex, EdgeNode next) {
this.adjevex = adjevex;
this.next = next;
}
public EdgeNode(int adjevex, int weight, EdgeNode next) {
this.adjevex = adjevex;
this.weight = weight;
this.next = next;
}
}
顶点节点：
public class VertexNode {
public int in;
public Object data;
public EdgeNode firstedge;
public VertexNode(Object data, int in, EdgeNode firstedge) {
this.data = data;
this.in = in;
this.firstedge = firstedge;
}
}
通过拓扑排序求得etv
public boolean ToplogicalSort() {
EdgeNode e;
int k, gettop;
int count = 0;
etv = new int[adjList.length];
for (int i = 0; i < adjList.length; i++) {
if(adjList[i].in == 0) {
stack.push(i);
}
}
for (int i = 0; i < adjList.length; i++) {
etv[i] = 0;
}
while(!stack.isEmpty()) {
gettop = (int) stack.pop();
count++;
stack2.push(gettop);
for (e = adjList[gettop].firstedge; e != null; e = e.next) {
k = e.adjevex;
if((--adjList[k].in) == 0) {
stack.push(k);
}
if(etv[gettop] + e.weight > etv[k]) {
etv[k] = etv[gettop] + e.weight;
}
}
}
if(count < adjList.length) return false;
else return true;
}
关键路径算法：
public void CriticalPath() {
EdgeNode e;
int gettop, k, j;
int ete, lte;
if(!this.ToplogicalSort()) {
System.out.println("该网中存在回路!");
return;
}
ltv = new int[adjList.length];
for (int i = 0; i < adjList.length; i++) {
ltv[i] = etv[etv.length - 1];
}
while(!stack2.isEmpty()) {
gettop = (int) stack2.pop();
for(e = adjList[gettop].firstedge; e != null; e = e.next) {
k = e.adjevex;
if(ltv[k] - e.weight < ltv[gettop]) {
ltv[gettop] = ltv[k] - e.weight;
}
}
}
for (int i = 0; i < adjList.length; i++) {
for(e = adjList[i].firstedge; e != null; e = e.next) {
k = e.adjevex;
ete = etv[i];
lte = ltv[k] - e.weight;
if(ete == lte) {
System.out.print("<" + adjList[i].data + "," + adjList[k].data + "> length: " + e.weight + ",");
}
}
}
}
完整代码：
public class CriticalPathSort {
int[] etv, ltv;
Stack stack = new Stack(); //存储入度为0的顶点，便于每次寻找入度为0的顶点时都遍历整个邻接表
Stack stack2 = new Stack(); //将顶点序号压入拓扑序列的栈
static VertexNode[] adjList;
public boolean ToplogicalSort() {
EdgeNode e;
int k, gettop;
int count = 0;
etv = new int[adjList.length];
for (int i = 0; i < adjList.length; i++) {
if(adjList[i].in == 0) {
stack.push(i);
}
}
for (int i = 0; i < adjList.length; i++) {
etv[i] = 0;
}
while(!stack.isEmpty()) {
gettop = (int) stack.pop();
count++;
stack2.push(gettop);
for (e = adjList[gettop].firstedge; e != null; e = e.next) {
k = e.adjevex;
if((--adjList[k].in) == 0) {
stack.push(k);
}
if(etv[gettop] + e.weight > etv[k]) {
etv[k] = etv[gettop] + e.weight;
}
}
}
if(count < adjList.length) return false;
else return true;
}
public void CriticalPath() {
EdgeNode e;
int gettop, k, j;
int ete, lte;
if(!this.ToplogicalSort()) {
System.out.println("该网中存在回路!");
return;
}
ltv = new int[adjList.length];
for (int i = 0; i < adjList.length; i++) {
ltv[i] = etv[etv.length - 1];
}
while(!stack2.isEmpty()) {
gettop = (int) stack2.pop();
for(e = adjList[gettop].firstedge; e != null; e = e.next) {
k = e.adjevex;
if(ltv[k] - e.weight < ltv[gettop]) {
ltv[gettop] = ltv[k] - e.weight;
}
}
}
for (int i = 0; i < adjList.length; i++) {
for(e = adjList[i].firstedge; e != null; e = e.next) {
k = e.adjevex;
ete = etv[i];
lte = ltv[k] - e.weight;
if(ete == lte) {
System.out.print("<" + adjList[i].data + "," + adjList[k].data + "> length: " + e.weight + ",");
}
}
}
}
public static EdgeNode getAdjvex(VertexNode node) {
EdgeNode e = node.firstedge;
while(e != null) {
if(e.next == null) break;
else
e = e.next;
}
return e;
}
public static void main(String[] args) {
int[] ins = {0, 1, 1, 2, 2, 1, 1, 2, 1, 2};
int[][] adjvexs = {
{2, 1},
{4, 3},
{5, 3},
{4},
{7, 6},
{7},
{9},
{8},
{9},
{}
};
int[][] widths = {
{4, 3},
{6, 5},
{7, 8},
{3},
{4, 9},
{6},
{2},
{5},
{3},
{}
};
adjList = new VertexNode[ins.length];
for (int i = 0; i < ins.length; i++) {
adjList[i] = new VertexNode("V"+i, ins[i],null);
if(adjvexs[i].length > 0) {
for (int j = 0; j < adjvexs[i].length; j++) {
if(adjList[i].firstedge == null)
adjList[i].firstedge = new EdgeNode(adjvexs[i][j], widths[i][j], null);
else {
getAdjvex(adjList[i]).next = new EdgeNode(adjvexs[i][j], widths[i][j], null);
}
}
}
}
CriticalPathSort c = new CriticalPathSort();
c.CriticalPath();
}
}
若有收获，就点个赞吧
0 人点赞
