广度优先搜索(Breadth-First-Search)和深度优先搜索(Deep－First－Search)是搜索策略中最经常用到的两种方法,特别常用于图的搜索.
BFS的思想： 从一个图的某一个顶点V0出发，首先访问和V0相邻的且未被访问过的顶点V1、V2、……Vn，然后依次访问与V1、V2……Vn相邻且未被访问的顶点。如此继续，找到所要找的顶点或者遍历完整个图。我们采用队列来存储访问过的节点。
DFS的思想：
深度优先搜索所遵循的策略就是尽可能“深”的在图中进行搜索，对于图中某一个顶点V，如果它还有相邻的顶点且未被访问，则访问此顶点。如果找不到，则返回到上一个顶点。这一过程一直进行直到所有的顶点都被访问为止。 DFS可以搜索出从某一个顶点到另外的一个顶点的所有路径。 由于要进行返回的操作，我们采用的是递归的方法。
邻接表：
邻接表是图的一种链式存储结构。在邻接表中，对图中的每个顶点vi建立一个单链表，把鱼vi相邻的顶点放在这个链表中。
邻接矩阵：
邻接矩阵是表示顶点之间相邻关系的矩阵。设G(V,E）是具有n个顶点的无向图，则其对应了一个n阶方阵。设这个方阵为A，则对于A[i][j]有两种取值，当A[i][j]=1时，，表示顶点i和顶点j是连通的；当A[i][j]=0时，表示顶点i和顶点j是不连通的。
基于邻接矩阵的DFS:
<span style="font-size:14px;">//基于邻接矩阵的DFS，时间复杂度为O(n^2)#include <stdio.h>#include <string.h>const int GNumber = 8;//存储节点个数int G[GNumber][GNumber];//存储邻接矩阵int color[GNumber];//存储节点状态void DFS_Visit(int G[][GNumber], int i, int n){int j;color[i] = 1;for(j=0; j< n; j++){if(G[i][j] && !color[j]){printf(" V%d ", j+1);color[j] = 1;DFS_Visit(G, j, n);}}}void DFS(int G[][GNumber], int n){int i;memset(color, 0, sizeof(color));for(i=0; i<n; i++){//遍历每一个节点if(!color[i]){//判断是否访问printf(" V%d ", i+1);DFS_Visit(G,i,n);printf("\n");}}}int main(){FILE *fr;int i,j;fr = fopen("测试用例.txt","r");if(!fr){printf("fopen failed\n");return -1;}while(fscanf(fr,"%d%d", &i, &j) != EOF){G[i-1][j-1] = 1;G[j-1][i-1] = 1;}DFS(G,GNumber);getchar();return 0;}</span>
基于邻接矩阵的BFS:
<span style="font-size:14px;">//基于邻接矩阵的BFS，时间复杂度为O(n^2)#include <stdio.h>#include <string.h>const int GNumber = 8;//存储节点个数int G[GNumber][GNumber];//存储邻接矩阵int color[GNumber];// 防止回环,记录节点状态 struct Queue{//用数组模拟队列 int queue[GNumber];int start;int end;}MyQueue;void BFS(int G[][GNumber], int n){int j;MyQueue.queue[MyQueue.end++] = 0;color[0] = 1;while(MyQueue.end != MyQueue.start){for(j=0; j<n; j++){if(G[MyQueue.start][j] && !color[j]){color[j] = 1;MyQueue.queue[MyQueue.end++] = j;}}printf(" V%d ", MyQueue.queue[MyQueue.start++]+1);}}int main(int argc, char **argv){FILE *fr;int i,j;fr = fopen("测试用例.txt","r");if(!fr){printf("fopen failed\n");return -1; }//printf("%d %d\n",MyQueue.start,MyQueue.end);while(fscanf(fr,"%d%d", &i, &j) != EOF){G[i-1][j-1] = 1;G[j-1][i-1] = 1;}memset(&MyQueue, 0, sizeof(MyQueue));memset(color, 0, sizeof(color));BFS(G,GNumber);getchar();return 0;}</span>
基于邻接表的BFS和DFS：
<span style="font-size:14px;">#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX 8 //最大顶点数typedef struct node{ //边节点int adjvex; //该边指向的顶点位置//int weightstruct node* next; //指向下一条边的指针}ArcNode;//边表结点typedef struct VNode{int vertex;ArcNode* firstarc; //指向第一条依附该顶点的指针}VNode;//顶点表结点typedef VNode Adjlist[MAX+1];//adj_list是邻接表类型typedef struct {int n, m;//图中顶点数和边数Adjlist adjlist;//邻接表}ALGraph;void create_algraph(ALGraph* g)//建立无向图的邻接表{ArcNode* newnode;int i, j, k;printf("please input node number and edge number: ");scanf("%d%d", &g->n, &g->m);printf("node number = %d, edges = %d\n", g->n, g->m);for(i = 1; i <= g->n; i++){g->adjlist[i].vertex = i;g->adjlist[i].firstarc = NULL;}printf("please input new edge: \n");//用相邻的两个顶点来表示边for(k = 1; k <= g->m; k++){scanf("%d%d", &i, &j);//printf("\n");newnode = (ArcNode* )malloc(sizeof(ArcNode));newnode->adjvex = j;//newnode->weight = 0;newnode->next = g->adjlist[i].firstarc;g->adjlist[i].firstarc = newnode;newnode = (ArcNode* )malloc(sizeof(ArcNode));newnode->adjvex = i;//newnode->weight = 0;newnode->next = g->adjlist[j].firstarc;g->adjlist[j].firstarc = newnode;}}void pr_algraph(ALGraph* g)//输出邻接表{ArcNode* node;int i;for(i = 1; i<= g->n; i++){node = g->adjlist[i].firstarc;printf("g->adjlist[%d] = %d: ", i, g->adjlist[i].vertex);while(node != NULL){printf("%d \t", node->adjvex);node = node->next;}printf("\n");}}int visted[MAX+1];//记录节点状态void DFS(ALGraph *g,int v){visted[v] = 1;//访问初始点ArcNode *p = g->adjlist[v].firstarc;while(p!=NULL){if (visted[p->adjvex]==0){//如果没有被访问过，则递归调用DFS访问printf("%d ",p->adjvex);DFS(g,p->adjvex);}p = p->next;//继续下一条边}//printf("\n");}void BFS(ALGraph *g,int v){//for (int i=0;i<g->n;i++) visted[i] = 0;int queue[MAX],front,rear;front = rear = 0;rear = (rear+1)%MAX;queue[rear] = v; //v顶点入队int u;ArcNode *p;while(/*rear!=0*/front!=rear)//当队列满时{front = (front+1)%MAX;u = queue[front];p = g->adjlist[u].firstarc;while(p!=NULL)//首先访问u的所有节点{if (visted[p->adjvex]==0){visted[p->adjvex] = 1;//访问p->adjvex节点，标记为访问rear = (rear+1)%MAX;printf("%d ",p->adjvex);queue[rear] = p->adjvex;//p->adjvex节点入队}p = p->next;}}printf("\n");}int main(int argc, char** argv){ALGraph* g;//定义一个无向图g = (ALGraph* )malloc(sizeof(ALGraph));printf("begin create algraph\n");create_algraph(g);printf("finish create algraph\n");printf("the algraph is:\n");pr_algraph(g);memset(visted,0,sizeof(visted));visted[1]=1;printf("BFS is:\n");printf("1 ");BFS(g,1);memset(visted,0,sizeof(visted));printf("DFS is:\n");printf("1 ");DFS(g,1);printf("\n");return 0;}</span> 邻接矩阵和邻接表都是实现BFS和DFS的方法，邻接矩阵时间复杂度为O(n^2)，邻接表的时间复杂度为O(n+e);因此邻接矩阵适用于稠密图，邻接表适用于稀疏图。
带上心灵去旅行，以平和的心态看待一切，
