20210510

回顾

• corporate adj.公司的；法人的；全体的；共同的
• incorporate v.把..合并；使并入；混合；包含
• manual adj.手工的；人力的；手动的
• subconscious adj.下意识地；潜意识的
• heal v.使治愈；愈合；和解
• pharmaceutical [ˌfɑ:məˈsu:tɪkl ]adj.制药的
• aviation n.航空；飞行
• aesthetic adj.美学的；艺术的；审美的
• intricate adj.错综复杂的；难理解的

数据结构-图的遍历-图（二）

从图中的某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，这一过程就叫做图的遍历(Traversing Graph)

图的遍历算法-深度优先搜索遍历（DFS）

想象一下，此时站在A处（其他也可以），（面向D的方向）。给自己定一个原则，右手原则（或左手原则也可以），从A开始要走遍所有的图顶点并做上标记，开始走了噢！

不难发现其实就是一个递归的过程，再细心观察，其实就是一棵树的前序遍历（先访问根结点，再左子树，再右子树）。

void DFS(int v,AGraph *G)
{
    visit[v] = 1;
    Visit(v);
    ArcNode *q = G->adjList[v].first;
    while(q != NULL)
    {
        if (visit[q->adjv] == 0)
            DFS(q->adjv,G);
        q = q->next;
    }
}

图的遍历算法-广度优先搜索遍历（BFS）

将之前那个图变一下形状：

那么，从顶点A出发，则与A相邻的有B、F。（假如遵守右手原则），则是A→B→F。然后B又找到下一层CIG，F又找到下一层GE（但G已经被B遍历过有标记了），即为A→B→F→C→I→G→E,然后C找到下一层D，I找到下一层D（已标记），G找到下一层H，E找到下一层H，（已标记），所以为：A→B→F→C→I→G→E→D→H

void BFS(AGraph *G, int v, int visit[maxSize])
{
    ArcNode *p;
    int que[maxSize], front = 0 , rear = 0;
    int j;
    Visit(v);
    Visit[v] = 1;
    rear = (rear+1)%maxSize;
    que[rear] = v;
    while( front != rear)
    {
        front = (front+1)%maxSize;
        j = que[front];
        p = G->adjlist[j]first;
        while( p != NULL)
        {
            if(visit[p->adjv] ==0)
            {
                visit[p->adjv];
                visit[p->adjv] = 1;
                rear = (rear + 1)%maxSize;
                que[rear] = p->adjv;
            }
            p = p->next;
        }
    }
}

GS2-660-C5-58~61

这章蛮难的，很多细节和方法以及固定的思维定势要在这一章形成。加油

恋词U14

• essence n.本质；实质；精髓
• outlook n.景色；观点；世界观；人生观；展望，前景
• ritual n.（宗教等的）意识；例行公事 adj.作为仪式一部分的；例行的
• sacred adj.神圣的；宗教性的；庄严的
• preach v.宣讲；竭力鼓吹；说教；
• dean n.（圣公会）教长；大学的学院院长；系主任；训导主任
• pilgrim n.朝圣者；
• resemble v.像；类似于
• analogous adj.相似的；类似的
• stereotype n.模式化观念；刻板印象 v.对..产生成见
• conceal v.隐藏；隐瞒；掩盖
• zeal n.热情；热枕
• affiliation n.联系；从属关系
• filter n.过滤器；筛选程序； v.过滤；筛选
• dedicate v.奉献；把..用在
• verdict n.（陪审团的）裁定；裁决；判决；定论
• fall short of 未达到；不符合
• shorthand n.速记
• superfluous adj.过剩的；多余的
• superficial adj.表面的；肤浅的；浅薄的
• constitute v.组成；构成；被视为
• substitute n.代替者；代替物；替补 v.用..代替；取代
• readiness n.愿意；乐意；准备就绪