Windows Việt

Cộng Đồng Công Nghệ Thông Tin Việt

Trang ChínhTrang Chính  Sự kiện  Tìm kiếmTìm kiếm  Đăng kýĐăng ký  Đăng NhậpĐăng Nhập  

Share
 
 Code C thuật toán BFS
Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down 
Tác giảThông điệp
boy_saudoi
Member

boy_saudoi
Member
Giới tính : Nam
Tuổi : 30
Posts Posts : 43
Coins Coins : 85
Thanked Thanked : 8
Code C thuật toán BFS Empty
Bài gửiTiêu đề: Code C thuật toán BFS   Code C thuật toán BFS EmptyMon 11 Oct 2010, 21:03

Code:

#include<stdio.h>
#include<conio.h>
#include<string.h>
#define MAX 100

typedef struct Queue
{
  int *QArray;
  int QMax;
  int QNumItems;
  int QFront;
  int QRear;
}QUEUE;

int InitQueue(QUEUE &q,int MaxItems)
{
  q.QArray=new int [MaxItems];
  if(q.QArray==NULL)
      return 0;
  q.QMax=MaxItems;
  q.QNumItems=0;
  q.QFront=q.QRear=-1;
  return 1;
}
int IsQueueEmpty(const QUEUE &q)
{
  if(q.QNumItems==0)
  {
      return 1;
  }
  return 0;
}

int IsQueueFull(const QUEUE &q)
{
  if(q.QNumItems==q.QMax)
  {
      return 1;
  }
  return 0;
}

int EnQueue(QUEUE &q , int newitem)
{
  if(IsQueueFull(q))
  {
      return 0;
  }
  q.QRear++;
  if(q.QRear==q.QMax)
  {
      q.QRear=0;
  }
  q.QArray[q.QRear]=newitem;
  if(IsQueueEmpty(q))
      q.QFront=0;
  q.QNumItems++;
  return 1;
}

int DeQueue(QUEUE &q , int &outitem)
{
  if(IsQueueEmpty(q))
      return 0;
  outitem=q.QArray[q.QFront];
  q.QFront++;
  q.QNumItems--;
  if(q.QFront==q.QMax)
      q.QFront=0;
  if(IsQueueEmpty(q))
      q.QFront=q.QRear=-1;
  return 1;
}

int QueueFront(const QUEUE &q , int &outitem)
{
  if(IsQueueEmpty(q))
      return 0;
  outitem=q.QArray[q.QFront];
  return 1;
}
int QueueRear(const QUEUE &q , int &outitem)
{
  if(IsQueueEmpty(q))
      return 0;
  outitem=q.QArray[q.QRear];
  return 1;
}

struct MYGRAPH
{
  int N;
  int A[MAX][MAX];
  int Previous[MAX];
};
void InputGraph(MYGRAPH &g,char *file,int &start ,int &end)
{
  int b=0;
  FILE*f= fopen(file,"r");
  fscanf(f,"%d",&g.N);
  fscanf(f,"%d",&start);
  fscanf(f,"%d",&end);
  int i=0,j=0;
  while(!feof(f))
  {
      if(b%g.N==0 && b!=0)
      {
        i++;
        j=0;
      }
      fscanf(f,"%d",&g.A[i][j]);
      j++;
      b++;
  }
  for(i=0;i<g.N;i++)
  {
      g.Previous[i]=-1;
  }
  fclose(f);
}
int BFS(MYGRAPH &g,int start,int end)
{
  QUEUE q;
  InitQueue(q,100);
  int flag=0;
  EnQueue(q,start);
  int s;
  g.Previous[start] = -2;
  while(IsQueueEmpty(q)==0 && flag==0)
  {
      DeQueue(q,s);
      for(int i=0;i<g.N;i++)
      {
        if(g.A[s][i]!=0 && g.Previous[i]==-1)
        {
            EnQueue(q,i);
            g.Previous[i]=s;
            if(i==end)
            {
              flag=1;
              return flag;
            }
        }
      }
  }
  return flag;
}
void PrintPath(MYGRAPH g,int end)
{
  int i=end;
  printf("\nDuong di:\n");
  printf("%d",end);
      i=g.Previous[i];

  while(i!=-2)
  {
      printf("<- %d",i);
      i=g.Previous[i];
  }
}



void main()
{
 
  MYGRAPH g;
  int start,end;
  InputGraph(g,"C:/input.txt",start ,end);
  printf("%d,%d\n",start,end);
  if(BFS(g,start,end))
  {
      PrintPath(g,end);
  }
}
File input.txt có nội dung tương tự trong file hướng dẫn và ghi vào ỗ đĩa C

P/S: Code chỉ mang tính tham khảo


Sống Trên Đời Phải Có Chữ "Tâm"

Code C thuật toán BFS Av7005

Muốn Sinh Tồn Phải Thêm Chữ "Nhẫn"


Được sửa bởi boy_saudoi ngày Tue 12 Oct 2010, 19:23; sửa lần 1. (Reason for editing : update)

※ Bài viết cùng chuyên mục


Tác giảThông điệp
$teppy$
Member

$teppy$
Member
Giới tính : Nam
Tuổi : 30
Posts Posts : 32
Coins Coins : 61
Thanked Thanked : 9
Code C thuật toán BFS Empty

thanks cái, mặc dù coi vẫn chưa hỉu j Very Happy Very Happy cheers

※ Bài viết cùng chuyên mục


Tác giảThông điệp
mecme
Member

mecme
Member
Giới tính : Nam
Tuổi : 29
Posts Posts : 8
Coins Coins : 15
Thanked Thanked : 1
Code C thuật toán BFS Empty

Sao chạy hong dc nhỉ, mình tạo 1 file input.txt giống trong silde mà sao chạy hong dc bạn?

※ Bài viết cùng chuyên mục


Tác giảThông điệp
boy_saudoi
Member

boy_saudoi
Member
Giới tính : Nam
Tuổi : 30
Posts Posts : 43
Coins Coins : 85
Thanked Thanked : 8
Code C thuật toán BFS Empty

Nội dung file input có nội dung như sau :
Code:

4
0 1
0 0 1 1
0 0 1 1
1 1 0 0
1 1 0 0
Dòng 1 -> Số đỉnh
Dòng 2 -> Từ Start đến End
Dòng 3 -> n : Ma Trận kề .
Cái này đã học trong Toán Rời Rac thì phải Very Happy .


Sống Trên Đời Phải Có Chữ "Tâm"

Code C thuật toán BFS Av7005

Muốn Sinh Tồn Phải Thêm Chữ "Nhẫn"

※ Bài viết cùng chuyên mục


Tác giảThông điệp
Sponsored content


Code C thuật toán BFS Empty

※ Bài viết cùng chuyên mục


 
Code C thuật toán BFS
Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang 
Trang 1 trong tổng số 1 trang

Permissions in this forum:Bạn không có quyền trả lời bài viết
Windows Việt :: Lưu Trữ :: Lưu Trữ - Các môn học cũ :: Trí Tuệ Nhân Tạo-
[Windows Việt] Deverloped by Nguyễn Gia Phú - https://windows.forumvi.com
Powered by © Forumotion.com - phpBB™ version ©phpBB2
Go to top Go to bottom