第六章学习小结

超、凢脫俗 2022-01-06 09:19 258阅读 0赞

本章学习了图，图这种数据结构相对树的数据结构，又是复杂了许多，这一章图的作业是分别用深度搜索DFS和BFS广度搜索来输出非连通分量。抛开具体的存储结构，整个程序主要由三部分组成，主函数，调用DFS的函数，调用BFS的函数，循环多次调用广搜和深搜的函数，便可输出非连通图。

void DFS_AM(AMGraph &G,int v)
     {  //邻接矩阵的深度搜索 
     	for(int w=0;w<G.vexnum;w++)
     	if(G.arcs[v][w]!=0 && (!visited[w]) )
     	{
    	 visited[w]=true;     //每访问一个就要将其置为true 
    	 cout << w << " ";
         DFS_AM(G,w);
     }
    }

void BFS_AM(AMGraph &G,int v)
     {
         visited[v]=1;
         queue<int> q;
         int u;
         q.push(v);
        while(!q.empty())
         {
         u=q.front();
        q.pop();
         cout<< u << " ";
    
        for(int w=0;w<G.vexnum;w++)
        {
            if(G.arcs[u][w]!=0 && (!visited[w]))
            {
                visited[w]=1;
                q.push(w);
            }
        }
         }

在作业题我们可以看到，我采用的存储结构是邻接矩阵，因为在进行对矩阵的两个顶点的边进行初始化时双向边用数组操作较为方便，如果用链式存储，对于指针的操作时十分复杂的。

还有关于图的应用，经过老师上课的分析在对图的最小生成树，最短路径的应用中，我们需要掌握算法思想，以及需要用到的辅助结构，包括它们的初态和终态，这三个算法核心思想十分相似，这为我们以后的解题提供了新思路。

转载于:https://www.cnblogs.com/liusiling/p/10889637.html

发表评论取消回复

表情：

评论列表（有 0 条评论，258人围观）

还没有评论，来说两句吧...

相关阅读

相关第六章

1.目录管理的主要功能：按名存取；提高检索速度；文件共享；允许文件重名。 2.在索引节点中设置连接引用（links）计数的目的是为了实现目录管理的文件共享功能。 3.实现“

以你之姓@/ 2022年06月17日 03:46/ 0 赞/ 303 阅读

相关《JAVA编程思想(第四版)》第六章(访问权限控制)小结

控制对成员的访问权限有两个原因. 第一,为了使用户不要碰触那些他们不该碰触的部分,这些部分对于类内部的操作时必要的,但是他并不属于客户端程序员所需接口的一部分.因此,将方法和

迈不过友情╰/ 2022年05月18日 00:54/ 0 赞/ 179 阅读

相关第六章学习小结

本章学习了图，图这种数据结构相对树的数据结构，又是复杂了许多，这一章图的作业是分别用深度搜索DFS和BFS广度搜索来输出非连通分量。抛开具体的存储结构，整个程序主要由三部分组成

超、凢脫俗/ 2022年01月06日 09:19/ 0 赞/ 259 阅读

相关第四章学习小结

第四章学习了串和数组的相关内容，以及学习了BF算法和KMP算法。这周上机课老师带着我们打了AI核心代码。看到题目就觉得要求好多代码肯定很难写，听到老师说这道题目会有很多的边

小鱼儿/ 2021年12月24日 01:19/ 0 赞/ 247 阅读

相关 DS第六章学习小结

一、知识总结　　先上思维导图 ![1627752-20190519202112384-737552169.png][] 　　本章“图”可以说是树的延伸，所以说理解

以你之姓@/ 2021年12月17日 10:23/ 0 赞/ 266 阅读

相关第六章学习小结

题目：给定一个有N个顶点和E条边的无向图，请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时，假设我们总是从编号最小的顶点出发，按编号递增的顺序

骑猪看日落/ 2021年12月13日 20:29/ 0 赞/ 275 阅读

相关第七章学习小结

一、本章内容小结：本章主要学习了查找的基本概念以及对于基于不同的数据结构的各种查找表适用的查找方法的定义、查找及算法，其中主要包括3种不同结构的查找表：线性表、树表和散列表

布满荆棘的人生/ 2021年12月12日 16:41/ 0 赞/ 293 阅读

相关学习笔记5（第六章：字典）

1、在Python中，字典是一系列键-值对。每个键都与一个值相关联，可以使用键来访问与之相关联的值。与键相关联的值可以是数字、字符串、列表乃至字典。 2、字典用放在花括号\{

「爱情、让人受尽委屈。」/ 2021年11月29日 23:52/ 0 赞/ 287 阅读

相关 DS第5章学习小结

一、谈谈你对本章的学习心得，或者任选本章一道题目，谈谈你解决该题的心得体会　　谈谈我做　　第5章作业7-1 List Leaves　　的心得体会吧 ![1627872-2

拼搏现实的明天。/ 2021年11月22日 08:14/ 0 赞/ 279 阅读

相关第六章总结

第六章我们学习到的是图，一种比树还要复杂一点的数据结构。首先是图的定义：图G有两个集合V和E组成，记为G=（V,E），其中V是顶点的有穷非空集合，E为V中顶点偶对的有穷集

「爱情、让人受尽委屈。」/ 2021年11月01日 08:56/ 0 赞/ 413 阅读