图算法 · QQldd2019/javaStructures@49050a9 · GitHub
Skip to content

Commit 49050a9

Browse files
shinezejianshinezejian
committed
图算法
1 parent 1f22532 commit 49050a9

33 files changed

Lines changed: 2385 additions & 0 deletions

‎.idea/modules.xml‎

Lines changed: 8 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎.idea/uiDesigner.xml‎

Lines changed: 124 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎.idea/vcs.xml‎

Lines changed: 6 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎DirectedGraph.txt‎

Lines changed: 17 additions & 0 deletions

‎javaStructures.iml‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<module type="JAVA_MODULE" version="4">
3+
<component name="FacetManager">
4+
<facet type="web" name="Web">
5+
<configuration>
6+
<descriptors>
7+
<deploymentDescriptor name="web.xml" url="file://$MODULE_DIR$/web/WEB-INF/web.xml" />
8+
</descriptors>
9+
<webroots>
10+
<root url="file://$MODULE_DIR$/web" relative="/" />
11+
</webroots>
12+
</configuration>
13+
</facet>
14+
</component>
15+
<component name="NewModuleRootManager" inherit-compiler-output="true">
16+
<exclude-output />
17+
<content url="file://$MODULE_DIR$">
18+
<sourceFolder url="file://$MODULE_DIR$/src" isTestSource="false" />
19+
</content>
20+
<orderEntry type="inheritedJdk" />
21+
<orderEntry type="sourceFolder" forTests="false" />
22+
</component>
23+
</module>

‎src/com/zejian/structures/Graph/DirectedGraph/DStronglyConnectedGraph.java‎

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
package com.zejian.structures.Graph.DirectedGraph;
2+
3+
/**
4+
* Created by zejian on 2018/1/27.
5+
* Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
6+
* 有向强连通图,求强连通分量
7+
*/
8+
public class DStronglyConnectedGraph {
9+
10+
11+
12+
13+
}

‎src/com/zejian/structures/Graph/DirectedGraph/DepthFirstOrder.java‎

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
package com.zejian.structures.Graph.DirectedGraph;
2+
3+
import com.zejian.structures.Graph.NoWeightGraph.Graph;
4+
5+
import java.util.LinkedList;
6+
import java.util.Queue;
7+
import java.util.Stack;
8+
9+
/**
10+
* Created by zejian on 2018/1/27.
11+
* Blog : http://blog.csdn.net/javazejian [原文地址,请尊重原创]
12+
* 有向图中基于深度优先搜索的顶点排序
13+
* 基本思想:深度优先搜索正好只会访问每个顶点一次,如果将dfs()访问的每个顶点保存到一个
14+
* 数据结构中,那么遍历这个数据结构就能访问到有向图的所有顶点.遍历的顺序取决于
15+
* 这个数据结构的性质以及在递归调用之前还是之后进行保存.
16+
*
17+
* 前序遍历:在递归调用之前将顶点加入队列
18+
* 后序遍历:在递归调用之后将顶点加入队列
19+
* 逆后序: 在递归调用之后将顶点压入栈中
20+
*/
21+
public class DepthFirstOrder {
22+
23+
24+
private boolean marked[];
25+
private Queue<Integer> pre; //前序排序
26+
private Queue<Integer> post; //后序排序
27+
private Stack<Integer> reversePost; //逆后序
28+
29+
public DepthFirstOrder(Graph G){
30+
marked = new boolean[G.V()];
31+
pre = new LinkedList<>();
32+
post = new LinkedList<>();
33+
reversePost = new Stack<>();
34+
35+
for(int v = 0; v < G.V(); v++){
36+
if (!marked[v]){
37+
dfs(G , v);
38+
}
39+
}
40+
41+
}
42+
43+
private void dfs(Graph G , int v){
44+
marked[v] = true;
45+
pre.add(v);//递归调用之前入队
46+
47+
for (int w : G.adj(v)){
48+
if (!marked[w]){
49+
dfs(G,w);
50+
}
51+
}
52+
53+
//递归调用之后
54+
post.add(v);
55+
reversePost.push(v);
56+
}
57+
58+
public Iterable<Integer> pre(){
59+
return pre;
60+
}
61+
62+
public Iterable<Integer> post(){
63+
return post;
64+
}
65+
66+
public Iterable<Integer> reversePost(){
67+
return reversePost;
68+
}
69+
}

‎src/com/zejian/structures/Graph/DirectedGraph/DirectedGraphCycle.java‎

Lines changed: 76 additions & 0 deletions

0 commit comments

Comments
 (0)