img
不明白深度优先生成树 然后是先找出权重最大的边 接下来就不懂了
构成最小生成树需要4条边
1-3
1-2
0-5
4-5
有用望采纳：
首先，我们可以根据给定的图形和权重构建一个邻接矩阵表示图形。
0 1 2 3 4 5
-----------------------
0 | 0 10 0 20 0 2
1 |10 0 3 5 0 0
2 | 0 3 0 0 15 0
3 |20 5 0 0 11 10
4 | 0 0 15 11 0 0
5 | 2 0 0 10 0 0
接下来，我们可以使用深度优先遍历算法来生成深度优先生成树。从顶点0开始，我们逐个访问相邻顶点，并标记已经访问的顶点和边，直到所有的顶点都被访问过。
下面是深度优先生成树的推导过程：
以下是深度优先生成树的结果：
0-5-3-4-2-1
接下来，我们可以使用最小生成树算法来构建最小生成树。常用的最小生成树算法有Prim算法和Kruskal算法。此处使用Prim算法来构建最小生成树。
以下是Prim算法的推导过程：
以下是最小生成树的结果：
0-5-3-4-2-1
最小生成树的权重为：
2+10+11+15+3 = 41
所以，深度优先生成树为0-5-3-4-2-1，最小生成树为0-5-3-4-2-1，权重为41。
目录
图的遍历
层序(宽度优先)遍历：
深度优先遍历：（逮着一条路走到黑）
题目举例：
深度遍历：
宽度遍历：
拓扑排序算法：
题目举例：
方法1：（一个节点的指向节点处理完之后将该节点放入栈中，也就是越早的节点放在栈顶）
方法2：（寻找入度为0的入队列，弹出，将弹出的节点的影响消除，再选择新的入度为0的入队列）
针对无向图的算法：
生成最小生成树（保证连通性且权值最小）
1：kruskal（K算法）
2：prim算法
3：Dijkstra算法
图的遍历
层序(宽度优先)遍历：
建立队列和一张hashset，
从一个点开始，将点放在队列里面和哈希表中。
将该点从队列中处理弹出。
选择与此点联通的点检查这些点在哈希表中是否被记录过，将没有被记录过的联通点都放在队列和哈希表中。（建立哈希表的目的就在于避免重复处理）
弹出队列top的点并重复处理（检查，放入，弹出~~~~）
深度优先遍历：（逮着一条路走到黑）
使用栈和hashset实现：（先处理后弹出）
建立栈和一张hashset，
从一个点开始，将点处理后放在栈里面和哈希表中。
将该点从队列中弹出。
加入当前front节点A有B，C，D三个邻接点，首先判断B是否在hashset里面，如果不在将A节点和B节点依次压到栈里面，如果B在hashset里面，则判断依次C，D，只要判断了一个结点满足条件就break出来，不再探索其余的邻接点。
弹出B，B的邻接点一定有A，但正是因为hashset的原因，不会重复处理A节点。
因为每一次都是压入源节点和邻接点，所以栈里面存走过的节点。如果还发现又没走过的节点，栈就增长，如果所有的节点都走完了，那么就会一直弹出直到栈空。
题目举例：
547. 省份数量 - 力扣（LeetCode） (leetcode-cn.com)
https://leetcode-cn.com/problems/number-of-provinces/
深度遍历：
class Solution {
public:
void bianli(vector<vector<int>>& isConnected,unordered_set<int>&hashset,int i){
hashset.insert(i);
for(int j=0;j<isConnected.size();j++){
if(isConnected[i][j]!=0&&hashset.count(j)==0) {
bianli(isConnected,hashset,j);
}
}
}
int findCircleNum(vector<vector<int>>& isConnected) {
int result=0;
int len=isConnected.size();
unordered_set<int>hashset;
for(int i=0;i<len;i++){
if(hashset.count(i)!=0){continue;}
hashset.insert(i);
result++;
for(int j=0;j<len;j++){
if(i==j){continue;}
if(hashset.count(j)==0&&isConnected[i][j]!=0){
bianli(isConnected,hashset,j);
//cout<<hashset.count(j)<<endl;
}
}
}
return result;
}
};
一条路走到黑
一个一个城市的处理，如果该城市没被处理过，看看哪个跟他有关系且没被处理过，逮住一个就往死里遍历，直到深度遍历的城市的邻居都是被处理过了的就返回。然后再返回去处理其余的。
宽度遍历：
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int len=isConnected.size();
int result=0;
queue<int>q;
vector<int>remember(len);
for(int i=0;i<len;i++){
if(remember[i]==0)
{
q.push(i);remember[i]=1;
while(!q.empty()){
int xi=q.front();
q.pop();
for(int j=0;j<len;j++){
if(isConnected[xi][j]!=0&&remember[j]==0&&j!=xi){q.push(j);}//将第j行的没有被记录过的元素压入队列中
}
remember[xi]=1;
}
result++;
}
}
return result;
}
};
通过广度优先搜索的方法得到省份的总数。对于每个城市，如果该城市尚未被访问过，则从该城市开始广度优先搜索，直到同一个连通分量中的所有城市都被访问到，即可得到一个省份。
也就是说在第一层for循环里，如果这一城市没有被处理过，那么这一城市代表的是一个全新的省份，这一次循环就要连根拔起的处理完所有和该城市有关系的城市。
处理的过程中用宽度遍历的方法，也就是将与该城市有联系的只要没处理过的都先一个一个压入队列，然后不断弹出并将弹出的城市的有关系城市且没被处理过的压入队列······
处理完之后将省份数量+1。
拓扑排序算法：
大概就是调用的意思，排序中靠前的点表示先左做，只有先做了这个点才能做后面的点，比如上图只有先做了A才能做B，A和B都做了才能做C，CB都做了才能做D。所以上图的拓扑排序表示为A，B，C，D。
前提不能有环
题目举例：
207. 课程表 - 力扣（LeetCode） (leetcode-cn.com)
https://leetcode-cn.com/problems/course-schedule/
方法1：（一个节点的指向节点处理完之后将该节点放入栈中，也就是越早的节点放在栈顶）
class Solution {//拓扑排序
public:
void bianli(vector<vector<int>>&xi,int i,vector<int>&remember,int numCourses,stack<int>&p,bool &result){
remember[i]=1;
for(int j=0;j<numCourses;j++){
if(xi[i][j]!=0&&remember[j]==1){result=false;return;}
if(xi[i][j]!=0&&remember[j]==0){
bianli(xi,j,remember,numCourses,p,result);
}
}
remember[i]=2;
p.push(i);
return;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>>xi(numCourses,vector<int>(numCourses));
vector<int>remember(numCourses);
for(int i=0;i<prerequisites.size();i++){
xi[prerequisites[i][1]][prerequisites[i][0]]=1;
}//建立二维向量，其中xi[a][b]=1表示a是b的先修课程
stack<int>p;
bool result=true;
for(int i=0;i<numCourses;i++){
bianli(xi,i,remember,numCourses,p,result);cout<<" "<<i<<" "<<remember[i]<<endl;
if(result==false){break;}
}
return result;
}
};
拓扑排序成立的前提是不存在环结构。
对于该题来说，返回true的前提是不存在环结构，
设置三种状态：未查询，查询中，已查询。
一旦发现a是b的先修课程，这时候查询b的后续课程发现b是c的先修课程，但是c处于“查询中”也就是c是a的先修课程，这样判断就存在环，也就可以返回false。
方法2：（寻找入度为0的入队列，弹出，将弹出的节点的影响消除，再选择新的入度为0的入队列）
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>>xi(numCourses,vector<int>(numCourses));
vector<int>inedges(numCourses);
queue<int>p;
unordered_set<int>hashset;
//int nums=0;//用nums表示处理了多少个课程了，如果有环，那么循环判断之后总有剩下的就是环。
for(int i=0;i<prerequisites.size();i++){
xi[prerequisites[i][1]][prerequisites[i][0]]=1;
inedges[prerequisites[i][0]]++;
}//建立二维向量，其中xi[a][b]=1表示a是b的先修课程
for(int i=0;i<numCourses;i++){
if(inedges[i]==0){
p.push(i);
hashset.insert(i);
}
}//首先将所有入度为0的节点放入队列
while(!p.empty()){
int x=p.front();
p.pop();
for(int i=0;i<numCourses;i++){
if(xi[x][i]==1){inedges[i]--;}
if(inedges[i]==0&&hashset.count(i)==0){p.push(i);hashset.insert(i);}
}//将对应的行不为0的对应列入度减1，同时边选择新的入度为0的放入队列。
}
return hashset.size()==numCourses;
}
};
首先选择入度为0的结点A，然后将A及其影响（A的出度边）擦掉，
然后再选择入度为0的点B，然后将B及其影响（B的出度边）擦掉，
......
直到处理完。
我们使用一个队列来进行广度优先搜索。初始时，所有入度为0的节点都被放入队列中，它们就是可以作为拓扑排序最前面的节点，并且它们之间的相对顺序是无关紧要的。
在广度优先搜索的每一步中，我们取出队首的节点u：
我们将u放入答案中；
移除u的所有出边，也就是将u的所有相邻节点的入度减少1。如果某个相邻节点v的入度变为0，那么我们就将v放入队列中。
在广度优先搜索的过程结束后。如果处理了在答案里的节点个数等于节点总数，那么我们就找到了一种拓扑排序，否则说明图中存在环，也就不存在拓扑排序了。
针对无向图的算法：
生成最小生成树（保证连通性且权值最小）
1：kruskal（K算法）
不断选择最小的边，考虑加上会不形成环，如果加上不会形成环，那么就加上否则抛弃并判断下一个。
重点：如何判断有没有环
初始将每个节点看成一个单一的集合，在选择边的过程中查询边的两个点是否在一个集合里，如果不在一个集合里证明添加上这条边不会产生环。然后将变得两个点的集合合并。
2：prim算法
从一个选定的点出发，选择与其邻接的边中最小的，添加点进集合，选择与集合邻接的边中最小的
添加，选择......
3：Dijkstra算法
Dijkstra算法算是贪心思想实现的，首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的，所谓的松弛操作就是，遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。