我敢说，这图绝对跟你想象中的不太一样！

Original 倪升武程序员私房菜 2018-12-04

阅读本文大概需要6分钟

我没骗你们，这个图的确不是你想象中的图。你想看什么图我还不知道？不过，我的图却是大千世界，继续以通俗易懂的方式给你提升一波内功。不信你继续往下读。

图是一种与树有些相像的数据结构，实际上，从数学意义上说，树是图的一种。然而在计算机程序设计中，图的应用方式与树不同。

我前面一些文章中讨论的数据结构都有一个框架，这个框架都是由相应的算法设定的。比如说，二叉树是那样一个形状，就是因为那样的形状使它更容易搜索数据和插入新数据，树的边表示了从一个节点到另一个节点的快捷方式。而图通常也有一个固定的形状，这是由物理或抽象的问题所决定的。比如说，图中节点表示城市，而边表示城市间的航班线，这些都是固定的。即，图的形状取决于真实世界的具体情况。在图中，我们称节点为顶点。

在大多数情况下，顶点表示某个真实世界的对象，这个对象必须用数据项来描述。例如顶点代表城市，那么它需要存储城市名字、海拔高度、地理位置等相关信息。因此通常用一个顶点类的对象来表示一个顶点。这里我们仅仅在顶点中存储了一个字母来标识顶点，同时还有一个标志位，用来判断该顶点有没有被访问过。

class Vertex { //顶点类
public char label; //label: eg.'A'
public boolean wasVisited;
public Vertex(char lab) {
label = lab;
wasVisited = false;
}
}

顶点对象能放在数组（这里用vertexList数组）中，然后用下标指示，也可以放在链表或其他数据结构中，但不论使用什么数据结构，存储只为了使用方便，这与边如何连接点没有关系。

前面提到的树的表示中，大多数情况下都是每个节点包含它的子节点的引用，也可以用数组表示树，数组中的节点位置决定了它和其他节点的关系，比如堆。然而，图并不像树那样拥有几种固定的结构，因为图的每个顶点可以与任意多个顶点连接。为了模拟这种自由形式的组织结构，需要用一种不同的方法表示边，一般用两种方式：邻接矩阵和邻接表。

邻接矩阵是一个二维数组，里面的数据表示两点间是否存在边。如果图有N个顶点，那么邻接矩阵就是N*N的数组，如下表所示：1表示有边，0表示没有边，也可以用true和false来表示。

邻接表是一个链表数组（或者链表的链表），每个单独的链表表示了有哪些顶点与当前顶点邻接，如下表所示：A邻接顶点有B、C和D。

下面讨论下图中的搜索。在图中实现的基本操作之一就是搜索从一个定到可以到达其他哪些顶点，或者找所有当前顶点可到达的顶点。有两种常用的方法可用来搜索图：深度优先搜索（DFS）和广度优先搜索（BFS），它们最终都会到达所有的连通顶点。深度优先搜索通过栈来实现，而广度优先搜索通过队列来实现。具体的见下面的程序：

public class Graph {
private final int MAX_VERTS = 20;
private Vertex vertexArray[]; //存储顶点的数组
private int adjMat[][]; //存储是否有边界的矩阵数组, 0表示没有边界，1表示有边界
private int nVerts; //顶点个数
private StackX stack; //深度搜索时用来临时存储的栈
private QueueX queue; //广度搜索时用来临时存储的队列
public Graph() {
vertexArray = new Vertex[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for(int i = 0; i < MAX_VERTS; i++) {
for(int j = 0; j < MAX_VERTS; j++) {
adjMat[i][j] = 0;
}
}
stack = new StackX();
queue = new QueueX();
}
public void addVertex(char lab) {
vertexArray[nVerts++] = new Vertex(lab);
}
public void addEdge(int start, int end) {
adjMat[start][end] = 1;
adjMat[start][end] = 1;
}
public void displayVertex(int v) {
System.out.print(vertexArray[v].label);
}
/*
* 深度优先搜索算法:做四件事
* 1. 用peek()方法检查栈顶的顶点
* 2. 试图找到这个顶点还未访问的邻节点
* 3. 如果没有找到，出栈
* 4. 如果找到这样的顶点，访问这个顶点，并把它放入栈
* 深度优先算法类似于从树的跟逐个沿不同路径访问到不同的叶节点
*/
public void depthFirstSearch() {
//begin at vertex 0
vertexArray[0].wasVisited = true; //make it
displayVertex(0);
stack.push(0);
while(!stack.isEmpty()) {
//get an unvisited vertex adjacent to stack top
int v = getAdjUnvisitedVertex(stack.peek());
if(v == -1) { //if no such vertex
stack.pop();
}
else { //if it exists
vertexArray[v].wasVisited = true;
displayVertex(v);
stack.push(v);
}
}
//stack is empty, so we're done
for(int i = 0; i < nVerts; i++) {
vertexArray[i].wasVisited = false;
}
}
//returns an unvisited vertex adj to v
public int getAdjUnvisitedVertex(int v) {
for(int i = 0; i < nVerts; i++) {
if(adjMat[v][i] == 1 && vertexArray[i].wasVisited == false) {//v和i之间有边，且i没被访问过
return i;
}
}
return -1;
}
/*
* 广度优先搜索算法：做四件事
* 1. 用remove()方法检查栈顶的顶点
* 2. 试图找到这个顶点还未访问的邻节点
* 3. 如果没有找到，该顶点出列
* 4. 如果找到这样的顶点，访问这个顶点，并把它放入队列中
* 深度优先算法中，好像表现的要尽快远离起始点，在广度优先算法中，要尽可能靠近起始点。
* 它首先访问其实顶点的所有邻节点，然后再访问较远的区域。这种搜索不能用栈，而要用队列来实现。
* 广度优先算法类似于从树的跟逐层往下访问直到底层
*/
public void breadthFirstSearch() {
vertexArray[0].wasVisited = true;
displayVertex(0);
queue.insert(0);
int v2;
while(!queue.isEmpty()) {
int v1 = queue.remove();
//until it has no unvisited neighbors
while((v2 = getAdjUnvisitedVertex(v1)) != -1) {
vertexArray[v2].wasVisited = true;
displayVertex(v2);
queue.insert(v2);
}
}
for(int i = 0; i < nVerts; i++) {
vertexArray[i].wasVisited = false;
}
}
}