## Friday, November 27, 2015

### Graph Misc

http://segmentfault.com/a/1190000002680101

## 无向图的数据结构

``````Class Graph
private final int V;  边数
private int E; 边的数目
``````

## 无向图的API

``````public class Graph
Graph(int V)   创建一个含有V个节点但不含边的无向图
Graph(In)    从输入流中读取一幅图
int V()      返回图中有多少个节点
int E()      边数
String toString       对象的字符串表示``````
``````public class Graph {
private final int V;
private int E;

public Graph(int V){
this.V = V;
this.E = 0;
for(int v = 0;v < V;v++){
}
}

public Graph(In in){
for(int i = 0;i < E;i++){
}
}

public int V(){ return V;}
public int E(){ return E;}

E++;
}
}

}``````
http://segmentfault.com/a/1190000002680168

• 从一个顶点s能否到达顶点v?
• 以s为顶点能到达的所有顶点?

``````//基于深度优先算法，搜索查找图中的路径
//解决单点路径问题，即，从一点开始是否存在到另一个点的路径
public class DepthFirstPaths {
private boolean[] marked;//这个顶点调用过dfs了吗
private int[] edgeTo;//从起点到该点路径上的最后一个顶点
private final int s;//起点

public DepthFirstPaths(Graph g,int s)
{
marked = new boolean[g.V()];
edgeTo = new int[g.V()];
this.s = s;
dfs(g,s);
}

private void dfs(Graph G,int V){
marked[V] = true;
if(!marked[w]){
edgeTo[w] = V;//表示这条路径上，w之前是v
dfs(G,w);
}
}
}

public boolean hasPathTo(int V){
return marked[V];
}

public Iterable<Integer> pathTo(int V){
if(!hasPathTo(V)) return null;
Stack<Integer> path = new Stack<Integer>();
for(int x = V;x != s; x = edgeTo[x])//从终点开始往上回溯
path.push(x);
path.push(s);
return path;

}
}``````
``````
`http://segmentfault.com/a/1190000002680208`

``````public class BreadthFirstPaths {
private boolean[] marked;
private int[] edgeTo;
private final int s;

{
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
this.s = s;
bfs(G,s);
}
private void bfs(Graph G,int s)
{
Queue<Integer> queue = new Queue<Integer>();
marked[s] = true;
queue.enqueue(s);
while(!queue.isEmpty())
{
int v = queue.dequeue();//从队列中删除改顶点
{
edgeTo[w] = v;
marked[w] = true;
queue.enqueue(w);
}
}
}
public boolean hasPathTo(int v){
return marked[v];
}
public Iterable<Integer> pathTo(int v)
{
Stack<Integer> path = new Stack<Integer>();
while(edgeTo[v] != s)//同上一篇，通过该数组往上回溯
{
path.push(v);
v = edgeTo[v];
}
path.push(s);
return path;
}
}``````
http://segmentfault.com/a/1190000002680241

``````public class CC {
/*
* 计算一个图中的连通分量，从起始点开始进行dfs算法，同时用一个以顶点作为索引的数组id[]来保存该点所在的连通分量的起始点，也就是id
* 这样，判断两个点是否处于同一个连通分量，只要判断id是否相同
*/
private boolean[] marked;
private int[] id;
private int count;

public CC(Graph G){
marked = new boolean[G.V()];
id = new int[G.V()];
for(int s = 0;s < G.V();s++){
if(!marked[s]){
dfs(G,s);
count++;
}
}
}
private void dfs(Graph G,int v){
marked[v] = true;
id[v] = count;          //该连通分量的起始节点
if(!marked[w])
dfs(G,w);
}
}

public boolean connected(int v,int w){
return id[v] == id[w];
}
public int id(int v){
return id[v];
}
public int count(){
return count;
}
}``````

// not efficient implementation
``````/*
* 使用dfs算法，来判断一个图中的顶点是否可以用两种颜色染色，使得相邻的顶点颜色不同
* 也就是，判断该图是否是一个二分图：
* 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。
*
*/
public class TwoColor {
private boolean[] marked;
private boolean[] color;
private boolean isTwoColorable = true;

public TwoColor(Graph G){
marked = new boolean[G.V()];
color = new boolean[G.V()];
for(int s = 0;s < G.V();s++){
if(!marked[s])
dfs(G,s);
}
}

private void dfs(Graph G,int v){
marked[v] = true;
if(!marked[w]){
color[w] =!color[v];
}
else if (color[w] == color[v])
isTwoColorable = false;
}
}
public boolean isTwoColorable(){
return isTwoColorable;
}
}``````