java@ 利用ArrayList实现dijkstra算法以及topological 排序算法(java.util.ArrayList)

时间:2021-09-21 03:16:57
package dataStructure;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.io.*; class node {
int to, dist;
node(int t, int d) {
to = t;
dist = d;
}
} public class Graph { public static void dfs(ArrayList<ArrayList<node> > map, int v, boolean[] vis) {
vis[v] = true;
System.out.print(v + " "); ArrayList<node> rhs = map.get(v);
for(int i=; i<rhs.size(); ++i) {
int nv = rhs.get(i).to;
if(!vis[nv]) dfs(map, nv, vis);
}
} public static void bfs(ArrayList<ArrayList<node> > map, int v) {
boolean[] color = new boolean[map.size()];
LinkedList<Integer> Q = new LinkedList<Integer> (); color[v] = true;
Q.push(v);
int d = ;
System.out.print(v + "(" + d +") "); while(!Q.isEmpty()) {
int top = Q.peek();
Q.pop();
++d; for(node nc: map.get(top)) {
if(!color[nc.to]) {
color[nc.to] = true;
Q.push(nc.to);
System.out.print(nc.to + "(" + d +") ");
}
}
} } public static void caseInit(ArrayList<ArrayList<node> > map) {
addEdge(map, , , );
addEdge(map, , , );
addEdge(map, , , );
addEdge(map, , , );
addEdge(map, , , );
addEdge(map, , , );
addEdge(map, , , );
addEdge(map, , , );
addEdge(map, , , );
addEdge(map, , , );
addEdge(map, , , );
} public static void customize(ArrayList<ArrayList<node> > map) {
Scanner input = new Scanner(System.in);
while(true) {
int v = input.nextInt();
if(v == -) break; int w = input.nextInt(), d = input.nextInt();
addEdge(map, v, w, d);
}
input.close();
} public static void addEdge(ArrayList<ArrayList<node> > map, int from, int to, int dist) {
if(from < || from >= map.size() || to < || to >= map.size()) return; ArrayList<node> rhs = map.get(from);
rhs.add(new node(to, dist)); //ArrayList<node> rhs2 = map.get(to);
//rhs2.add(new node(from, dist));
} public static int[] dijkstra(ArrayList<ArrayList<node> > map, int v) {
int[] min_dis = new int[map.size()];
for(int i=; i<min_dis.length; ++i) min_dis[i] = Integer.MAX_VALUE;
for(int i=; i<map.get(v).size(); ++i) {
min_dis[map.get(v).get(i).to] = map.get(v).get(i).dist;
} boolean[] vis = new boolean[map.size()]; min_dis[v] = ;
vis[v] = true;
ArrayList<node> rhs = map.get(v); for(int i=; i<map.size(); ++i) { int Min = Integer.MAX_VALUE, Minj = v;
for(int j=; j<map.size(); ++j) {
if(!vis[j] && min_dis[j] < Min) {
Min = min_dis[j];
Minj = j;
}
} vis[Minj] = true;
ArrayList<node> tmp = map.get(Minj); for(int k=; k<tmp.size(); ++k) {
if(!vis[tmp.get(k).to] && min_dis[Minj] + tmp.get(k).dist < min_dis[tmp.get(k).to]) {
min_dis[tmp.get(k).to] = min_dis[Minj] + tmp.get(k).dist;
}
}
}
return min_dis;
} public static void topologicalSort(ArrayList<ArrayList<node> > map) {
int[] ind = new int[map.size()];
for(int i=; i<map.size(); ++i) {
for(node nc: map.get(i)) {
++ind[nc.to];
}
} LinkedList<Integer> Q = new LinkedList<Integer> ();
for(int i=; i<map.size(); ++i) {
if(ind[i] == ) {
Q.addLast(i);
//System.out.print(i + " ");
}
} while(!Q.isEmpty()) {
int top = Q.peek();
System.out.print(top + " ");
Q.poll();
for(node nc: map.get(top)) {
--ind[nc.to];
if(ind[nc.to] == ) Q.addLast(nc.to);
}
} }
public static void main(String[] args) {
ArrayList<ArrayList<node> > map = new ArrayList<ArrayList<node> > (); for(int i=; i<; ++i) {
ArrayList<node> row = new ArrayList<node> ();
map.add(row);
}
caseInit(map); int[] min_dis = dijkstra(map, );
//for(int i=0; i<min_dis.length; ++i) System.out.print(min_dis[i] + " "); //bfs(map, 0); topologicalSort(map);
} }