图论与深度优先搜索、广度优先搜索算法（Java语言实现）

一、图的概念

顶点（Vertex）：图中的数据元素，我们称之为顶点，图至少有一个顶点（非空有穷集合）。
边（Edge）：顶点之间的关系用边表示。

1.图（Graph）

图 G 由顶点集 V 和边集 E 组成，记为 $G=(V,E)$ ，其中V(G)表示图G中顶点的有限非空集；$E(G)$ 表示图 G 中顶点之间的关系（边）集合。若 V = { v 1 , v 2 , … , v n } V = \{ v_1 , v_2 , … , v_n \} V={v1​,v2​,…,vn​}，则用 $|V|$ 表示图 G 中顶点的个数，也称图G的阶（Order），$E=\{(u,v)|u\in V,v\in V\}$，用 $|E|$表示图 G 中边的条数

注意：线性表可以是空表，树可以是空树，但图不可以是空，即V一定是非空集

上面的图可以表示为：

$G=(V,E)$
V = { A , B , C , D , E , F } V = \{A, B, C, D, E, F\} V={A,B,C,D,E,F}
$E=\{(A,B),(A,C),(A,D),(B,E),(B,F),(C,E),(D,F)\}$
图的阶数$|V|=6$
图的边的条数 $|E|=7$。

2.无向图（Undirected Graph）与有向图（Directed Graph）

（1）无向图（Undirected Graph）

若 E 是无向边（简称边）的有限集合时，则图 G 为无向图。边是顶点的无序时，记为 $(v,w)$ 或 $(w,v)$ ，因为 $(v,w)=(w,v)$ ，其中v、w是顶点。可以说顶点 w 和顶点 v 互为邻接点。边 $(v,w)$依附于顶点 w 和 v ，或者说边 $(v,w)$ 和顶点 v 、w 相关联。

简单来说，边没有方向的图就是无向图。

$G_u=(V_u,E_u)$
V u = { A , B , C , D , E } V_u = \{A, B, C, D, E\} Vu​={A,B,C,D,E}
$E_u=\{(A,B),(B,D),(B,E),(C,D),(C,E),(D,E)\}$

（2）有向图（Directed Graph）

若 E 是有向边（也称弧（Arcs））的有限集合时，则图 G 为有向图。弧是顶点的有序对，记为 $<v,w>$ ，其中 v 、 w 是顶点， v 称为弧尾， w 称为弧头， $<v,w>$ 称为从顶点v到顶点w的弧，也称v邻接到 w ，或 w 邻接自 v 。 $<v,w>\ne <w,v>$

简单来说，边有方向的图就是有向图。

3. 简单图（Simple Graph）与多重图（Multi Graph）

（1）简单图（Simple Graph）

不存在重复边并且不存在顶点到自身的边的图称为简单图

（2）多重图（Multi Graph）

允许两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联的图多重图。

4. 顶点的度（Degree）

度（Degree）：顶点v的度是指依附于该顶点的边的条数，记为TD(v)。
入度（Indegree）：入度是有向图中以顶点 v 为终点的有向边的数目，记为ID(v)；
出度（Outdegree）：出度是有向图中以顶点 v 为起点的有向边的数目，记为OD(v)。

在有向图中，顶点 v 的度等于其入度和出度之和，即
$TD(v)=ID(v)+OD(v)$。

度在有向图和无向图中都存在，而入度和出度只存在于无向图中。

5. 描述顶点关系的几个概念

• 路径（path）：顶点 v_p 到顶点 v_q 之间的一条路径是指顶点序列 { v p , v i 1 , v i 2 , . . . , v i m − 1 , v i m , v q } \{v_p, v_{i1}, v_{i2},... ,v_{im-1},v_{im},v_q\} {vp​,vi1​,vi2​,...,vim−1​,vim​,vq​}。

• 回路（circuit）：第一个顶点和最后一个顶点相同的路径称为回路或环。

• 简单路径（Simple Path）：在路径序列中，顶点不重复出现的路径称为简单路径。

• 简单回路（Simple Circuith）：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路或环（Cycle）。

• 路径长度（Path Length）：路径上边的数目。

• 点到点的距离（Distance）：从顶点 u 出发到顶点v的最短路径若存在，则此路径的长度称为从 u 到 v 的距离。若从 u 到 v 根本不存在路径，则记该距离为无穷（∞）。

• 连通（connected）：无向图中，若从顶点 v 到顶点 w 有路径存在，则称 v 和 w 是连通的

• 强连通（Strongly Connected）：有向图中，若从顶点 v 到顶点 w 和从顶点 w 到顶点 v 之间都有路径，则称这两个顶点是强连通。

• 弱连通（Weakly Connected）：若一张有向图的边替换为无向边后，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则称原来这张有向图是弱连通。

6.连通图（Connected Graph）与强连通图（Strongly Connected Graph）

连通图（Connected Graph）：若图 G 中任意两个顶点都是连通的，则称图 G 为连通图，否则称为非连通图。
强连通图（Strongly Connected Graph）：若有向图中任何一对顶点都是强连通的，则称此图为强连通图。
弱连通图（Weakly Connected Graph）：将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。

7. 子图（SubGraph）与生成子图（Spanning SubGraph）

设有两个图 $G=(V,E)$ 和 $G^{\prime }=(V^{\prime },E^{\prime })$，若 $V^{\prime }$是 $V$ 的子集，且 $E^{\prime }$是 $E$ 的子集，则称 $G^{\prime }$ 是 $G$ 的子图。

若有满足$V(G^{\prime })=V(G)$的子图 $G^{\prime }$，则称其为 G 的生成子图。

8. 连通分量（Connected Component）

连通分量（Connected Component）：无向图中的极大连通子图称为连通分量。
强连通分量（Strongly Connected Component）：有向图中极大强连通子图称为强连通分量。
弱连通分量（Weakly Connected Component）：将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。一个有向图的基图的极大连通子图称为弱连通分量。

8.生成树（Spanning Tree）和生成森林（Spanning Forest）

如果连通图的一个子图是一棵包含的所有顶点的树，则该子图称为G的生成树(SpanningTree)。

生成树的结果不是唯一的，如图展示的是一张连通图的两个生成树。

生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林（Spanning Forest）。

如图展示的是一张非连通图的生成森林。

9.边的权值（Weight）

• 边的权（Weight）：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
• 带权图（Weighted Graph）：边上带有权值的图称为带权图，也称网（NetWork）。
• 带权路径长度（Weighted Path Length）：当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度

二、图的存储

常见的图的存储方式有四种方式，其中邻接表存储和邻接矩阵存储较为重要。

1.邻接矩阵（Adjacency Matrix）存储

（1）邻接矩阵概念

邻接矩阵是以数组的形式实现图的储存的，一个邻接矩阵需要一个一维数组和一个二维数组共同工作。一维数组存储图中顶点信息，二维数组存储图中的边或弧（邻接关系）的信息。存储邻接关系的二维数组叫做邻接矩阵。

结点数为 n 的图 $G=(V,E)$ 的邻接矩阵 A 是$n\times n$的。

将 G 的顶点编号为 { v 1 , v 2 , … , v n } \{v_1,v_2,…,v_n\} {v1​,v2​,…,vn​}，若$(v_i,v_j)\in E$，则$A[i][j]=0$，否则$A[i][j]=1$。

$$A[i][j]=\{\begin{array}{l}1，若(v_i,v_j)或<v_i,v_j>是E(G)中的边\\ 0，若(v_i,v_j)或<v_i,v_j>不是E(G)中的边\end{array}$$
在加权图中
$$A[i][j]=\{\begin{array}{l}{w}_{ij}，若(v_i,v_j)或<v_i,v_j>是E(G)中的边\\ 0，若(v_i,v_j)或<v_i,v_j>不是E(G)中的边\end{array}$$

如下图是一张无向图的邻接表：

如下图是一张有向图的邻接表：

如下图是一张加权无向图的邻接表：

如下图是一张加权有向图的邻接表：

（2）邻接矩阵实现

以下是创建一个邻接矩阵数据结构以及初始化的代码。

// 邻接矩阵
public class AdjacencyMatrixGraph {
	ArrayList<String> vertexList; //存储顶点集合
	int[][] arcs; // 邻接矩阵
    int vertexNumber; // 图的当前顶点的数目
    int edgeNumber; // 图的当前边的数目
	
    // 初始化
    public AdjacencyMatrixGraph(int maxVertex) {
    	vertexList = new ArrayList<String>(maxVertex);
    	arcs = new int[maxVertex][maxVertex];
    	vertexNumber = 0;
    	edgeNumber = 0;
    	for (int i = 0; i < maxVertex; i++) {
        	for (int j = 0; j < maxVertex; j++) {
    			arcs[i][j] = 0;
    		}
		}
    }
}

2.邻接表（Adjacency Latrix）存储

（1）邻接表的概念

邻接表法结合了顺序存储和链式存储，节省了很大的空间。

邻接表，是指对图 G 中的每个顶点 v 建立一个单链表，第 i 个单链表中的结点表示依附于顶点 v 的边（对于有向图则是以顶点 v 为尾的弧），这个单链表就称为顶点的边表（对于有向图则称为出边表）。

边表的头指针和顶点的数据信息采用顺序存储（称为顶点表），所以在邻接表中存在两种结点：顶点表结点和边表结点。

顶点表结点由顶点域（data）和指向第一条邻接边的指针（irstarc）构成，边表（邻接
表）结点由邻接点域（adjvex）和指向下一条邻接边的指针域（nextarc）构成。

以下是一张无向图邻接表的示意图：

（2）邻接表的实现

以下是创建一个邻接表数据结构以及初始化的代码。

//邻接表
public class AdjacencyListGraph {
	// 邻接表中表对应的链表的顶点
	public class EdgeNode{
        String vertex; // 顶点值
        int weight; // 以该顶点为终点的边的权值
        int adjvex; // 邻接点域，存储该顶点对应的下标
        EdgeNode next; // 指向下一个边的地址域
        EdgeNode() {	
		}
        EdgeNode(String vertex) { 
			this.vertex = vertex; 
		}
        EdgeNode(String vertex, EdgeNode next) { 
			this.vertex = vertex;
			this.next = next; 
		}
        EdgeNode(String vertex, EdgeNode next, int weight) { 
        	this.vertex = vertex;
        	this.next = next; 
        	this.weight = weight;
        }
	}
	// 作为某个点的邻接点的顶点信息
	public class VertexNode{
        String data; // 顶点的值
        EdgeNode firstEdge; // 指向第一条依附该顶点的弧
        VertexNode() {	
		}
        VertexNode(String data) { 
			this.data = data; 
		}
	}
	
	ArrayList<String> vertexList; //存储顶点集合
	VertexNode[] headNode; // 邻接表中左侧所有节点，每一行链表的头结点
    int vertexNumber = 0; // 图的当前顶点的数目
    int edgeNumber = 0; // 图的当前边的数目
    
    // 初始化
    public AdjacencyListGraph(int maxVertex) {
    	vertexList = new ArrayList<String>(maxVertex);
    	headNode = new VertexNode[maxVertex];
    }
}

3.十字链表（Orthogonal Linked List）存储（存储有向图）

十字链表是有向图的另一种链式存储结构。该结构可以看成是将有向图的邻接表和逆邻接表结合起来得到的。用十字链表来存储有向图，可以达到高效的存取效果。

在十字链表中，对应于有向图中的每条弧有一个结；对应于每个顶点也有一个结点。

这些结点的结构如下图所示。

弧结点中有5个域：尾域（tailvex）和头域（headvex）分别指示弧尾和弧头这两个顶
点在图中的位置；链域（hlink）指向弧头相同的下一条弧；链域 （tlink）指向弧尾相同的下一条弧；信息域（info）指向该弧的相关信息。这样，弧头相同的弧就在同一个链表上，弧尾相同的弧也在同一个链表上。

顶点结点中有3个域：data域存放顶点相关的数据信息，如顶点名称；firstin和 firstout
两个域分别指向以该顶点为弧头或弧尾的第一个弧结点。

以下是一张图的十字链表表示法：

4.邻接多重表（Adjacency Multi List）存储（存储无向图）

邻接多重表是无向图的一种存储方式。

邻接多重表是邻接表的改进，它把边的两个顶点存放在边表结点中，所有依附于同一个顶点的边串联在同一链表中，由于每条边依附于两个顶点，则每个边表结点同时链接在两个链表中。

与十字链表类似，在邻接多重表中，每条边用一个结点表示，其结构如下所示。

其中，mark 为标志域，可用以标记该条边是否被搜索过；ivex 和 jvex 为该边依附的两个顶点在图中的位置；ilink 指向下一条依附于顶点 ivex 的边；jlink 指向下一条依附于顶点 jvex 的边，info 为指向和边相关的各种信息的指针域。

每个顶点也用一个结点表示，它由如下所示的两个域组成。

其中，data域存储该顶点的相关信息，firstedge域指示第一条依附于该顶点的边。

以下是一张图的邻接多重表表示法：

三、图的遍历与搜索

1.广度优先遍历（BFS）

广度优先搜索（Breadth First Search，BFS）类似于二叉树的层序遍历算法。

（1）算法思想

基本思想是：首先访问起始顶点 v ，接着由v 出发，依次访问v的各个未访问过的邻接顶点 $w_1,w_2,\dots ,w_i$，然后依次访问$w_1,w_2,\dots ,w_i$的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。若此时图中尚有顶点未被访问，则另选图中个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。

换句话说，广度优先搜索遍历图的过程是以 v 为起始点，由近至远依次访问和 v 有路径相通且路径长度为1，2,…的顶点。

广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。

为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。

（2）算法案例

假设从a 结点开始访问，a 先入队。此时队列非空，取出队头元素 a ，由于 b、c与a 邻接且未被访问过，于是依次访问b、c，并将b、c依次入队。队列非空，取出队头元素 b，依次访问与 b 邻接且未被访问的顶点d、e，并将 d、e入队（注意: a 与 b 也邻接，但 a 已置访问标记，故不再重复访问）。此时队列非空，取出队头元素 c ，访问与 c 邻接且未被访问的顶点 f、 g，并将 f、 g入队。此时，取出队头元素 d，但与 d 邻接且未被访问的顶点为空，故不进行任何操作。继续取出队头元素 e，将 h 入队列。最终取出队头元素h 后，队列为空，从而循环自动跳出。

遍历结果为：a b c d e f g h。

（3）代码实现

3.1 邻接矩阵存储方式：

    /**
     *  Breadth First Search Algorithm: 广度优先搜索算法(bfs)
     *  @return: java.util.List<java.lang.Object>
     */
    public List<Object> breadthFirstSearch() {
        return breadthFirstSearch(0);
    }
    public List<Object> breadthFirstSearch(int startIndex) {
    	List<Object> bfsList = new ArrayList<Object>();
        boolean[] isVisited = new boolean[vertexList.size()]; // 定义给数组boolean[], 记录某个结点是否被访问
    	isVisited = new boolean[vertexList.size()];
        //遍历所有的结点，依次进行bfs
        for (int i = startIndex; i < vertexNumber+startIndex; i++) {
        	int index = i%vertexNumber;
            if (!isVisited[index]) {
            	breadthFirstSearch(isVisited, index, bfsList);
            }
        }
        return bfsList;
    }
    public void breadthFirstSearch(boolean[] isVisited, int index, List<Object> bfsList) {
    	int u; // u代表队列的头结点对应的下标。
    	int w; // w代表邻接节点
    	Queue<Integer> queue = new ArrayDeque<>(); // 辅助队列
    	bfsList.add(vertexList.get(index));
//    	System.out.print(vertexList.get(index) + " "); // 首先我们访问该结点,输出
    	isVisited[index] = true; // index已经在上一行被访问过了，所以变为true
    	queue.add(index); // 使A进入队列
    	// 对队列中的几个元素依次执行广度遍历
    	while (!queue.isEmpty()) {
            u = queue.poll();// 取出队列的头
            w = getFirstNeighbor(u); // 得到第一个邻接点的下标
            while (w != -1) { // 如果有邻接顶点就循换，直到没有了为止
                if (!isVisited[w]) { // 如果w没被访问过
                    //如果第一个邻接点未被访问则访问第一个邻接节点
                	bfsList.add(getValueByIndex(w));
//                    System.out.print(getValueByIndex(w) + " ");
                    isVisited[w] = true;
                    queue.add(w);
                }
        		// 如果w结点已经被访问过，寻找u的下一个邻接顶点。实现广度遍历
        		w = getNextNeighbor(u, w);
            }
    	}
    }

3.2 邻接表存储方式：

    /**
     *  Breadth First Search Algorithm: 广度优先搜索算法(bfs)
     *  @return: java.util.List<java.lang.Object>
     */
    public List<Object> breadthFirstSearch() {
        return breadthFirstSearch(0);
    }
    public List<Object> breadthFirstSearch(int startIndex) {
    	List<Object> bfsList = new ArrayList<Object>();
        boolean[] isVisited = new boolean[vertexList.size()]; // 定义给数组boolean[], 记录某个结点是否被访问
    	isVisited = new boolean[vertexList.size()];
        //遍历所有的结点，依次进行bfs
        for (int i = startIndex; i < vertexNumber+startIndex; i++) {
        	int index = i%vertexNumber;
            if (!isVisited[index]) {
            	breadthFirstSearch(isVisited, index, bfsList);
            }
        }
        return bfsList;
    }
    public void breadthFirstSearch(boolean[] isVisited, int index, List<Object> bfsList) {
    	Queue<Integer> queue = new ArrayDeque<>(); // 辅助队列
        if (!isVisited[index]) {
        	isVisited[index] = true;
        	bfsList.add(headNode[index].data);
        	queue.add(index); // 进入队列
        }
    	isVisited[index] = true; // index已经在上一行被访问过了，所以变为true
    	// 对队列中的几个元素依次执行广度遍历
    	while (!queue.isEmpty()) {
    		int j = queue.poll();// 取出队列的头
            EdgeNode edgeNode = headNode[j].firstEdge;
            while (edgeNode != null) {
                int k = edgeNode.adjvex;
                if (!isVisited[k])
                {
                	isVisited[k] = true;
                	bfsList.add(headNode[k].data);
                    queue.add(k);
                }
                edgeNode = edgeNode.next;
            }
    	}
    }

（4）性能分析

无论是邻接表还是邻接矩阵的存储方式，BFS算法都需要借助一个辅助队列Q，n个顶点均需入队一次，在最坏的情况下，空间复杂度为 $O(|V|)$。
采用邻接表存储方式时，每个顶点均需搜索一次(或入队一次)，故时间复杂度为 $O(|V|)$，在搜索任一顶点的邻接点时，每条边至少访问一次，故时间复杂度为 $O(|E|)$，算法总的时间复杂度为 $O(|V|+|E|)$。采用邻接矩阵存储方式时，查找每个顶点的邻接点所需的时间为 $O(|V|)$，故算法总的时间复杂度为 $O(|V{|}^2)$。

2.深度优先遍历（DFS）

深度优先搜索(Depth First Search，DFS)类似于树的先序遍历。

（1）算法思想

基本思想：首先访问图中某一起始顶点，然后由 v 出发，访问与 v 邻接且未被访问的任一顶点 w ，再访问与 w ，邻接且未被访问的任一顶点 w 。重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

（2）算法案例

假设从a 结点开始访问，a 先入被访问。此时以 a 为基准，开始沿着 b 或 c 中的一个顶点深度搜索。例如先访问 b 顶点，然后以 b 为基准，继续访问 d 顶点。访问 d 顶点后，发现其除了 b 顶点没有其他的相邻顶点，所以回到上一步访问的 b 顶点并开始沿着另一条路线访问，依次访问 e 和 h 后，返回到 a 顶点，并开始沿着另一条路线访问 c 顶点，c 顶点为基准再次深度优先搜索，先访问 f 顶点，发现已经访问到尽头后返回 c 顶点并访问 g 顶点。

遍历结果为：a b d e h c f g。

（3）代码实现

3.1 邻接矩阵存储方式：

    /**
     *  Deep First Search Algorithm: 深度优先搜索算法(dfs)
     *  @return: java.util.List<java.lang.String>
     */
    public List<Object> deepFirstSearch() {
        return deepFirstSearch(0);
    }
    public List<Object> deepFirstSearch(int startIndex) {
    	List<Object> dfsList = new ArrayList<Object>();
        boolean[] isVisited = new boolean[vertexList.size()]; // 定义给数组boolean[], 记录某个结点是否被访问
        //遍历所有的结点，进行dfs[回溯]
        for (int i = startIndex; i < vertexNumber+startIndex; i++) {
        	int index = i%vertexNumber;
            if (!isVisited[index]) {
            	deepFirstSearch(isVisited, index ,dfsList);
            }
        }
        return dfsList;
    }
    public void deepFirstSearch(boolean[] isVisited, int index, List<Object> dfsList) {
    	dfsList.add(vertexList.get(index)); // 首先我们访问该结点,输出
//    	System.out.print(vertexList.get(index) + " "); // 首先我们访问该结点,输出
    	isVisited[index] = true; // index已经在上一行被访问过了，所以变为true
    	// 深度优先搜索，重复找第一个邻接节点，直到找不到了为止
    	int w = getFirstNeighbor(index); // 得到index顶点的第一个邻接结点的下标
    	while (w != -1) { // 如果有邻接顶点就循换，直到没有了为止
    		if (!isVisited[w]) { // 如果w没被访问过
    			deepFirstSearch(isVisited, w, dfsList);
    		}
    		// 如果w结点已经被访问过，说明一轮深度搜索已完成！寻找下一个邻接顶点
    		w = getNextNeighbor(index, w);
    	}
    }

3.2 邻接表存储方式：

    /**
     *  Deep First Search Algorithm: 深度优先搜索算法(dfs)
     *  @return: java.util.List<java.lang.String>
     */
    public List<Object> deepFirstSearch() { 
        return deepFirstSearch(0) ; // 默认遍历起始节点为0
    }
    public List<Object> deepFirstSearch(int startIndex) {
    	List<Object> dfsList = new ArrayList<>(); // 存放遍历结果
        int i;
        boolean[] visited = new boolean[vertexNumber]; // 记录每个顶点是否被访问过
        for (i = startIndex; i < vertexNumber+startIndex; i++) {
        	int index = i%vertexNumber;
            if (!visited[index]) {
            	deepFirstSearch(index, visited, dfsList);
            }
        }
        return dfsList;
    }
    public void deepFirstSearch(int index, boolean[] visited, List<Object> dfsList) {
        dfsList.add(headNode[index].data); // 遍历到第index节点
        EdgeNode edgeNode = headNode[index].firstEdge; // 此顶点的第一条边
        visited[index] = true;
        while (edgeNode != null) {
            if (!visited[edgeNode.adjvex]) {
            	deepFirstSearch(edgeNode.adjvex, visited, dfsList);
            }
            edgeNode = edgeNode.next;
        }
    }

（4）性能分析

DFS 算法是一个递归算法，需要借助一个递归工作栈，故其空间复杂度为 $O(|V|)$。
遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所用的存储结构。以邻接矩阵表示时,查找每个顶点的邻接点所需的时间为 $O(|V|)$,故总的时间复杂度为 $O(|V{|}^2)$。以邻接表表示时，查找所有顶点的邻接点所需的时间为 $O(|E|)$，访问顶点所需的时间为 $O(|V|)$，此时，总的时间复杂度为 $O(|V|+|E|)$。

四、完整测试代码

分别用邻接矩阵（Adjacency Matrix）存储方式和邻接表（Adjacency List）存储方式，创建如下所示的图，打印其数据结构，并分别使用深度优先搜索（Deep First Search）和广度优先搜索（BreadthFirst Search）进行遍历。

代码如下：

1.邻接矩阵存储

package graph;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Queue;

// 邻接矩阵
public class AdjacencyMatrixGraph {
	ArrayList<String> vertexList; //存储顶点集合
	int[][] arcs; // 邻接矩阵
    int vertexNumber; // 图的当前顶点的数目
    int edgeNumber; // 图的当前边的数目
	
    // 初始化
    public AdjacencyMatrixGraph(int maxVertex) {
    	vertexList = new ArrayList<String>(maxVertex);
    	arcs = new int[maxVertex][maxVertex];
    	vertexNumber = 0;
    	edgeNumber = 0;
    	for (int i = 0; i < maxVertex; i++) {
        	for (int j = 0; j < maxVertex; j++) {
    			arcs[i][j] = 0;
    		}
		}
    }
	
    //插入顶点
    public void insertVertex(String vertex) {
        vertexList.add(vertex); // 把要插入的值添加到vertexList中即可。
        vertexNumber ++;
        System.out.println(vertex + " has been entered!");
    }
    
    /**
         * 添加边（a->b的边）
     * @param a 
     * @param b
     * @param weight 权重（不带权的图即weight=1）
     */
    public void insertEdge(int a, int b, int weight) {
    	if(a < vertexNumber && b < vertexNumber) {
        	if (arcs[a][b] == 0) {
            	arcs[a][b] = weight; // 将权重添加到arcs[a][b]中即可
            	System.out.println(vertexList.get(a)+"->"+vertexList.get(b)+" connect edge!");
        	}
        	edgeNumber ++;
    	}
    }

    // 得到index顶点的第一个邻接结点的下标
    public int getFirstNeighbor(int index) {
        for (int j = 0; j < vertexNumber; j++) {
            if (arcs[index][j] > 0) { // arcs[index][j]即为第一个邻接点的权重
//            	System.out.println(vertexList.get(j) + " is the first neighbor");
                return j;
            }
        }
        return -1;
    }
    
    //根据前一个邻接结点的下标来获取下一个邻接结点
    public int getNextNeighbor (int a, int b) {
        for (int j = b+1; j < vertexNumber; j++) {
            if (arcs[a][j] > 0) { // arcs[a][j]即为下一个邻接点的权重
//            	System.out.println(vertexList.get(j) + " is the next neighbor");
                return j;
            }
        }     
    	return -1;
    }
    
    
    // 返回结点对应的顶点值 0:"A" 1:"B" 2:"C" 3:"D" 4:"E"
    public String getValueByIndex(int index) {
    	return vertexList.get(index);
    }
    // 获取a->b的权值
    public int getWeight(int a, int b) {
    	return arcs[a][b];
    }

    
    /**
     *  Deep First Search Algorithm: 深度优先搜索算法(dfs)
     *  @return: java.util.List<java.lang.String>
     */
    public List<Object> deepFirstSearch() {
        return deepFirstSearch(0);
    }
    public List<Object> deepFirstSearch(int startIndex) {
    	List<Object> dfsList = new ArrayList<Object>();
        boolean[] isVisited = new boolean[vertexList.size()]; // 定义给数组boolean[], 记录某个结点是否被访问
        //遍历所有的结点，进行dfs[回溯]
        for (int i = startIndex; i < vertexNumber+startIndex; i++) {
        	int index = i%vertexNumber;
            if (!isVisited[index]) {
            	deepFirstSearch(isVisited, index ,dfsList);
            }
        }
        return dfsList;
    }
    public void deepFirstSearch(boolean[] isVisited, int index, List<Object> dfsList) {
    	dfsList.add(vertexList.get(index)); // 首先我们访问该结点,输出
//    	System.out.print(vertexList.get(index) + " "); // 首先我们访问该结点,输出
    	isVisited[index] = true; // index已经在上一行被访问过了，所以变为true
    	// 深度优先搜索，重复找第一个邻接节点，直到找不到了为止
    	int w = getFirstNeighbor(index); // 得到index顶点的第一个邻接结点的下标
    	while (w != -1) { // 如果有邻接顶点就循换，直到没有了为止
    		if (!isVisited[w]) { // 如果w没被访问过
    			deepFirstSearch(isVisited, w, dfsList);
    		}
    		// 如果w结点已经被访问过，说明一轮深度搜索已完成！寻找下一个邻接顶点
    		w = getNextNeighbor(index, w);
    	}
    }
    

    /**
     *  Breadth First Search Algorithm: 广度优先搜索算法(bfs)
     *  @return: java.util.List<java.lang.Object>
     */
    public List<Object> breadthFirstSearch() {
        return breadthFirstSearch(0);
    }
    public List<Object> breadthFirstSearch(int startIndex) {
    	List<Object> bfsList = new ArrayList<Object>();
        boolean[] isVisited = new boolean[vertexList.size()]; // 定义给数组boolean[], 记录某个结点是否被访问
    	isVisited = new boolean[vertexList.size()];
        //遍历所有的结点，依次进行bfs
        for (int i = startIndex; i < vertexNumber+startIndex; i++) {
        	int index = i%vertexNumber;
            if (!isVisited[index]) {
            	breadthFirstSearch(isVisited, index, bfsList);
            }
        }
        return bfsList;
    }
    public void breadthFirstSearch(boolean[] isVisited, int index, List<Object> bfsList) {
    	int u; // u代表队列的头结点对应的下标。
    	int w; // w代表邻接节点
    	Queue<Integer> queue = new ArrayDeque<>(); // 辅助队列
    	bfsList.add(vertexList.get(index));
//    	System.out.print(vertexList.get(index) + " "); // 首先我们访问该结点,输出
    	isVisited[index] = true; // index已经在上一行被访问过了，所以变为true
    	queue.add(index); // 使A进入队列
    	// 对队列中的几个元素依次执行广度遍历
    	while (!queue.isEmpty()) {
            u = queue.poll();// 取出队列的头
            w = getFirstNeighbor(u); // 得到第一个邻接点的下标
            while (w != -1) { // 如果有邻接顶点就循换，直到没有了为止
                if (!isVisited[w]) { // 如果w没被访问过
                    //如果第一个邻接点未被访问则访问第一个邻接节点
                	bfsList.add(getValueByIndex(w));
//                    System.out.print(getValueByIndex(w) + " ");
                    isVisited[w] = true;
                    queue.add(w);
                }
        		// 如果w结点已经被访问过，寻找u的下一个邻接顶点。实现广度遍历
        		w = getNextNeighbor(u, w);
            }
    	}
    }
    
    // 显示图对应的矩阵
    public void display() {

    	for (int i = 0; i < vertexNumber; i++) {
            System.out.print(vertexList.get(i)+"\t");
    	}
        System.out.println();
    	for (int i = 0; i < vertexNumber; i++) {
        	for (int j = 0; j < vertexNumber; j++) {
                System.out.print(arcs[i][j] + "\t");
    		}
        	System.out.println();
		}
	}
    
	public static void main(String[] args) {
		AdjacencyMatrixGraph adjacencyMatrixGraph = new AdjacencyMatrixGraph(5);
		adjacencyMatrixGraph.insertVertex("A");
		adjacencyMatrixGraph.insertVertex("B");
		adjacencyMatrixGraph.insertVertex("C");
		adjacencyMatrixGraph.insertVertex("D");
		adjacencyMatrixGraph.insertVertex("E");
		
		adjacencyMatrixGraph.insertEdge(0, 1, 15);
		adjacencyMatrixGraph.insertEdge(0, 4, 9);
		adjacencyMatrixGraph.insertEdge(1, 2, 3);
		adjacencyMatrixGraph.insertEdge(2, 3, 2);
		adjacencyMatrixGraph.insertEdge(3, 0, 11);
		adjacencyMatrixGraph.insertEdge(3, 1, 7);
		adjacencyMatrixGraph.insertEdge(4, 2, 21 );

		System.out.println("==========Adjacency Matrix==========");
		adjacencyMatrixGraph.display();
//		adjacencyMatrixGraph.getFirstNeighbor(1);
//		adjacencyMatrixGraph.getNextNeighbor(3, 0);
		System.out.println("============Deep First Search============");
		List<Object> dfsList = adjacencyMatrixGraph.deepFirstSearch(); // A B C D E 
		System.out.println(dfsList);
		System.out.println("==========Breadth First Search===========");
		List<Object> bfsList = adjacencyMatrixGraph.breadthFirstSearch(); // A B E C D
		System.out.println(bfsList);
		System.out.println("============Prim============");
		adjacencyMatrixGraph.prim(adjacencyMatrixGraph.arcs);
		System.out.println("============Kruskal============");
		adjacencyMatrixGraph.kruskal(adjacencyMatrixGraph.arcs);
		/*   A B C D E
		 * A 0 1 0 0 1 
		 * B 0 0 1 0 0 
		 * C 0 0 0 1 0 
		 * D 1 1 0 0 0 
		 * E 0 0 1 0 0 
		 */
		
	}
}

2.邻接表存储

package graph;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

//邻接表
public class AdjacencyListGraph {
	// 邻接表中表对应的链表的顶点
	public class EdgeNode{
        String vertex; // 顶点值
        int weight; // 以该顶点为终点的边的权值
        int adjvex; // 邻接点域，存储该顶点对应的下标
        EdgeNode next; // 指向下一个边的地址域
        EdgeNode() {	
		}
        EdgeNode(String vertex) { 
			this.vertex = vertex; 
		}
        EdgeNode(String vertex, EdgeNode next) { 
			this.vertex = vertex;
			this.next = next; 
		}
        EdgeNode(String vertex, EdgeNode next, int weight) { 
        	this.vertex = vertex;
        	this.next = next; 
        	this.weight = weight;
        }
	}
	// 作为某个点的邻接点的顶点信息
	public class VertexNode{
        String data; // 顶点的值
        EdgeNode firstEdge; // 指向第一条依附该顶点的弧
        VertexNode() {	
		}
        VertexNode(String data) { 
			this.data = data; 
		}
	}
	
	ArrayList<String> vertexList; //存储顶点集合
	VertexNode[] headNode; // 邻接表中左侧所有节点，每一行链表的头结点
    int vertexNumber = 0; // 图的当前顶点的数目
    int edgeNumber = 0; // 图的当前边的数目
    
    // 初始化
    public AdjacencyListGraph(int maxVertex) {
    	vertexList = new ArrayList<String>(maxVertex);
    	headNode = new VertexNode[maxVertex];
    }
    
    //插入顶点
    public void insertVertex(String vertex) {
    	insertVertex(vertex, 1); // 默认权值为1
    }
    public void insertVertex(String vertex, int weight) {
    	VertexNode graphNode = new VertexNode(vertex);
    	// 需要将顶点值添加到adjacencyListNode数组中，但是不知道数组空位在哪里，所以需要循换
        for (int i = 0; i < headNode.length; i++){
            if(headNode[i] == null){ // 如果第i个位置是null。说明添加到该位置中
            	headNode[i] = graphNode;// 添加到邻接表中左侧
            	vertexList.add(vertex); // 把要插入的顶点值添加到vertexList中。
            	vertexNumber ++;
            	System.out.println(vertex + " has been entered!");
                break;
            }
        }
    }
    
    /**
     * @descript 创建一条firstNode与secondNode相连的边，其权重为weight
     * @param firstNode 第一个顶点的名称
     * @param secondNode 第二个顶点的名称
     * @param weight 两点之间的边的权重
     */

    public void insertEdge(String firstNode, String secondNode) {
    	insertEdge(firstNode, secondNode, 1);
    }
    public void insertEdge(String firstNode, String secondNode, int weight) {
    	boolean isContainsFirst = vertexList.contains(firstNode);
    	boolean isContainsSecond = vertexList.contains(secondNode);
    	if (isContainsFirst && isContainsSecond) { // 要添加的两个点存在于顶点集合里
    		for (int i = 0; i < headNode.length; i++) { // 遍历所有的头结点
    			if (headNode[i] != null && headNode[i].data.equals(firstNode)) {
    				VertexNode vertexNode = headNode[i]; // 要对哪个头结点操作，先标记出来
    				boolean isExist = false; // 标记要添加的边是否存在
					int adjvex = -1;
		    		for (int j = 0; j < headNode.length; j++) { // 遍历所有的头结点
		    			if (headNode[j].data.equals(secondNode)) {
		    				adjvex = j;
		    			}
		    		}
    				if(vertexNode.firstEdge == null) {
    					EdgeNode edgeNode = new EdgeNode();
    					edgeNode.vertex = secondNode;
    					edgeNode.weight = weight;
    					edgeNode.adjvex = adjvex;
    					vertexNode.firstEdge = edgeNode;
    					System.out.println(firstNode+"->"+secondNode+" have added edges!");
    					continue;
    				}
    				EdgeNode edgeNode = vertexNode.firstEdge;
    				// 以此寻找graphNode为头结点的链表所有节点，看是否有和secondNode相同的
    				// 如果和secondNode名字相同，说明两个节点间的边已经存在
    				while (edgeNode.next != null) {
    					if(edgeNode.vertex.equals(secondNode)) {
    						isExist = true; // 两个节点间的边已经存在
    						break;
    					}
    					edgeNode = edgeNode.next;
    				}
    				
    				// 两个节点之间的边不存在，那么在链表中添加信息
    				if (!isExist) {
    					EdgeNode newEdgeNode = new EdgeNode();
    					newEdgeNode.vertex = secondNode;
    					newEdgeNode.weight = weight;
    					newEdgeNode.adjvex = adjvex;
    					edgeNode.next = newEdgeNode;
    					System.out.println(firstNode+"->"+secondNode+" have added edges!");
    				}
    				break;	
    			}
    		}
    	}
    }
    
    
	//打印
	public void display(){
		for (int i = 0; i < headNode.length; i++) {
			EdgeNode edgeNode = headNode[i].firstEdge;
            System.out.print(headNode[i].data);
			if (edgeNode != null) {
				System.out.print("-->"+edgeNode.weight+"\t"+  "[" + headNode[edgeNode.adjvex].data + "|" + edgeNode.weight + "]");
				EdgeNode temp = edgeNode.next;
                while (temp != null){
                    System.out.print("-->"+edgeNode.weight +"\t"+ "[" + headNode[temp.adjvex].data + "|" + temp.weight + "]");
                    temp = temp.next;
                }
                System.out.println();
			} else {
				break;
			}
		}
	}
	
    /**
     *  Deep First Search Algorithm: 深度优先搜索算法(dfs)
     *  @return: java.util.List<java.lang.String>
     */
    public List<Object> deepFirstSearch() { 
        return deepFirstSearch(0) ; // 默认遍历起始节点为0
    }
    public List<Object> deepFirstSearch(int startIndex) {
    	List<Object> dfsList = new ArrayList<>(); // 存放遍历结果
        int i;
        boolean[] visited = new boolean[vertexNumber]; // 记录每个顶点是否被访问过
        for (i = startIndex; i < vertexNumber+startIndex; i++) {
        	int index = i%vertexNumber;
            if (!visited[index]) {
            	deepFirstSearch(index, visited, dfsList);
            }
        }
        return dfsList;
    }
    public void deepFirstSearch(int index, boolean[] visited, List<Object> dfsList) {
        dfsList.add(headNode[index].data); // 遍历到第index节点
        EdgeNode edgeNode = headNode[index].firstEdge; // 此顶点的第一条边
        visited[index] = true;
        while (edgeNode != null) {
            if (!visited[edgeNode.adjvex]) {
            	deepFirstSearch(edgeNode.adjvex, visited, dfsList);
            }
            edgeNode = edgeNode.next;
        }
    }

    /**
     *  Breadth First Search Algorithm: 广度优先搜索算法(bfs)
     *  @return: java.util.List<java.lang.Object>
     */
    public List<Object> breadthFirstSearch() {
        return breadthFirstSearch(0);
    }
    public List<Object> breadthFirstSearch(int startIndex) {
    	List<Object> bfsList = new ArrayList<Object>();
        boolean[] isVisited = new boolean[vertexList.size()]; // 定义给数组boolean[], 记录某个结点是否被访问
    	isVisited = new boolean[vertexList.size()];
        //遍历所有的结点，依次进行bfs
        for (int i = startIndex; i < vertexNumber+startIndex; i++) {
        	int index = i%vertexNumber;
            if (!isVisited[index]) {
            	breadthFirstSearch(isVisited, index, bfsList);
            }
        }
        return bfsList;
    }
    public void breadthFirstSearch(boolean[] isVisited, int index, List<Object> bfsList) {
    	Queue<Integer> queue = new ArrayDeque<>(); // 辅助队列
        if (!isVisited[index]) {
        	isVisited[index] = true;
        	bfsList.add(headNode[index].data);
        	queue.add(index); // 进入队列
        }
    	isVisited[index] = true; // index已经在上一行被访问过了，所以变为true
    	// 对队列中的几个元素依次执行广度遍历
    	while (!queue.isEmpty()) {
    		int j = queue.poll();// 取出队列的头
            EdgeNode edgeNode = headNode[j].firstEdge;
            while (edgeNode != null) {
                int k = edgeNode.adjvex;
                if (!isVisited[k])
                {
                	isVisited[k] = true;
                	bfsList.add(headNode[k].data);
                    queue.add(k);
                }
                edgeNode = edgeNode.next;
            }
    	}
    }
    
    
	public static void main(String[] args) {
		AdjacencyListGraph adjacencyListGraph = new AdjacencyListGraph(5);

		adjacencyListGraph.insertVertex("A");
		adjacencyListGraph.insertVertex("B");
		adjacencyListGraph.insertVertex("C");
		adjacencyListGraph.insertVertex("D");
		adjacencyListGraph.insertVertex("E");
		
		adjacencyListGraph.insertEdge("A", "B", 15);
		adjacencyListGraph.insertEdge("A", "E", 9);
		adjacencyListGraph.insertEdge("B", "C", 3);
		adjacencyListGraph.insertEdge("C", "D", 2);
		adjacencyListGraph.insertEdge("D", "A", 11);
		adjacencyListGraph.insertEdge("D", "B", 7);
		adjacencyListGraph.insertEdge("E", "C", 21);
		System.out.println("==========Adjacency List==========");
		adjacencyListGraph.display();
		System.out.println("==========Deep First Search==========");
		List<Object> dfsList = adjacencyListGraph.deepFirstSearch();
		System.out.println(dfsList);

		System.out.println("==========Breadth First Search==========");
		List<Object> bfsList = adjacencyListGraph.breadthFirstSearch();
		System.out.println(bfsList);
		/*
		 * A-->15	[B|15]-->15	[E|9]
		 * B-->3	[C|3]
		 * C-->2	[D|2]
		 * D-->11	[A|11]-->11	[B|7]
		 * E-->21	[C|21]
		 */
	}
}