LaneBlog

蝼蚁虽小,也有梦想

PHP Socket服务 | PHP微信开发框架 | 开源博客

算法九:深度优先搜索和广度优先搜索来遍历图

Clicks: 40997 Date: 2014-11-14 18:25:34 Power By 李轩Lane

    

图的遍历,我们用深度优先搜索遍历图和广度优先搜索遍历图。最简单的一种图的遍历-穷举!

如下的图:

F1062065-133F-4EB8-AD78-3E7168FF00C7.png

点1和点2,3,5有边,点3和点5有边,点2和点4有边。mac画的好累。。没有鼠标。。


输入:第一行是点的总数和边的总数,下面几行都是那几个点有边。

        5 5

        1 2

        1 3

        1 5

        2 4

        3 5


深度优先搜索来遍历图,代码如下:

#include <stdio.h>

int a[101][101];

int book[101];

int m, n, sum=0;

void dfs(int node);

int main(){

    int i, j, x, y;

    scanf("%d %d", &m, &n);

    for(i=1; i<=n; i++){

        for(j=1; j<=n; j++){

            a[i][j] = 0;

        }

    }

    for(i=0; i<m; i++){

        scanf("%d %d", &x, &y);

        a[x][y] = 1;

        a[y][x] = 1;

    }

    book[1] = 1;

    dfs(1);

}

void dfs(int node){

    printf("%d ", node);

    sum++;

    if(sum == n){

        return;

    }

    int i = 0;

    for(i=1; i<=n; i++){

        if(book[i] != 0 || a[node][i] != 1) continue;

        book[i] = 1;

        dfs(i);

    }

}

输出:1,2,4,3,5



广度优先搜索来遍历图,代码如下:

输入:第一行是点的总数和边的总数,下面几行都是那几个点有边。


#include <stdio.h>

int a[101][101];

int book[101];

int m, n;

void dfs(int node);


int main(){

    int i, j, x, y;

    scanf("%d %d", &m, &n);

    for(i=1; i<=n; i++){

        for(j=1; j<=n; j++){

            a[i][j] = 0;

        }

    }

    for(i=0; i<m; i++){

        scanf("%d %d", &x, &y);

        a[x][y] = 1;

        a[y][x] = 1;

    }

    book[1] = 1;

    //广度优先搜索

    int head = 0, tail = 0;

    int queue[25];

    for(i=0; i<25; i++) queue[i] = 0;

    queue[tail] = 1;

    tail++;

    while(head<tail){

        printf("%d ", queue[head]);

        for(i=1; i<=n; i++){

            if(book[i] != 0 || a[queue[head]][i] != 1) continue;

            book[i] = 1;

            queue[tail] = i;

            tail++;

        }

        head++;

    }

}

输出:1,2,3,5,4

Reply: Zheng On 2014-11-18 11:14:15

学习了,希望博主多多分享。

回复

Reply: Refugia On 2020-09-25 00:25:52

http://nopain.fun/ buy sildenafil eu http://nopain.fun/drug/alkeran/reviews buy sildenafil eu http://nopain.fun/condition/pancreas-transplant-rejection buy sildenafil eu http://nopain.fun/drug/zyprexa/reviews/3

回复

Reply: Therese On 2020-10-01 22:35:42

http://www.aiuextension.org/groups/buy-brand-lipitor/ lithium evanescence listen online ,https://myshoopy.com/groups/donde-comprar-liquido-zantac-mejor-sitio-web-para-comprar-generico/ buy carbamazepine ,http://www.ganja-farmer.net/forums/topic/adipex-cheap-cialis-eteamz-active-com-link-online/ where can i buy xenical online ,https://totalmakeoverprogram.com/groups/where-can-i-buy-vp-gl-in-johannesburg/ acarbose online bestellen , https://sesameautisme.fr/groups/where-to-buy-bupropion/ how to order a dexamethasone suppression test ,https://happyfolks.info/groups/cheap-periactin-pills/ can you buy lithium carbonate over the counter ,https://updev.co.za/forums/topic/buy-magic-renova/ where to buy simvastatin tablets ,https://www.lasercutterreviews.com/forums/topic/buy-zyrtec-in-canada/ clobetasol cream buy online , http://gamecomenius.com/forums/forum/geral/ where to buy priligy in delhi ,https://www.cubica.net/groups/where-to-buy-cialis-in-new-zealand/ orlistat pills online , buy viagra canada pharmacy , http://www.pinebeltchevrolet.biz/__media__/js/netsoltrademark.php?d=www.lasercutterreviews.com%2Fforums%2Ftopic%2Fbuy-nizoral-shampoo-online-india%2F ,

回复

Reply: Loretta On 2020-11-05 22:06:07

Every weekend i used to pay a visit this website, as i wish for enjoyment, since this this website conations truly pleasant funny data too.

回复

Reply: glupleAgRilla On 2020-11-09 00:01:01

23063 topless cam girls http://greatparkcityrental.com/__media__/js/netsoltrademark.php?d=michelejullian.info/anal/621-albums-with-ella-nova-new-anal-recruits.php 7277 pounding mia khalifa for another http://geneticrafters.com/__media__/js/netsoltrademark.php?d=michelejullian.info/lesbian/13671-redheaded-slut-bree-daniels-takes-on-big-dick.php 299 red dildo on the chair https://mailer.reyrey.net/Click.ashx?p=2&env=1&AccountId=68174&IssueId=825842&SubscriberId=0&LogId=b11&Action=w&LinkType=&url=michelejullian.info%2fsexy%2f11878-mia-sollis-in-piros-by-luca-helios.php 24401 hot wife enjoys her young neighbor http://fisher-investment-market-minder.org/__media__/js/netsoltrademark.php?d=michelejullian.info/anal/7858-teens-prefer-anal-streaming-or-on-demand.php 22536 wicked teen sonja romanoff fucked in her tight anal hole http://solarizewv.com/__media__/js/netsoltrademark.php?d=michelejullian.info/model/19903-eva-part-lovia-tushy.php 16286 camarera tetona madura anal http://uniastrum.com/__media__/js/netsoltrademark.php?d=michelejullian.info/pussy/5824-playing-with-my-pussy-webcam-com.php 17574 maricella in behind the innocent look by girls http://ww5.explosivelabs.com/__media__/js/netsoltrademark.php?d=michelejullian.info/tits/11655-naked-petite-redhead-trans-gifs-striptease-babes.php 8295 juliett lea sexart brunette nude legs spreadi http://hindilinks4u.com/__media__/js/netsoltrademark.php?d=michelejullian.info/teen/6935-small-tits-club-zoey-kush.php 5000 alise moreno with rose removes panties russian sexy girls http://ihateusf.net/__media__/js/netsoltrademark.php?d=michelejullian.info/milf/3404-bondage-bound-gefesselt.php 23879 cute teenage babes in hot threeway from teen mega world http://dewanfam.com/__media__/js/netsoltrademark.php?d=michelejullian.info/nude/19605-jane-wilde-in-took-my-from-skeet.php 10759 smoking hot lexi lore knows what naughty guy likes the most http://pershing-llc.org/__media__/js/netsoltrademark.php?d=michelejullian.info/blonde/24485-spencer-blonde-vixen-takes-her-babes.php 19186 cum shots wifi http://youthleaguesusa.org/__media__/js/netsoltrademark.php?d=michelejullian.info/teen/3094-teens-behaving-badly.php 11806 amber pumps her pussy and asshole deep pichunter http://agribear.com/__media__/js/netsoltrademark.php?d=michelejullian.info/sexy/25281-spermmania-yui-kawagoe-hdfree-hit-fuck-javpornpics.php 17441 goth girl dianna dee shows oiled ass in fishnet stockings http://nuterrain.com/__media__/js/netsoltrademark.php?d=michelejullian.info/teen/8124-holly-hendrix-young-small-girl-in-double-fun-for-enlarge.php 3382 debora amy naked closeup shaved pussy labia ass anus http://ericalynschwartz.com/__media__/js/netsoltrademark.php?d=michelejullian.info/amateur/4241-flat-as-board-bitch-roxy-bell-gets-her-anus-fanalucked.php 13104 devilsfilm sex belinda japanesebeauties http://www.replacementsltd.biz/__media__/js/netsoltrademark.php?d=michelejullian.info/teen/16799-new-teen-nude.php 13865 dark haired nurse in white stockings gives nice dick massa http://esb.am/__media__/js/netsoltrademark.php?d=michelejullian.info/mature/22346-blonde-teen-cutie-holly-morgan-gives-nasty-blowjob.php 4070 pinkfineart margarita pink kneehighs from wearehairy http://www.wheelchairtennis.org/__media__/js/netsoltrademark.php?d=michelejullian.info/blonde/8575-sensual-blonde-with-cute-face-caroline-is-posing-on-her-heels.php 13668 sophia santi aka natalia cruze http://consolidated.biz/__media__/js/netsoltrademark.php?d=michelejullian.info/model/15969-remy-lacroix-outdoor-yoga.php 2595 blacked first interracial for kristen lee on home http://otclassifieds.com/__media__/js/netsoltrademark.php?d=michelejullian.info/cock/14193-black-girls-getting-fucked-anal-sex-pass.php 918 chloe carter burning angel http://a31.velaconnect.com/lt.php?id=ch4BHldfBlFRSAAFVAcLAA0%3D&nexturl=bWljaGVsZWp1bGxpYW4uaW5mbyUyZm1vZGVsJTJmMjI0NjktbWV0LWFydC1za2lubnktcmVkaGVhZC1uYXRhbGlhLnBocA== 12015 zoey delaying your orgasm tease pov http://parisfamilyoffice.com/__media__/js/netsoltrademark.php?d=michelejullian.info/lesbian/24751-aidra-fox-and-lena-paul-the-celebrity-girls-way-lesbian.php 16301 megan bath art http://www.alaskawoodworker.com/__media__/js/netsoltrademark.php?d=michelejullian.info/hairy/4986-wearehairy-terry-takes-off-floral-dress-to-show-sexy.php 23254 karmen karma gets nailed in black leather lingerie ang http://startupguru.in/__media__/js/netsoltrademark.php?d=michelejullian.info/model/24749-pinkfineart-cherry-potter-from-als-scan.php 6154 teen pink teenpinkvideos model lovest young thumbnail http://www.nisekoresortholdings.org/__media__/js/netsoltrademark.php?d=michelejullian.info/pussy/3537-angel-smalls-shaved-pussy-fucked-doggystyle.php 10180 blonde office doll kylie gets nailed on the desk stream http://yamahadirect.com/__media__/js/netsoltrademark.php?d=michelejullian.info/ass/5797-enamour-ass-very-skinny-asian-teen-amai-liu-onher-knees-sucking-showing.php 12264 rachel aldanas breasts old man nails big titted chubby teen http://exclusive-pm.ru/redir.asp?id=https%3a%2f%2fmichelejullian.info%2fhairy%2f23199-rachel-bush-play-bed-from-wearehairy.php 9889 brunette teen bounces her pussy on massive dick http://buyjerky.net/__media__/js/netsoltrademark.php?d=michelejullian.info/sexy/7624-ashley-bulgari-peekaboo.php 11268 cute teen sapphira getting naked in the living room http://www.radicalpacs.net/__media__/js/netsoltrademark.php?d=michelejullian.info/sex/6177-tgirls-brittany-jane.php 2137 hairy amateur annabella http://icravespending.com/__media__/js/netsoltrademark.php?d=michelejullian.info/lesbian/6288-old-and-young-lesbian-hot-nude.php

回复

Reply: Marlene On 2021-02-12 21:12:34

I like what you guys are usually up too. This kind of clever work and exposure! Keep up the wonderful works guys I've incorporated you guys to my personal blogroll.

回复

Add Comment
©2014 www.lanecn.com , All rights reserved. Power By Li Xuan.  京ICP备14005030号-1