图相关算法

发表于 | 分类于 ，

图简介：

　　图的表示方式：
　　　　邻接矩阵
　　　　邻接表
　　图的代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Graph {
	// 存储定点集合
	private ArrayList<String> vertexList;
	// 存储图对应的邻接矩阵
	private int[][] edges;
	// 表示边的数目
	private int numOfEdges;
	// 标记结点是否被访问过
	private boolean[] isVisited;
	// 构造器
	public Graph(int n) {
		vertexList = new ArrayList<>(n);
		edges = new int[n][n];
		numOfEdges = 0;
		isVisited = new boolean[n];
	}
	
	// 插入节点
	public void insertVertex(String vertex) {
		vertexList.add(vertex);
	}
	// 添加边
	public void insertEdge(int v1,int v2,int weight) {
		edges[v1][v2] = weight;
		edges[v1][v2] = weight;
		numOfEdges++;
	}
	// 得到第一个邻接结点的下标w
	public int getFirstNeighbor(int index) {
		for(int j = 0;j < vertexList.size();j++) {
			if (edges[index][j] > 0) {
				return j;
			}
		}
		return -1;
	}
	// 根据前一个邻接结点的下标来获取下一个邻接结点
	public int getNextNeighbor(int v1,int v2) {
		for(int j = v2+1;j < vertexList.size();j++) {
			if (edges[v1][j] > 0) {
				return j;
			}
		}
		return -1;
	}
}

深度优先搜索（DFS）：

　　深度优先遍历，从初始访问结点出发，初始访问结点可能有多个邻接结点，深度优先遍历的策略就是首先访问第一个邻接结点，然后再以这个被访问的邻接
结点作为初始结点，访问它的第一个邻接结点。可以理解为：每次都在访问完当前结点后首先访问当前结点的第一个结点。
　　很明显，深度优先遍历是一个递归的过程。

算法步骤：

　　1.访问初始结点v，并标记结点v为已访问
　　2.查找v的第一个邻接结点w
　　3.若w存在，则继续执行4，如果w不存在，则回到第一步，将从v的下一个节点继续。
　　4.若w未被访问，对w进行深度优先遍历递归
　　5.查找节点v的w邻接结点的下一个邻接结点，转到步骤3.

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
private void dfs(boolean[] isVisited,int i) {
	// 首先输出初始结点
	System.out.print(vertexList.get(i) + " ");
	// 将结点设置为已访问
	isVisited[i] = true;
	// 查找结点i的第一个邻接结点
	int w = getFirstNeighbor(i);
	while(w != -1) {
		if (!isVisited[w]) {
			dfs(isVisited, w);
		}
		w = getNextNeighbor(i, w);
	}
	
}

// 对dfs进行一个重载，遍历我们所有的结点，并进行dfs
public void dfs() {
	// 遍历所有的结点，进行dfs(回溯)
	for(int i = 0;i < vertexList.size();i++) {
		if (!isVisited[i]) {
			dfs(isVisited,i);
		}
	}
}

广度优先搜索（BFS）

　　图的广度优先搜索类似于树的层序遍历，即访问初始结点后，再依次访问初始结点的邻接结点，当前结点的所有邻接结点访问完成之后，再访问第一个邻接
结点的所有结点，以此类推。

算法算法步骤

　　1.访问初始结点v并标记为已访问
　　2.结点v入队列
　　3.当队列非空时，继续执行，否则算法结束。。。。。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// bfs
private void bfs(boolean[] isVisited,int i) {
	int u; // 表示队列头结点
	int w; // 表示邻接结点
	Queue<Integer> queue = new LinkedList<>();
	System.out.println(vertexList.get(i));
	isVisited[i] = true;
	queue.add(i);
	while(!queue.isEmpty()) {
		u = queue.poll();
		w = getFirstNeighbor(u);
		while(w != -1) {
			if (!isVisited[w]) {
				System.out.println(vertexList.get(w));
				isVisited[w] = true;
				queue.add(w);
			}
			w = getNextNeighbor(u, w);
		}
	}
}
public void bfs() {
	for(int i = 0;i < vertexList.size();i++) {
		if (!isVisited[i]) {
			bfs(isVisited, i);
		}
	}
}

普里姆算法（Prim）

　　普里姆算法用来求图的最小生成树。该算法的核心思想为贪心。
　　该算法首先从某一起始结点出发，遍历邻接结点，找出最小的边，并把该结点标记为已访问；然后再以这两个结点为起始结点，分别遍历它们的邻接结点，找出最小的边，
并把该结点标记为已访问，以此类推。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Prim {
	public void prim(Graph graph,int v) {
		int[] isVisited = new int[graph.getSize()];
		isVisited[v] = 1;
		// 
		int h1 = -1;
		int h2 = -1;
		int minWeight = 10000;
		for(int k = 1;k < graph.getSize();k++) {
			for(int i = 0;i < graph.getSize();i++) {
				for(int j = 0;j < graph.getSize();j++) {
					if (isVisited[i] == 1 && isVisited[j] == 0 && graph.getWeight(i, j) < minWeight) {
						minWeight = graph.getWeight(i, j);
						h1 = i;
						h2 = j;
					}
				}
			}
			System.out.println("边<"+graph.getByIndex(h1)+","+graph.getByIndex(h2)+">权值："+minWeight);
			isVisited[h2] = 1;
			minWeight = 10000;
		}
	}

克鲁斯卡尔（Kruskal）算法

　　该算法也是用来求最小生成树，该算法同样用到了贪心思想。
　　该算法的实现为：首先要对图的所有边权值进行排序，然后依次从小到大取边组成最小生成树，在取的同时还要进行判断是否构成回路的操作，如果构成了回路则要跳过该条边。
　　注意：判断是否构成回路的算法是理解难点。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Kruskal {
	public void kruskal(Graph graph) {
		int index = 0;
		int[] ends = new int[graph.getSize()];
		EData[] result = new EData[graph.getSize()-1];
		
		EData[] edges = graph.getEdges();
		System.out.println("图的边的集合"+Arrays.toString(edges));
		graph.sortEdges(edges);
		System.out.println("排序后边的集合："+Arrays.toString(edges));
		for(int i = 0;i < graph.getNumOfedges();i++) {
			int p1 = graph.getPosition(edges[i].start);
			int p2 = graph.getPosition(edges[i].end);
			int m = graph.getEnd(ends, p1);
			int n = graph.getEnd(ends, p2);
			System.out.println("m:"+m+" n:" + n);
			if (m != n) {
				result[index++] = edges[i];
				ends[m] = n;
			}
		}
		System.out.println(Arrays.toString(ends));
		System.out.println("kruskal:"+Arrays.toString(result));
	}
}

迪杰斯特拉（Dijkstra）算法：

　　该算法用来求某一结点到其他结点的最短路径。
　　该算法用到了BFS的思想。它以起始点为中心，向外层层扩展。每次先获取到各结点路径中最短的路径，再在此最短路径基础上更新到其他路径的最短路径。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Dijkstra {
	public void dijkstra(Graph graph,int v) {
		int n = graph.getSize();
		// 出发点到各顶点的最短距离
		int[] minPath = new int[n];
		// 各顶点的前驱节点下标
		int[] preNode = new int[n];
		// 是否已找到初始顶点到各顶点的最短路径，0表示未找到，1表示已找到。
		int[] finded = new int[n];
		for(int i = 0;i < n;i++) {
			finded[i] = 0;
			minPath[i] = graph.getWeight(v, i);
			preNode[i] = 0;
		}
		minPath[v] = 0;
		finded[v] = 1;
		int k = 0;
		int min = 10000;
		for(int i = 1;i < n;i++) {
			// 这里为了方便用10000表示无穷大
			min = 10000;
			// 在未找出最小路径的结点中找出路径最小的结点，将其作为初始结点，进行层序遍历，找出最短路径。
			for(int j = 0;j < n;j++) {
				if (finded[j] == 0 && minPath[j] < min) {
					k = j;
					min = minPath[j];
				}
			}
			// 将结点k标记为已找到
			finded[k] = 1;
			for(int j = 0;j < n;j++) {
				if (finded[j] == 0 && (min+graph.getWeight(k, j)) < minPath[j]) {
					minPath[j] = min+graph.getWeight(k, j);
					preNode[j] = k;
				}
			}
		}
		System.out.println(Arrays.toString(minPath));
	}
}

弗洛伊德（Floyd）算法：

　　核心思想：选取中间结点，比较两个结点本身路径长度与经过中间节点的路径的大小，如果经过中间结点的距离更小， 则更新最短路径矩阵和最短路径前驱结点矩阵。 　　

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Floyd {
	public void floyd(Graph graph) {
		int n = graph.getSize();
		// 最短路径长度矩阵
		int[][] minPath = new int[n][n];
		// 最短路径前驱结点矩阵
		int[][] preNode = new int[n][n];
		// 初始化最短路径长度矩阵和最短路径前驱结点矩阵
		for(int i = 0;i < n;i++) {
			for(int j = 0;j < n;j++) {
				minPath[i][j] = graph.getWeight(i, j);
				preNode[i][j] = j;
			}
		}
		// 核心思想：选取中间结点，比较两个结点本身路径长度与经过中间节点的路径的大小，如果经过中间结点的距离更小，
		// 则更新最短路径矩阵和最短路径前驱结点矩阵。
		for(int k = 0;k < n;k++) {
			for(int i = 0;i < n;i++) {
				for(int j = 0;j < n;j++) {
					if (minPath[i][j] > minPath[i][k] + minPath[k][j]) {
						minPath[i][j] = minPath[i][k] + minPath[k][j];
						preNode[i][j] = k;
					}
				}
			}
		}
		System.out.println("最短路径矩阵：");
		for(int[] link:minPath) {
			System.out.println(Arrays.toString(link));
		}
		System.out.println("最短路径前驱结点矩阵");
		for(int[] link:preNode) {
			System.out.println(Arrays.toString(link));
		}
	}
}