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 1 )
1 11 11 111 11 111 111 1111 1 1 11 1 11 11 111 4-dimentional binary hyper cube
......
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(){ g return this.edges; 4.34.4 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 = 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) g ( ) ){ to.getedges().add(this); public void connectto(node<e> to){ this.edges.add(to); // 有向辺を追加 8
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>>(); L static { test_data.add(nodea); public class DepthFirstSearch { test_data.add(nodeb); private static <E> void visit(node<e> node){ test_ data.add(nodec); test_data.add(noded); test_data.add(nodee); test_data.add(nodef); test_data.add(nodeg); node.setvisited(true); s ted(true); System.out.print(node.getValue()); for(node<e> neighbor: node.getedges()){ if(neighbor.isvisited()) continue; // 訪問済み System.out.print(" t t(" -> "); 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() t tl tv l () + " から探索します "); visit(node); System.out.println(); 9
public static void main(string[] args) { System.out.println("4.3.2"); for(node<character> node: test_data){ node.reset(); public static void main(string[] i args) { System.out.println("4.3.3"); nodea.connect(nodec); for(node<character> node: test_data){ nodea.connect(noded); nodea.connect(nodeb); nodec.connect(nodee); nodec.connect(nodef); noded.connect(nodeb); nn ct(n d noded.connect(nodef); nodee.connect(nodeg); nodee.connect(nodef); search(test_data); node.reset(); public static void main(string[] args) { System.out.println("4.3.4"); nodea.connect(nodec); for(node<character> node: test_data){ nodea.connect(noded); nodea.connect(nodeb); d nodec.connect(nodef); nodec.connect(nodee); noded.connect(nodeb); noded.connect(nodef); nodee.connect(nodeg); nodee.connect(nodef); search(test_data); t t 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
....
public class DirectedDepthFirstSearch<E> { private int sequence; private void visit(node<e> node){ node.setvisited(true); d(t 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); i // 木の辺 else if (neighbor.getsequence() > node.getsequence()) { System.out.print(" 下降辺 (" + node.getvalue() + ", " + neighbor.getvalue() + ")"); else if (neighbor.issearching()){ g()){ 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
public static void main(string[] args) { System.out.println("4.3.4"); println("434"); 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
5 2 5 4 3 2 2 5 3 2 4 5 4 3 5 5 5 4.3.6
....
public class BreadthFirstSearch { public static <E> void search(collection<node<e>> graph){ Queue<Node<E>> queue = new LinkedList<Node<E>>(); // FIFO for(node<e> node: graph){ if(node.isvisited()){ continue; // 訪問済み queue.add(node); // enqueue node.setvisited(true); while(!queue.isempty() ){ Node<E> next = queue.remove(); u // dequeue u System.out.print(" 頂点 " + next.getvalue()); for(node<e> neighbor: next.getedges()){ if( neighbor.isvisited() ){ continue; queue.add(neighbor); // enqueue neighbor.setvisited(true); System.out.print(" 辺 (" + next.getvalue() + ", " + neighbor.getvalue() + ")"); System.out.print(" -> "); System.out.println(); 16
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); Dc nn ct(n d noded.connect(nodef); nodee.connect(nodeg); nodee.connect(nodef); search(test_data); 17
public class DepthFirstSearchStack { public static <E> void search(collection<node<e>> graph){ Stack<Node<E>> stack = new Stack<Node<E>>(); // LIFO for(node<e> node: graph){ if(node.isvisited()){ continue; // 訪問済み stack.push(node); // push node.setvisited(true); while(!stack.empty() t ){ Node<E> next = stack.pop(); // pop System.out.print(" 頂点 " + next.getvalue()); for(node<e> neighbor: next.getedges()){ if( neighbor.isvisited() ){ continue; stack.add(neighbor); // push neighbor.setvisited(true); System.out.print(" -> "); System.out.println(); 18