目 录
1、题目
2、详细题解过程
1、邻接表
2、遍历(DFS、BFS)
2.1、邻接表-图示
2.2、 深度优先遍历序列-DFS
2.3、 广度优先遍历序列-BFS
2.4、标准答案
3、Prime最小生成树
1、题目
2、详细题解过程
1、邻接表
图的邻接表,不唯一,有多种写法。【拿A来说,就是A后面的三个链表的位置可以不同!】
2、遍历(DFS、BFS)
2.1、邻接表-图示
2.2、 深度优先遍历序列-DFS
深度优先搜索-DFS:先根遍历。例如:以a作为出发点,一个点一个点地遍历。
【A、B、C、D、F、E、G】【节点遍历顺序:A->B->C->D->F->E->F->G->F->D->C->B->A】
按照邻接表进行遍历。
2.3、 广度优先遍历序列-BFS
广度优先搜索-BFS: 一圈圈地搜索。
每一层的节点,如果可以往外延伸,就一定要延伸;每次延伸一个节点。
2.4、标准答案
3、Prime最小生成树
某国有7个城市 它们互相之间没有公路相通 因此交通十分不便。为解决这一“行路难”的问题 政府决定修建公路 经过调研 如果把这7个城市之间的关系看成一个图 字母代表城市名称 数字代表修路的花费。【详解】