线性存储元素时，元素的关系也同时确定了。而非线性数据结构就不同了，需要同时考虑存储数据元素和数据元素的逻辑关系。例如，图这种数据结构的矩阵存储就是用一个顶点向量存储顶点元素，再用一个邻接矩阵存储元素关系。

由于图的结构比较复杂，任意两个顶点之间都可能存在联系，因此无法以数据元素在存储区中的物理位置来表示元素之间的关系，即图没有顺序存储结构，但可以借助二维表来表示元素之间的关系，一般称为邻接矩阵。另一方面，由于图的任意两个顶点间都可能存在关系，因此，用链式存储表示图结构是很自然的事，其中有代表性的一种链式存储称为邻接表。

在图的邻接矩阵表示法中，用邻接矩阵表示顶点间的相邻关系，而用一个顺序表来存储顶点信息。

图的邻接矩阵表示法适用范围广泛，可以用来描述有向图、有向表、无向图、无向表。

邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。设G(V,E)是具有n个顶点的图，则G的邻接矩阵是具有如下性质的n阶方阵：

则上图的邻接矩阵可以表示为：

若是带权图（网），则G的邻接矩阵是具有如下性质的n阶方阵：

其邻接矩阵可以表示为：

邻接矩阵表示法表示图一般可抽象如下：

#define MaxInt 32767 // 表示极大值，即∞#define MVNum 100 // 最大顶点数typedef char VerTexType; // 假设顶点的数据类型为字符型typedef int ArcType; // 假设边的权值类型为整型typedef struct{ VerTexType vexs[MVNum]; // 顶点表 ArcType arcsMVNum][MVNum]; // 邻接矩阵 int vexnum,arcnum; // 图的当前顶点数和边数}AMGraph;

图遍历背后的关键思想是在我们第一次访问每个顶点时对其进行标记，并跟踪我们尚未完全探索的内容。尽管面包屑或解开的线被用来标记童话迷宫中参观过的地方，但我们将依赖布尔标志或枚举类型来进行。

每个顶点将以三种状态之一存在：

未发现-顶点处于原始状态。

已发现-顶点已找到，但尚未检查其所有入射边。

已处理–访问所有关联边后的顶点。

显然，一个顶点只有在我们发现它之后才能被处理，所以每个顶点的状态在遍历过程中从未发现到发现再到处理。

我们还必须维护一个包含我们已经发现但尚未完全处理的顶点的结构。最初，只有一个起始顶点被认为是被发现的。为了完全探索一个顶点v，我们必须计算每一条离开v的边。如果一条边转到一个未发现的顶点x，我们标记x 为“已发现”并将其添加到要做的工作列表中。我们要忽略处理过的顶点的边，因为进一步的探索不会告诉我们关于图的任何新的东西。我们还可以忽略到已发现但未处理的顶点的任何边，因为目标已位于要处理的顶点列表中。

BFS(Depth First Search--DFS)和DFS(Breadth First Search--BFS)结果的区别在于它们探索顶点的顺序。此顺序完全取决于用于存储已发现但未处理的顶点的容器数据结构。

Stack–通过将顶点存储在后进先出（last-in，first-out，LIFO）堆栈中，我们通过沿着路径一直前行、访问新邻居（如果有的话）和仅当我们被以前发现的顶点包围时才回退来探索新的顶点。因此，我们的探索很快偏离了起点，定义了深度优先搜索。

一旦发现一个顶点，它就被放置在栈（显式或隐式栈）中。由于我们按后入先出的顺序处理这些顶点，所以最新的顶点将首先展开，这些顶点正是最远离根的顶点。

队列-通过将顶点存储在先进先出（FIFO）队列中，我们首先探索最古老的未探索顶点。因此，我们的探索从起始顶点缓慢地向外辐射，定义了广度优先搜索。

一旦发现一个顶点，它就被放置在队列中。由于我们按先入先出的顺序处理这些顶点，所以最旧的顶点将首先展开，这些顶点正是最接近根的顶点。

深度优先搜索有一个简洁的递归实现，它消除了显式使用堆栈的需要。

我们需要能够对每个入口和出口分别采取行动。

深度优先搜索的另一个重要特性是它将无向图的边划分为两类：tree edges和back edges。tree edges发现新的顶点，并且是在parent关系中编码的顶点。back edges是那些其另一个端点是被展开顶点的ancestor的边，因此它们指向树中。

1 深度优先遍历（先孩子后上一辈的兄弟）

优先向深度探索，一直走到头才回头到路径的上一个相邻顶点，直到回溯到最开始顶点。

如上图的深度优先遍历的顺序：0 1 2 3 4 5 6 8 9 7

如果使用递归，则相当于使用了一个隐式的栈数据结构（编译器对函数递归调用的压栈和回归的出栈操作）。

如果使用抱定代，则需要显式使用一个栈数据结构。

2 广度优先遍历（先兄弟后孩子）

广度优先遍历，也就是从某一个顶点开始，优先访问全部的相邻顶点，按层次辐射，直到全部顶点访问完。

如上图使用广度优先遍历的顺序：0 1 3 2 4 5 6 7 8 9

广度优先遍历需显式使用一个队列的数据结构。广度优先搜索是一种分层的搜索过程，不像深度优先遍历那样有往回退的情况。因此，广度优先遍历不能递归实现，可以使用先进先出的队列来实现。

深度搜索与广度搜索的控制结构和产生系统很相似，唯一的区别在于对扩展节点选取上。由于其保留了所有的前继节点，所以在产生后继节点时可以去掉一部分重复的节点，从而提高了搜索效率。这两种算法每次都扩展一个节点的所有子节点，而不同的是，深度搜索下一次扩展的是本次扩展出来的子节点中的一个，而广度搜索扩展的则是本次扩展的节点的兄弟节点。也就是说，广度优先搜索会优先考虑最早被发现的顶点，也就是说离起点越近的顶点优先级越高。深度优先搜索会优先考虑最后被发现的顶点。

在20世纪50年代，广度优先搜索最早由Edward F. Moor在研究迷宫路径问题时发现，深度优先搜索在人工智能方面获得了广泛应用。

#include <stdio.h>#include <stdlib.h>typedef int VertexType; // 顶点类型应由用户定义typedef int EdgeType; // 边上的权值类型应由用户定义#define MAXSIZE 15 // 存储空间初始分配量#define MAXEDGE 15#define MAXVEX 10#define INFINITY 65535int arc[MAXVEX][MAXVEX]={ // 布尔数组{0,1,0,1,0,0,0,0,0,0},{1,0,1,0,1,0,0,0,0,0},{0,1,0,1,1,0,0,0,0,0},{1,0,1,0,0,0,0,0,0,0},{0,1,1,0,0,0,0,0,0,0},{0,0,0,0,0,0,1,1,1,0},{0,0,0,0,0,1,0,0,1,1},{0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,1,1,0,0,0},{0,0,0,0,0,0,1,0,0,0}};// 0的元素数目远远多于非0元素的数目，称为稀疏矩阵，用链式存储较节省空间typedef struct{ VertexType vexs[MAXVEX]; // 顶点表 EdgeType arc[MAXVEX][MAXVEX]; // 邻接矩阵，可看作边表 int numVertexes, numEdges; // 图中当前的顶点数和边数 }MGraph;typedef struct // 循环队列顺序存储结构{ int data[MAXSIZE]; int front; // 头指针 int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置}Queue;void CreateMGraph(MGraph *G){ int i,j; G->numEdges=15; G->numVertexes=10;for(i=0; i<G->numVertexes; i ) // 建立顶点表G->vexs[i] = i; for (i = 0; i < G->numVertexes; i ) // 初始化图 { for (int j = 0; j < G->numVertexes; j ) { G->arc[i][j]=arc[i][j]; } }} bool visited[MAXVEX]; // 访问标志的数组void DFS(MGraph G, int i) // 邻接矩阵的深度优先递归算法{ visited[i] = true; printf("%d ", G.vexs[i]); // 打印顶点，也可以其它操作 for(int j=0; j<G.numVertexes; j ) if(G.arc[i][j] == 1 && !visited[j]) DFS(G, j); // i = j不断压栈}void DFSTraverse(MGraph G) // 非连能图各子图的DFS{ for(int i=0; i<G.numVertexes; i ) visited[i] = false; // 初始所有顶点状态都是未访问过状态 for(i=0; i<G.numVertexes;i ) if(!visited[i]) // 对未访问过的顶点调用DFS，若是连通图，只会执行一次 DFS(G, i);}bool InitQueue(Queue *Q); // 初始化一个空队列Qbool QueueEmpty(Queue Q); // 入队bool EnQueue(Queue *Q,int e); // 出队bool DeQueue(Queue *Q,int *e); // 删除Q中队头元素，用e返回其值void BFSTraverse(MGraph G) // 邻接矩阵的广度遍历算法{ Queue Q; for(int i=0; i<G.numVertexes; i ) visited[i] = false; InitQueue(&Q); // 初始化一辅助用的队列 for(i=0; i<G.numVertexes; i ) // 非连能图各子图 { if (!visited[i]) // 若是未访问过就处理 { visited[i]=true; // 设置当前顶点访问过 printf("%d ", G.vexs[i]); // 打印顶点，也可以其它操作 EnQueue(&Q,i); // 将此顶点入队列 while(!QueueEmpty(Q)) // 若当前队列不为空 { DeQueue(&Q,&i); // 将队对元素出队列，赋值给i for(int j=0;j<G.numVertexes;j ) { // 判断其它顶点若与当前顶点存在边且未访问过 if(G.arc[i][j] == 1 && !visited[j]) { visited[j]=true; // 将找到的此顶点标记为已访问 printf("%d ", G.vexs[j]); // 打印顶点 EnQueue(&Q,j); // 将找到的此顶点入队列 } }// for } // while } // if } // for}int main(void){ MGraph G; CreateMGraph(&G); printf("\n1.深度优先遍历："); DFSTraverse(G); printf("\n2.广度优先遍历："); BFSTraverse(G); getchar();getchar(); return 0;}bool InitQueue(Queue *Q) // 初始化一个空队列Q{ Q->front=0; Q->rear=0; return true;}bool QueueEmpty(Queue Q){ if(Q.front==Q.rear) // 队列空的标志 return true; else return false;}bool EnQueue(Queue *Q,int e){ if ((Q->rear 1)%MAXSIZE == Q->front) // 队列满的判断 return false; Q->data[Q->rear]=e;// 将元素e赋值给队尾 Q->rear=(Q->rear 1)%MAXSIZE; // rear指针向后移一位置， // 若到最后则转到数组头部 return true;}bool DeQueue(Queue *Q,int *e) // 删除Q中队头元素，用e返回其值{ if (Q->front == Q->rear) // 队列空的判断 return false; *e=Q->data[Q->front]; // 将队头元素赋值给e Q->front=(Q->front 1)%MAXSIZE; // front指针向后移一位置，// 若到最后则转到数组头部 return true;}

无论那种搜索，都是通过对一个线性表进行处理，只不过是先处理头部还是尾部的问题罢了。处理头部优先的时候，也就是先加入的先探索，就是广度优先了，因为，头部的都是兄弟节点；而尾部的则是深度优先，因为放入尾部的都是刚刚生产出来的节点，后加入的先探索——也就是所谓一条路走到死。 同理可以联想到启发式搜索。启发式搜索就是先以你自定义的优先级处理，然后再以广度为优先级处理。 所以，归根结底，所谓的搜索，就是一种定义了优先级的枚举。

－End－