图论基础
图分为有向图，和无向图。
如果图的边数接近顶点数其为稠密图
如果图的边数远远小于顶点数其为稀疏图
表示稠密图一般采用邻接矩阵的方法
文章图片
package bobo.algo;
import java.util.Vector;
// 稠密图 - 邻接矩阵
public class DenseGraphimplements Graph{
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;
}// 返回边的个数
// 向图中添加一个边
public void addEdge(int v, int w ){
assert v >=0 && v < n;
assert w >=0 && w < n;
if( hasEdge( v, w ) )
return;
g[v][w] =true;
if( !directed )
g[w][v] =true;
m ++;
}
// 验证图中是否有从v到w的边
public boolean hasEdge(int v, int w ){
assert v >=0 && v < n;
assert w >=0 && w < n;
return g[v][w];
}
// 显示图的信息
public void show(){
for(int i =0 ;
i < n;
i ++ ){
for(int j =0 ;
j < n;
j ++ )
System.out.print(g[i][j]+"\t");
System.out.println();
}
}
// 返回图中一个顶点的所有邻边
// 由于java使用引用机制，返回一个Vector不会带来额外开销,
public Iterable adj(int v) {
assert v >=0 && v < n;
Vector adjV =new Vector();
for(int i =0 ;
i < n;
i ++ )
if( g[v][i] )
adjV.add(i);
return adjV;
}
}
表示稀疏图一般采用邻接表的方法。
文章图片
package bobo.algo;
import java.util.Vector;
// 稀疏图 - 邻接表
public class SparseGraphimplements Graph {
private int n;
// 节点数
private int m;
// 边数
private boolean directed;
// 是否为有向图
private Vector[] 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[])new Vector[n];
for(int i =0 ;
i < n;
i ++)
g[i] =new Vector();
}
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 adj(int v) {
assert v >=0 && v < n;
return g[v];
}
}
图的深度优先遍历
文章图片
从0开始，遍历1，再遍历1的子节点0，发现已遍历完子节点退回到上层，遍历2，遍历0，发现遍历完了，再遍历5，遍历 0发现已经遍历换下一个，3，遍历3的子节点4，遍历4的子节点3，5，6，以此类推
联通分量
联通分量之间没有节点相连
深度优先遍历能遍历完一个联通分量
求联通分量和深度遍历
package bobo.algo;
// 求无权图的联通分量
public class Components {
Graph G;
// 图的引用
private boolean[] visited;
// 记录dfs的过程中节点是否被访问
private int ccount;
// 记录联通分量个数
private int[] id;
// 每个节点所对应的联通分量标记
// 图的深度优先遍历
void dfs(int v ){
visited[v] =true;
id[v] = ccount;
for(int i: G.adj(v) ){
if( !visited[i] )
dfs(i);
}
}
// 构造函数, 求出无权图的联通分量
public Components(Graph graph){
// 算法初始化
G = graph;
visited =new boolean[G.V()];
id =new int[G.V()];
ccount =0;
for(int i =0 ;
i < G.V();
i ++ ){
visited[i] =false;
id[i] = -1;
}
// 求图的联通分量
for(int i =0 ;
i < G.V();
i ++ )
if( !visited[i] ){
dfs(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];
}
}
找出两点之间的路径一般是在深度遍历时记录上一个点的位置即可
package bobo.algo;
import java.util.Vector;
import java.util.Stack;
public class Path {
private Graph G;
// 图的引用
private int s;
// 起始点
private boolean[] visited;
// 记录dfs的过程中节点是否被访问
private int[] from;
// 记录路径, from[i]表示查找的路径上i的上一个节点
// 图的深度优先遍历
private void dfs(int v ){
visited[v] =true;
for(int i : G.adj(v) )
if( !visited[i] ){
from[i] = v;
dfs(i);
}
}
// 构造函数, 寻路算法, 寻找图graph从s点到其他点的路径
public Path(Graph graph, int s){
// 算法初始化
G = graph;
assert s >=0 && s < G.V();
visited =new boolean[G.V()];
from =new int[G.V()];
for(int i =0 ;
i < G.V();
i ++ ){
visited[i] =false;
from[i] = -1;
}
this.s = s;
// 寻路算法
dfs(s);
}
// 查询从s点到w点是否有路径
boolean hasPath(int w){
assert w >=0 && w < G.V();
return visited[w];
}
// 查询从s点到w点的路径, 存放在vec中
Vector path(int w){
assert hasPath(w);
Stack s =new Stack();
// 通过from数组逆向查找到从s到w的路径, 存放到栈中
int p = w;
while( p != -1 ){
s.push(p);
p = from[p];
}
// 从栈中依次取出元素, 获得顺序的从s到w的路径
Vector res =new Vector();
while( !s.empty() )
res.add( s.pop() );
return res;
}
// 打印出从s点到w点的路径
void showPath(int w){
assert hasPath(w);
Vector 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(" -> ");
}
}
}
俩点之间的最短路径（无权图）
用广度遍历，先遍历其所有子节点，第一个子节点的子节点入栈，第二个子节点的子结点再入栈，以此类推，到第一个子节点的子节点的子节点入账即可
package bobo.algo;
import java.util.Vector;
import java.util.Stack;
import java.util.LinkedList;
import java.util.Queue;
public class ShortestPath {
private Graph G;
// 图的引用
private int s;
// 起始点
private boolean[] visited;
// 记录dfs的过程中节点是否被访问
private int[] from;
// 记录路径, from[i]表示查找的路径上i的上一个节点
private int[] ord;
// 记录路径中节点的次序。ord[i]表示i节点在路径中的次序。
// 构造函数, 寻路算法, 寻找图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 q =new LinkedList();
q.add(s);
visited[s] =true;
ord[s] =0;
while( !q.isEmpty() ){
int v = q.remove();
for(int i : G.adj(v) )
if( !visited[i] ){
q.add(i);
visited[i] =true;
from[i] = v;
ord[i] = ord[v] +1;
}
}
}
// 查询从s点到w点是否有路径
public boolean hasPath(int w){
assert w >=0 && w < G.V();
return visited[w];
}
// 查询从s点到w点的路径, 存放在vec中
public Vector path(int w){
assert hasPath(w);
Stack s =new Stack();
// 通过from数组逆向查找到从s到w的路径, 存放到栈中
int p = w;
while( p != -1 ){
s.push(p);
p = from[p];
}
// 从栈中依次取出元素, 获得顺序的从s到w的路径
Vector res =new Vector();
while( !s.empty() )
res.add( s.pop() );
return res;
}
// 打印出从s点到w点的路径
public void showPath(int w){
assert hasPath(w);
Vector 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(" -> ");
}
}
// 查看从s点到w点的最短路径长度
// 若从s到w不可达，返回-1
public int length(int w){
assert w >=0 && w < G.V();
return ord[w];
}
【图论基础】}
