简单版-----图论-----图的两种遍历方式：DFS 和 BFS

图的遍历

• 图的遍历是和树的遍历类似，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点都仅仅被访问一次，这一过程就叫做图的遍历(Traversing Graph)
• 图的两种遍历算法：深度优先搜索(DFS)，广度优先搜索(BFS)
  值得强调的是，树是一种特殊的图，因此图的遍历也类似于树的遍历

#include<stdio.h>
#include<stdlib.h>

#define TypeE int
#define TypeV int
#define MaxVertexNum 20
#define MAXSIZE 69999

typedef struct {
	TypeE G[MaxVertexNum][MaxVertexNum]; //邻接矩阵
	TypeV vex[MaxVertexNum]; //顶点数组，存储目标数据 
	TypeE numEdges; //边数 
	TypeV numVertexes; //顶点数  	
}MGraph;

typedef struct QNode {
	int data;
	struct QNode* next;
}QNode , *QueuePtr;

typedef struct
{
	QueuePtr front, rear;//队头, 队尾
}LinkQueue;

深度优先搜索(DFS)

• 深度优先搜索(Depth_First_Search)的定义：
  从图中某个顶点V出发，访问该顶点，然后从该点的邻接点出发深度优先遍历，直到图中所有和V有路径相通的点都被访问到。
  实际上，我们这里讲的是连通图，对于非连通图，若图中还有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复上述过程，直到图中所有点都被访问
• 深度优先搜索的分析：
  假设有9个房间，分别给这几个房间编号A~I，从A房间出发沿着路走遍所有房间，你会怎么做呢?
  hh，我打赌你肯定会走乱的，因为你没有一个准确的方案.
  • 如果让你选择这样一套方案，从开始的房间走向一个相邻的房间，然后以该房间为起点找走到下一个相邻的房间，直到无路可走（与当前房间相邻的房间都被访问过），然后回到上一个房间看看与它相邻的房间是否访问过，如果有，就走向这个相邻的房间，如果没有，就回到上上一个房间看看与它相邻的房间是否访问过，重复上述过程，直到全部房间被访问完全为止。
    类似于树的前序遍历

假设从A号房间出发到达下一个房间，然后到B号房间，直到无路可走后，回溯，直到所有顶点被访问过

实现代码：

int visited[MaxVertexNum];//1表示访问过，0表示未访问过
void DFS(MGraph* p, int i)
{
	int j;
	visited[i] = 1;//设置为访问过

	printf("%d ", p->vex[i] );
	for (j = 0; j < p->numVertexes; j++) {
		if (!visited[j] && p->G[i][j] < MaxVertexNum && p->G[i][j] > 0)
			DFS( p, j);
	}

}
/*邻接矩阵的深度遍历操作*/
void DFSTraverse(MGraph* p)
{
	int i;
	for (i = 0; i < p->numVertexes; i++) 
		visited[i] = 0;//将全部结点设置为未访问
	
	for (i = 0; i < p->numVertexes; i++) {
		if (!visited[i])//若未被访问过
			DFS(p, i);
	}
}

小插曲：深度优先搜索是一种在开发爬虫早期使用较多的方法。它的目的是要达到被搜索结构的叶结点(即那些不包含任何超链的HTML文件) 。在一个HTML文件中，当一个超链被选择后，被链接的HTML文件将执行深度优先搜索，即在搜索其余的超链结果之前必须先完整地搜索单独的一条链。深度优先搜索沿着HTML文件上的超链走到不能再深入为止，然后返回到某一个HTML文件，再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时，说明搜索已经结束。

广度优先搜索(BFS)

• 广度优先搜索(Depth_First_Search)的定义：
  从图中某个顶点V出发，访问该顶点，入队列，然后将队列中元素全部逐一弹出，然后在每次弹出元素的时候，将该元素对应顶点的邻接点全部访问并且入队列，直到该顶点V的所有邻接点都被访问到，重复上述操作，直到图中所有和V有路径相通的点都被访问到。（下列同样是非连通图）
• 深度优先搜索的分析：
  还是上述的例子，假设有9个房间，分别给这几个房间编号A~I，从A房间出发沿着路走遍所有房间，你会怎么做呢?
  除了上述的方案以外，还有另一套方案， 从开始的房间走遍所有相邻的房间，然后继续从每个相邻的房间出发，走遍每个相邻房间的相邻房间，一层一层的走完，直到全部顶点访问完成。
  类似于树的层序遍历
  
  以下是队列图：执行顺序是1->2->3->4->…，直到结束
  
  实现代码：

void BSFTraverse(MGraph* p)
{
	int i, j;
	LinkQueue* Q = (LinkQueue* )malloc(sizeof(LinkQueue ));
	if (!Q) return;
	Q->front = NULL;
	Q->rear = NULL;
	QueuePtr head = (QueuePtr)malloc(sizeof(QNode));
	if (!head)
		return ;
	Q->rear = head;
	Q->front = head;

	for (i = 0; i < p->numVertexes; i++)
		visited[i] = 0;
	
	for (i = 0; i < p->numVertexes; i++) {
		if (!visited[i]) {            /*若是未访问过就处理*/
			visited[i] = 1;         
			printf("%d ", p->vex[i]);/*打印顶点，也可以其他操作*/
			EnQueue(Q, i);/*将此顶点入队列*/
			while (!QueueEmpty(Q)) {/*若当前队列不为空*/
				DeQueue(Q, i);
				for (j = 0; j < p->numVertexes; j++) {
					/*判断其他顶点若与当前顶点存在边且未访问过*/
					if (p->G[i][j] > 0 && p->G[i][j] < MAXSIZE && !visited[j]) {
						visited[j] = 1;/*将找到的此顶点标记为已访问*/
						printf("%d ", p->vex[j]);
						EnQueue(Q, j);/*将找到的此顶点入队列*/
					}
				}
			}
		}
	}

}

小插曲：宽度优先搜索算法(又称广度优先搜索)是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。