Skip to content

Commit 77584a9

Browse files
author
cfdcoder
committed
Add DepthFirstSearch.java
1 parent 0325548 commit 77584a9

File tree

78 files changed

+7525
-1616
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

78 files changed

+7525
-1616
lines changed

‎.metadata/.log

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -40,3 +40,17 @@ user global configuration and to define the default location to store repositori
4040
not correct please set the HOME environment variable and restart Eclipse. Otherwise Git for Windows and
4141
EGit might behave differently since they see different configuration options.
4242
This warning can be switched off on the Team > Git > Confirmations and Warnings preference page.
43+
!SESSION 2016-01-05 16:41:28.771 -----------------------------------------------
44+
eclipse.buildId=4.5.1.M20150904-0015
45+
java.version=1.8.0_65
46+
java.vendor=Oracle Corporation
47+
BootLoader constants: OS=win32, ARCH=x86_64, WS=win32, NL=en_US
48+
Framework arguments: -product org.eclipse.epp.package.java.product
49+
Command-line arguments: -os win32 -ws win32 -arch x86_64 -product org.eclipse.epp.package.java.product
50+
51+
!ENTRY org.eclipse.egit.ui 2 0 2016-01-05 16:41:59.252
52+
!MESSAGE Warning: The environment variable HOME is not set. The following directory will be used to store the Git
53+
user global configuration and to define the default location to store repositories: 'C:\Users\cfdcoder'. If this is
54+
not correct please set the HOME environment variable and restart Eclipse. Otherwise Git for Windows and
55+
EGit might behave differently since they see different configuration options.
56+
This warning can be switched off on the Team > Git > Confirmations and Warnings preference page.

‎.metadata/.plugins/org.eclipse.core.resources/.history/0/e0ca42db27b400151fe1f0ac08278cd9

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
package study;
2+
3+
import edu.princeton.cs.algs4.Graph;
4+
import library.In;
5+
import library.StdOut;
6+
7+
public class DepthFirstSearch {
8+
private boolean[] marked; //marked[v]== is there an path from source-vertice to other-vertices
9+
private int count;//number of vertices connected to source vertex
10+
11+
public DepthFirstSearch(Graph G, int s){
12+
marked=new boolean[G.V()];
13+
dfs(G,s);
14+
}
15+
16+
private void dfs(Graph G, int v){
17+
count++;
18+
marked[v]=true;
19+
for(int w: G.adj(v)){
20+
if(!marked[w])
21+
dfs(G,w);
22+
}
23+
}
24+
25+
public boolean marked(int v) {
26+
return marked[v];
27+
}
28+
29+
public int count() {
30+
return count;
31+
}
32+
33+
34+
35+
public static void main(String[] args) {
36+
// TODO Auto-generated method stub
37+
In in = new In(args[0]);
38+
Graph G = new Graph(in);
39+
int s = Integer.parseInt(args[1]);
40+
DepthFirstSearch search = new DepthFirstSearch(G, s);
41+
for (int v = 0; v < G.V(); v++) {
42+
if (search.marked(v))
43+
StdOut.print(v + " ");
44+
}
45+
46+
StdOut.println();
47+
if (search.count() != G.V()) StdOut.println("NOT connected");
48+
else StdOut.println("connected");
49+
}
50+
51+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/1/c0d8e90928b400151fe1f0ac08278cd9

Lines changed: 52 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
package study;
2+
3+
import edu.princeton.cs.algs4.Graph;
4+
import library.In;
5+
import library.StdOut;
6+
7+
8+
public class DepthFirstSearch {
9+
private boolean[] marked; //marked[v]== is there an path from source-vertice to other-vertices
10+
private int count;//number of vertices connected to source vertex
11+
12+
public DepthFirstSearch(Graph G, int s){
13+
marked=new boolean[G.V()];
14+
dfs(G,s);
15+
}
16+
17+
private void dfs(Graph G, int v){
18+
count++;
19+
marked[v]=true;
20+
for(int w: G.adj(v)){
21+
if(!marked[w])
22+
dfs(G,w);
23+
}
24+
}
25+
26+
public boolean marked(int v) {
27+
return marked[v];
28+
}
29+
30+
public int count() {
31+
return count;
32+
}
33+
34+
35+
36+
public static void main(String[] args) {
37+
// TODO Auto-generated method stub
38+
In in = new In(args[0]);
39+
Graph G = new Graph(in);
40+
int s = Integer.parseInt(args[1]);
41+
DepthFirstSearch search = new DepthFirstSearch(G, s);
42+
for (int v = 0; v < G.V(); v++) {
43+
if (search.marked(v))
44+
StdOut.print(v + " ");
45+
}
46+
47+
StdOut.println();
48+
if (search.count() != G.V()) StdOut.println("NOT connected");
49+
else StdOut.println("connected");
50+
}
51+
52+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/11/502dcbc721b400151fe1f0ac08278cd9

Lines changed: 115 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,115 @@
1+
package library;
2+
3+
import java.util.InputMismatchException;
4+
import java.util.Locale;
5+
import java.util.NoSuchElementException;
6+
import java.util.Scanner;
7+
import java.util.regex.Pattern;
8+
9+
/******************************************************************************
10+
* Compilation: javac StdIn.java
11+
* Execution: java StdIn (interactive test of basic functionality)
12+
* Dependencies: none
13+
*
14+
* Reads in data of various types from standard input.
15+
*
16+
******************************************************************************/
17+
18+
public class StdIn {
19+
20+
private static final String CHARSET_NAME="UTF-8";
21+
private static final Locale LOCATION=Locale.US;
22+
private static final Pattern WHITESPACE_PATTERN=Pattern.compile("\\p{javaWhitespace}+");
23+
private static final Pattern EMPTY_PATTERN=Pattern.compile("");
24+
private static final Pattern EVERYTHNG_PATTERN=Pattern.compile("\\A");
25+
26+
private static Scanner scanner;
27+
private StdIn(){}
28+
29+
public static boolean isTmpty(){
30+
return !scanner.hasNext();
31+
}
32+
33+
public static boolean hasNext(){
34+
return scanner.hasNextLine();
35+
}
36+
37+
public static boolean hasNextChar(){
38+
scanner.useDelimiter(EMPTY_PATTERN);
39+
boolean result=scanner.hasNext();
40+
scanner.useDelimiter(WHITESPACE_PATTERN);
41+
return result;
42+
}
43+
44+
public static String readLine(){
45+
String line;
46+
try{
47+
line=scanner.nextLine();
48+
}catch(NoSuchElementException e){
49+
line=null;
50+
}
51+
return line;
52+
}
53+
54+
public static char readChar(){
55+
scanner.useDelimiter(EMPTY_PATTERN);
56+
String ch=scanner.next();
57+
assert ch.length()==1 : "Internal error: (Std)In.readChar()!";
58+
scanner.useDelimiter(WHITESPACE_PATTERN);
59+
return ch.charAt(0);
60+
}
61+
62+
public static String readAll(){
63+
if(!scanner.hasNextLine())
64+
return "";
65+
66+
String result=scanner.useDelimiter(EVERYTHNG_PATTERN).next();
67+
scanner.useDelimiter(WHITESPACE_PATTERN);
68+
return result;
69+
}
70+
71+
public static String readString(){
72+
return scanner.next();
73+
}
74+
75+
public static int readInt(){
76+
return scanner.nextInt();
77+
}
78+
79+
public static double readDouble(){
80+
return scanner.nextDouble();
81+
}
82+
83+
public static float readFloat(){
84+
return scanner.nextFloat();
85+
}
86+
87+
public static long readLong(){
88+
return scanner.nextLong();
89+
}
90+
91+
public static short readShort(){
92+
return scanner.nextShort();
93+
}
94+
95+
public static byte readByte(){
96+
return scanner.nextByte();
97+
}
98+
99+
public static boolean readBoolean(){
100+
String s=readString();
101+
if(s.equalsIgnoreCase("true")) return true;
102+
if(s.equalsIgnoreCase("false")) return false;
103+
if(s.equalsIgnoreCase("1")) return true;
104+
if(s.equalsIgnoreCase("0")) return false;
105+
throw new InputMismatchException();
106+
}
107+
108+
109+
110+
public static void main(String[] args) {
111+
// TODO Auto-generated method stub
112+
113+
}
114+
115+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/20/00fd89ff1eb400151fe1f0ac08278cd9

Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
package library;
2+
3+
import java.util.Locale;
4+
import java.util.Scanner;
5+
import java.util.regex.Pattern;
6+
7+
/******************************************************************************
8+
* Compilation: javac StdIn.java
9+
* Execution: java StdIn (interactive test of basic functionality)
10+
* Dependencies: none
11+
*
12+
* Reads in data of various types from standard input.
13+
*
14+
******************************************************************************/
15+
16+
public class StdIn {
17+
18+
private static final String CHARSET_NAME="UTF-8";
19+
private static final Locale LOCATION=Locale.US;
20+
private static final Pattern WHITESPACE_PATTERN=Pattern.compile("\\p{javaWhitespace}+");
21+
private static final Pattern EMPTY_PATTERN=Pattern.compile("");
22+
private static final Pattern EVERYTHNG_PATTERN=Pattern.compile("\\A");
23+
24+
private static Scanner scanner;
25+
private StdIn(){}
26+
27+
public static boolean isTmpty(){
28+
return !scanner.hasNext();
29+
}
30+
31+
public static boolean hasNext(){
32+
return scanner.hasNextLine();
33+
}
34+
35+
public static boolean hasNextChar(){
36+
scanner.useDelimiter(EMPTY_PATTERN);
37+
boolean result=scanner.hasNext();
38+
scanner.useDelimiter(WHITESPACE_PATTERN);
39+
return result;
40+
}
41+
42+
public static void main(String[] args) {
43+
// TODO Auto-generated method stub
44+
45+
}
46+
47+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/26/60c15f8823b400151fe1f0ac08278cd9

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
package library;
2+
3+
public class StdOut {
4+
5+
public static void main(String[] args) {
6+
// TODO Auto-generated method stub
7+
8+
}
9+
10+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/2e/60786ca326b400151fe1f0ac08278cd9

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
package study;
2+
3+
public class DepthFirstSearch {
4+
5+
public static void main(String[] args) {
6+
// TODO Auto-generated method stub
7+
8+
}
9+
10+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/3f/b0ab9cdb1cb400151fe1f0ac08278cd9

Whitespace-only changes.

‎.metadata/.plugins/org.eclipse.core.resources/.history/40/d0289de01fb400151fe1f0ac08278cd9

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
package library;
2+
3+
import java.util.Locale;
4+
import java.util.NoSuchElementException;
5+
import java.util.Scanner;
6+
import java.util.regex.Pattern;
7+
8+
/******************************************************************************
9+
* Compilation: javac StdIn.java
10+
* Execution: java StdIn (interactive test of basic functionality)
11+
* Dependencies: none
12+
*
13+
* Reads in data of various types from standard input.
14+
*
15+
******************************************************************************/
16+
17+
public class StdIn {
18+
19+
private static final String CHARSET_NAME="UTF-8";
20+
private static final Locale LOCATION=Locale.US;
21+
private static final Pattern WHITESPACE_PATTERN=Pattern.compile("\\p{javaWhitespace}+");
22+
private static final Pattern EMPTY_PATTERN=Pattern.compile("");
23+
private static final Pattern EVERYTHNG_PATTERN=Pattern.compile("\\A");
24+
25+
private static Scanner scanner;
26+
private StdIn(){}
27+
28+
public static boolean isTmpty(){
29+
return !scanner.hasNext();
30+
}
31+
32+
public static boolean hasNext(){
33+
return scanner.hasNextLine();
34+
}
35+
36+
public static boolean hasNextChar(){
37+
scanner.useDelimiter(EMPTY_PATTERN);
38+
boolean result=scanner.hasNext();
39+
scanner.useDelimiter(WHITESPACE_PATTERN);
40+
return result;
41+
}
42+
43+
public static String readLine(){
44+
String line;
45+
try{
46+
line=scanner.nextLine();
47+
}catch(NoSuchElementException e){
48+
line=null;
49+
}
50+
return line;
51+
}
52+
53+
public static char readChar(){
54+
scanner.useDelimiter(EMPTY_PATTERN);
55+
String ch=scanner.next();
56+
assert ch.length()==1 : "Internal error: (Std)In.readChar()!";
57+
scanner.useDelimiter(WHITESPACE_PATTERN);
58+
return ch.charAt(0);
59+
}
60+
61+
62+
63+
64+
public static void main(String[] args) {
65+
// TODO Auto-generated method stub
66+
67+
}
68+
69+
}

‎.metadata/.plugins/org.eclipse.core.resources/.history/49/300ac1ac25b400151fe1f0ac08278cd9

Whitespace-only changes.

‎.metadata/.plugins/org.eclipse.core.resources/.history/4c/204cb5a11eb400151fe1f0ac08278cd9

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
package library;
2+
3+
public class StdIn {
4+
5+
public static void main(String[] args) {
6+
// TODO Auto-generated method stub
7+
8+
}
9+
10+
}

0 commit comments

Comments
 (0)