package com.unit4.Graph;
import com.unit1.algs1_2.Stack;
public class DepthFirstPath {
private boolean[] marked;
private int[] edgeTo;
private final int s;
public DepthFirstPath(Graph graph, int s) {
this.marked = new boolean[graph.VERTEX_NUM()];
this.edgeTo = new int[graph.VERTEX_NUM()];
this.s = s;
dfs(graph, s);
}
private void dfs(Graph graph, int v) {
marked[v] = true;
for (int w : graph.adj(v)) {
if (!marked[w]) {
edgeTo[w] = v;
dfs(graph, w);
}
}
}
public boolean hasPathTo(int v) {
return marked[v];
}
public Iterable<Integer> pathTo(int v) {
if (!hasPathTo(v)) {
return null;
}
Stack<Integer> path = new Stack<>();
for (int x = v; x != s; x = edgeTo[x]) {
path.push(x);
}
path.push(s);
return path;
}
}
package com.unit4.Graph;
import java.util.Scanner;
public class Graph {
private final int VERTEX_NUM;
private int edgeNum;
private Bag<Integer>[] adjacencyList;
public Graph(int VERTEX_NUM) {
this.VERTEX_NUM = VERTEX_NUM;
this.edgeNum = 0;
adjacencyList = new Bag[VERTEX_NUM];
for (int v = 0; v < VERTEX_NUM; v++) {
adjacencyList[v] = new Bag<>();
}
}
public Graph(Scanner in) {
this(in.nextInt());
int edgeNum = in.nextInt();
for (int i = 0; i < edgeNum; i++) {
int v = in.nextInt();
int w = in.nextInt();
addEdge(v, w);
}
}
public int VERTEX_NUM() {
return this.VERTEX_NUM;
}
public int edgeNum() {
return this.edgeNum;
}
public void addEdge(int v, int w) {
adjacencyList[v].add(w);
adjacencyList[w].add(v);
edgeNum++;
}
public Iterable<Integer> adj(int v) {
return adjacencyList[v];
}
public static int degree(Graph graph, int v) {
int degree = 0;
for (int w : graph.adj(v)) {
degree++;
}
return degree;
}
@Override
public String toString() {
String s = VERTEX_NUM + "vertices," + edgeNum + " edges\n";
for (int v = 0; v < VERTEX_NUM; v++) {
s = s + v + ": ";
for (int w : this.adj(v)) {
s = s + w + " ";
}
s = s + "\n";
}
return s;
}
}
package com.unit1.algs1_2;
import java.util.Iterator;
public class Stack<Item> implements Iterable<Item> {
private Node first;
private int N;
private class Node {
Item item;
Node next;
}
public boolean isEmpty() {
return N == 0;
}
public int size() {
return N;
}
public void push(Item item) {
Node oldFirst = first;
first = new Node();
first.item = item;
first.next = oldFirst;
N++;
}
public Item pop() {
Item item = first.item;
first = first.next;
N--;
return item;
}
@Override
public Iterator<Item> iterator() {
return new ReverseStack();
}
private class ReverseStack implements Iterator<Item> {
private Node current = first;
@Override
public boolean hasNext() {
return current != null;
}
@Override
public Item next() {
Item item = (Item) current.item;
current = current.next;
return item;
}
@Override
public void remove() {
}
}
}
package com.unit4.Graph;
import java.util.Scanner;
public class DFSTest {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Graph graph = new Graph(in);
int s = in.nextInt();
DepthFirstPath dfs = new DepthFirstPath(graph, s);
for (int v = 0; v < graph.VERTEX_NUM(); v++) {
System.out.print(s + " to " + v + ": ");
if (dfs.hasPathTo(v)) {
for (int x : dfs.pathTo(v)) {
if (x == s) {
System.out.print(x);
} else {
System.out.print("-" + x);
}
}
}
System.out.println();
}
}
}