図論初級アルゴリズム
図遍歴アルゴリズム----DFS&BFS...
最小生成ツリー---Prim&Kruskal...
最短経路---Dijkstra&Floyed...
図の表示...
Kruskalアルゴリズムで使用され、セットを調べます.
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("
");
}
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]);
}
}