[c]lý thuyết đồ thị

[diepanh]

có ai đã học qua lý thuyết đồ thị rồi chưa.Làm ơn giải thích cho mình cách chạy của một bài duyệt theo chiều rộng và tìm kiếm dựa theo BFS với. Khó hiểu quá!

[thandongdatviet]

Thủ tục:duyệt đồ thị theo chiều rộng BFS
void BFS(G,v)
{ Init Q(Q);
visit(v);
visited[v] = 1; //nếu v đã được thăm thì đẩy nó vào q
Insert Q(Q,v);
while (!=Empty Q(Q))
{ v = Delete Q(Q);
for các đỉnh w là đỉnh kề của v
if (visited[w] = 0)
{ visit(w);
visited[w] = 1;
Insert Q(Q,w);}
}
}
================================================
code

void mgraph::BFS(int v1)
{
int visited[100];
int v;
Queue Q;
for(int i=1;i<=V;i++)
visited[i]=0;
visited[v1]=1;
Creat(Q,V);
Push(Q,v1);

cout<<"Ket qua duyet do thi\n"<<v1;
while(!Empty(Q))
{
v=Pop(Q);
for(int i=1;i<=V;i++)
if(g[v][i]!=0&&visited[i]==0)
{

Push(Q,i);
visited[i]=1;
cout<<" "<<i;
}
}

Chúc bạn thành công nha!

[huongit1984]

Thủ tục:duyệt đồ thị theo chiều rộng BFS
void BFS(G,v)
{ Init Q(Q);
visit(v);
visited[v] = 1; //nếu v đã được thăm thì đẩy nó vào q
Insert Q(Q,v);
while (!=Empty Q(Q))
{ v = Delete Q(Q);
for các đỉnh w là đỉnh kề của v
if (visited[w] = 0)
{ visit(w);
visited[w] = 1;
Insert Q(Q,w);}
}
}
================================================
code

Chúc bạn thành công nha!

bài viết thật hay cảm ơn nhiều lắm
nhưng hàm Creat(Q,V) thế nào??
hàm Push(Q,V1) thế nào ?
bác làm giúp em !

[thandongdatviet]

Bạn dùng thử cái này xem.
Hàm Creat

void Creat(Queue &Q,int n)
{
Q.size=n;
for(int i=0;i<n;i++)Q.Item[i]=0;
Q.tail=Q.head=-1;
}

======================================
Hàm Push

void Push(Queue &Q,int v)
{
if(Q.tail==-1)Q.tail=0;
if(!Full(Q))
{
Q.tail++;
Q.Item[Q.tail]=v;
}
else { cout<<"\nQueue tran"; getch();}
}

Bạn còn gì thắc mắc nữa không vậy?

[huongit1984]

Bạn dùng thử cái này xem.
Hàm Creat
======================================
Hàm Push

Bạn còn gì thắc mắc nữa không vậy?

hay lắm thanks kju ju bạn nhiều