图的实现

图的邻接表实现

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
/**
 * 文件名：Graph.java
 * 时间：2014年11月13日下午4:51:12
 * 作者：修维康
 */
package chapter9;
import java.util.*;
/**
 * 类名：Graph 说明：
 */
class Vertex<AnyType> {
	public AnyType value;
	public int indegree = 0;// 顶点的入度，拓扑排序的时候用到
	public LinkedList<Vertex> adjacent = new LinkedList<Vertex>();
	public int topNum = 0;// 拓扑排序
	private int size = 0;
	private int index = 0;
	public int dist = Integer.MAX_VALUE;// 到一个顶点的距离,开始默认都不可达
	public boolean visited = false;
	public Vertex path = null;
	public Vertex(AnyType value) {
		this.value = value;
	}
	public void addAdj(Vertex v) {
		v.indegree++;
		adjacent.add(v);
		size++;
	}
	
	public Vertex next() {
		return adjacent.get(index++);
	}
	public boolean hasAdj() {
		int temp = index;//定义一个临时的变量，使其到尾部的时候在指向0
		if(index == size)
			index = 0;
		return temp != size;
	}
}
class Graph {
	public ArrayList<Vertex<Integer>> vList = new ArrayList<Vertex<Integer>>();
	public Graph() {
		Vertex<Integer> v1 = new Vertex<Integer>(1);
		Vertex<Integer> v2 = new Vertex<Integer>(2);
		Vertex<Integer> v3 = new Vertex<Integer>(3);
		Vertex<Integer> v4 = new Vertex<Integer>(4);
		Vertex<Integer> v5 = new Vertex<Integer>(5);
		Vertex<Integer> v6 = new Vertex<Integer>(6);
		Vertex<Integer> v7 = new Vertex<Integer>(7);
		v1.addAdj(v2);
		v1.addAdj(v3);
		v1.addAdj(v4);
		v2.addAdj(v4);
		v2.addAdj(v5);
		v3.addAdj(v6);
		v4.addAdj(v3);
		v4.addAdj(v6);
		v4.addAdj(v7);
		v5.addAdj(v4);
		v5.addAdj(v7);
		v7.addAdj(v6);
		vList.add(v1);
		vList.add(v2);
		vList.add(v3);
		vList.add(v4);
		vList.add(v5);
		vList.add(v6);
		vList.add(v7);
	}
	public String toString() {
		StringBuffer s = new StringBuffer();
		Iterator<Vertex<Integer>> ite = vList.iterator();
		System.out.println("v1  v2  v3  v4  v5  v6  v7   ");
		while (ite.hasNext())
			s.append(ite.next().topNum + "   ");
		return new String(s);
	}
	public String printDist() {
		StringBuffer s = new StringBuffer();
		Iterator<Vertex<Integer>> ite = vList.iterator();
		System.out.println("v1  v2  v3  v4  v5  v6  v7   ");
		while (ite.hasNext())
			s.append(ite.next().dist + "   ");
		return new String(s);
	}
}
public class GraphTest {
	/**
	 * 方法名：topSort 说明：拓扑排序 是对无环图进行的
	 */
	public static void topSort(Graph graph) {
		Queue<Vertex<Integer>> q = new LinkedList<Vertex<Integer>>();
		Vertex v = findIndegreeZero(graph);
		if (v == null) {
			System.out.println("该图有环，无法进行拓扑排序");
			return;
		}
		q.add(v);
		int count = 0;
		while (!q.isEmpty()) {
			Vertex w = q.poll();
			w.topNum = ++count;
			while (w.hasAdj()) {
				Vertex e = w.next();
				if (--e.indegree == 0)
					q.add(e);
			}
		}
	}
	private static Vertex<Integer> findIndegreeZero(Graph graph) {
		for (Vertex<Integer> v : graph.vList) {
			if (v.indegree == 0)
				return v;
		}
		return null;
	}
	/**
	 * 方法名：unWeighted 说明：无权的最短路径
	 */
	public static void unWeighted(Vertex s) {
		Queue<Vertex<Integer>> q = new LinkedList<Vertex<Integer>>();
		s.dist = 0;
		q.add(s);
		while (!q.isEmpty()) {
			Vertex<Integer> v = q.poll();
			while (v.hasAdj()) {
				Vertex<Integer> w = v.next();
				if (!w.visited) {
					w.dist = v.dist + 1;
					w.visited = true;
					q.add(w);
				}
			}
		}
	}
	public static void main(String[] args) {
		Graph g = new Graph();
		topSort(g);
		System.out.println(g);
		unWeighted(g.vList.get(0));// 各个顶点到0的路径；
		System.out.println(g.printDist());
	}
}