深度优先搜索程序模板

模板一：







procedure DFS(G);
   begin
1    for 每个顶点u∈V[G] do
       begin
2        color[u]←White;
3        π[u]←NIL;
       end;
4    time←0;
5    for 每个顶点u∈V[G] do
6      if color[u]=White
7          then DFS_Visit(G,u);
end;

procedure DFS_Visit(G,u);
begin
1   color[u]←Gray;              Δ白色结点u已被发现
2   d[u]←time←time+1;
3   for 每个顶点v∈Adj[u] do     Δ探寻边(u,v)
4      if color[v]=White
          then begin
5                π[v]←u;
6                DFS_Visit(G,v);
               end;
7   color[u]←Black;             Δ完成后置u为黑色
8   f[u]←time←time+1;
end;



评论

  1. lisa2012年2月10日 17:56

    我正在学深度优先搜索 你写的程序也都研究过了 请问 可不可以细说一下 谢谢 我十分需要你的帮助 yangxuebj@sohu.com 也可发到我邮箱里

    回复删除

发表评论

此博客中的热门博文

Linux/ARM Page Table Entry 属性设置分析

图片
注：该博文写的比较凌乱，需要以后再修改。 Linux 的页表项总体可以划分为两部分，一部分是物理映射地址，另一部分是对物理地址对应的访问属性。在Linux/ARM的Kernel中，为各式各样的内存属性与定义了一下条目 ：   198 static struct mem_type mem_types[] = {  199         [MT_DEVICE] = {           /* Strongly ordered / ARMv6 shared device */  200                 .prot_pte       = PROT_PTE_DEVICE | L_PTE_MT_DEV_SHARED |  201                                   L_PTE_SHARED,  202                 .prot_l1        = PMD_TYPE_TABLE,  203                 .prot_sect      = PROT_SECT_DEVICE | PMD_SECT_S,  204                 .domain         = DOMAIN_IO,  205     ...
阅读全文

由RFE指令引发的一串故事

图片
前段时间,我们在bring up一块Cortex-A5主控的芯片时,发现在跑FreeRTOS时, 系统总是crash. 通过GDB定位到一旦RFE指令执行结束后,系统便进入data abort mode. <图一> 一旦执行RFE便进入data abort <图二>， FreeRTOS中RFE相关代码片段 RFE指令如其字面含义, return from exception. 它的主要作用是: 从栈中弹出值分别赋值给cpsr和pc. 这条指令在恢复现场时,具有不可替代的作用(如果用其他指令来代替同样的功能, 自然就污染其他寄存器了). RFE指令在ARM v7 spec中的伪码： <图三>，RFE指令的伪码 曾经一度怀疑是Cortex-A5的errata，但是CPU指令级别的仿真测试对于RFE指令是没有问题的。而且，之前在FPGA上做预开发的时候，在FPGA平台上也没有发现此类问题。所以，一度陷入到困局中，没有思路。 如果整个FreeRTOS来让SOC仿真，那么仿真的时间会比较久，因此我们写了下面一段比较小的代码来进行仿真测试。但是仿真下来并没有发现问题。 _start:     ldr r0, =vectors     mcr p15, 0, r0, c12, c0, 0   // PLD Capablity     mrc p15, 0, r0, c0, c2, 2 //MAIN IDR     mrc p15, 0, r0, c0, c0, 0 // CCSIDR     mrc p15, 1, r0, c0, c0, 0     cps #0x17     ldr r0, =0x30009000     str r0, [r0]     ldr r0, =0x10009000     mov sp, r0     cps #0x1f     ldr r0, =0x10008000     mov sp, r0     mrs r0...
阅读全文

Why cann’t we remove the ZONE_DMA from Linux

ZONE_DMA设置的原因是因为，当年主板上的ISA总线中的DMA控制器只能寻址24位物理地址，因此最多能够寻址到16MB的地方。现在，随着硬件的发展，ISA早已经成为历史。可是，为什么现在还要保留着ZONE_DMA区呢？ 这是在linux-kernel mail list上的答案： http://lkml.org/lkml/2010/4/4/2 While ISA is gone as a true peripheral interconnect for new systems it does, actually, still live on in a lot of systems that Linux still supports. While those systems, generally, are running the same kernel and userspace they were a decade ago I have no doubt that somebody might find an old machine and put Linux on it - just because they could. And that also discounts the non-IBM PC machines that are out there that Linux also supports. While I don't know enough about them to say for sure, I am quite certain that at least some of them are still using the ISA bus. DRH > Thanks for your reply.And do you means that , If I use a modern PC,such as > my pc (CPU:Intel dual-core 2.6GHZ; Memory 2GB; And no pci ).I can remove > the ZONE_DMA .And make sure this system also run smoothly as before? *MAYBE* - if yo...
阅读全文