网络营销的主要形式有建设网站,网站开发好吗,app推广是什么意思,正规做兼职的网站文章出处#xff1a;极客时间《数据结构和算法之美》-作者#xff1a;王争。该系列文章是本人的学习笔记。
拓扑排序能解决的问题
在一个项目中会有很多源代码文件。编译器在编译代码的时候需要按照依赖关系#xff0c;依次编译每个源文件。例如A.java依赖B.java#xff…文章出处极客时间《数据结构和算法之美》-作者王争。该系列文章是本人的学习笔记。
拓扑排序能解决的问题
在一个项目中会有很多源代码文件。编译器在编译代码的时候需要按照依赖关系依次编译每个源文件。例如A.java依赖B.java那就需要先编译B.java再编译A.java。要想完整编译整个项目就需要确定一个全局的编译顺序。确定这样一个全局的编译顺序就用到拓扑排序。
拓扑排序就是解决有向无环图的图中所有顶点的满足依赖条件的顶点顺序。
解决思路
可以将每个源文件看做一个顶点源文件和源文件之间的依赖关系看做一条边。图的基本结构如下。 public class Graph {private int v; // 顶点的个数private LinkedListInteger adj[]; // 邻接表public Graph(int v) {this.v v;adj new LinkedList[v];for (int i0; iv; i) {adj[i] new LinkedList();}}public void addEdge(int s, int t) { // s先于t边s-tadj[s].add(t);}
}排序算法有两种方式BFS和DFS。
BFS遍历
BFS遍历也称为Khan算法。在构建图的时候如果A.java依赖B.java那就从B到A有一条边B-A。那入度为0的点就是最先编译的。 找到入度为0的顶点X将其输出到拓扑排序结果列表中然后删除以X为起点的所有的边。继续查找入度为0的顶点添加到结果列表中。 public ListInteger topSortByKahn(){int[] inDegree new int[v];for(int i 0; i adjacency.length; i){for(Edge edge : adjacency[i]){inDegree[edge.tid] ;}}QueueInteger queue new LinkedList();for(int i0;iinDegree.length;i){if(inDegree[i] 0){queue.add(i);}}ListInteger path new ArrayList();while(! queue.isEmpty()){int node queue.poll();path.add(node);for(Edge edge : adjacency[node]){inDegree[edge.tid]--;if(inDegree[edge.tid] 0){queue.offer(edge.tid);}}}return path;}DFS遍历
按照深度优先搜索的方式遍历每个顶点。假如有条路径是A-B-C-E、A-D-C。 DFS的时候如果先走的是第一条要先访问了C、E才会访问D-C这条路线。这样的话就不能找到C什么时候可以执行。所以需要将邻接矩阵转为逆邻接矩阵。 E-C-B-A、C-D-A。 说明A先执行了才能执行BB、D先执行才能执行CC执行了才能执行 E。这个顺序符合要求。
在DFS处理环节把一个顶点所依赖的所有节点先输出再输出本节点。 public ListInteger topSortByDFS(){LinkedListInteger[] inverseAdg new LinkedList[this.v];for(int i 0; i adjacency.length; i){inverseAdg[i] new LinkedList();}for(int i 0; i adjacency.length; i){for(Edge edge : adjacency[i]){inverseAdg[edge.tid].add(edge.sid);}}boolean[] visited new boolean[v];ListInteger path new ArrayList();for(int i0;ithis.v;i){if(visited[i] false){dfs(i,inverseAdg,visited,path);}}return path;}private void dfs(int sid, LinkedListInteger[] inverseAdg, boolean[] visited,ListInteger path) {visited[sid] true;for(int tid : inverseAdg[sid]){if(visited[tid] false){dfs(tid,inverseAdg,visited,path);}}path.add(sid);}完整代码
