赞
踩
什么是拓扑排序在这里就不说了。直接讲讲拓扑排序的DFS和BFS实现算法。
一、DFS实现拓扑排序
算法描述:递归实现
利用了一个辅助函数实现递归,下面先对这个辅助函数进行分析:
base case:当所有的“邻居”点都被访问过后结束递归,并将当前节点加入到队列的0号位置
general case:如果存在未被访问的“邻居”节点,则对其进行访问(递归)
实现代码:
- template<int max_size>
- void Graph<max_size>::DFS(List<Vertex>& output) const
- {
- output.clear();
- bool visited[max_size];
- for (int i = 0; i < max_size; i++)
- visited[i] = false;
- for (Vertex v = 0; v < count; v++) { //防止出现联通分支
- if (!visited[v])
- recursive_DFS(v, visited, output); //进入递归
- }
- }
- template<int max_size>
- void Graph<max_size>::recursive_DFS(Vertex v, bool * visited, List<Vertex>& output) const
- {
- visited[v] = true;
- for (int i = 0; i < neighbours[v].size(); i++) {
- Vertex w;
- neighbours[v].retrieve(i, w);
- if (!visited[w])recursive_DFS(w, visited, output);
- }
- output.insert(0, v);
- }
-
算法描述:利用辅助队列实现
1)遍历整个图,计算每个节点的入度
2)找出入度为0的点,入队
3)取出队列中的第一个节点,存入结果链表中,并将其“邻居”节点入度--
4)重复3)直至队列为空
算法结束。
实现代码:
- template<int max_size>
- void Graph<max_size>::BFS(List<Vertex>& output) const
- {
- output.clear();
- int in_degree[max_size];
- //入度置零
- for (int i = 0; i < max_size; i++)
- in_degree[i] = 0;
-
- //1)计算初始入度:
- for (Vertex v = 0; v < count; v++) {
- Vertex w;
- for (int i = 0; i < neighbours[v].size(); i++) {
- neighbours[v].retrieve(i, w);
- in_degree[w]++;
- }
- }
-
- queue<Vertex> wait;
- for (Vertex v = 0; v < count; v++) //2)第一轮度数为0的点入队
- if (in_degree[v] == 0)wait.push(v);
- while (!wait.empty()) {
- Vertex x = wait.front();
- output.insert(output.size(), x); //3)取出队首放入output
- Vertex w;
- for (int i = 0; i < neighbours[x].size(); i++) {//4)“邻居”节点入度--
- neighbours[x].retrieve(i, w);
- in_degree[w]--;
- if (in_degree[w] == 0)wait.push(w);
- }
- wait.pop();
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。