09.图的表示
2019-10-09 本文已影响0人
哈哈大圣
图的表示
不考虑自环边和平行边
- 实现图的接口
/**
* 图的接口
* @author Liucheng
* @date 2019/10/13 15:48
*/
public interface Graph {
public int V();
public int E();
public void addEdge( int v , int w );
boolean hasEdge( int v , int w );
void show();
public Iterable<Integer> adj(int v);
}
一、邻接矩阵 Adjacency Matrix
使用一个 2x2 的矩阵表示一个图的联通性,标识一个点与所有点的连接信息
1). 无向图的邻接矩阵表示方法
无向图邻接矩阵.png
无向图具有对角线(“\”)对称性，1标识联通，0表示不通
2). 有向图的邻接矩阵表示方法
有向图邻接矩阵.png
1标识联通，0表示不通
3). 邻接矩阵适合表示稠密图Dense Graph
稠密图与完全图.png
完全图就是每个节点之间都进行相连
4). 使用邻接矩阵实现稠密图
import java.util.Vector;
/**
* 稠密图 - 邻接矩阵;
* 不考虑自环边、平行边和删除节点
* @author Liucheng
* @since 2019-10-09
*/
public class DenseGraph implements Graph {
/**
* 图的节点数
*/
private int n;
/**
* 图的边数
*/
private int m;
/**
* 是否为有向图，true有向图，false无向图
*/
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为布尔类型变量的默认值 */
this.g = new boolean[n][n];
}
/**
* 返回节点个数
*/
@Override
public int V() {return n;}
/**
* 返回边的个数
*/
@Override
public int E() {return m;}
/**
* 向图中添加一个连接，也就是一条边
*/
@Override
public void addEdge(int v, int w) {
if (this.hasEdge(v, w)) {
return;
}
g[v][w] = true;
// 如果为无向图，由于对称性，需要进行设置
if (!directed) {
g[w][v] = true;
}
m++;
}
/**
* 验证图中是否有从v到w的边
*/
@Override
public boolean hasEdge(int v, int w) {
// 不能越界
assert (v >= 0 && v < n);
assert (w >= 0 && w < n);
return g[v][w];
}
/**
* 返回图中一个顶点的所有邻边，
* 由于java使用引用机制，返回一个Vector不会带来额外的开销
* 可以使用java变准库中提供的迭代器
*/
@Override
public Iterable<Integer> adj(int v) {
assert v >= 0 && v < n;
Vector<Integer> adjV = new Vector<>();
for (int i = 0; i < n; i++) {
if (g[v][i]) {
adjV.add(i);
}
}
return adjV;
}
/**
* 显示图的信息
*/
@Override
public void show() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print((g[i][j] ? 1 : 0) + "\t");
}
System.out.println();
}
}
}
二、邻接表 Adjacency Lists
使用一个列表标识只与自己连接的节点信息
1). 无向图的邻接矩阵表示方法
无向图邻接表.png
2). 有向图的邻接矩阵表示方法
有向图邻接表.png
3). 邻接表适合表示稀疏图Sparse Graph
稀疏图.png
4). 使用邻接表实现稀疏图
import java.util.*;
/**
* 稀疏图 - 邻接表：
* 不考虑自环边、平行边和删除节点情况
* @author Liucheng
* @since 2019-10-09
*/
public class SparseGraph implements Graph {
/**
* 图的节点数
*/
private int n;
/**
* 图的边数
*/
private int m;
/**
* 是否为有向图,true表示有向图；false表示无向图
*/
private boolean directed;
/**
* 具体的图数据
* 邻接矩阵 true代表有边，false代表没有边
*/
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]都为空，即没有任何边*/
this.g = (Vector<Integer>[]) new Vector[n];
for (int i = 0; i < n; i++) {
g[i] = new Vector<Integer>();
}
}
/**
* 返回节点的个数
*/
@Override
public int V() {return n;}
/**
* 返回边的个数
*/
@Override
public int E() {return m;}
/**
* 向图中添加一个边
*/
@Override
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的边
*/
@Override
public boolean hasEdge(int v, int w) {
assert (v >= 0 && v < n);
assert (w >= 0 && w < n);
return g[v].contains(w);
}
/**
* 返回图中一个顶点的所有邻边
*/
@Override
public Iterable<Integer> adj(int v) {
assert v >= 0 && v < n;
return g[v];
}
@Override
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();
}
}
}
三、测试
1). 准备的文件内容 (maven工程的resources目录下)
- testG1.txt
13 13
0 5
4 3
0 1
9 12
6 4
5 4
0 2
11 12
9 10
0 6
7 8
9 11
5 3
- testG2.txt
6 8
0 1
0 2
0 5
1 2
1 3
1 4
3 4
3 5
2). 文件读取工具类
import java.io.*;
import java.util.InputMismatchException;
import java.util.Locale;
import java.util.NoSuchElementException;
import java.util.Scanner;
/**
* @author Liucheng
* @since 2019-10-13
*/
public class ReadGraph {
private Scanner scanner;
public ReadGraph(Graph graph, String filename){
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(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);
}
}
}
3). 测试方法
/**
* 创建图测试
*/
@Test
public void createGraph() {
// 使用两种图的存储方式读取testG1.txt文件
String filename = Thread.currentThread().getContextClassLoader().getResource("testG1.txt").getPath();
SparseGraph g1 = new SparseGraph(13, false);
ReadGraph readGraph1 = new ReadGraph(g1, filename);
System.out.println("test G1 in Sparse Graph:");
g1.show();
System.out.println();
DenseGraph g2 = new DenseGraph(13, false);
ReadGraph readGraph2 = new ReadGraph(g2 , filename );
System.out.println("test G1 in Dense Graph:");
g2.show();
System.out.println();
// 使用两种图的存储方式读取testG2.txt文件
filename = Thread.currentThread().getContextClassLoader().getResource("testG2.txt").getPath();
SparseGraph g3 = new SparseGraph(6, false);
ReadGraph readGraph3 = new ReadGraph(g3, filename);
System.out.println("test G2 in Sparse Graph:");
g3.show();
System.out.println();
DenseGraph g4 = new DenseGraph(6, false);
ReadGraph readGraph4 = new ReadGraph(g4, filename);
System.out.println("test G2 in Dense Graph:");
g4.show();
}
- 运行结果
test G1 in Sparse Graph:
vertex 0: 5 1 2 6
vertex 1: 0
vertex 2: 0
vertex 3: 4 5
vertex 4: 3 6 5
vertex 5: 0 4 3
vertex 6: 4 0
vertex 7: 8
vertex 8: 7
vertex 9: 12 10 11
vertex 10: 9
vertex 11: 12 9
vertex 12: 9 11
test G1 in Dense Graph:
0 1 1 0 0 1 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0 0 0 0
0 0 0 1 0 1 1 0 0 0 0 0 0
1 0 0 1 1 0 0 0 0 0 0 0 0
1 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 1 1
0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0 1 0 1 0
test G2 in Sparse Graph:
vertex 0: 1 2 5
vertex 1: 0 2 3 4
vertex 2: 0 1
vertex 3: 1 4 5
vertex 4: 1 3
vertex 5: 0 3
test G2 in Dense Graph:
0 1 1 0 0 1
1 0 1 1 1 0
1 1 0 0 0 0
0 1 0 0 1 1
0 1 0 1 0 0
1 0 0 1 0 0
