数据结构-深度遍历和广度遍历（转）

本文转自http://blog.csdn.net/wingofeagle/article/details/13020373
深度遍历：
从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。
其更适合：目标比较明确，以找到目标为主要目的的情况。
广度遍历：
类似于树中的层序遍历，首先遍历完和某一顶点v相连的所有顶点，然后再遍历和这些顶点相连的顶点，以此类推。
其更适合于：不断扩大遍历范围时找到相对最优解的情况。
具体代码如下：
  1 // GraphSearch.cpp : Defines the entry point for the console application.  
  2 //  
  3   
  4 #include "stdafx.h"  
  5 #include "stdio.h"      
  6   
  7 #define OK 1  
  8 #define ERROR 0  
  9 #define TRUE 1  
 10 #define FALSE 0  
 11   
 12 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */    
 13 typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */  
 14   
 15 typedef char VertexType; /* 顶点类型应由用户定义 */  
 16 typedef int EdgeType; /* 边上的权值类型应由用户定义 */  
 17   
 18 #define MAXSIZE 9 /* 存储空间初始分配量 */  
 19 #define MAXEDGE 15  
 20 #define MAXVEX 9  
 21 #define INFINITY 65535  
 22   
 23 typedef struct  
 24 {  
 25     VertexType vexs[MAXVEX]; /* 顶点表 */  
 26     EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */  
 27     int numVertexes, numEdges; /* 图中当前的顶点数和边数 */   
 28 }MGraph;  
 29   
 30 /* 用到的队列结构与函数********************************** */  
 31   
 32 /* 循环队列的顺序存储结构 */  
 33 typedef struct  
 34 {  
 35     int data[MAXSIZE];  
 36     int front;      /* 头指针 */  
 37     int rear;       /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */  
 38 }Queue;  
 39   
 40 /* 初始化一个空循环队列Q */  
 41 Status InitQueue(Queue *Q)  
 42 {  
 43     Q->front=0;  
 44     Q->rear=0;  
 45     return  OK;  
 46 }  
 47   
 48 /* 若队列Q为空队列,则返回TRUE,否则返回FALSE */  
 49 Status QueueEmpty(Queue Q)  
 50 {   
 51     if(Q.front==Q.rear) /* 队列空的标志 */  
 52         return TRUE;  
 53     else  
 54         return FALSE;  
 55 }  
 56   
 57 /* 若队列未满，则插入元素e为Q新的队尾元素 */  
 58 Status EnQueue(Queue *Q,int e)  
 59 {  
 60     if ((Q->rear+1)%MAXSIZE == Q->front)  /* 队列满的判断 */  
 61         return ERROR;  
 62     Q->data[Q->rear]=e;           /* 将元素e赋值给队尾 */  
 63     Q->rear=(Q->rear+1)%MAXSIZE;/* rear指针向后移一位置， */  
 64     /* 若到最后则转到数组头部 */  
 65     return  OK;  
 66 }  
 67   
 68 /* 若队列不空，则删除Q中队头元素，用e返回其值 */  
 69 Status DeQueue(Queue *Q,int *e)  
 70 {  
 71     if (Q->front == Q->rear)          /* 队列空的判断 */  
 72         return ERROR;  
 73     *e=Q->data[Q->front];             /* 将队头元素赋值给e */  
 74     Q->front=(Q->front+1)%MAXSIZE;    /* front指针向后移一位置， */  
 75     /* 若到最后则转到数组头部 */  
 76     return  OK;  
 77 }  
 78 /* ****************************************************** */  
 79   
 80   
 81 void CreateMGraph(MGraph *G)  
 82 {  
 83     int i, j;  
 84   
 85     G->numEdges=15;  
 86     G->numVertexes=9;  
 87   
 88     /* 读入顶点信息，建立顶点表 */  
 89     G->vexs[0]='A';  
 90     G->vexs[1]='B';  
 91     G->vexs[2]='C';  
 92     G->vexs[3]='D';  
 93     G->vexs[4]='E';  
 94     G->vexs[5]='F';  
 95     G->vexs[6]='G';  
 96     G->vexs[7]='H';  
 97     G->vexs[8]='I';  
 98   
 99   
100     for (i = 0; i < G->numVertexes; i++)/* 初始化图 */  
101     {  
102         for ( j = 0; j < G->numVertexes; j++)  
103         {  
104             G->arc[i][j]=0;  
105         }  
106     }  
107   
108     G->arc[0][1]=1;  
109     G->arc[0][5]=1;  
110   
111     G->arc[1][2]=1;   
112     G->arc[1][8]=1;   
113     G->arc[1][6]=1;   
114   
115     G->arc[2][3]=1;   
116     G->arc[2][8]=1;   
117   
118     G->arc[3][4]=1;  
119     G->arc[3][7]=1;  
120     G->arc[3][6]=1;  
121     G->arc[3][8]=1;  
122   
123     G->arc[4][5]=1;  
124     G->arc[4][7]=1;  
125   
126     G->arc[5][6]=1;   
127   
128     G->arc[6][7]=1;   
129   
130   
131     for(i = 0; i < G->numVertexes; i++)  
132     {  
133         for(j = i; j < G->numVertexes; j++)  
134         {  
135             G->arc[j][i] =G->arc[i][j];  
136         }  
137     }  
138   
139 }  
140   
141 Boolean visited[MAXVEX]; /* 访问标志的数组 */  
142   
143 /* 邻接矩阵的深度优先递归算法 */  
144 void DFS(MGraph G, int i)  
145 {  
146     int j;  
147     visited[i] = TRUE;  
148     printf("%c ", G.vexs[i]);/* 打印顶点，也可以其它操作 */  
149     for(j = 0; j < G.numVertexes; j++)  
150         if(G.arc[i][j] == 1 && !visited[j])  
151             DFS(G, j);/* 对为访问的邻接顶点递归调用 */  
152 }  
153   
154 /* 邻接矩阵的深度遍历操作 */  
155 void DFSTraverse(MGraph G)  
156 {  
157     int i;  
158     for(i = 0; i < G.numVertexes; i++)  
159         visited[i] = FALSE; /* 初始所有顶点状态都是未访问过状态 */  
160     for(i = 0; i < G.numVertexes; i++)  
161         if(!visited[i]) /* 对未访问过的顶点调用DFS，若是连通图，只会执行一次 */   
162             DFS(G, i);  
163 }  
164   
165 /* 邻接矩阵的广度遍历算法 */  
166 void BFSTraverse(MGraph G)  
167 {  
168     int i, j;  
169     Queue Q;  
170     for(i = 0; i < G.numVertexes; i++)  
171         visited[i] = FALSE;  
172     InitQueue(&Q);      /* 初始化一辅助用的队列 */  
173     for(i = 0; i < G.numVertexes; i++)  /* 对每一个顶点做循环 */  
174     {  
175         if (!visited[i])    /* 若是未访问过就处理 */  
176         {  
177             visited[i]=TRUE;        /* 设置当前顶点访问过 */  
178             printf("%c ", G.vexs[i]);/* 打印顶点，也可以其它操作 */  
179             EnQueue(&Q,i);      /* 将此顶点入队列 */  
180             while(!QueueEmpty(Q))   /* 若当前队列不为空 */  
181             {  
182                 DeQueue(&Q,&i); /* 将队对元素出队列，赋值给i */  
183                 for(j=0;j<G.numVertexes;j++)   
184                 {   
185                     /* 判断其它顶点若与当前顶点存在边且未访问过  */  
186                     if(G.arc[i][j] == 1 && !visited[j])   
187                     {   
188                         visited[j]=TRUE;            /* 将找到的此顶点标记为已访问 */  
189                         printf("%c ", G.vexs[j]);   /* 打印顶点 */  
190                         EnQueue(&Q,j);              /* 将找到的此顶点入队列  */  
191                     }   
192                 }   
193             }  
194         }  
195     }  
196 }  
197   
198   
199 int main(void)  
200 {      
201     MGraph G;  
202     CreateMGraph(&G);  
203     printf("深度遍历如下：
");  
204     DFSTraverse(G);  
205     printf("
广度遍历如下：
");  
206     BFSTraverse(G);  
207     return 0;  
208 }
运行效果如下：