最近在看数据结构，之前用c实现，现在用java实现图的算法
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
public class Graph {
private final int V;
private int E;
private Bag<Integer>[] adj;
public (int V){
StdOut.println(V);
this.V = V;
this.E = 0;
adj = (Bag<Integer>[]) new Bag[V];
for(int v = 0;v < V;v++){
adj[v] = new Bag<Integer>();
}
}
public (In in){
this(in.readInt());
int E = in.readInt();
for(int i= 0;i < E;i ++){
int v = in.readInt();
int w = in.readInt();
addEdge(v,w);
}
}
int V(){
return V;
}
int E(){
return E;
}
public void addEdge(int v,int w){
adj[v].add(w);
adj[w].add(v);
E++;
}
Iterable<Integer> adj(int v){
return adj[v];
}
public String toString(){
String s = V + " vertices" + E+" edgesn";
for(int v = 0;v < V;v++){
s += v + ": ";
for(int w:this.adj(v))
s+= w + " ";
}
return s;
}
public static int degree(Graph G,int v){
int degree = 0;
for(int w : G.adj(v))
degree++;
return degree;
}
public static int maxDegree(Graph G){
int max = 0;
for(int v = 0; v < G.V();v++){
if(degree(G,v) > max)
max = degree(G,v);
}
return max;
}
public static double avgDegree(Graph G){
return 2.0*G.E()/G.V();
}
public static int numberOfSelfLoops(Graph G){
int count = 0;
for(int v = 0; v < G.V(); v++){
for(int w : G.adj(v))
if(v==w)
count ++;
}
return count/2;
}
public static void main(String[] args) {
}
}
|
再次基础上，实现深度优先搜索遍历
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
52
53
54
55
56
57
58
59
60
61
62
63
64
|
public class BreadthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
private final int s;
public BreadthFirstPaths(Graph G,int s){
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
this.s = s;
bfs(G,s);
}
private void bfs(Graph G,int s){
Queue<Integer> queue = new Queue<Integer>();
marked[s] = true;
queue.enqueue(s);
while(!queue.isEmpty()){
int v = queue.dequeue();
for(int w : G.adj(v)){
if(!marked[w])
{
edgeTo[w] = v;
marked[w] = true;
queue.enqueue(w);
}
}
}
}
public boolean hasPathTo(int v){
return marked[v];
}
public Iterable<Integer> pathTo(int v){
if(!hasPathTo(v))
return null;
Stack<Integer> path = new Stack<Integer>();
for(int x = v; x != s; x = edgeTo[x]){
path.push(x);
}
path.push(s);
return path;
}
public static void main(String[] args) {
Graph G = new Graph(new In(args[0]));
int s = Integer.parseInt(args[1]);
BreadthFirstPaths search = new BreadthFirstPaths(G,s);
for(int v = 0; v < G.V(); v++){
StdOut.print(s + " to " + v + ": ");
if(search.hasPathTo(v)){
for(int x : search.pathTo(v))
if(x==s)
StdOut.print(x);
else
StdOut.print("-" + x);
}else{
StdOut.print("null");
}
StdOut.println();
}
}
}
|
近期评论