这一章我们学习了图的类型定义，存储结构，遍历及应用。下图是我对本章所学知识的大致总结。

 

 

其中重点便是DFS算法和BFS算法，从PTA作业题和实践题都有体现。

DFS算法类似于树的先序遍历：

bool visited [MVNum] ; ／／访问标志数组， 其初值为 "false"
void DFS(Graph G,int v) 
｛//从第 v 个顶点出发递归地深度优先遍历图G
   cout<<v;visited[v)=true; ／／访问第 v 个顶点， 并置访问标志数组相应分量值为 true
   for(w=FirstAdjVex(G,v);w>=O;w=NextAdjVex(G,v,w)) //依次检查 v 的所有邻接点 w , FirstAdjVex (G, v)表示 v 的第一个邻接点
if(!visited[w]) DFS(G,w);//对 v 的尚未访问的邻接顶点 w 递归调用 DFS
}

BFS算法类似于树的层次遍历：

void BFS{Graph G,int v) 
｛//按广度优先非递归遍历连通图G
  cout<<v;visited[v]=true;//访问第v个顶点，并置访问标志数组相应分量值为true
  InitQueue{Q); //辅助队列Q初始化， 置空
  EnQueue{Q,v); //v进队
  while ( ! QueueEmpty (Q)) // 队列非空
  {
    DeQueue (Q, u); / /队头元素出队并置为u
    for(w=FirstAdjVex(G,u);w>=O;w=NextAdjVex(G,u,w)) 
    //依次检查u的所有邻接点w, FirstAdjVex(G,u)表示u的第一个邻接点
    //NextAdjVex(G,u,w)表示u相对于w的下一个邻接点，w>=0表示存在邻接点
       if (!visited [w]) ///w为u的尚未访问的邻接顶点
       {
           cout<<w; visited[w]=true; ／／访问 w, 并置访问标志数组相应分扯值为true
           EnQueue{Q,v); //w进队
        }
  }
}

需要注意的是BFS算法用到了队列。

 

作业思考：

1.P 是顶点 S 到 T 的最短路径，如果该图中的所有路径的权值都加 1，P 仍然是 S 到 T 的最短路径。

这题较具迷惑性，在脑海中对图像并不清晰的时候容易误选。分析：假如说最短路径上一共有10条边，而另一条路径虽然比最短路径长，但它只有一条边，如果全加1，就会导致边少的路径成为新的最短路径。

 

2.拯救007这道代码题对我来说难度也是较大的，且难于分析方面。因为题目中鳄鱼坐标所构成的顶点之间的边是题目没有给的，而需要自己去判断，所以我一开始的想法是在用邻接矩阵把坐标信息全部接收的同时将将相应顶点之间的边连接起来，但是由于不知道边数，这种想法还是较难操作，在学习了网上的代码思路后，我不得不赞叹人家的思维，简洁又清晰。

博文连接：https://www.cnblogs.com/X-Do-Better/p/9048604.html

作者解题思路：

我们要写出主体函数Save007，Save007应包括FirstJump，DFS，IsSafe，Jump

判断要点：

    ①湖是一个正方形，边长为100，中心在(0,0)四个定点分别为(50,50),(50,-50),(-50,-50),(-50,50)，湖中小岛直径是15，半径7.5.如果007步长d大于50-7.5=42.5，就可以直接从小岛直接跳到湖岸

    ②判断007能否从岛上跳到湖中某一点A(x, y)，即d+7.5>=sqrt(x*x+y*y);也就是(d+7.5)*(d+7.5)>=x*x+y*y;（FirstJump函数）

    ③判断007能否从A点直接跳到湖岸，当007步长大于A点到湖岸的距离时，说明可以到达换，即d>= 50-| x | 或者d>= 50-| y |;（IsSafe函数）

    ④如果跳上一点不能直接跳到湖岸，那就跳上另一点看能不能跳到湖岸满足③条件，这里就是判断能否从A(x1,y1)点跳到B(x2,y2)点，如果007的步长d>=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)),即d*d >= (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)。如果满足，说明可以从A点跳到B点，否则不行。（Jump+DFS函数）如果不行，就继续递归尝试另一个B点，如果此路不通，返回②条件，换一条路，换一个起点A继续尝试，如果所有路都无法到达对岸，说明无法逃生。

 

学习心得：在学习过程中我感觉理解相对容易，但是在做题时却总是想不起来如何合理运用所学知识，这也是我的基本功不扎实的表现，所以在接下来的学习中，我还是要尽量回顾以往知识内容，多积累做题经验，多用思维导图的方式让自己对每章的内容都有个大致的印象。