private int n; // 节点数 private int m; // 边数 private boolean directed; // 是否为有向图 private boolean[][] g; // 图的具体数据
// 构造函数 public DenseGraph( int n , boolean directed ){ assert n >= 0; this.n = n; this.m = 0; // 初始化没有任何边 this.directed = directed; // g初始化为n*n的布尔矩阵, 每一个g[i][j]均为false, 表示没有任和边 // false为boolean型变量的默认值 g = new boolean[n][n]; }
public int V(){// 返回节点个数 return n; } public int E(){ // 返回边的个数 return m; }
// 向图中顶点v和顶点v之间添加一条边 public void addEdge( int v , int w ){ //先判断是否越界 assert v >= 0 && v < n ; assert w >= 0 && w < n ; //如果v，w之间已经有边了，则直接返回 if( hasEdge( v , w ) ) return;
private int n; // 节点数 private int m; // 边数 private boolean directed; // 是否为有向图 private Vector<Integer>[] g; // 图的具体数据
// 构造函数 public SparseGraph( int n , boolean directed ){ assert n >= 0; this.n = n; this.m = 0; // 初始化没有任何边 this.directed = directed; // g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边 g = (Vector<Integer>[])new Vector[n]; //g的每一个元素g[i]也都是一个Vector for(int i = 0 ; i < n ; i ++) g[i] = new Vector<Integer>(); }
public int V(){ return n;} // 返回节点个数 public int E(){ return m;} // 返回边的个数
// 向图中添加一个边 public void addEdge( int v, int w ){
assert v >= 0 && v < n ; assert w >= 0 && w < n ;
g[v].add(w); if( v != w && !directed ) g[w].add(v);
m ++; }
// 验证图中是否有从v到w的边 boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ; assert w >= 0 && w < n ; //g[v]是一个Vector，循环g[v]查看其中是否含有w for( int i = 0 ; i < g[v].size() ; i ++ ) if( g[v].elementAt(i) == w ) return true; return false; } }
// 返回图中一个顶点的所有邻边 // 由于java使用引用机制，返回一个Vector不会带来额外开销, public Iterable<Integer> adj(int v) { //定义一个可迭代方法，求v节点的临边所对应节点 assert v >= 0 && v < n; Vector<Integer> adjV = new Vector<Integer>(); for(int i = 0 ; i < n ; i ++ ) //遍历v节点所在的那一行 if( g[v][i] ) //如果为true证明有临边 adjV.add(i); //将临边对应的节点存入vector return adjV; //返回vector }
2、邻接链表的迭代方法实现：
这里的g是Vector类型变量，里面存储的元素就是临边所对应的节点。
1 2 3 4 5 6
// 返回图中一个顶点的所有邻边 // 由于java使用引用机制，返回一个Vector不会带来额外开销, public Iterable<Integer> adj(int v){ assert v >= 0 && v < n; return g[v]; }
图的算法框架
1、首先建立Graph的接口
1 2 3 4 5 6 7 8 9 10
// 图的接口 public interface Graph {
public int V(); //返回节点个数 public int E(); //返回边的个数 public void addEdge( int v , int w ); // 向图中添加一个边 boolean hasEdge( int v , int w ); // 验证图中是否有从v到w的边 void show(); // 显示图的信息 public Iterable<Integer> adj(int v); // 返回图中一个顶点的所有邻边(所对应节点) }
// 稀疏图 - 邻接表 import java.util.Vector; public class SparseGraph implements Graph {
private int n; // 节点数 private int m; // 边数 private boolean directed; // 是否为有向图 private Vector<Integer>[] g; // 图的具体数据
// 构造函数 public SparseGraph( int n , boolean directed ){ assert n >= 0; this.n = n; this.m = 0; // 初始化没有任何边 this.directed = directed; // g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边 g = (Vector<Integer>[])new Vector[n]; for(int i = 0 ; i < n ; i ++) g[i] = new Vector<Integer>(); }
public int V(){ return n;} // 返回节点个数 public int E(){ return m;} // 返回边的个数
// 向图中添加一个边 public void addEdge( int v, int w ){
assert v >= 0 && v < n ; assert w >= 0 && w < n ;
g[v].add(w); if( v != w && !directed ) g[w].add(v);
m ++; }
// 验证图中是否有从v到w的边 public boolean hasEdge( int v , int w ){
assert v >= 0 && v < n ; assert w >= 0 && w < n ;
for( int i = 0 ; i < g[v].size() ; i ++ ) if( g[v].elementAt(i) == w ) return true; return false; }
// 显示图的信息 public void show(){
for( int i = 0 ; i < n ; i ++ ){ System.out.print("vertex " + i + ":\t"); for( int j = 0 ; j < g[i].size() ; j ++ ) System.out.print(g[i].elementAt(j) + "\t"); System.out.println(); } }
// 返回图中一个顶点的所有邻边 // 由于java使用引用机制，返回一个Vector不会带来额外开销, public Iterable<Integer> adj(int v) { assert v >= 0 && v < n; return g[v]; } }
public ReadGraph(Graph graph, String filename){// //定义类型为Graph(向上转型)，使得在这个模板中既可以传入稀疏图又可以传入稠密图。 readFile(filename); //读取文件
try { int V = scanner.nextInt(); //读取文本文件第一行第一个元素（代表节点个数） if (V < 0) throw new IllegalArgumentException("number of vertices in a Graph must be nonnegative"); assert V == graph.V(); //判断读取文件的节点数和图中的节点数是一致的
int E = scanner.nextInt(); //读取文本文件第一行第二个元素（代表临边个数） if (E < 0) throw new IllegalArgumentException("number of edges in a Graph must be nonnegative");
for (int i = 0; i < E; i++) { int v = scanner.nextInt(); //读取第二行第一个元素(代表节点) int w = scanner.nextInt(); //读取第二行第二个元素(代表节点) assert v >= 0 && v < V; assert w >= 0 && w < V; //在这两个节点之间加一条临边,调用的是传进来的graph所对应子类的addEdge方法。 graph.addEdge(v, w); } } catch (InputMismatchException e) { String token = scanner.next(); throw new InputMismatchException("attempts to read an 'int' value from input stream, but the next token is \"" + token + "\""); } catch (NoSuchElementException e) { throw new NoSuchElementException("attemps to read an 'int' value from input stream, but there are no more tokens available"); } }
private void readFile(String filename){ //定义读取文件的方法 assert filename != null; try { File file = new File(filename); if (file.exists()) { //如果该文件存在 FileInputStream fis = new FileInputStream(file); scanner = new Scanner(new BufferedInputStream(fis), "UTF-8"); scanner.useLocale(Locale.ENGLISH); } else throw new IllegalArgumentException(filename + "doesn't exist."); } catch (IOException ioe) { //无法打开该文件 throw new IllegalArgumentException("Could not open " + filename, ioe); } } }
// 构造函数, 求出无权图的联通分量。 public Components(Graph graph){
// 算法初始化 G = graph; visited = new boolean[G.V()]; //根据图中节点数量给visited开空间 id = new int[G.V()]; ccount = 0; for( int i = 0 ; i < G.V() ; i ++ ){ //通过循环初始化visited，将每个元素都设为false visited[i] = false; id[i] = -1; }
// 求图的联通分量 for( int i = 0 ; i < G.V() ; i ++ ) // if( !visited[i] ){ //如果该节点没有被访问过(visited[i]为false) dfs(i); //dfs()它可以将i和与i相连接的所有节点遍历一遍，没遍历的节点一定在另外的一个联通分量中 ccount ++; } }
// 返回图的联通分量个数 int count(){ return ccount; }
// 查询点v和点w是否联通 boolean isConnected( int v , int w ){ assert v >= 0 && v < G.V(); assert w >= 0 && w < G.V(); return id[v] == id[w]; } }
Stack<Integer> s = new Stack<Integer>(); // 通过from数组逆向查找到从s到w的路径, 存放到栈中 int p = w; //设置指针p指向当前节点w while( p != -1 ){ //不是起始节点。因为起始节点的前一个节点是-1，而当p==-1时，证明起始节点已经压入栈中，则退出循环 s.push(p); //将当前节点压入栈中 p = from[p]; //指针p指向当前节点的前一个节点 }
// 从栈中依次取出元素, 获得顺序的从s到w的路径 Vector<Integer> res = new Vector<Integer>(); while( !s.empty() ) //只要栈不为空，则出栈 res.add( s.pop() );
return res; }
// 打印出从s点到w点的路径 void showPath(int w){
assert hasPath(w) ;
Vector<Integer> vec = path(w); for( int i = 0 ; i < vec.size() ; i ++ ){ // System.out.print(vec.elementAt(i)); if( i == vec.size() - 1 ) //遍历到了最后一个节点 System.out.println(); else System.out.print(" -> "); } } }
// 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径 public ShortestPath(Graph graph, int s){
// 算法初始化 G = graph; assert s >= 0 && s < G.V();
visited = new boolean[G.V()]; //是否已经遍历 from = new int[G.V()]; ord = new int[G.V()]; for( int i = 0 ; i < G.V() ; i ++ ){ visited[i] = false; from[i] = -1; ord[i] = -1; } this.s = s;
// 无向图最短路径算法, 从s开始广度优先遍历整张图 Queue<Integer> q = new LinkedList<Integer>();