Graph
Definisi Graph
Graph adalah kumpulan dari simpul dan busur yang secara matematis dinyatakan sebagai :
G = (V, E)
Dimana :
G = Graph
V = Simpul atau Vertex, atau Node
E = Busur atau Edge, atau arc
Sifat-Sifat Graph
žSebuah graph mungkin hanya terdiri dari satu simpul
žSebuah graph belum tentu semua simpulnya terhubung dengan busur
ž
žSebuah graph mungkin mempunyai simpul yang tak terhubung dengan simpul yang lain
žSebuah graph mungkin semua simpulnya saling berhubungan
Contoh Graph
V terdiri dari V1, V2, V3 .....,V5
E terdiri dari e1, e2, e3, .....,e5
Dimana :
V = Vertex
E = Edge
Istilah-Istilah dalam Graph
žIncident
Jika e merupakan busur dengan simpul-simpulnya adalah v dan w yang ditulis e=(v,w), makav dan w disebut “terletak” pada e, dan e disebut incident dengan v dan w.
žDegree
Degree dari suatu verteks x dalam undigraph adalah jumlah busur yang incident dengansimpul tersebut.
žIndegree
Indegree dari suatu verteks x dalam digraph adalah jumlah busur yang kepalanya incidentdengan simpul tersebut, atau jumlah busur yang “masuk” atau menuju simpul tersebut.
žOut Degree
Outdegree dari suatu verteks x dalam digraph adalah jumlah busur yang ekornya incidentdengan simpul tersebut, atau jumlah busur yang “keluar” atau berasal dari simpultersebut.
žAdjacent
Pada graph tidah berarah, 2 buah simpul disebut adjacent bila ada busur yang menghubungkan kedua simpul tersebut. Simpul v dan w disebut adjacent.
Pada graph berarah, simpul v disebut adjacent dengan simpul w bila ada busur dari w ke v.
žSuccessor dan Predecessor
Pada graph berarah, bila simpul v adjacent dengan simpul w, maka simpul v adalah successorsimpul w, dan simpul w adalah predecessor dari simpul v.
žPath
Sebuah path adalah serangkaian simpul-simpul berbeda yang adjacent secara berturut-turutdari simpul satu ke simpul berikutnya.
Representasi Graph dalam Matrik
Kotak yang berisi angka satu menunjukan bahwa dalam dua vertex tersebut terdapat edge yang menghubungkannya. Dan jika dalam kotak terdapat angka nol, maka hal tersebut menandakan tidak ada edge yang mengubungkan secara langsung dua vertex tersebut.
Pada Weighted Direct Graph, penulisan matrix tidak menggunakan angka no 1 dan 0 lagi,melainkan menggunakan nilai (bobot) jika ada edge yang menghubungkan dua buah verterxdan nilai 0 jika tidak ada edge yang menghubungkan vertex - vertex tersebut.
Jenis-Jenis Graph
Derected Graph
Sebuah Graph yang sisi atau busurnya berlaku satu arah saja, sesuai dengan arah tanda panah.
Misal :
e1 = (A,B)
Berarti hanya berlaku untuk Graph A ke B saja, tidak berlaku
Untuk B ke A
Undirect Graph
Graph yang sisi atau busurnya bisa berlaku ke dua Arah. Secara Grafik dapat dilihat tidak ada arah panah pada Busur.
Edge pada Undigraph bisa direpresentasikan sebagai garis dengan panah 2 arah.
Misal :
e1 = (A,B)
e1 = Bisa dikatakan Graph A ke B atau Graph B ke A
Weighted Graph
ž
Weighted Graph adalah Graph yang sisi /busurnya memiliki nilai (bobot). Weighted Graph terdiri dua jenis :
- Weighted Direct Graph
Bobot berlaku satu arah saja
- Weighted Undirect Graph
Bobot Berlaku 2 arah
Metode Pencarian Vertex
DEPTH FIRST SEARCH (DFS)
žPencarian dengan metode ini dilakukan dari node awal secara mendalam hingga yang paling akhir (dead-end) atau sampai ditemukan
žKelebihan :
- Cepat Mencapai kedalaman ruang pencarian
- Tidak boros waktu, jika lintasannya panjang
- Lebih efisien
žKekurangan
- Memungkinkan tidak ditemukan tujuan yang di harapkan
- Pada setiap pencarian hanya menghasilkan 1 solusi saja
ž
BREADTH FIRST SEARCH (BFS)
žProsedur Breadth First Search merupakan pencarian yang dilakukan dengan mengunjungi tiap-tiap node secara sistematis pada setiap level hingga keadaan tujuan (goal state) ditemukan.
žKelebihan
- Tidak akan menemukan jalan Buntu
- Jika lebih dari solusi, maka BFS akan solusi minimum akan ditemukan
žKekurangan
- Menyimpan memori yang besar karena menyimpan semua node yang ada dalam satuatu pohon.
MINIMMUM SPANNING TREE
žSpanning Tree adalah sebuah cabang yang terbentuk dari subset edge-edge serta menghubungkan setiap vertex dalam suatu Graph.
ž
žMinimum Spanning Tree adalah total bobot minimal dari edge-edge yang menghubungkansetiap vertex.
žAlgoritma MST :
1. Algoritma Kruskal
2. Algoritma Prim
žContoh Minimum Spanning Tree
Unweighted Undirect Graph
Kemungkinan MST
GRAPH pada JAVA
žUntuk pengaplikasian teori Graph dapat di lakukan pada program Java.
Software yang kita gunakan pada Program yang kita buat adalah Eclipse žUntukpengaplikasian teori Graph dapat di lakukan pada program Java.
Software yang kita gunakan pada Program yang kita buat adalah Eclipse.
žPada Package GRAPH_BASIC
Terdapat 5 file berextensi .java yang saling berhubungan.
Untuk melakukan Logika pada package GRAPH_BASIC
terdapat pada file main.java
Output yang di hasilkan akan seperti di Bawah ini
Referensi:
http://gallerycode.files.wordpress.com/2010/11/graph1.pptx
package bubblesort;
BalasHapuspublic class BubbleSort {
public static void main(String[] args) {
int list[] = {1, 8, 4, 6, 0, 3, 5, 2, 7, 9};
int tmp;
int i, j;
boolean swapped;
int loop = 1;
for (i = 0; i < list.length; i++) {
System.out.print(list[i] + " ");
}
System.out.println("\n");
for (i = list.length - 1; i > 0; i--) {
swapped = false;
System.out.println("iteration" + (loop++));
for (int k = 0; k < list.length; k++) {
System.out.print(list[k] + " ");
}
System.out.println("\n");
for (j = 0; j < list.length - 1; j++) {
if (list[j] < list[j + 1]) {
System.out.println("[" + list[j] + "," + list[j + 1] + "]" + "=" + "not swapped");
}
if (list[j] > list[j + 1]) {
swapped = true;
tmp = list[j];
list[j] = list[j + 1];
list[j + 1] = tmp;
System.out.println("[" + list[j + 1] + "," + list[j] + "]" + "=" + "swapped" + "[" + list[j] + "," + list[j + 1] + "]");
}
}
System.out.println("\n");
if (!swapped) {
//return;
break;
}
return;
}
System.out.print("Sorted array : ");
for (i = 0; i < list.length; i++) {
System.out.print(list[i] + " ");
}
}
}
BalasHapuspackage coba2;
class StackX
{
private final int SIZE = 20;
private int[] st;
private int top;
public StackX() {
st = new int[SIZE]; // make array
top = -1;
}
public void push(int j)
{
st[++top] = j;
}
public int pop()
{
return st[top--];
}
public int peek()
{
return st[top];
}
public boolean isEmpty()
{
return (top == -1);
}
}
class Graph
{
private final int MAX_VERTS = 20;
private Vertex vertexList[]; // array of vertices
public int adjMat[][]; // adjacency matrix
public int nVerts; // current number of vertices
private StackX theStack;
public Graph() // constructor
{
vertexList = new Vertex[MAX_VERTS];
// adjacency matrix
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for(int y=0; y<MAX_VERTS; y++) // set adjacency
for(int x=0; x<MAX_VERTS; x++) // matrix to 0
adjMat[x][y] = 0;
theStack = new StackX();
}
public void addVertex(char lab)
{
vertexList[nVerts++] = new Vertex(lab);
}
public void addEdge(int start, int end)
{
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}
public void displayVertex(int v)
{
System.out.print(vertexList[v].label);
}
}
class Vertex
{
public char label; // label (e.g. 'A')
public boolean wasVisited;
public Vertex(char lab) // constructor
{
label = lab;
wasVisited = false;
}
}
class App
{
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
////////////////// Print Vertex //////////////////
System.out.print("List of Vertex : ");
for(int i=0; i<theGraph.nVerts ; i++)
theGraph.displayVertex(i);
System.out.println();
System.out.println();
//////////////////////////////////////////////////
//////////////// Print Adjency Matrix ////////////
System.out.println("Adjency Matrix : ");
for(int j=0; j<theGraph.nVerts; j++)
{
for(int k =0; k<theGraph.nVerts; k++)
System.out.print(theGraph.adjMat[j][k] + " ");
System.out.println();
}
//////////////////////////////////////////////////
}
}
Komentar ini telah dihapus oleh pengarang.
BalasHapuspackage bubblesort;
BalasHapusimport java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int list[] = {1, 8, 4, 6, 0, 3, 5, 2, 7, 9};
int tmp;
int i, j;
boolean swapped;
//int loop = 0;
for (i = 0; i < list.length; i++) {
System.out.print(list[i] + " ");
}
System.out.println("\n");
for (i = 1; i < list.length - 1; i++) {
if (i > 1) {
System.out.println("iteration" + (i-1) + Arrays.toString(list));
System.out.println("\n");
}
swapped = true;
for (j = 0; j < (list.length - i); j++) {
if (list[j] > list[j + 1]) {
swapped = false;
tmp = list[j];
list[j] = list[j + 1];
list[j + 1] = tmp;
System.out.println("[" + list[j + 1] + "," + list[j] + "]" + "=" + "swapped" + "[" + list[j] + "," + list[j + 1] + "]");
} else {
System.out.println("[" + list[j] + "," + list[j + 1] + "]" + "=" + "not swapped");
}
}
System.out.println("\n");
if (swapped) {
return;
//break;
}
//return;
}
System.out.print("Sorted array : ");
for (i = 0; i < list.length; i++) {
System.out.print(Arrays.toString(list));
}
}
}
package coba2;
BalasHapusclass Graph {
private final int MAX_VERTS = 20;
private Vertex vertexList[];
public int adjMat[][];
public int nVerts;
public Graph()
{
vertexList = new Vertex[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for (int y = 0; y < MAX_VERTS; y++)
{
for (int x = 0; x < MAX_VERTS; x++)
{
adjMat[x][y] = 0;
}
}
//theStack = new StackX();
}
public void addVertex(char lab) {
vertexList[nVerts++] = new Vertex(lab);
}
public void addEdge(int start, int end) {
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}
public void displayVertex(int v) {
System.out.print(vertexList[v].label);
}
}
class Vertex {
public char label;
public boolean wasVisited;
public Vertex(char lab)
{
label = lab;
wasVisited = false;
}
}
class App {
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
////////////////// Print Vertex //////////////////
System.out.print("List of Vertex : ");
for (int i = 0; i < theGraph.nVerts; i++) {
theGraph.displayVertex(i);
}
System.out.println();
System.out.println();
//////////////////////////////////////////////////
//////////////// Print Adjency Matrix ////////////
System.out.println("Adjency Matrix : ");
for (int j = 0; j < theGraph.nVerts; j++) {
for (int k = 0; k < theGraph.nVerts; k++) {
System.out.print(theGraph.adjMat[j][k] + " ");
}
System.out.println();
}
//////////////////////////////////////////////////
}
}
kak implementasiin dong kak tolong,satu persatu
Hapuspackage javaapplication2;
BalasHapuspublic class BubbleSort {
void bubbleSort(int arr[])
{
int n ;
for (int i = 0; i < arr.length-1; i++){
n=0;
for (int j = 0; j < arr.length-i-1; j++){
System.out.print("\titems compared: [ " + arr[j] + " , " + arr[j+1] +" ] => ");
if (arr[j] > arr[j+1])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
System.out.println(" swapped [ " + arr[j+1] + " , " + arr[j] +" ]");
n++;
}
else
System.out.println(" not swapped");
}
if(n==0)
break;
System.out.print("iteration "+ (i+1) +"# = ");
this.printArray(arr);
}
}
void printArray(int arr[])
{
int n = arr.length;
System.out.print("[ ");
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.print(" ]");
System.out.println();
}
}
Komentar ini telah dihapus oleh pengarang.
BalasHapusMinta lagi
BalasHapus