图

图（Graph）结构是一种非线性的数据结构，图在实际生活中有很多例子，比如交通运输网，地铁网络，社交网络，计算机中的状态执行（自动机）等等都可以抽象成图结构。图结构比树结构复杂的非线性结构。

构成

图由顶点（vertex）和边（edge）构成。 所有的顶点构成一个顶点集合，所有的边构成边的集合，一个完整的图结构就是由顶点集合和边集合组成。图结构在数学上记为以下形式：

	G=（V,E） 或者 G=（V（G），E（G））

其中 V（G）表示图结构所有顶点的集合，顶点可以用不同的数字或者字母来表示。E（G）是图结构中所有边的集合，每条边由所连接的两个顶点来表示。
图结构中顶点集合V（G）不能为空，必须包含一个顶点，而图结构边集合可以为空，表示没有边。

顶点

在Java中，定义一个顶点对象，使顶点具有存储数据和表示是否被访问的标志。

public class Vertex {
    public char label;
    public boolean wasVisited;

    public Vertex(char label) {
        this.label = label;
    }
}

边

有两种方式表示边，邻接矩阵和邻接表。本质是使用数组与链表两种不同的数据结构表达和存储图的边。
这里使用邻接矩阵，也就是二维数组存储图的边。

深度优先搜索(DFS)

深度优先搜索，使用栈这个数据结构存储作为临时存储的容器，每次访问一个顶点时，将该顶点放入栈，并标记该顶点已被访问。当该边最后一个顶点被访问后，按顺序依次弹栈，再访问该顶点相邻另外一条边的顶点。直至头顶点弹出栈，搜索

搜索结果

使用伪代码表示

• 检查栈顶点
• 查找该顶点未被访问的邻接点
• 如果没有找到，出栈
• 如果找到邻接点，访问这个顶点并入栈

使用代码表示上面的流程

 Stack stack = new Stack<>();
        vertexList[0].wasVisited = true;
        displayVertex(0);//输出元素
        stack.push(0);

        while (!stack.isEmpty()) {
            int v = getAdjUnvisitedVertex(stack.peek());//获取栈顶元素的相关联顶点
            if (v == -1) {
                stack.pop();//弹出栈
            } else {
                vertexList[v].wasVisited = true;//标记已被访问
                displayVertex(v);//输出元素
                stack.push(v);
            }
        }

广度优先搜索(BFS)

广度优先搜索有点类似于树的层次遍历。就像一个水波一样，先遍历内圈，再一次访问外圈。使用队列这个数据结构，作为临时存储容器。每次遇到一个未被访问的顶点且必须是邻接点时，加入队列中。循环队列中的元素，使队列为空，搜索结束。

搜索结果

使用伪代码表示上面流程

• 将第一个顶点的邻接点入队
• 取出队列的队首元素
• 查找该顶点未被访问的邻接点
• 如果找到邻接点，访问这个顶点并入队
• 如果没有找到，将该下一个队首顶点出队，重复流程

使用代码表示

 vertexList[0].wasVisited = true;
        LinkedList queue = new LinkedList<>();
        queue.push(0);//第一个元素入队
        displayVertex(0);//输出元素

        while (!queue.isEmpty()) {
            int v = queue.pop();//获取队首元素并出队
            int vv;
            while ( (vv = getAdjUnvisitedVertex(v)) != -1) {//如果队首元素有邻接点
                vertexList[vv].wasVisited = true;//标记该邻接点
                displayVertex(vv);
                queue.push(vv);//入队
            }
        }

总代码

package mgGraph;

/**
 * @author dxy
 */
public class Vertex {
    public char label;
    public boolean wasVisited;

    public Vertex(char label) {
        this.label = label;
    }
}

package mgGraph;

import java.util.LinkedList;
import java.util.Stack;

/**
 * @author dxy
 */
public class Graph {
    private final int MAX_SIZE = 20;//最大容量
    private int adjMat[][];//邻接矩阵
    private int nVerts;//顶点数
    private Vertex vertexList[];//顶点数组


    public Graph() {
        //初始化
        vertexList = new Vertex[MAX_SIZE];
        adjMat = new int[MAX_SIZE][MAX_SIZE];
        nVerts = 0;
        for (int i = 0; i < MAX_SIZE; i++) {
            for (int j = 0; j < MAX_SIZE; j++) {
                adjMat[i][j] = 0;
            }
        }
    }


    public void addVertex(char lab) {
        vertexList[nVerts++] = new Vertex(lab);
    }

    public void addEdge(int start, int end) {
        adjMat[start][end] = 1;
        adjMat[end][start] = 1;
    }


    public void displayVertex(int v) {
        System.out.print(vertexList[v].label);
    }

    //查找被搜索的顶点的坐标
    public int getAdjUnvisitedVertex(int v) {
        for (int i = 0; i < nVerts; i++) {
            if (adjMat[v][i] == 1 && vertexList[i].wasVisited == false) {
                return i;
            }
        }
        return -1;
    }

    //深度优先搜索 使用栈
    public void dfs() {
        Stack stack = new Stack<>();
        vertexList[0].wasVisited = true;
        displayVertex(0);//输出元素
        stack.push(0);

        while (!stack.isEmpty()) {
            int v = getAdjUnvisitedVertex(stack.peek());//获取栈顶元素的相关联顶点
            if (v == -1) {
                stack.pop();//弹出栈
            } else {
                vertexList[v].wasVisited = true;//标记已被访问
                displayVertex(v);//输出元素
                stack.push(v);
            }
        }

        for (int i = 0; i < nVerts; i++) {
            vertexList[i].wasVisited = true;
        }
    }


    public void bfs() {
        vertexList[0].wasVisited = true;
        LinkedList queue = new LinkedList<>();
        queue.push(0);//第一个元素入队
        displayVertex(0);//输出元素

        while (!queue.isEmpty()) {
            int v = queue.pop();//获取队首元素并出队
            int vv;
            while ( (vv = getAdjUnvisitedVertex(v)) != -1) {//如果队首元素有邻接点
                vertexList[vv].wasVisited = true;//标记该邻接点
                displayVertex(vv);
                queue.push(vv);//入队
            }
        }

        for (int i = 0; i < nVerts; i++) {
            vertexList[i].wasVisited = false;
        }

    }


    public static void main(String[] args) {
        Graph g = new Graph();
        g.addVertex('A');
        g.addVertex('B');
        g.addVertex('C');
        g.addVertex('D');
        g.addVertex('E');
        g.addVertex('F');

        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(0, 3);
        g.addEdge(3, 4);
        g.bfs();
    }
}