内容较基础，从简记录。
图的一些概念
有向图，无向图，有权图，无权图，简单图(无自环边和平行边)，多重图，稠密图，稀疏图(一般|E|<|V||logV|时称)；
顶点的度，入度，出度，边的权值；
子图，连通图，强联通图，弱连通图，连通分量，强连通分量，弱连通分量；
路径，简单路径，回路，简单回路，距离，欧拉路径，哈密顿路径，欧拉回路，哈密顿回路；
生成树，生成森林，最小生成树。
......
更多图相关的概念将在后续笔记介绍具体图论算法时给出。
图的表示概述
图的表示最基本的有邻接矩阵和邻接表。
邻接矩阵：适用于稠密图
邻接表：适用于稀疏图
图的表示时空复杂度分析
(以无向无权图为例)
要做的一点说明是，邻接表方式中所谓"表"只是邻接顶点的组织形式，可以使用普通链表，也可以使用红黑树，哈希表。
各种图的表示对算法的影响如下：
| 数据结构类型 | 空间复杂度 | 建立图的时间复杂度 | 判断两顶点相邻与否时间复杂度 | 查找某顶点所有临边时间复杂度 |
|---|---|---|---|---|
| 邻接矩阵 | O(V^2) | O(E) | O(1) | O(V) |
| 邻接表(普通链表) | O(V+E) | O(E)(如果查重O(V*E)) | O(degree(V)) | O(degree(V)) |
| 邻接表(红黑树) | O(V+E) | O(ElogV) | O(logV) | O(degree(V)) |
| 邻接表(哈希表) | O(V+E+?) | O(E) | O(1) | O(degree(V)) |
上面列举的图的操作是图论领域很多经典算法的基础，所以选择适合的数据结构研究图论问题是必要的。
在邻接表的各种实现中，虽然哈希表性能最优，但是顶点之间的顺序性失去了，这在一些图论算法的调试和模拟中非常不方便，而红黑树可以保持节点间的顺序，且红黑树相比哈希表只是在部分操作多了一个logV数量级，还是可以接受的，故本文及以后的图论问题讨论邻接表都采用红黑树数据结构。当然如果在竞赛和刷题中追求效率可以用哈希表。
邻接矩阵表示(基于无向无权图)
/*Ice_spring 2020/3/26*/
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
// 图的邻接矩阵表示，无向无权图
public class AdjMatrix {
private int V; // 顶点数
private int E; // 边数
private int[][] adj; // 邻接矩阵
public AdjMatrix(String filename){
File file = new File(filename);
try(Scanner scanner = new Scanner(file)){
V = scanner.nextInt();
if(V < 0) throw new IllegalArgumentException("V must be a non-neg number!");
adj = new int[V][V];
E = scanner.nextInt();
if(E < 0) throw new IllegalArgumentException("E must be a non-neg number!");
for(int i=0; i < E; i ++){
int a = scanner.nextInt();
validateVertex(a);
int b = scanner.nextInt();
validateVertex(b);
// 本代码只处理简单图
if(a == b) throw new IllegalArgumentException("检测到self-loop边！");
if(adj[a][b] == 1) throw new IllegalArgumentException("Parallel Edges are detected!");
adj[a][b] = 1;
adj[b][a] = 1;
}
}
catch(IOException e){
e.printStackTrace();//打印异常信息
}
}
private void validateVertex(int v){
// 判断顶点v是否合法
if(v < 0 ||v >= V)
throw new IllegalArgumentException("vertex " + v + "is invalid!");
}
public int V(){ // 返回顶点数
return V;
}
public int E(){
return E;
}
public boolean hasEdge(int v, int w){
// 顶点 v 到 w 是存在边
validateVertex(v);
validateVertex(w);
return adj[v][w] == 1;
}
public ArrayList<Integer> adj(int v){
// 返回和顶点 v 相邻的顶点
validateVertex(v);
ArrayList<Integer> res = new ArrayList<>();
for(int i = 0; i < V; i ++)
if(adj[v][i] == 1)
res.add(i);
return res;
}
public int degree(int v){
// 返回节点 v 的度，即与该顶点相邻的顶点个数
return adj(v).size(); // adj 函数
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append(String.format("V = %d, E = %d\n",V, E));
for(int i = 0; i < V; i ++){
for(int j = 0; j < V; j ++){
sb.append(String.format("%d ", adj[i][j]));
}
sb.append('\n');
}
return sb.toString();
}
public static void main(String args[]){
AdjMatrix adjMatrix = new AdjMatrix("g.txt");
System.out.println(adjMatrix);
}
}
邻接表表示(基于无向无权图，表数据结构使用红黑树)
/*Ice_spring 2020/3/26*/
import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.TreeSet;
// 图的邻接表表示，无向无权图
public class AdjSet {
private int V; // 顶点数
private int E; // 边数
private TreeSet<Integer>[] adj; // 邻接矩阵
public AdjSet(String filename){
File file = new File(filename);
try(Scanner scanner = new Scanner(file)){
V = scanner.nextInt();
if(V < 0) throw new IllegalArgumentException("V must be a non-neg number!");
adj = new TreeSet[V];
for(int i = 0; i < V; i ++)
adj[i] = new TreeSet<>();
E = scanner.nextInt();
if(E < 0) throw new IllegalArgumentException("E must be a non-neg number!");
for(int i=0; i < E; i ++){
int a = scanner.nextInt();
validateVertex(a);
int b = scanner.nextInt();
validateVertex(b);
// 本代码只处理简单图
if(a == b) throw new IllegalArgumentException("检测到self-loop边！");
if(adj[a].contains(b)) throw new IllegalArgumentException("Parallel Edges are detected!");
adj[a].add(b);
adj[b].add(a);
}
}
catch(IOException e){
e.printStackTrace();//打印异常信息
}
}
private void validateVertex(int v){
// 判断顶点v是否合法
if(v < 0 ||v >= V)
throw new IllegalArgumentException("vertex " + v + "is invalid!");
}
public int V(){ // 返回顶点数
return V;
}
public int E(){
return E;
}
public boolean hasEdge(int v, int w){
// 顶点 v 到 w 是存在边
validateVertex(v);
validateVertex(w);
return adj[v].contains(w);
}
public Iterable<Integer> adj(int v){
// 返回值可以是TreeSet，不过用 Iterable 接口更能体现面向对象
// 返回和顶点 v 相邻的所有顶点
validateVertex(v);
return adj[v];
}
public int degree(int v){
// 返回节点 v 的度，即与该顶点相邻的顶点个数
validateVertex(v);
return adj[v].size(); //
}
@Override
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append(String.format("V = %d, E = %d\n",V, E));
for(int v = 0; v < V; v ++){
// 编程好习惯 i,j,k 作索引, v,w 作顶点
sb.append(String.format("%d : ", v));
for(int w: adj[v])
sb.append(String.format("%d ", w));
sb.append('\n');
}
return sb.toString();
}
public static void main(String args[]){
AdjSet adjList = new AdjSet("g.txt");
System.out.println(adjList);
}
}
最后，在上面的时空复杂度分析中可以看到，综合来看，相比于邻接矩阵邻接表(红黑树)性能是更好的，所以以后对图论各个算法的实现均采用邻接表(红黑树)，这样更多的注意力可以集中在算法本身。
网友评论