Daily Archives: 29 March,09

<!– /* Font Definitions */ @font-face {font-family:”Cambria Math”; panose-1:0 0 0 0 0 0 0 0 0 0; mso-font-charset:1; mso-generic-font-family:roman; mso-font-format:other; mso-font-pitch:variable; mso-font-signature:0 0 0 0 0 0;} @font-face {font-family:Calibri; panose-1:2 15 5 2 2 2 4 3 2 4; mso-font-charset:0; mso-generic-font-family:swiss; mso-font-pitch:variable; mso-font-signature:-1610611985 1073750139 0 0 159 0;} /* Style Definitions */ p.MsoNormal, li.MsoNormal, div.MsoNormal {mso-style-unhide:no; mso-style-qformat:yes; mso-style-parent:”"; margin-top:0in; margin-right:0in; margin-bottom:10.0pt; margin-left:0in; line-height:115%; mso-pagination:widow-orphan; font-size:11.0pt; font-family:”Calibri”,”sans-serif”; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:Calibri; mso-fareast-theme-font:minor-latin; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:”Times New Roman”; mso-bidi-theme-font:minor-bidi;} .MsoChpDefault {mso-style-type:export-only; mso-default-props:yes; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-fareast-font-family:Calibri; mso-fareast-theme-font:minor-latin; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:”Times New Roman”; mso-bidi-theme-font:minor-bidi;} .MsoPapDefault {mso-style-type:export-only; margin-bottom:10.0pt; line-height:115%;} @page Section1 {size:8.5in 11.0in; margin:1.0in 1.0in 1.0in 1.0in; mso-header-margin:.5in; mso-footer-margin:.5in; mso-paper-source:0;} div.Section1 {page:Section1;} –>
/* Style Definitions */
table.MsoNormalTable
{mso-style-name:”Table Normal”;
mso-tstyle-rowband-size:0;
mso-tstyle-colband-size:0;
mso-style-noshow:yes;
mso-style-priority:99;
mso-style-qformat:yes;
mso-style-parent:”";
mso-padding-alt:0in 5.4pt 0in 5.4pt;
mso-para-margin-top:0in;
mso-para-margin-right:0in;
mso-para-margin-bottom:10.0pt;
mso-para-margin-left:0in;
line-height:115%;
mso-pagination:widow-orphan;
font-size:11.0pt;
font-family:”Calibri”,”sans-serif”;
mso-ascii-font-family:Calibri;
mso-ascii-theme-font:minor-latin;
mso-fareast-font-family:”Times New Roman”;
mso-fareast-theme-font:minor-fareast;
mso-hansi-font-family:Calibri;
mso-hansi-theme-font:minor-latin;}

void kruskal ( )

{

int i,x,b[MAX_NODE],top,w,v;

int min_wt,y,f_wt[MAX_NODE],bentuk;

node *ptr1;

f_node *ptr2;

f_list=NULL;

for(i=1;i<=totNodes;i++)

status[i]=unseen;

x=1;

status[x]=intree;

top=0;

bentuk=0;

while( (top <= (totNodes-1)) && (!bentuk

{

ptr1=adj[x];

while(ptr1!=NULL)

{

y=ptr1->vertex;

w=ptr1->weight;

if((status[y]==fringe) && (w<f_wt[y]))

{

b[y]=x;

f_wt[y]=w;

}

else if(status[y]==unseen)

{

status[y]=fringe;

b[y]=x;

f_wt[y]=w;

Insert_Beg(y);

}

ptr1=ptr1->next;

}

if(f_list==NULL)

bentuk=1;

else

{

x=f_list->vertex;

min_wt=f_wt[x];

ptr2=f_list->next;

while(ptr2!=NULL)

{

w=ptr2->vertex;

if(f_wt[w] < min_wt)

{

x=w;

min_wt=f_wt[w];

}

ptr2=ptr2->next;

}

del(x);

status[x]=intree;

top++;

}

for(x=2;x<=totNodes;x++)

cout<<”(“<<x<<”,”<<b[x]<<”)\n”;

delay(10);

}

→ Leave a comment

Posted in Uncategorized

Prim algorithm

Posted on 29 March,09 | Leave a comment

Procedure Prim(input G : graf, output T : pohon)

{ Membentuk pohon merentang minimum T dari

graf terhubung G.

Masukan : graf-berbobot terhubung G = (V, E),

dimana V = n

Keluaran : pohon rentang minimum T = (V, E’)

}

Deklarasi

i, p, q, u, v : integer

Algoritma

Cari sisi (p,q) dari E yang berbobot terkecil

T {(p,q)}

for i 1 to n-2 do

Pilih sisi (u,v) dari E yang bobotnya terkecil

namun bersisian dengan suatu simpul di

dalam T

T T {(u,v)}

endfor

→ Leave a comment

Posted in Uncategorized

Bellman Ford algorithm

Posted on 29 March,09 | Leave a comment

procedure BellmanFord(list vertices, list edges, vertex source)
   // This implementation takes in a graph, represented as lists of vertices
   // and edges, and modifies the vertices so that their distance and
   // predecessor attributes store the shortest paths.

   // Step 1: Initialize graph
   for each vertex v in vertices:
       if v is source then v.distance := 0
       else v.distance := infinity
       v.predecessor := null

   // Step 2: relax edges repeatedly
   for i from 1 to size(vertices)-1:       
       for each edge uv in edges: // uv is the edge from u to v
           u := uv.source
           v := uv.destination             
           if v.distance > u.distance + uv.weight:
               v.distance := u.distance + uv.weight
               v.predecessor := u

   // Step 3: check for negative-weight cycles
   for each edge uv in edges:
       u := uv.source
       v := uv.destination
       if v.distance > u.distance + uv.weight:
           error "Graph contains a negative-weight cycle"

→ Leave a comment

Posted in Uncategorized

DFS & BFS algorithm

Posted on 29 March,09 | Leave a comment

algoritma DFS

dfs(graph G)
{
  list L = empty
  tree T = empty
  choose a starting vertex x
  search(x)
  while(L is not empty)
  {
    remove edge (v, w) from beginning of L
    if w not yet visited
    {
      add (v, w) to T
      search(w)
    }
  }
}

search(vertex v)
{
  visit v
  for each edge (v, w)
    add edge (v, w) to the beginning of L
}

BFS algoritma


 
  Normal
  0
  
  
  
  
  false
  false
  false
  
  EN-US
  X-NONE
  X-NONE
  
   
   
   
   
   
   
   
   
   
   
   
  
  MicrosoftInternetExplorer4
  
   
   
   
   
   
   
   
   
   
   
   
  

 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
 

<!--
 /* Font Definitions */
 @font-face
	{font-family:"Cambria Math";
	panose-1:0 0 0 0 0 0 0 0 0 0;
	mso-font-charset:1;
	mso-generic-font-family:roman;
	mso-font-format:other;
	mso-font-pitch:variable;
	mso-font-signature:0 0 0 0 0 0;}
@font-face
	{font-family:Calibri;
	panose-1:2 15 5 2 2 2 4 3 2 4;
	mso-font-charset:0;
	mso-generic-font-family:swiss;
	mso-font-pitch:variable;
	mso-font-signature:-1610611985 1073750139 0 0 159 0;}
 /* Style Definitions */
 p.MsoNormal, li.MsoNormal, div.MsoNormal
	{mso-style-unhide:no;
	mso-style-qformat:yes;
	mso-style-parent:"";
	margin-top:0in;
	margin-right:0in;
	margin-bottom:10.0pt;
	margin-left:0in;
	line-height:115%;
	mso-pagination:widow-orphan;
	font-size:11.0pt;
	font-family:"Calibri","sans-serif";
	mso-ascii-font-family:Calibri;
	mso-ascii-theme-font:minor-latin;
	mso-fareast-font-family:Calibri;
	mso-fareast-theme-font:minor-latin;
	mso-hansi-font-family:Calibri;
	mso-hansi-theme-font:minor-latin;
	mso-bidi-font-family:"Times New Roman";
	mso-bidi-theme-font:minor-bidi;}
.MsoChpDefault
	{mso-style-type:export-only;
	mso-default-props:yes;
	mso-ascii-font-family:Calibri;
	mso-ascii-theme-font:minor-latin;
	mso-fareast-font-family:Calibri;
	mso-fareast-theme-font:minor-latin;
	mso-hansi-font-family:Calibri;
	mso-hansi-theme-font:minor-latin;
	mso-bidi-font-family:"Times New Roman";
	mso-bidi-theme-font:minor-bidi;}
.MsoPapDefault
	{mso-style-type:export-only;
	margin-bottom:10.0pt;
	line-height:115%;}
@page Section1
	{size:8.5in 11.0in;
	margin:1.0in 1.0in 1.0in 1.0in;
	mso-header-margin:.5in;
	mso-footer-margin:.5in;
	mso-paper-source:0;}
div.Section1
	{page:Section1;}
-->




 Inisialisasi Matriks Boolean yang diset false 

Inisialisasi
Sebuah Antrian Kosong 

Buat Simpul
Asal 

Masukkan
Simpul Asal ke dalam Antrian 

Buat Simpul
Tujuan 

Boolean
ketemu=false 

int jarak =
1 

While
AntrianTidakKosong and not ketemu do  

Ambil simpul n dari antrian  

if n=simpul_tujuan then

ketemu=true   

output(jarak)   

return solusi  

else

increment
(level)   

Bangkitkan
suksesor n  dari n   

for setiap
suksesor n  dari n  

if(dikunjungi[posisi  x  dari 

n ][posisi  y  dari  n
]=false) 

then

Set parent dari n  menjadi n 

Masukkan
n  ke dalam antrian 

endfor

endwhile

→ Leave a comment

Posted in Uncategorized

M	T	W	T	F	S	S
« Nov				May »
						1
2	3	4	5	6	7	8
9	10	11	12	13	14	15
16	17	18	19	20	21	22
23	24	25	26	27	28	29
30	31

Daily Archives: 29 March,09

Warshall algorithm

Kruskal algorithm

Prim algorithm

Bellman Ford algorithm

DFS & BFS algorithm

my post

Blogroll

Calender!!!

Pages

Meta

Follow “A Whole New World”