LaneBlog

蝼蚁虽小,也有梦想

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

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

Clicks: 40279 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

回复

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