深度优先算法和广度优先算法

介绍

在数据结构中，树和图可以说是不可或缺的两种数据结构。其中，对于图来说，最重要的算法可以说就是遍历算法。而搜索算法中，最标志性的就是深度优先算法和广度优先算法。

图的定义

图的定义普遍为两种，一种是邻接表，另一种是邻接矩阵。 图的邻接矩阵表示是唯一的，但对于邻接表来说，若边的输入次序不同生成的邻接表也不同。因此，对于同一个表，基于邻接矩阵的遍历所得到的BFS序列和DFS序列是不唯一的，基于邻接表的遍历所得到的BFS和DFS是唯一的。

邻接表

#define MXNUM 100
typedef char VertexType;
typedef int EdgeType;
typedef struct VNode
{
    VertexType data;
    ArcNode *first;
}VNode,AdjList[MXNUM];

typedef struct{
    AdjList vertics;
    int vexnum,arcnum;
}ALGraph;

邻接矩阵

#define MXNUM 100
typedef char VertexType;
typedef int EdgeType;
typedef struct 
{
    VertexType  Vex[MXNUM];
    EdgeType    Edge[MXNUM][MXNUM];
    int Vexnum,Edgenum;
}MGraph;

typedef struct ArcNode{
    int adjvex;
    struct ArcNode *next;
}ArcNode;

广度优先算法 广度优先算法的实现

广度优先算法是一种分层的查找过程，每向前走一步可能会访问一批顶点，不像深度优先搜索算法那样有回溯的情况，因此它不是一个递归的算法。为了实现逐层访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。

void BFSTraverse(MGraph G)
{
    int i;
    for(i=0;i