Strona główna > Grafy > BFS przeszukiwanie grafu wszerz -implementacja C

BFS przeszukiwanie grafu wszerz -implementacja C

25 Sierpień 2011 Dodaj komentarz Go to comments
//BFS przeszukiwanie grafu wszerz
#include <stdlib.h>
#define bialy 0
#define szary 1
#define czarny 2
#define MAX 6

typedef struct lista{
        struct lista *next;
        int klucz;
        }lista;

typedef struct FIFO{
        int key;
        struct FIFO *next;
        struct FIFO *prev;
        }FIFO;

typedef struct wierzcholek{
        lista *head;
        int kolor;
        int odleglosc;
        int poprzednik;
        }wierzcholek;

void DodajDoListy(lista **head, int wartosc)
{
     lista *tmp, *nowy;
     nowy=(lista *)malloc(sizeof(lista));
     nowy->next=NULL;
     nowy->klucz=wartosc;

     if(*head==NULL) *head=nowy;
     else{ 
           tmp=*head;
           while(tmp) tmp=tmp->next;
           tmp=nowy;
         }
}

void DodajRelacje(wierzcholek tab[], int x, int y)
{
     DodajDoListy(&tab[x].head,y);
}

void push(FIFO **head, FIFO **tail, int el)
{
     FIFO *nowy;
     nowy= (FIFO *)malloc(sizeof(FIFO));
     nowy->key=el;
     nowy->next=NULL;
     nowy->prev=NULL;

     if(*head==NULL){
         *head=nowy;
         *tail=nowy;
         }
     else{
         nowy->prev=(*tail);
         (*tail)->next=nowy;
         (*tail)=nowy;
         }
}
void pop(FIFO **head)
{
     FIFO *tmp=(*head);
     if((*head)==NULL){
       printf("Brak el...");
        }
     else if((*head)->next==NULL){
     *head=NULL;}
     else{
        (*head)=(*head)->next;
        (*head)->prev=NULL;
        free(tmp);
        }
}

void BFS(wierzcholek tab[], int Source)
{
     int i,u;
     for(i=0;i<MAX;i++)
     {
           tab[i].kolor=bialy;
           tab[i].odleglosc=-1;
           tab[i].poprzednik=-1;
     }
     tab[Source].kolor=szary;
     tab[Source].odleglosc=0;
     tab[Source].poprzednik=-1;

     lista *tmp;
     FIFO *head=NULL;
     FIFO *tail=NULL;
     push(&head,&tail,Source);     

     while (head!=NULL)
     {
        u=head->key;
        pop(&head);
        tmp=tab[u].head;
        while(tmp!=NULL)
        {
           if(tab[tmp->klucz].kolor==bialy)
           {
               tab[tmp->klucz].kolor=szary;
               tab[tmp->klucz].odleglosc=tab[u].odleglosc+1;
               tab[tmp->klucz].poprzednik=u;
               push(&head,&tail,tmp->klucz);   
           }
           tmp=tmp->next;
           printf("%d ", head->key);
        }
        tab[u].kolor=czarny;
     }      
}

int main(int argc, char *argv[])
{
  int i;
    wierzcholek tab[MAX];
    for(i=0;i<MAX;i++)
    {
         tab[i].head=NULL;
    }

    DodajRelacje(tab,0,1);
	DodajRelacje(tab,0,2);
    DodajRelacje(tab,0,3);
    DodajRelacje(tab,1,4);
    DodajRelacje(tab,2,4);
    DodajRelacje(tab,4,5);
    DodajRelacje(tab,1,3);
    /*DodajRelacje(tab,4,2);
    DodajRelacje(tab,5,4);*/

    BFS(tab,0);
    printf("\t\t BFS");
    for(i=0;i<MAX;i++){
    printf("\nWierzcholek: %d  ", i);
    printf("/ %d /", tab[i].odleglosc);
    printf(" %d  / ", tab[i].kolor);    
    printf(" %d  / ", tab[i].poprzednik);
    }
    printf("\n");
  system("PAUSE");	
  return 0;
}
  1. 2 Lipiec 2013 o 6:22 pm

    Thank you for another informative web site.
    Where else may I get that type of info written in such an ideal means?
    I have a undertaking that I am just now working on, and I’ve been on the glance out for such information.

  2. how to install
    2 Lipiec 2013 o 6:58 pm

    With havin so much written content do you ever run into any
    problems of plagorism or copyright infringement?
    My blog has a lot of completely unique content I’ve either created myself or outsourced but it looks like a lot of it is popping it up all over the internet without my agreement. Do you know any methods to help prevent content from being stolen? I’d
    definitely appreciate it.

  3. 12 Grudzień 2013 o 12:23 am

    Тhanks for sharing уour thoughtѕ on liar quotes tumblr.
    Regаrds

  4. 14 Grudzień 2013 o 8:46 pm

    It’s awesome for me to have a website, which is beneficial in
    support of my experience. thanks admin

  5. 19 Grudzień 2013 o 11:27 pm

    Does your site have a contact page? I’m having trouble locating it
    but, I’d like to shoot you an e-mail. I’ve got some ideas for your blog you might be interested in hearing.

    Either way, great blog and I look forward to seeing it
    develop over time.

  6. 21 Styczeń 2014 o 6:36 pm

    Hi my loved one! I want to say that this article is amazing,
    great written and come with almost all vital infos.
    I would like to peer more posts like this .

  7. 9 Luty 2014 o 5:17 pm

    So get yourself away from him and live your life your way.
    To them, Facebook has become the most essential part of life.
    Net Credibility – blogging manujfactured bloggfers an additional sort of journalists bringing different types of information published in this kind of a
    way to reflect the viewpoint of the men
    and women who have winessed the situations on first account
    oor to reflect their individual way of speaking.

  8. 13 Luty 2014 o 12:03 pm

    I love BFS przeszukiwanie grafu wszerz -implementacja
    C | Czas na zeszyt…xD
    Asking questions are truly pleasant thing if you are not understanding anything fully, however this piece of
    writing provides pleasant understanding even.

  9. 20 Luty 2014 o 2:42 pm

    This similar potential market is expecting the likelihood to download new and old
    reserve apps into their sparkly new iPads. Track feedings,
    diapers and sleep right on your iPhone. In case you require to
    obtain a widespread collection of data that happen to be synchronized and immediately available all over the place, you should use Dropbox –
    Safe online record sync.

  10. 21 Luty 2014 o 1:29 pm

    Heya i’m for the first time here. I found this board and I
    find It truly useful & it helped me out a lot. I hope to give something back
    and aid others like you helped me.

  11. 21 Luty 2014 o 2:19 pm

    Wow, this article is pleasant, my younger sister is analyzing these kinds of things,
    thus I am going to inform her.

  12. 21 Luty 2014 o 2:31 pm

    I’ve been browsing online more than three hours today, yet I never found any interesting article like yours.
    It is pretty worth enough for me. In my opinion, if all web owners and bloggers made good content as you did, the web will be a lot more useful than ever before.

  13. 3 Marzec 2014 o 4:19 am

    I drop a leave a response whenever I like a post on a site or I have something
    to add to the conversation. Usually it is a result of the sincerness displayed in the article I read.

    And on this article BFS przeszukiwanie grafu wszerz -implementacja C | Czas
    na zeszyt…xD. I was excited enough to post a comment😉 I
    actually do have 2 questions for you if it’s okay.
    Is it only me or does it give the impression like some of
    the responses look like left by brain dead people?
    😛 And, if you are posting at additional social sites, I would like to keep
    up with anything fresh you have to post. Could you make a list
    every one of all your social pages like your twitter feed, Facebook page or linkedin
    profile?

  14. 17 Marzec 2014 o 10:24 am

    All that being said, the aspect to all of this that
    I wish to share, and perhaps provide a dose of caution, is:
    Grades. The golden toad and the harlequin frog of Costa Rica
    are gone completely as a result of the global warming changes
    we are experiencing. Three years ago, the visual difference between a console game and an
    online game was staggering.

  15. 23 Marzec 2014 o 11:09 pm

    Hi there, I think your blog could possibly be having internet
    browser compatibility issues. Whenever I take a
    look at your web site in Safari, it looks fine but when opening
    in I.E., it has some overlapping issues. I just wanted to provide
    you with a quick heads up! Apart from that, excellent site!

  16. 11 Kwiecień 2014 o 1:10 am

    Spain’s shocking defeat at the palms of Switzerland in the 2010 FIFA
    World Cup was a key debacle. The Swiss astounded the catalans with a 1-
    consequence from the European Champions. The truth that
    made this outcome even more pronounced was that Spain’s was seemingly impressive
    line up even with no Raul and Morientes and other aged war
    horses. I was just pondering about these popular soccer gamers from Spain and considered why not see who
    all produced glory on the soccer pitch. Claudia Schiffer additional a contact of glamour to proceedings The 2006 World Cup has got
    under way in Germany with an extravagant opening ceremony
    in Munich’s Allianz Arena.

  17. 13 Kwiecień 2014 o 12:01 pm

    In addition to the reliability of mesh safety pool covers stemming from their durable construction,
    proper installation of these covers provides highly dependable protection in the sense
    that they won’t come loose or unfastened. If you need a mat for building a
    new trampoline of your thoughts, you might choose custom-built mats in any unusual shape you think.
    There have been reports of people flipping off of the trampoline and breaking their necks, so my advice is to not try it.

  18. 30 Kwiecień 2014 o 3:32 am

    I think this is among the most important information for me.

    And i’m glad reading yolur article. But wanna remark on
    some general things, The site style is great, the articles is really
    great : D. Good job, cheers

  19. 2 Maj 2014 o 6:24 pm

    Cheers forr a very well-informed blogpost. Really makes me think about making a crack writing yet again.
    Whatever assistance on how greatest to get going???

  20. 8 Maj 2014 o 1:03 am

    I visit every day a few web sites and sites to read content, however this webpage offers quality based writing.

  21. 28 Maj 2014 o 6:53 pm

    Let me instantly get hold of ones rss feed while i can not in locating your own e-mail ongoing website link or e-newsletter support. Conduct you may have every? Please let everyone find out to ensure I possibly could sign up. Many thanks.

  22. 28 Maj 2014 o 10:43 pm

    I got this web site from my pal who told me on the
    topic of this web site and now this time I am browsing this website and reading
    very informative articles at this place.

  23. 31 Maj 2014 o 9:26 am

    This is my first time visit at here and i am genuinely impressed
    to read all at alone place.

  24. 2 Czerwiec 2014 o 12:18 am

    You’re an exceptional writer. I have subscribed to your web site cos
    I’d rather not miss your upcoming articles or blog posts

  25. 3 Czerwiec 2014 o 11:12 pm

    I am actually grateful to the owner of this web page who
    has shared this wonderful paragraph at at this time.

  26. 4 Czerwiec 2014 o 6:59 pm

    Superb point. Could not agree with you more.

  27. 4 Czerwiec 2014 o 9:31 pm

    I was extremely pleased to discover this website.
    I want to to thank you for ones time for this particularly wonderful read!!
    I definitely enjoyed every little bit of it and i also have you bookmarked to see new stuff in your blog.

  28. 12 Czerwiec 2014 o 8:13 am

    What you posted was actually very reasonable.
    But, think about this, suppose you were to write a awesome post title?
    I mean, I don’t want to tell you how to run your blog,
    but what if you added something to possibly grab people’s
    attention? I mean BFS przeszukiwanie grafu wszerz -implementacja C | Czas na zeszyt…xD is kinda vanilla.
    You could look at Yahoo’s front page and note how they create article headlines to get viewers to open the links.
    You might add a video or a related picture or two to get people excited
    about everything’ve written. Just my opinion, it might make your blog a little bit more interesting.

  29. 5 Lipiec 2014 o 4:14 am

    Thank you for the auspicious writeup. It in fact was a amusement account it.
    Look advanced to far added agreeable from you! By the way,
    how could we communicate?

  30. 10 Lipiec 2014 o 10:02 pm

    Wonderful post! We will be linking to this particularly great article on our site.
    Keep up the good writing.

  31. 12 Lipiec 2014 o 9:19 pm

    Hello, I enjoy reading through your article. I wanted to wrijte a little comment tto support you.

  32. 23 Lipiec 2014 o 3:56 am

    Actually no matter if someone doesn’t know afterward its up
    to other users that they will help, so here
    it happens.

  33. 24 Lipiec 2014 o 12:31 am

    This website was… how do you say it? Relevant!! Finally I’ve found
    something that helped me. Thanks a lot!

  34. 25 Lipiec 2014 o 1:58 pm

    Wow I love this! Have you noticed this escort seo
    article!Take a lok at this article on escort seo!

  35. 1 Sierpień 2014 o 6:41 am

    Itts nott my first time to pay a quick visit this website, i am browsing this webb
    site dailly and obtain nice data from here everyday.

  36. 1 Sierpień 2014 o 6:22 pm

    Howdy, amazing website post. It genuinely has inspired to learn more on line.

  37. 5 Sierpień 2014 o 7:51 pm

    Have you any kind of tips on establishing a blog? I am really
    bored of doing the same kind of thing at the office and want something totally new.

  38. 6 Sierpień 2014 o 12:12 am

    Good blog. Inspires me to get going producing articles online again

  39. 16 Sierpień 2014 o 5:51 am

    Thhis page certainly has all the information I wanted concerning this subjeft and didn’t know who to
    ask.

  40. 3 Wrzesień 2014 o 2:02 am

    I waas curios if you ever hought of changing thhe layout of your website?
    Its very well written; I love what youve got to say.
    But maytbe you could a little more in the way of conent so people could
    connect with it better. Youve got an awful lot of text for only having one or 2 images.

    Maybe you could space it out better?

  41. 13 Wrzesień 2014 o 7:55 am

    I think this is one of the most significant info for
    me. And i am glad reading your article. But want to remark on few general
    things, The web site style is ideal, the articles is really nice :
    D. Good job, cheers

  42. 7 Październik 2014 o 10:49 am

    Hello There. I found your blog using msn. This iis a very well written article.

    I’ll be sure to bookmark it and come back to read more of
    your useful information. Thanks for the post.

    I wil definitely return.

  43. 4 Listopad 2014 o 6:09 am

    After looking at a number of the articles onn your website, I truly
    like your technique of blogging. I book-marked it to
    mmy bookmark website list and will be checking back in the near future.
    Please visit myy webb site as well and let me know what you think.

  44. 12 Kwiecień 2015 o 4:14 am

    I got this web page from my friend who informed me about this web page and now this time I am browsing this web page and reading
    very informative content at this place.

  1. 10 Wrzesień 2014 o 3:03 am
  2. 12 Październik 2014 o 8:05 pm
  3. 20 Październik 2014 o 9:22 am
  4. 23 Październik 2014 o 5:28 am
  5. 24 Październik 2014 o 2:42 am

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s

%d bloggers like this: