java图及其算法详解[手把手教程]

　　一 图的基本概念及存储结构

　　图G是由顶点的有穷集合，以及顶点之间的关系组成，顶点的集合记为V，顶点之间的关系构成边的集合E

　　G=(V,E).

　　说一条边从v1,连接到v2,那么有v1Ev2(E是V上的一个关系)《=》∈E.

　　图有有向图，无向图之分，无向图的一条边相当于有向图的中两条边，即如果无向图的顶点v1和v2之间有一条边

　　，那么既有从v1连接到v2的边，也有从v2连接到v1的边，∈E 并且∈E，而有向图是严格区分方向的。

　　一般图的存储有两种方式

　　1)相邻矩阵，用一个矩阵来保持边的情况，∈E则Matrix[v1][v2]=Weight.

　　2)邻接表，需要保存一个顺序存储的顶点表和每个顶点上的边的链接表。

　　这里的实现采用第二种方案，另外图又复杂图，简单图之分，复杂图可能在两点之间同一个方向有多条边，我们考虑的都是无环简单图，无环简单图是指顶点没有自己指向自己的边的简单图，即任取vi属于V => 不属于E并且没有重复边。

　　我们先给出图的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);
　　}

　　其中的方法大多数比较一目了然，

　　其中

　　1)Edge firstEdge(int vertex)返回指定节点的边的链表里存的第一条边

　　2)Edge nextEdge(Edge edge)，顺着边链表返回下一条边

　　3)fromVertex,toVertex很简单返回该边的起始顶点和终结顶点

　　4)getVertexLabel返回该定点对应的标号,assignLabels给所有顶点标上号

　　GraphVisitor是一个很简单的接口：

　　package algorithms.graph;
　　public interface GraphVisitor {
　　void visit(Graph g,int vertex);
　　}

　　OK，下面是该部分实现：

　　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
　　{
　　labels[i]=i+"";
　　}
　　this.edgeQueues=new _EdgeStaticQueue[numVertexes];
　　for(int i=0;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
　　...
　　}

　　二 深度优先周游

　　即从从某一点开始能继续往前就往前不能则回退到某一个还有边没访问的顶点，沿这条边看该边指向的点是否已访问，如果没有访问，那么从该指向的点继续操作。

　　那么什么时候结束呢，这里我们在图的ADT实现里加上一个标志数组。该数组记录某一顶点是否已访问，如果找不到不到能继续往前访问的未访问点，则结束。

　　你可能会问，如果指定图不是连通图(既有2个以上的连通分量)呢?

　　OK,解决这个问题，我们可以让每一个顶点都有机会从它开始周游。

　　下面看deepFirstTravel的实现：

　　/* (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
　　{
　　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);
　　}
　　}
　　}

　　三 广度优先周游

　　广度优先周游从每个指定顶点开始，自顶向下一层一层的访问。上一层所有顶点访问完了才继续下一层的访问。可以把二叉树的广度优先周游看成图的广度优先周游的特例。

　　(二叉树是连通的无回路的有向图，也是一棵根树)

　　同样，广度优先也要借助与一个队列来存储待访问顶点

　　下面是breathFirstTravel的实现，为了减小Java库的影响，我自己实现一个很简单的队列。(你也可以使用

　　ArrayList,但是记住队列的定义，只能在头删除，在尾插入)：

　　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
　　{
　　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，最后我们测试一下：

　/**
　　* @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();
　　}

　　邻接表有向图的介绍

　　邻接表有向图是指通过邻接表表示的有向图。

　　上面的图G2包含了"A,B,C,D,E,F,G"共7个顶点，而且包含了",,,,,,,,"共9条边。

　　上图右边的矩阵是G2在内存中的邻接表示意图。每一个顶点都包含一条链表，该链表记录了"该顶点所对应的出边的另一个顶点的序号"。例如，第1个顶点(顶点B)包含的链表所包含的节点的数据分别是"2,4,5";而这"2,4,5"分别对应"C,E,F"的序号，"C,E,F"都属于B的出边的另一个顶点。

　　邻接表有向图的代码说明

　　1. 基本定义

　　public class ListDG {
　　// 邻接表中表对应的链表的顶点
　　private class ENode {
　　int ivex; // 该边所指向的顶点的位置
　　ENode nextEdge; // 指向下一条弧的指针
　　}
　　// 邻接表中表的顶点
　　private class VNode {
　　char data; // 顶点信息
　　ENode firstEdge; // 指向第一条依附该顶点的弧
　　};
　　private VNode[] mVexs; // 顶点数组
　　...
　　}

　　(01) ListDG是邻接表对应的结构体。 mVexs则是保存顶点信息的一维数组。

　　(02) VNode是邻接表顶点对应的结构体。 data是顶点所包含的数据，而firstEdge是该顶点所包含链表的表头指针。

　　(03) ENode是邻接表顶点所包含的链表的节点对应的结构体。 ivex是该节点所对应的顶点在vexs中的索引，而nextEdge是指向下一个节点的。

　　2. 创建矩阵

　　这里介绍提供了两个创建矩阵的方法。一个是用已知数据，另一个则需要用户手动输入数据。

　　2.1 创建图(用已提供的矩阵)

　　/*
　　* 创建图(用已提供的矩阵)
　　*
　　* 参数说明：
　　* vexs -- 顶点数组
　　* edges -- 边数组
　　*/
　　public ListDG(char[] vexs, char[][] edges) {
　　// 初始化"顶点数"和"边数"
　　int vlen = vexs.length;
　　int elen = edges.length;
　　// 初始化"顶点"
　　mVexs = new VNode[vlen];
　　for (int i = 0; i < mVexs.length; i++) {
　　mVexs[i] = new VNode();
　　mVexs[i].data = vexs[i];
　　mVexs[i].firstEdge = null;
　　}
　　// 初始化"边"
　　for (int i = 0; i < elen; i++) {
　　// 读取边的起始顶点和结束顶点
　　char c1 = edges[i][0];
　　char c2 = edges[i][1];
　　// 读取边的起始顶点和结束顶点
　　int p1 = getPosition(edges[i][0]);
　　int p2 = getPosition(edges[i][1]);
　　// 初始化node1
　　ENode node1 = new ENode();
　　node1.ivex = p2;
　　// 将node1链接到"p1所在链表的末尾"
　　if(mVexs[p1].firstEdge == null)
　　mVexs[p1].firstEdge = node1;
　　else
　　linkLast(mVexs[p1].firstEdge, node1);
　　}
　　}

　　该函数的作用是创建一个邻接表有向图。实际上，该方法创建的有向图，就是上面的图G2。该函数的调用方法如下：

　　char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
　　char[][] edges = new char[][]{
　　{'A', 'B'},
　　{'B', 'C'},
　　{'B', 'E'},
　　{'B', 'F'},
　　{'C', 'E'},
　　{'D', 'C'},
　　{'E', 'B'},
　　{'E', 'D'},
　　{'F', 'G'}};
　　ListDG pG;
　　pG = new ListDG(vexs, edges);

　　2.2 创建图(自己输入)

　　/*
　　* 创建图(自己输入数据)
　　*/
　　public ListDG() {
　　// 输入"顶点数"和"边数"
　　System.out.printf("input vertex number: ");
　　int vlen = readInt();
　　System.out.printf("input edge number: ");
　　int elen = readInt();
　　if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) {
　　System.out.printf("input error: invalid parameters!\n");
　　return ;
　　}
　　// 初始化"顶点"
　　mVexs = new VNode[vlen];
　　for (int i = 0; i < mVexs.length; i++) {
　　System.out.printf("vertex(%d): ", i);
　　mVexs[i] = new VNode();
　　mVexs[i].data = readChar();
　　mVexs[i].firstEdge = null;
　　}
　　// 初始化"边"
　　//mMatrix = new int[vlen][vlen];
　　for (int i = 0; i < elen; i++) {
　　// 读取边的起始顶点和结束顶点
　　System.out.printf("edge(%d):", i);
　　char c1 = readChar();
　　char c2 = readChar();
　　int p1 = getPosition(c1);
　　int p2 = getPosition(c2);
　　// 初始化node1
　　ENode node1 = new ENode();
　　node1.ivex = p2;
　　// 将node1链接到"p1所在链表的末尾"
　　if(mVexs[p1].firstEdge == null)
　　mVexs[p1].firstEdge = node1;
　　else
　　linkLast(mVexs[p1].firstEdge, node1);
　　}
　　}