struktur data graf

Click here to load reader

Post on 30-May-2018

221 views

Category:

Documents

0 download

Embed Size (px)

TRANSCRIPT

  • 8/14/2019 Struktur Data Graf

    1/26

    STRUKTUR DATA (9)

    Oleh Antonius Rachmat C, S.Kom,M.Cs

    Dan Dra. Widi Hapsari, M.T

    Struktur Data Graf

  • 8/14/2019 Struktur Data Graf

    2/26

    GRAPH

    Graph adalah kumpulan dari simpuldan busur yang secara matematis

    dinyatakan sebagai :G = (V, E)

    DimanaG = GraphV = Simpul atau Vertex, atau Node, atau TitikE = Busur atau Edge, atau arc

  • 8/14/2019 Struktur Data Graf

    3/26

    Contoh graph :

    B

    A C

    D E

    Undirectedgraph

    vertex

    edge

    e1 e3e4

    e7e5e2

    e6

    v1

    v2

    v4 v5

    v3

    V terdiri dari v1, v2, , v5

    E terdiri dari e1, e2, , e7

  • 8/14/2019 Struktur Data Graf

    4/26

    Sebuah graph mungkinhanya terdiri dari satusimpul

    Sebuah graph belum tentusemua simpulnyaterhubung dengan busur

    Sebuah graph mungkinmempunyai simpul yangtak terhubung dengan

    simpul yang lain Sebuah graph mungkin

    semua simpulnya salingberhubungan

  • 8/14/2019 Struktur Data Graf

    5/26

    Graph Berarah dan Graph Tak

    Berarah :B

    A C

    D E

    B

    A C

    D E

    Directedgraph

    Undirectedgraph

    e1 e3

    e4

    e7e5e2

    e6

    v1

    v2

    v4 v5

    v3v1

    v2

    v3

    v5v4

    e1

    e2

    e3

    e4

    e5

    e6

    e7

    e8 e9

    e10

    Dapat dilihat dari bentuk busur yang artinya urutanpenyebutan pasangan 2 simpul.

  • 8/14/2019 Struktur Data Graf

    6/26

    Graph tak berarah (undirected graphatau non-directed graph) :

    Urutan simpul dalam sebuah busur tidakdipentingkan. Mis busur e1 dapat disebutbusur AB atau BA

    Graph berarah (directed graph) : Urutan simpul mempunyai arti. Mis busur

    AB adalah e1 sedangkan busur BA adalah

    e8.

  • 8/14/2019 Struktur Data Graf

    7/26

    Graph Berbobot (Weighted Graph) Jika setiap busur mempunyai nilai yang

    menyatakan hubungan antara 2 buahsimpul, maka busur tersebut dinyatakanmemiliki bobot.

    Bobot sebuah busur dapat menyatakan

    panjang sebuah jalan dari 2 buah titik, jumlah rata-rata kendaraan perhari yangmelalui sebuah jalan, dll.

  • 8/14/2019 Struktur Data Graf

    8/26

    Graph Berbobot :

    B

    A C

    D E

    B

    A C

    D E

    Directedgraph

    Undirectedgraph

    5 3

    12

    684

    3

    v1

    v2

    v4 v5

    v3v1

    v2

    v3

    v5v4

    5

    e2

    312

    8

    3

    6

    4 7

    10

    Panjang busur (atau bobot) mungkin tidak digambarkan secarapanjang yang proposional dengan bobotnya. Misal bobot 5digambarkan lebih panjang dari 7.

  • 8/14/2019 Struktur Data Graf

    9/26

    Istilah pada graph

    Incident Jika e merupakan busur dengan simpul-simpulnya adalah v dan w yang ditulis

    e=(v,w), maka v dan w disebut terletak padae, dan e disebut incident dengan v dan w.Degree (derajat), indegree dan outdegree

    Degree sebuah simpul adalah jumlah busur yangincident dengan simpul tersebut.

  • 8/14/2019 Struktur Data Graf

    10/26

    Indegree sebuah simpul pada graph

    berarah adalah jumlah busur yangkepalanya incident dengan simpultersebut, atau jumlah busur yang masukatau menuju simpul tersebut.

    Outdegree sebuah simpul pada graphberarah adalah jumlah busur yangekornya incident dengan simpul tersebut,atau jumlah busur yang keluar atauberasal dari simpul tersebut.

  • 8/14/2019 Struktur Data Graf

    11/26

    3. AdjacentPada graph tidah berarah, 2 buah

    simpul disebut adjacent bila ada busuryang menghubungkan kedua simpultersebut. Simpul v dan w disebutadjacent.

    Pada graph berarah, simpul v disebutadjacent dengan simpul w bila adabusur dari w ke v.

    we

    v

    v

    e w

  • 8/14/2019 Struktur Data Graf

    12/26

    4. Successor dan PredecessorPada graph berarah, bila simpul vadjacent dengan simpul w, maka simpulv adalah successor simpul w, dan simpulw adalah predecessor dari simpul v.

    5. PathSebuah path adalah serangkaian simpul-simpul yang berbeda, yang adjacentsecara berturut-turut dari simpul satu ke

    simpul berikutnya.1

    43

    2

    4

    2

    4

    2

    4

    21

    3

    1

    3

    1

    3

  • 8/14/2019 Struktur Data Graf

    13/26

    Representasi Graph dalambentuk matrix Adjacency Matrix Graph tak berarah

    B

    A C

    D E

    Graph

    0 1 0 1 01 0 1 0 1

    0 1 0 1 1

    1 0 1 0 1

    0 1 1 1 0

    A B

    A

    0

    B

    C

    1 2 43C D E

    D

    E

    0

    1

    2

    4

    3

    Urut abjad

    Degree simpul : 3

  • 8/14/2019 Struktur Data Graf

    14/26

  • 8/14/2019 Struktur Data Graf

    15/26

    Adjency List graph tak berarah Digambarkan sebagai sebuah simpul

    yang memiliki 2 pointer. Simpul vertex : Simpul edge :

    Representasi Graph dalambentuk Linked List

    info info

    Menunjuk ke simpulvertex berikutnya,

    dalam untaian simpulyang ada.

    Menunjuk ke simpuledge pertama Menunjuk ke

    simpul edgeberikutnya, bila

    masih ada.Menunjuk ke simpulvertex tujuan yang

    berhubungan dengansimpul vertex asal.

    left right left right

  • 8/14/2019 Struktur Data Graf

    16/26

    Define struct untuk sebuah simpulyang dapat digunakan sebagaivertex maupun edge.

    typedef struct tipeS {

    tipeS *Left;

    int INFO;

    tipeS *Right;

    };

    tipeS *FIRST, *PVertex, *PEdge;

  • 8/14/2019 Struktur Data Graf

    17/26

    Contoh : untuk vertex A, memiliki 2edge yang terhubung yaitu e1 dan e2.

    A

    C

    D

    B

    E

    e2

    Graph

    e1B

    A C

    D E

    e1e3

    e4

    e7e5e2

    e6

    Urut abjad

  • 8/14/2019 Struktur Data Graf

    18/26

    Gambar di atas dapat disusun denganlebih sederhana, sbb :

    A

    C

    D

    B

    E

    D

    A

    B

    A

    B

    C E

    D E

    C

    C D

    B

    A C

    D E

    Graph

    B

    E

  • 8/14/2019 Struktur Data Graf

    19/26

    Adjency List graph berarah

    A

    C

    D

    B

    E

    D

    A

    B

    C

    E

    C

    B

    E

    B

    A C

    D E

  • 8/14/2019 Struktur Data Graf

    20/26

    Graph berarah danberbobot

    B

    A C

    D E

    5 3

    2

    14

    12

    6

    7

    12

    0 5 0 2 06 0 3 0 00 0 0 0 90 0 12 0 7

    0 14 0 0 0

    A

    A

    0

    B

    C

    1 2 43

    D

    E

    0

    1

    2

    4

    3

    B C D E

    Perhatikan pemilihan nilai 0.

  • 8/14/2019 Struktur Data Graf

    21/26

    Penyelesaian kasus Graphhalaman sebelumnya :

    Define simpul untuk vertex dan edge Mengidentifikasi Simpul pertama

    sebagai vertex yang pertama Tambahkan vertex sisanya Tambahkan edge pada masing-

    masing vertex yang telah terbentuk Tampilkan representasi graphberikut bobotnya

  • 8/14/2019 Struktur Data Graf

    22/26

  • 8/14/2019 Struktur Data Graf

    23/26

  • 8/14/2019 Struktur Data Graf

    24/26

  • 8/14/2019 Struktur Data Graf

    25/26

    Hasil :

  • 8/14/2019 Struktur Data Graf

    26/26

    Next

    Fungsi Rekursif