网站开发seo要求,做一元购网站 要多少钱,昌乐网页设计,深圳燃气公司目录
1、广度优先#xff08;BFS#xff09;
算法思想
广度优先生成树
知识树
代码实现
2、深度优先#xff08;DFS#xff09;
算法思想
深度优先生成树
知识树
代码实现 1、广度优先#xff08;BFS#xff09;
算法思想 图的广度优先遍历#xff0…目录
1、广度优先BFS
算法思想
广度优先生成树
知识树
代码实现
2、深度优先DFS
算法思想
深度优先生成树
知识树
代码实现 1、广度优先BFS
算法思想 图的广度优先遍历BFS是一种遍历图的算法其思想是从起始顶点开始遍历图先访问起始顶点的所有直接邻居然后遍历这些邻居的直接邻居以此类推直到遍历完整个图。
BFS算法需要使用一个队列来保存已经遍历过但还未访问其邻接顶点。具体步骤如下
将起始顶点加入队列中并标记为已访问。从队列中取出一个顶点V并依次访问V的所有未被访问的邻接顶点并将这些邻接顶点加入队列中并标记为已访问。重复步骤2直到队列为空。 广度优先生成树 广度优先搜索BFS可以用来生成一棵图的广度优先生成树BFS树该树的根节点为起始节点其余节点按照宽度优先的顺序依次加入。BFS树可以用来解决最短路径问题以及其他需要按照距离或层次访问节点的问题。
具体的实现步骤如下
初始化BFS树将起始节点加入树中。将起始节点加入待访问队列。对于队列中的每个节点依次遍历其所有邻居节点。对于每个邻居节点如果该节点还未加入BFS树则将其加入并将该邻居节点的父节点设为当前节点。将已访问的节点从队列中移除。重复步骤3-5直到队列为空。 知识树 代码实现 下面是C语言实现BFS的示例代码
#include stdio.h
#include stdlib.h#define MAXV 100 // 最大顶点数typedef struct {int edges[MAXV][MAXV]; // 邻接矩阵int n; // 顶点数
} Graph;typedef struct {int data[MAXV];int front, rear;
} Queue;int visited[MAXV]; // 标记已经遍历的结点void initQueue(Queue* q) {q-front q-rear 0;
}void enqueue(Queue* q, int x) {q-data[q-rear] x;
}int dequeue(Queue* q) {return q-data[q-front];
}int isEmpty(Queue* q) {return q-front q-rear;
}void initGraph(Graph* g, int n) {g-n n;for (int i 0; i n; i)for (int j 0; j n; j)g-edges[i][j] 0;
}void addEdge(Graph* g, int u, int v) {g-edges[u][v] 1;g-edges[v][u] 1;
}void bfs(Graph* g, int u) {Queue* q (Queue*) malloc(sizeof(Queue));initQueue(q);visited[u] 1;printf(%d , u);enqueue(q, u);while (!isEmpty(q)) {int v dequeue(q);for (int w 0; w g-n; w) {if (g-edges[v][w] !visited[w]) {visited[w] 1;printf(%d , w);enqueue(q, w);}}}
}int main() {Graph g;int n, m, u, v;printf(输入顶点数和边数);scanf(%d %d, n, m);initGraph(g, n);printf(输入每条边的两个端点\n);for (int i 0; i m; i) {scanf(%d %d, u, v);addEdge(g, u, v);}printf(输入起始顶点);scanf(%d, u);printf(广度优先遍历结果);bfs(g, u);printf(\n);return 0;
} 首先定义了一个邻接矩阵表示图以及一个队列来存放待遍历的顶点。初始化队列为空然后将起始顶点加入队列并标记为已访问。然后开始遍历队列中的顶点对于每个顶点遍历其未访问的邻居将其添加到队列中并标记为已访问。代码中使用了visited数组来标记顶点是否已经被访问过了。
在以上代码中输入格式为
5 6
0 1
0 2
1 2
2 3
1 3
3 4
0
其中第一行为总顶点数和总边数第2~m1行为每条边的两个端点然后输入起始顶点编号。 2、深度优先DFS
算法思想 图的深度优先遍历Depth-First SearchDFS是一种遍历图的算法。其基本思想是从一个顶点开始沿着一条路径一直走到底直到所有的路径都被探索过为止。如果还有顶点未被访问则回溯到前一个顶点继续搜索下一条路径直到所有的顶点都被访问为止。
具体实现过程如下1. 从某一顶点开始遍历将该顶点标记为已访问。 2. 对当前访问的顶点的所有未访问的邻接顶点进行访问即从当前顶点的邻接顶点开始深度优先遍历。 3. 重复步骤2直到所有的顶点都被访问。 图的深度优先遍历可以用递归或栈来实现。在递归实现中每次访问一个顶点时递归地访问其未访问的邻接顶点直到所有的顶点都被访问。在栈实现中首先将起始顶点入栈然后对栈内的顶点进行出栈、访问、入栈操作直到所有的顶点都被访问。 深度优先生成树 深度优先生成树depth first search tree是一棵以图中某个顶点为根的深度优先遍历树它的生成过程为
选择图中任意一个未被遍历的顶点作为根节点以根节点为起点进行深度优先遍历遍历到一个未被遍历的节点时将该节点加入到生成树中并将其父节点与该节点之间的边添加到生成树中如果图中还存在未被遍历的节点则在剩余未被遍历的节点中选择一个节点作为新的根节点并重复上述过程。 生成树的过程可以通过递归实现也可以使用栈来实现。在遍历的过程中需要记录每个节点的状态即已被发现、已被访问或未被发现。 知识树 代码实现 以下是C语言中实现图的深度优先遍历的代码
#include stdio.h
#include stdbool.h#define MAX_VERTEX_NUM 100 // 顶点最大数量typedef struct {int vertex; // 顶点int next; // 指向下一个邻接点的指针
} EdgeNode;typedef struct {int vertex; // 顶点EdgeNode *edge; // 指向邻接点链表的指针
} VertexNode;VertexNode graph[MAX_VERTEX_NUM]; // 图
bool visited[MAX_VERTEX_NUM]; // 记录哪些顶点已经被访问过void addEdge(int v1, int v2) {// 添加边(v1, v2)EdgeNode *edge graph[v1].edge;if (edge NULL) {graph[v1].edge (EdgeNode *) malloc(sizeof(EdgeNode));graph[v1].edge-vertex v2;graph[v1].edge-next -1;} else {while (edge-next ! -1) {edge graph[v1].edge edge-next;}edge-next graph[v1].edge - edge addEdge(v2, -1);}
}void dfs(int vertex) {visited[vertex] true;printf(%d , vertex);EdgeNode *edge graph[vertex].edge;while (edge ! NULL) {int nextVertex edge-vertex;if (!visited[nextVertex]) {dfs(nextVertex);}edge graph[vertex].edge edge-next;}
}int main() {int n, m;scanf(%d %d, n, m); // n表示顶点数m表示边数for (int i 1; i n; i) {graph[i].vertex i;}for (int i 0; i m; i) {int v1, v2;scanf(%d %d, v1, v2);addEdge(v1, v2);addEdge(v2, v1); // 在无向图中边(v1, v2)和边(v2, v1)都要添加}memset(visited, false, MAX_VERTEX_NUM); // 初始化visited数组printf(DFS: );dfs(1); // 从顶点1开始进行DFSreturn 0;
} 其中addEdge函数用于添加一条边。在main函数中先读入图的顶点数和边数然后依次读入每条边并调用addEdge函数添加边。最后初始化visited数组为false并从顶点1开始进行深度优先遍历。
