图遍历算法 ---- DFS & BFS...
public class GraphTraveler {
LinkedList<Integer> open = new LinkedList<Integer>();
public void bfs(Graph g, int start) {
int n = g.getVolume();
Graph tree = new Graph(n, false);
boolean[] visited = new boolean[n];
Arrays.fill(visited, false);
open.add(start);
visited[start] = true;
while (!open.isEmpty()) {
int now = open.poll();
System.out.print(now + ", ");
List<int[]> nexts = g.getAdjs(now);
for (int[] e : nexts) {
if (!visited[e[1]]) {
open.add(e[1]);
visited[e[1]] = true;
tree.addEdge(e[0], e[1], e[2]);
}
}
}
System.out.println(tree);
}
public void dfs(Graph g, int start) {
int n = g.getVolume();
Graph tree = new Graph(n, false);
boolean[] visited = new boolean[n];
Arrays.fill(visited, false);
open.add(start);
visited[start] = true;
while (!open.isEmpty()) {
int now = open.pop();
System.out.print(now + ", ");
List<int[]> nexts = g.getAdjs(now);
for (int[] e : nexts) {
if (!visited[e[1]]) {
open.push(e[1]);
visited[e[1]] = true;
tree.addEdge(e[0], e[1], e[2]);
}
}
}
System.out.println(tree);
}
public static void main(String[] args) {
GraphTraveler t = new GraphTraveler();
Graph g = new Graph(9, false);
int[][] edges = {{0,1,4},{0,7,8},{1,2,8},{1,7,11},
{2,3,7},{2,5,4},{2,8,2},{3,4,9},{3,5,14},
{4,5,10},{5,6,2},{6,7,1},{6,8,6},{7,8,7}};
for (int[] e : edges)
g.addEdge(e[0], e[1], e[2]);
System.out.println(g);
System.out.println("---- BFS ----");
t.bfs(g, 4);
System.out.println("---- DFS ----");
t.dfs(g, 4);
}
}
最小生成树 ---- Prim & Kruskal...
public class GenericMST {
public Graph prim(Graph g) {
int n = g.getVolume();
Graph tree = new Graph(n, g.isDirected());
int[] cost = new int[n]; // cost[j]: min cost to tree
int[] from = new int[n]; // e : (from[i], i)
int[][] arcs = g.getArcs();
for (int i = 0; i < n; i++) {
cost[i] = arcs[i][0];
from[i] = 0;
}
for (int i = 1; i < n; i++) {
int min = Integer.MAX_VALUE;
int k = 0;
for (int j = 1; j < n; j++)
if (cost[j] != -1 && cost[j] < min) {
min = cost[j];
k = j;
}
cost[k] = -1;
for (int j = 1; j < n; j++)
if (arcs[k][j] < cost[j]) {
cost[j] = arcs[k][j];
from[j] = k;
}
}
for (int i = 0; i < n; i++)
tree.addEdge(from[i], i, arcs[from[i]][i]);
return tree;
}
public Graph kruskal(Graph g) {
int n = g.getVolume();
Graph tree = new Graph(n, g.isDirected());
PriorityQueue<int[]> queue = new PriorityQueue<int[]>(32,
new Comparator<int[]>() {
public int compare(int[] e1, int[] e2) {
return e1[2] - e2[2];
}
});
List<int[]> edges = g.getEdges();
DisjointSet set = new DisjointSet(n);
for (int[] e : edges)
queue.add(e);
while (!queue.isEmpty()) {
int[] e = queue.poll();
if (set.find(e[0]) != set.find(e[1])) {
tree.addEdge(e[0], e[1], e[2]);
set.union(e[0], e[1]);
}
}
return tree;
}
public static void main(String[] args) {
Graph g = new Graph(9, false);
/*int[][] edges = {{0,1,4},{0,7,8},{1,2,8},{1,7,11},
{2,3,7},{2,5,4},{2,8,2},{3,4,9},{3,5,14},
{4,5,10},{5,6,2},{6,7,1},{6,8,6},{7,8,7}};
for (int[] e : edges)
g.addEdge(e[0], e[1], e[2]);*/
g.shuffle();
System.out.println("----- Origine -----");
System.out.println(g);
GenericMST mst = new GenericMST();
System.out.println("----- Kruskal -----");
System.out.println(mst.kruskal(g));
System.out.println("----- Prim ------");
System.out.println(mst.prim(g));
}
}
最短路径 ---- Dijkstra & Floyed...
public class ShortestPath {
public void dijkstra(Graph g, int s) {
int n = g.getVolume();
int[][] arcs = g.getArcs();
boolean[] find = new boolean[n];
int[] cost = new int[n];
ArrayList[] paths = new ArrayList[n];
for (int i = 0; i < n; i++) {
find[i] = false;
cost[i] = arcs[s][i];
paths[i] = new ArrayList();
}
find[s] = true;
cost[s] = 0;
for (int i = 1; i < n; i++) {
int min = Integer.MAX_VALUE;
int k = -1;
for (int j = 0; j < n; j++)
if (!find[j] && cost[j] < min) {
min = cost[j];
k = j;
}
find[k] = true;
paths[k].add(k);
for (int j = 0; j < n; j++)
if (arcs[k][j] < Integer.MAX_VALUE &&
!find[j] && arcs[k][j] + min < cost[j]) {
cost[j] = arcs[k][j] + min;
paths[j] = (ArrayList) paths[k].clone();
}
}
for (int i = 0; i < n; i++)
System.out.println(cost[i] + " -- " + paths[i]);
}
public void floyed(Graph g) {
int n = g.getVolume();
int[][] arcs = g.getArcs();
int[][] cost = new int[n][n];
int[][] path = new int[n][n];
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
cost[i][j] = (i == j) ? 0 : arcs[i][j];
path[i][j] = -1;
}
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
if (cost[i][k] < Integer.MAX_VALUE &&
cost[k][j] < Integer.MAX_VALUE &&
cost[i][k] + cost[k][j] < cost[i][j]) {
cost[i][j] = cost[i][k] + cost[k][j];
path[i][j] = k;
}
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
System.out.format("(%d,%d) %3d: %d", i, j, cost[i][j], i);
showPath(path, i, j);
System.out.println();
}
}
public void showPath(int[][] path, int i, int j) {
int k = path[i][j];
if (k == -1) {
System.out.print("->" + j);
return;
}
showPath(path, i, k);
showPath(path, k, j);
}
public static void main(String[] args) {
ShortestPath sp = new ShortestPath();
Graph g = new Graph(5, true);
/*int[][] edges = {{0,1,10},{0,3,5},{1,2,1},{1,3,2},
{2,4,4},{3,1,3},{3,2,9},{3,4,2},{4,0,7},{4,2,6}};*/
int[][] edges = {{0,1,3},{0,2,8},{0,4,-4},{1,3,1},
{1,4,7},{2,1,4},{3,0,2},{3,2,-5},{4,3,6}};
for (int[] e : edges)
g.addEdge(e[0], e[1], e[2]);
System.out.println(g);
/*System.out.println("---- Dijkstra ----");
sp.dijkstra(g, 0);*/
System.out.println("---- Floyed ----");
sp.floyed(g);
}
}
图的表示...
public class Graph {
private int n;
private boolean directed;
private int[][] arcs;
public Graph(int n, boolean directed) {
this.n = n;
this.directed = directed;
arcs = new int[n][n];
for (int[] arc : arcs)
Arrays.fill(arc, Integer.MAX_VALUE);
}
public void addEdge(int from, int to, int weight) {
if (from < 0 || from >= n || to < 0 || to >= n || from == to)
return;
if (arcs[from][to] < Integer.MAX_VALUE)
return;
arcs[from][to] = weight;
if (!directed)
arcs[to][from] = weight;
}
public List<int[]> getAdjs(int from) {
List<int[]> adjs = new ArrayList<int[]>();
if (from >= 0 && from < n) {
for (int w, to = 0; to < n; to++)
if ((w = arcs[from][to]) < Integer.MAX_VALUE)
adjs.add(new int[]{from, to, w});
}
return adjs;
}
public List<int[]> getEdges() {
List<int[]> edges = new ArrayList<int[]>();
for (int i = 0; i < n; i++)
for (int w, j = (directed) ? 0 : i + 1; j < n; j++)
if ((w = arcs[i][j]) < Integer.MAX_VALUE)
edges.add(new int[]{i, j, w});
return edges;
}
public int getVolume() {
return n;
}
public boolean isDirected() {
return directed;
}
public int[][] getArcs() {
return arcs;
}
public void shuffle() {
Random r = new Random();
for (int k = 0; k < 3 * n; k++)
addEdge(r.nextInt(n), r.nextInt(n), 1 + r.nextInt(20));
}
public String toString() {
StringBuilder buf = new StringBuilder();
for (int i = 0; i < n; i++) {
buf.append(i + " -> ");
for (int j = 0; j < n; j++)
if (arcs[i][j] < Integer.MAX_VALUE)
buf.append("(" + j + "," + arcs[i][j] + ") ");
buf.append("\n");
}
return buf.toString();
}
}
Kruskal算法用到的并查集...
public class DisjointSet {
private int[] set;
public DisjointSet(int n) {
set = new int[n];
for (int i = 0; i < n; i++)
set[i] = -1;
}
public void union(int x, int y) {
int r1 = find(x);
int r2 = find(y);
if (r1 == r2)
return;
if (set[r2] < set[r1])
set[r1] = r2;
else {
if (set[r2] == set[r1])
set[r1]--;
set[r2] = r1;
}
}
public int find(int x) {
if (set[x] < 0)
return x;
return set[x] = find(set[x]);
}
}
分享到：
发表评论
相关推荐
《ACE初级算法设计》 在计算机科学领域，算法设计是至关重要的，它是解决问题和优化计算过程的核心工具。ACE（Adaptive Communication Environment）初级算法设计主要针对初学者，旨在引导他们理解并掌握基本的算法...
《C++算法大全》是一本面向初级和中级程序员的指南，旨在帮助读者深入理解并熟练掌握C++编程中的算法知识。算法是计算机科学的核心，它不仅仅是编程语言的精髓，更是解决问题的关键。无论你是正在学习C++的新手，...
通过解决这些算法题，开发者可以锻炼逻辑思维，理解和掌握数据结构，如数组、链表、栈、队列、树、图等，以及排序、搜索、图论、动态规划等核心算法。 在JAVA经典算法40题.doc中，可能包含的题目类型有递归、分治、...
【北大POJ初级-基本算法】是一系列针对北京大学在线编程平台POJ的初级算法题目解题报告和通过（AC）代码的集合。这个资源对于学习算法基础和提升编程能力非常有帮助，尤其适合初学者。POJ是许多计算机科学与技术专业...
【北大POJ初级-图算法】是一系列针对北京大学在线编程平台POJ（Problem Online Judge）上的初级编程题目，重点在于图论算法的应用。这个解题报告集合了多种图算法的实现，帮助学习者掌握如何在实际问题中运用这些...
《算法基础：打开算法之门（中文版）》则可能是一本更为初级的入门读物，它旨在为初学者揭开算法的神秘面纱。这本书可能从基础的算法思想出发，如分治策略、贪心算法和回溯法，逐步引导读者进入算法的世界。它可能还...
这个压缩包文件"LeetCode-master"很可能包含了一位开发者编写的针对LeetCode中初级算法题目的解决方案。 在LeetCode上，题目通常分为几个难度等级：Easy、Medium和Hard。"中级算法"可能指的是Medium级别的题目，...
书中涵盖了各种基础和进阶算法，包括但不限于排序算法（如冒泡排序、快速排序、归并排序、堆排序等）、搜索算法（如二分查找、广度优先搜索、深度优先搜索）、图论算法（如最短路径算法Dijkstra、最小生成树Prim和...
**算法设计初级教程PPT概览** 在计算机科学领域，算法设计是解决问题的关键技术，而数据结构则是支撑算法高效运行的基础。本初级教程PPT涵盖了多个核心概念，旨在帮助初学者构建坚实的理论基础并掌握实际操作技能。...
4. **图论算法**：如深度优先搜索（DFS）、广度优先搜索（BFS）和最短路径算法（Dijkstra、Floyd-Warshall），在社交网络分析、路线规划等领域有着广泛应用。 5. **动态规划**：背包问题、最长公共子序列、最短编辑...
初级算法，也称为基本算法，是学习编程的基础，涵盖了数据处理、逻辑推理和问题解决的基本方法。"elementaryAlgorithm:初级算法基本算法练习集 elementary algorithm practise" 提供的资料显然是为了帮助学习者通过...
无论是初级程序员还是有一定经验的开发者，都能从中受益，提升自己的算法思维和编程技巧。 最后，提供的"程序员实用算法.pdf"文件很可能是这本书的电子版，包含了所有这些内容，方便读者随时随地学习和查阅。利用这...
3. **图论算法**：包括深度优先搜索（DFS）和广度优先搜索（BFS），以及最小生成树（Prim或Kruskal算法）、最短路径问题（Dijkstra或Floyd-Warshall算法）等。这些在解决网络优化、社交网络分析等问题中至关重要。 ...
2. **排序与查找**：快速排序、归并排序、冒泡排序、二分查找等经典算法是初级阶段的重点。这些算法的实现和时间复杂度分析是必备技能。 3. **递归与回溯**：递归是解决许多问题的有效手段，如斐波那契数列、汉诺塔...
在算法领域，无论是初级程序员还是经验丰富的开发者，都需要不断学习和提升。本书涵盖了基础算法，如排序和搜索，到高级算法，如图论、动态规划和贪心策略。这些算法是解决计算机科学问题的核心工具，对于软件开发、...
3. **排序与查找**：排序算法（如冒泡排序、选择排序、插入排序、快速排序、归并排序等）和查找算法（如线性查找、二分查找、哈希查找等）是初级算法学习的重点，会讲解每种算法的工作原理和优缺点。 4. **递归与...
算法谜题有很多种类，比如排序谜题、搜索问题、动态规划、图论相关的谜题等。每种类型都旨在训练解题者特定方面的算法技能。例如，排序谜题可能会要求以最小的步骤数对一组数字进行排序；搜索问题可能要求在最少的步...
3. **图论算法**：包括最短路径算法（如Dijkstra算法、Floyd-Warshall算法）和最小生成树算法（如Prim算法、Kruskal算法），这些在解决网络问题、路由选择等领域有广泛应用。 4. **动态规划**：动态规划是一种解决...
5. **图论算法**： - **深度优先搜索(DFS)** 和 **广度优先搜索(BFS)**：遍历图的两种方法，常用于解决迷宫问题、社交网络分析等。 - **最小生成树**：如Prim和Kruskal算法，用于找出连通图的最小代价树。 - **...
这些算法涵盖了数据结构、排序、搜索、图论、动态规划等多个领域，是学习和实践算法的理想资料。下面将详细讨论其中的一些关键算法及其在实际开发中的应用。 1. **排序算法**： - 冒泡排序：基础排序算法，通过...