Sekolah Tinggi Teknologi Telematika Telkom

Laporan Praktikum Kecerdasan Buatan

Modul 2 (Implementasi DFS dan BFS)

Dosen Pengampu: Muhammad Zidny Naf’an,S.Kom., M.Kom.

Nama Mahasiswa

NIM

Kelas

: Deprilana Ego Prakasa

: 14102055

: S1 IF B 2014

VERTEX

Vertex.java

package graph; public class Vertex { public char label; public boolean wasVisited; public Vertex(char label){ this.label = label; wasVisited = false; } }

GRAPH

Graph.java

package graph; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class Graph { private char search; private final int MAX_VERTS =20; private Vertex vertexList[]; private int adjMat[][]; private int nVertexs; private Queue openQueue; private Stack openStack; public Graph(){ vertexList = new Vertex[MAX_VERTS]; adjMat = new int [MAX_VERTS][MAX_VERTS]; adjMat = new int [MAX_VERTS][MAX_VERTS]; nVertexs = 0; openQueue = new LinkedList(); openStack = new Stack<String>(); } public Graph(char search){ this.search = search;

vertexList = new Vertex[MAX_VERTS]; adjMat = new int[MAX_VERTS][MAX_VERTS]; nVertexs = 0; openQueue = new LinkedList(); openStack = new Stack<String>(); } public void addVertex(char label){ vertexList[nVertexs++] = new Vertex(label); } public void addEdge(int from, int to){ adjMat[from][to]=1; adjMat[to][to]=1; } public void displayVertex(int v){ System.out.print(vertexList[v].label); } public void depthFirstSearch(){ vertexList[0].wasVisited = true; openStack.push(0); int v2 = 0; while(!openStack.isEmpty()){ Integer v1 = (Integer) openStack.pop(); displayVertex(v1); if(vertexList[v1].label == search) break; while((v2 = getAdjUnvisitedVertexDFS(v1)) != -1){ vertexList[v2].wasVisited = true; openStack.add(v2); } } for (int j=0; j<nVertexs; j++){ vertexList[j].wasVisited = false; } } public void breadthFirstSearch(){ vertexList[0].wasVisited = true; openQueue.add(0); int v2; while(!openQueue.isEmpty()){ Integer v1 = (Integer) openQueue.remove(); displayVertex(v1); if(vertexList[v1].label == search)

break; while((v2 = getAdjUnvisitedVertexBFS(v1)) !=-1){ vertexList[v2].wasVisited = true; openQueue.add(v2); } } for(int j=0; j<nVertexs; j++){ vertexList[j].wasVisited = false; } } public int getAdjUnvisitedVertexBFS(int v){ for(int j = 0;j<nVertexs; j++){ if(adjMat[v][j]==1 && vertexList[j].wasVisited == false){ return j; } } return -1; } public int getAdjUnvisitedVertexDFS(int v){ for(int j = nVertexs-1;j>=0; j--){ if(adjMat[v][j]==1 && vertexList[j].wasVisited == false){ return j; } } return -1; } }

MAIN

Main.java

package graph; public class Main { public static void main(String[] args) { Graph theGraph = new Graph(); theGraph.addVertex('A'); //0 theGraph.addVertex('B'); //1 theGraph.addVertex('C'); //2 theGraph.addVertex('D'); //3 theGraph.addVertex('E'); //4 theGraph.addEdge(0, 1); //AB theGraph.addEdge(1, 2); //BC theGraph.addEdge(0, 3); //AD theGraph.addEdge(3, 4); //DE

System.out.println("Breadth First Search:"); System.out.println("Visits: "); theGraph.breadthFirstSearch(); System.out.println(); System.out.println("Depth First Search:"); System.out.println("Visits: "); theGraph.depthFirstSearch(); System.out.println(); // TODO code application logic here } }

SOAL LATIHAN

1.1

MAIN

Main.java

package graph; public class Main { public static void main(String[] args) { Graph theGraph = new Graph(); theGraph.addVertex('A'); //0 theGraph.addVertex('B'); //1 theGraph.addVertex('C'); //2 theGraph.addVertex('D'); //3 theGraph.addVertex('E'); //4

theGraph.addVertex('F'); //5 theGraph.addVertex('G'); //6 theGraph.addVertex('H'); //7 theGraph.addVertex('I'); //8 theGraph.addVertex('J'); //9 theGraph.addEdge(0, 1); //AB theGraph.addEdge(0, 2); //AC theGraph.addEdge(0, 3); //AD theGraph.addEdge(1, 6); //BG theGraph.addEdge(1, 7); //BH theGraph.addEdge(3, 4); //DE theGraph.addEdge(3, 5); //DF theGraph.addEdge(4, 8); //EI theGraph.addEdge(4, 9); //EJ System.out.println("Breadth First Search:"); System.out.println("Visits: "); theGraph.breadthFirstSearch(); System.out.println(); System.out.println("Depth First Search:"); System.out.println("Visits: "); theGraph.depthFirstSearch(); System.out.println(); // TODO code application logic here } }

2.1 Gambar Vertex dan Edge dari bentuk Graph pada Main Pertama

3.1 Bentuk adjacency matrix-nya

A B C D E

A 0 1 0 1 0

B 0 0 1 0 0

C 0 0 0 0 0

D 0 0 0 0 1

E 0 0 0 0 0

4.1 Apakah output dari Breadth First Search berdasarkan Graph tersebut,

Ya sesuai dengan Grapnya

5.1 Apakah output dari Depth First Search berdasarkan Graph tersebut,

Ya sesuai dengan Grapnya

A

B D

C E

6.1 Implementasi Graph berikut pada kode yang anda buat

Main.java

package graph; public class Main { public static void main(String[] args) { Graph theGraph = new Graph(); theGraph.addVertex('A'); //0 theGraph.addVertex('B'); //1 theGraph.addVertex('C'); //2 theGraph.addVertex('D'); //3 theGraph.addVertex('E'); //4 theGraph.addVertex('F'); //5 theGraph.addVertex('G'); //6 theGraph.addVertex('H'); //7 theGraph.addVertex('I'); //8 theGraph.addVertex('J'); //9 theGraph.addEdge(0, 1); //AB theGraph.addEdge(0, 2); //AC theGraph.addEdge(0, 3); //AD theGraph.addEdge(1, 6); //BG theGraph.addEdge(1, 7); //BH theGraph.addEdge(3, 4); //DE theGraph.addEdge(3, 5); //DF theGraph.addEdge(4, 8); //EI theGraph.addEdge(4, 9); //EJ System.out.println("Breadth First Search:"); System.out.println("Visits: ");

theGraph.breadthFirstSearch(); System.out.println(); System.out.println("Depth First Search:"); System.out.println("Visits: "); theGraph.depthFirstSearch(); System.out.println(); // TODO code application logic here } }

7.1. Output Breadth First Search untuk Graph No 6

8.1. Output Depth First Search untuk Graph No 6