《数据结构》复习参考2

《《数据结构》复习参考2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《数据结构》复习参考图篇（上）PS：额，本来应该接着上一篇《树与二叉树篇（上）》往下写，但老师讲得太急了，完全跟不上，囧。。。图十分重要，这毋庸置疑。关于图，最重要的两个算法就是BFS（宽度优先搜索）和DFS(深度优先搜索)。一切有关图的深层次问题和应用，都是基于这两个算法。因此，咱老师在课堂上强调多次，也不为过。【重难点提要】（知识要点会在《图篇（中）》中给出）1.图的存储结构——邻接矩阵与邻接表邻接矩阵好理解，咱们在离散数学课上就学的是用邻接矩阵来表示一个图。关于邻接矩阵，只需要提一个关键点：一个图的邻接矩阵表示是惟一的，且无向图的邻接矩阵一定是一个对称矩阵。邻接表其实是图的一种链

2、式存储结构：对图中的每个顶点i（0<=i<=n-1）建立一个单链表，把与顶点i相邻接的顶点放在该单链表中。关于邻接表，需要提到的有：1）一个图的邻接表表示不唯一；2）对于有n个顶点和e条边的无向图，其邻接表有n个顶点表节点和2e个边表结点（额，每条边所对应的顶点是两个）；3）在总边数小于n(n-1)/2的情况下，邻接表比邻接矩阵要节省空间（其实这个真不是绝对。老师的话很有道理，在图本身看上去不是很稀疏时，用邻接矩阵并不一定就比邻接表差劲，只是相对而言，邻接表更节省空间罢了）。2.（重中之重）图的遍历——BFS和DFS额，图的遍历是什么？从给定图G中任意指定的顶点（后来变成了生成树的根）

3、出发，按照某种搜索方法沿着图的边访问图中所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。两种方法——BFS和DFS。老师上课已经将原理讲得很明白了,不作赘述，后面的例题中会用到这两种看似朴素的算法。3.应用应用部分老师还没讲完，重要的应用有最小生成树问题、最短路径问题、拓扑排序、关键路径（AOE（囧。。。）网）问题。其中路径问题是关键，在后面的例题中会提到。【参考例题】例1（10年全国考研）若无向图G（V，E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（）。A.6B.15C.16D.21【解析】对于一个具有n个顶点的无向图，当其中n-1个顶点构成一个完全

4、图时，再加上任一条边必然构成连通图，所以最少边数=(n-1)(n-2)/2+1=16。选C。【吐槽】离散的老问题了，包一层皮又来数据结构里忽悠咱了。。。想到连通图与完全图的关系是关键。例2设A为有向图的0-1邻接矩阵，定义A1=A，An=An-1*A(n>1),则An[i,j]等于（）。A.顶点i到顶点j的距离B.顶点i到顶点j的长度为n的路径数目C.顶点i到顶点j的长度为n的路径数目-1D.顶点i到顶点j的长度为n的路径数目+1【解析】B【吐槽】仍然是离散的老问题。不过，在路径问题中，邻接矩阵显然比邻接表占优势。例3假设一个连通图采取邻接表作为存储结构，设计一个算法，判断其中是否存在

5、回路。【解】采用深度优先遍历算法，从顶点v出发，对每个访问的顶点w作标记（visited[w]=1）。若顶点w(先访问)和i(后访问）均已被访问过，表示从顶点w到顶点i存在一条路径。当从顶点i出发遍历时，发现顶点i到顶点w有一条边时，表示存在一个回路（该回路上包含顶点w和i），算法Cycle（G，v,has）从顶点v出发判断图G中是否存在回路，has是布尔值，初始调用置为false，执行后若为true表示有回路，否则表示图G中没有回路。对应的算法如下：voidCycle(AGraph*G,intv,bool&has){//调用时has置初值falseArcNode*p;inti;vis

6、ited[v]=1;//置已访问标记p=G->adjlist[v].firstarc;//p指向顶点v的第一个邻接点while(p!=NULL){i=p->adjvex;if(visited[i]==0)//若顶点i未访问，递归访问它Cycle(G,i,has);else//又找到了已访问的顶点说明有回路has=true;p=p->nextarc;//找下一个邻接点}}例4假设图G采用邻接表存储，设计一个算法，求不带权无向连通图G中距离顶点v的最远的一个顶点。【解析】图G是不带权的无向连通图，一条边的长度计为1.因此，求距离顶点v的最远顶点，即求距离顶点v的边数最多的顶点。利用广度优先

7、遍历算法，从v出发进行广度遍历，类似于从顶点v出发一层一层向外扩展，到达顶点j,…，最后到达的一个顶点v即为距离v最远的顶点。遍历时利用队列逐层暂存各个顶点，最后出队的一个顶点k即为所求。对应的算法如下：intMaxdist(AGraph*G,intv){ArcNode*p;intQu(MAXV);intfront=0,rear=0;intvisited(MAXV);inti,j,k;for(inti=0;in;i++)visited[