深度优先搜索算法（DFS）
深度优先搜索算法思路：（有点贪心算法的意思）
1，从某个给定结点a出发，访问它
2，查找关于a的邻接点，查找到a的第一个邻接点b之后，对b结点进行DFS搜索，也就是对b结点执行步骤2…当某个结点的所有邻接点都被访问过之后，回退上一层DFS算法中继续运行
3，程序执行完毕
下面给出了在邻接矩阵存储无向图情况下的深度优先算法，两点间存在相连的边时在邻接矩阵中标记为1，否则全标记为0（包括自身到自身相连的情况）。每个被访问过的结点用visited数组标记：
void DFSTraverse(mGraph& G){int v;for (v = 0; v < G.vexnum; v++)visited[v] = false;//初始化visited为空for (v = 0; v < G.vexnum; v++)//保证访问所有结点if (visited[v] == false)DFS(G, v);}void DFS(mGraph& G, int v){std::cout << G.vex[v] << ' ';visited[v] = true;int w;for (w = 0; w < G.vexnum; w++)if (G.arc[v][w]!=0)if (visited[w] == false)DFS(G, w);}
邻接表下的DFS函数：
void DFS(aGraph& G, int v){std::cout << G.vertices[v].data << ' ';visited[v] = true;arcNode* w;for (w = G.vertices[v].firstArc; w != NULL; w = w->nextArc)if (visited[w->adjvex] == false)DFS(G, w->adjvex);}
广度优先搜索算法（BFS）
广度优先搜索算法采用了辅助数据结构队列。
广度优先搜索算法思路：
1，从某个给定结点a开始，将其入队
2，a出队并进行访问，且将a的所有邻接点依次入队，每出队（并访问）一个结点，就将它的其余未被访问过的邻接点入队，直到将所有结点访问，程序执行完毕
下面给出了在邻接矩阵存储情况下的广度优先算法，每个被访问过的结点用visited数组标记：
void BFSTraverse(mGraph& G){int v, w, u;for (v = 0; v < G.vexnum; ++v)visited[v] = false;int front = 0, rear = 0;int* queue = new int[G.vexnum];//构造循环队列for (v = 0; v < G.vexnum; ++v)//遍历完图中所有结点{if (visited[v]==false){rear = (rear + 1) % G.vexnum;queue[rear] = v;visited[v] = true;//入队做标记while (rear!=front)//队列不为空时{front = (front + 1) % G.vexnum;u = queue[front];std::cout << G.vex[u] << ' ';//出队并访问for (w = 0; w<G.vexnum; w++)if (G.arc[u][w] != 0)if (visited[w] == false){rear = (rear + 1) % G.vexnum;queue[rear] = w;visited[w] = true;}}}}}
邻接表下的BFS算法类似于DFS，故省略掉。
完整示例
对上图进行深度优先搜索和广度优先搜索，代码如下：
#include<iostream>#define maxSize 8//顶点数目#define MAX 7//边的个数//邻接矩阵typedef struct {int vexnum, arcnum;//顶点数和边数char vex[maxSize];//顶点信息(字符)int arc[maxSize][maxSize];//二维数组(存储边上的信息)}mGraph;//邻接表typedef struct arcNode {int adjvex;//与该边所连顶点的序号double weight;//边上的权值struct arcNode* nextArc;}arcNode;//边表结点typedef struct {char data;//顶点中存储的数据arcNode* firstArc;}adjList;//顶点typedef struct{int vexnum, arcnum;adjList vertices[maxSize];}aGraph;bool visited[maxSize];//标记是否被访问void DFSTraverse(mGraph& G);//DFS搜索算法void DFS(mGraph& G, int v);void BFSTraverse(mGraph& G);//BFS搜索算法int main(){using namespace std;mGraph G;//邻接矩阵存储图并进行初始化G.vexnum = maxSize;G.arcnum = MAX;char vexData[maxSize] = {'a', 'b', 'c', 'd', 'e','f','g','h' };//顶点信息int arcData[MAX][2] = {{0, 3 }, {1, 3 }, {2, 4 }, {3, 4},{3, 5 }, {4, 6 }, {4, 7 } };//连接的边int i, j;for (i = 0; i < G.vexnum; ++i){G.vex[i] = vexData[i];for (j = 0; j < G.vexnum; j++)G.arc[i][j] = 0;}for (i = 0; i < G.arcnum; i++)G.arc[arcData[i][0]][arcData[i][1]] = G.arc[arcData[i][1]][arcData[i][0]] = 1;//初始化完毕cout << "深度优先搜索: ";DFSTraverse(G);cout << endl;cout << "广度优先搜索: ";BFSTraverse(G);cout << endl;return 0;}void DFSTraverse(mGraph& G){int v;for (v = 0; v < G.vexnum; v++)visited[v] = false;//初始化visited为空for (v = 0; v < G.vexnum; v++)if (visited[v] == false)DFS(G, v);}void DFS(mGraph& G, int v){std::cout << G.vex[v] << ' ';visited[v] = true;int w;for (w = 0; w < G.vexnum; w++)if (G.arc[v][w]!=0)if (visited[w] == false)DFS(G, w);}void BFSTraverse(mGraph& G){int v, w, u;for (v = 0; v < G.vexnum; ++v)visited[v] = false;int front = 0, rear = 0;int* queue = new int[G.vexnum];//构造循环队列for (v = 0; v < G.vexnum; ++v){if (visited[v]==false){rear = (rear + 1) % G.vexnum;queue[rear] = v;visited[v] = true;//入队做标记while (rear!=front){front = (front + 1) % G.vexnum;u = queue[front];std::cout << G.vex[u] << ' ';//出队并访问for (w = 0; w<G.vexnum; w++)if (G.arc[u][w] != 0)if (visited[w] == false){rear = (rear + 1) % G.vexnum;queue[rear] = w;visited[w] = true;}}}}}
输出结果为：
如果觉得《DFS深度优先搜索算法/BFS广度优先搜索算法（c/c++)》对你有帮助，请点赞、收藏，并留下你的观点哦！
