ALG2012-A.ppt

Size: px

Start display at page:

Download "ALG2012-A.ppt"

かおりちづ
5 years ago
Views:

21279 (sakai.keiichi@kochi-tech.ac.jp) http://www.

2 (, )ε

4 m = n C2 = n ( n 1) / 2 m = n ( n 1)

6 dimentional binary hyper cube

7 ......

8 public class Node<E> { private E value; // private Collection<Node<E>> edges; // private boolean visited; private int sequence; private boolean searching; public Node(E value, Collection<Node<E>> edges) { this.value = value; this.edges = edges; reset(); public void reset(){ this.visited = false; this.sequence = ; this.edges.clear(); this.searching = false; public E getvalue() { // return value; public Collection<Node<E>> getedges(){ return this.edges; public boolean isvisited() { return visited; public void setvisited(boolean v) { this.visited = v; public int getsequence() { return sequence; public void setsequence(int s) { this.sequence = s; public boolean issearching() { return searching; public void setsearching(boolean s) { this.searching = s; public void connect(node<e> to){ this.edges.add(to); // if(!to.getedges().contains(this) ){ to.getedges().add(this); public void connectto(node<e> to){ this.edges.add(to); // 8

9 private static Node<Character> nodea = new Node<Character>('A', new LinkedList<Node<Character>>()); private static Node<Character> nodeb = new Node<Character>('B', new LinkedList<Node<Character>>()); private static Node<Character> nodec = new Node<Character>('C', new LinkedList<Node<Character>>()); private static Node<Character> noded = new Node<Character>('D', new LinkedList<Node<Character>>()); private static Node<Character> nodee = new Node<Character>('E', new LinkedList<Node<Character>>()); private static Node<Character> nodef = new Node<Character>('F', new LinkedList<Node<Character>>()); private static Node<Character> nodeg = new Node<Character>('G', new LinkedList<Node<Character>>()); private static Collection<Node<Character>> test_data = new LinkedList<Node<Character>>(); static { test_data.add(nodea); test_data.add(nodeb); test_data.add(nodec); test_data.add(noded); test_data.add(nodee); test_data.add(nodef); test_data.add(nodeg); public class DepthFirstSearch { private static <E> void visit(node<e> node){ node.setvisited(true); System.out.print(node.getValue()); for(node<e> neighbor: node.getedges()){ if(neighbor.isvisited()) continue; // System.out.print(" -> "); visit(neighbor); public static <E> void search(collection<node<e>> graph){ for(node<e> node: graph){ if(node.isvisited()) continue; // System.out.println(node.getValue() + ""); visit(node); System.out.println(); 9

10 public static void main(string[] args) { System.out.println("4.3.2"); for(node<character> node: test_data){ node.reset(); nodea.connect(nodec); nodea.connect(noded); nodea.connect(nodeb); nodec.connect(nodee); nodec.connect(nodef); noded.connect(nodeb); noded.connect(nodef); nodee.connect(nodeg); nodee.connect(nodef); search(test_data); public static void main(string[] args) { System.out.println("4.3.3"); for(node<character> node: test_data){ node.reset(); nodea.connect(nodec); nodea.connect(noded); nodea.connect(nodeb); nodec.connect(nodef); nodec.connect(nodee); noded.connect(nodeb); noded.connect(nodef); nodee.connect(nodeg); nodee.connect(nodef); search(test_data); public static void main(string[] args) { System.out.println("4.3.4"); for(node<character> node: test_data){ node.reset(); nodea.connectto(nodec); nodea.connectto(noded); nodea.connectto(nodee); nodec.connectto(nodeb); nodeb.connectto(nodea); noded.connectto(nodec); noded.connectto(nodee); nodef.connectto(nodea); nodef.connectto(nodeg); search(test_data); 1

11 ....

12 public class DirectedDepthFirstSearch<E> { private int sequence; private void visit(node<e> node){ node.setvisited(true); node.setsequence(++this.sequence); node.setsearching(true); System.out.print(node.getValue()); for(node<e> neighbor: node.getedges()){ if(neighbor.getsequence() == ){ System.out.print(" -> "); visit(neighbor); // else if (neighbor.getsequence() > node.getsequence()) { System.out.print(" (" + node.getvalue() + ", " + neighbor.getvalue() + ")"); else if (neighbor.issearching()){ System.out.print(" (" + node.getvalue() + ", " + neighbor.getvalue() + ")"); else { System.out.print(" (" + node.getvalue() + ", " + neighbor.getvalue() + ")"); node.setsearching(false); public void search(collection<node<e>> graph){ this.sequence = ; for(node<e> node: graph){ if(node.getsequence() == ){ System.out.println(node.getValue() + ""); visit(node); System.out.println(); 12

13 public static void main(string[] args) { System.out.println("4.3.4"); for(node<character> node: test_data){ node.reset(); nodea.connectto(nodec); nodea.connectto(noded); nodea.connectto(nodee); nodec.connectto(nodeb); nodeb.connectto(nodea); noded.connectto(nodec); noded.connectto(nodee); nodef.connectto(nodea); nodef.connectto(nodeg); new DirectedDepthFirstSearch<Character>().search(test_data); 13

15 ....

16 public class BreadthFirstSearch { public static <E> void search(collection<node<e>> graph){ Queue<Node<E>> queue = new LinkedList<Node<E>>(); for(node<e> node: graph){ if(node.isvisited()){ continue; // queue.add(node); node.setvisited(true); while(!queue.isempty() ){ Node<E> next = queue.remove(); System.out.print("" + next.getvalue()); for(node<e> neighbor: next.getedges()){ if( neighbor.isvisited() ){ continue; // FIFO // enqueue // dequeue queue.add(neighbor); // enqueue neighbor.setvisited(true); System.out.print(" (" + next.getvalue() + ", " + neighbor.getvalue() + ")"); System.out.print(" -> "); System.out.println(); 16

17 public static void main(string[] args) { System.out.println("4.3.7"); for(node<character> node: test_data){ node.reset(); nodea.connect(nodec); nodea.connect(noded); nodea.connect(nodeb); nodec.connect(nodee); nodec.connect(nodef); noded.connect(nodeb); noded.connect(nodef); nodee.connect(nodeg); nodee.connect(nodef); search(test_data); 17

18 public class DepthFirstSearchStack { public static <E> void search(collection<node<e>> graph){ Stack<Node<E>> stack = new Stack<Node<E>>(); for(node<e> node: graph){ if(node.isvisited()){ continue; // stack.push(node); node.setvisited(true); while(!stack.empty() ){ Node<E> next = stack.pop(); System.out.print("" + next.getvalue()); for(node<e> neighbor: next.getedges()){ if( neighbor.isvisited() ){ continue; stack.add(neighbor); neighbor.setvisited(true); System.out.print(" -> "); System.out.println(); // LIFO // push // pop // push 18

untitled

untitled 21174 (sakai.keiichi@kochi-tech.ac.jp) http://www.info.kochi-tech.ac.jp/k1sakai/lecture/alg/211/index.html tech.ac.jp/k1sakai/lecture/alg/211/index.html html (, )ε m = n C2 = n ( n 1) / 2 m = n ( ( n