DFS深度优先搜索算法/BFS广度优先搜索算法（c/c++)

深度优先搜索算法（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++)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。