很早就想總結(jié)一下了，一直沒(méi)有時(shí)間，OK，進(jìn)入正題。
一 圖的基本概念及存儲(chǔ)結(jié)構(gòu)
圖G是由頂點(diǎn)的有窮集合，以及頂點(diǎn)之間的關(guān)系組成，頂點(diǎn)的集合記為V，頂點(diǎn)之間的關(guān)系構(gòu)成邊的集合E
G=(V,E).
說(shuō)一條邊從v1,連接到v2,那么有v1Ev2(E是V上的一個(gè)關(guān)系）《=》<v1,v2>∈E.
圖有有向圖，無(wú)向圖之分，無(wú)向圖的一條邊相當(dāng)于有向圖的中兩條邊，即如果無(wú)向圖的頂點(diǎn)v1和v2之間有一條邊
，那么既有從v1連接到v2的邊，也有從v2連接到v1的邊，<v1,v2>∈E 并且<v2,v1>∈E，而有向圖是嚴(yán)格區(qū)分方向的。
一般圖的存儲(chǔ)有兩種方式
1）相鄰矩陣，用一個(gè)矩陣來(lái)保持邊的情況，<v1,v2>∈E則Matrix[v1][v2]=Weight.
2）鄰接表，需要保存一個(gè)順序存儲(chǔ)的頂點(diǎn)表和每個(gè)頂點(diǎn)上的邊的鏈接表。
這里的實(shí)現(xiàn)采用第二種方案，另外圖又復(fù)雜圖，簡(jiǎn)單圖之分，復(fù)雜圖可能在兩點(diǎn)之間同一個(gè)方向有多條邊，我們考慮的都是無(wú)環(huán)簡(jiǎn)單圖，無(wú)環(huán)簡(jiǎn)單圖是指頂點(diǎn)沒(méi)有自己指向自己的邊的簡(jiǎn)單圖，即任取vi屬于V => <vi,vi>不屬于E并且沒(méi)有重復(fù)邊。
我們先給出圖的ADT:
package algorithms.graph;
/**
* The Graph ADT
* @author yovn
*
*/
public interface Graph {
//mark
public static interface Edge{
public int getWeight();
}
int vertexesNum();
int edgeNum();
boolean isEdge(Edge edge);
void setEdge(int from,int to, int weight);
Edge firstEdge(int vertex);
Edge nextEdge(Edge edge);
int toVertex(Edge edge);
int fromVertex(Edge edge);
String getVertexLabel(int vertex);
void assignLabels(String[] labels);
void deepFirstTravel(GraphVisitor visitor);
void breathFirstTravel(GraphVisitor visitor);
}
其中的方法大多數(shù)比較一目了然，
其中
1）
Edge firstEdge(int vertex)返回指定節(jié)點(diǎn)的邊的鏈表里存的第一條邊
2）Edge nextEdge(Edge edge)，順著邊鏈表返回下一條邊
3）fromVertex,toVertex很簡(jiǎn)單返回該邊的起始頂點(diǎn)和終結(jié)頂點(diǎn)
4）getVertexLabel返回該定點(diǎn)對(duì)應(yīng)的標(biāo)號(hào),assignLabels給所有頂點(diǎn)標(biāo)上號(hào)
GraphVisitor是一個(gè)很簡(jiǎn)單的接口：
package algorithms.graph;
/**
* @author yovn
*
*/
public interface GraphVisitor {
void visit(Graph g,int vertex);
}
OK，下面是該部分實(shí)現(xiàn)：
package algorithms.graph;
import java.util.Arrays;
/**
* @author yovn
*
*/
public class DefaultGraph implements Graph {
private static class _Edge implements Edge{
private static final _Edge NullEdge=new _Edge();
int from;
int to;
int weight;
_Edge nextEdge;
private _Edge()
{
weight=Integer.MAX_VALUE;
}
_Edge(int from, int to, int weight)
{
this.from=from;
this.to=to;
this.weight=weight;
}
public int getWeight()
{
return weight;
}
}
private static class _EdgeStaticQueue
{
_Edge first;
_Edge last;
}
private int numVertexes;
private String[] labels;
private int numEdges;
private _EdgeStaticQueue[] edgeQueues;
//tag the specified vertex be visited or not
private boolean[] visitTags;
/**
*
*/
public DefaultGraph(int numVertexes) {
if(numVertexes<1)
{
throw new IllegalArgumentException();
}
this.numVertexes=numVertexes;
this.visitTags=new boolean[numVertexes];
this.labels=new String[numVertexes];
for(int i=0;i<numVertexes;i++)
{
labels[i]=i+"";
}
this.edgeQueues=new _EdgeStaticQueue[numVertexes];
for(int i=0;i<numVertexes;i++)
{
edgeQueues[i]=new _EdgeStaticQueue();
edgeQueues[i].first=edgeQueues[i].last=_Edge.NullEdge;
}
this.numEdges=0;
}
/* (non-Javadoc)
* @see algorithms.graph.Graph#edgeNum()
*/
@Override
public int edgeNum() {
return numEdges;
}
/* (non-Javadoc)
* @see algorithms.graph.Graph#firstEdge(int)
*/
@Override
public Edge firstEdge(int vertex) {
if(vertex>=numVertexes) throw new IllegalArgumentException();
return edgeQueues[vertex].first;
}
/* (non-Javadoc)
* @see algorithms.graph.Graph#isEdge(algorithms.graph.Graph.Edge)
*/
@Override
public boolean isEdge(Edge edge) {
return (edge!=_Edge.NullEdge);
}
/* (non-Javadoc)
* @see algorithms.graph.Graph#nextEdge(algorithms.graph.Graph.Edge)
*/
@Override
public Edge nextEdge(Edge edge) {
return ((_Edge)edge).nextEdge;
}
/* (non-Javadoc)
* @see algorithms.graph.Graph#vertexesNum()
*/
@Override
public int vertexesNum() {
return numVertexes;
}
@Override
public int fromVertex(Edge edge) {
return ((_Edge)edge).from;
}
@Override
public void setEdge(int from, int to, int weight) {
//we don't allow ring exist
if(from<0||from>=numVertexes||to<0||to>=numVertexes||weight<0||from==to)throw new IllegalArgumentException();
_Edge edge=new _Edge(from,to,weight);
edge.nextEdge=_Edge.NullEdge;
if(edgeQueues[from].first==_Edge.NullEdge)
edgeQueues[from].first=edge;
else
edgeQueues[from].last.nextEdge=edge;
edgeQueues[from].last=edge;
}
@Override
public int toVertex(Edge edge) {
return ((_Edge)edge).to;
}
@Override
public String getVertexLabel(int vertex) {
return labels[vertex];
}
@Override
public void assignLabels(String[] labels) {
System.arraycopy(labels, 0, this.labels, 0, labels.length);
}
//to be continue
}
二 深度優(yōu)先周游
即從從某一點(diǎn)開(kāi)始能繼續(xù)往前就往前不能則回退到某一個(gè)還有邊沒(méi)訪問(wèn)的頂點(diǎn)，沿這條邊看該邊指向的點(diǎn)是否已訪問(wèn)，如果沒(méi)有訪問(wèn)，那么從該指向的點(diǎn)繼續(xù)操作。
那么什么時(shí)候結(jié)束呢，這里我們?cè)趫D的ADT實(shí)現(xiàn)里加上一個(gè)標(biāo)志數(shù)組。該數(shù)組記錄某一頂點(diǎn)是否已訪問(wèn)，如果找不到不到能繼續(xù)往前訪問(wèn)的未訪問(wèn)點(diǎn)，則結(jié)束。
你可能會(huì)問(wèn)，如果指定圖不是連通圖（既有2個(gè)以上的連通分量）呢?
OK,解決這個(gè)問(wèn)題，我們可以讓每一個(gè)頂點(diǎn)都有機(jī)會(huì)從它開(kāi)始周游。
下面看
deepFirstTravel的實(shí)現(xiàn)：
/* (non-Javadoc)
* @see algorithms.graph.Graph#deepFirstTravel(algorithms.graph.GraphVisitor)
*/
@Override
public void deepFirstTravel(GraphVisitor visitor) {
Arrays.fill(visitTags, false);//reset all visit tags
for(int i=0;i<numVertexes;i++)
{
if(!visitTags[i])do_DFS(i,visitor);
}
}
private final void do_DFS(int v, GraphVisitor visitor) {
//first visit this vertex
visitor.visit(this, v);
visitTags[v]=true;
//for each edge from this vertex, we do one time
//and this for loop is very classical in all graph algorithms
for(Edge e=firstEdge(v);isEdge(e);e=nextEdge(e))
{
if(!visitTags[toVertex(e)])
{
do_DFS(toVertex(e),visitor);
}
}
}
三 廣度優(yōu)先周游
廣度優(yōu)先周游從每個(gè)指定頂點(diǎn)開(kāi)始，自頂向下一層一層的訪問(wèn)。上一層所有頂點(diǎn)訪問(wèn)完了才繼續(xù)下一層的訪問(wèn)。可以把二叉樹(shù)的廣度優(yōu)先周游看成圖的廣度優(yōu)先周游的特例。
（二叉樹(shù)是連通的無(wú)回路的有向圖，也是一棵根樹(shù)）
同樣，廣度優(yōu)先也要借助與一個(gè)隊(duì)列來(lái)存儲(chǔ)待訪問(wèn)頂點(diǎn)
下面是
breathFirstTravel的實(shí)現(xiàn)，為了減小Java庫(kù)的影響，我自己實(shí)現(xiàn)一個(gè)很簡(jiǎn)單的隊(duì)列。（你也可以使用
ArrayList,但是記住隊(duì)列的定義，只能在頭刪除，在尾插入）：
private static class _IntQueue
{
private static class _IntQueueNode
{
_IntQueueNode next;
int value;
}
_IntQueueNode first;
_IntQueueNode last;
//queue can only insert to the tail
void add(int i)
{
_IntQueueNode node=new _IntQueueNode();
node.value=i;
node.next=null;
if(first==null)first=node;
else last.next=node;
last=node;
}
boolean isEmpty()
{
return first==null;
}
//queue can only remove from the head
int remove()
{
int val=first.value;
if(first==last)
first=last=null;
else
first=first.next;
return val;
}
}
/* (non-Javadoc)
* @see algorithms.graph.Graph#breathFirstTravel(algorithms.graph.GraphVisitor)
*/
@Override
public void breathFirstTravel(GraphVisitor visitor) {
Arrays.fill(visitTags, false);//reset all visit tags
for(int i=0;i<numVertexes;i++)
{
if(!visitTags[i])
{
do_BFS(i,visitor);
}
}
}
private void do_BFS(int v, GraphVisitor visitor) {
//and BFS will use an queue to keep the unvisited vertexes
// we can also just use java.util.ArrayList
_IntQueue queue=new _IntQueue();
queue.add(v);
while(!queue.isEmpty())
{
int fromV=queue.remove();
visitor.visit(this, fromV);
visitTags[fromV]=true;
for(Edge e=firstEdge(fromV);isEdge(e);e=nextEdge(e))
{
if(!visitTags[toVertex(e)])
{
queue.add(toVertex(e));
}
}
}
}
OK，最后我們測(cè)試一下：
/**
* @param args
*/
public static void main(String[] args) {
/**
* For example, we have a graph:
* 0→1→2
* ↓ ↑↓
* 3 4 5
* ↓ ↑↓
* 6→7←8
*
* here ,all weight is 0, its a DAG(Directed Acyclic Graph)
*/
DefaultGraph g=new DefaultGraph(9);
g.setEdge(0, 1, 0);
g.setEdge(0, 3, 0);
g.setEdge(1, 2, 0);
g.setEdge(4, 1, 0);
g.setEdge(2, 5, 0);
g.setEdge(3, 6, 0);
g.setEdge(7, 4, 0);
g.setEdge(5, 8, 0);
g.setEdge(6, 7, 0);
g.setEdge(8, 7, 0);
//now we visit it
GraphVisitor visitor=new GraphVisitor()
{
@Override
public void visit(Graph g, int vertex) {
System.out.print(g.getVertexLabel(vertex)+" ");
}
};
System.out.println("DFS==============:");
g.deepFirstTravel(visitor);
System.out.println();
System.out.println("BFS==============:");
g.breathFirstTravel(visitor);
System.out.println();
}