今天刷到了leetcode的547题也就是每日一题，昨天的除法真的好难，连续两天每日一题出了图论的题着实让我意外,图论的题首先就想DFS，BFS或者并查集（虽然我不咋会)。这个题不例外。


应该是找连通分量的意思，特点是一个独立的点也算一个连通分量。比如例1:1与2是相联的，算一个连通分量，点3是单独的算一个连通分量所以连通分量数为2，例2三个点均没有交点所以连通分量为3。再举一个例子:
如图:

只有一个连通分量所以最后得到的输出为1。分析到此就很明显了其实就是一个DFS解决。
题外话总结一下DFS和BFS，DFS相当于树的前序遍历可以用递归实现当然非递归形式可以用栈实现，BFS相当于树的层次遍历，需要用到队列。同样的老规矩来个例子:

如果从节点1出发使用DFS遍历(序列不唯一)，可以为1->2->4->3->5，如果使用BFS(序列不唯一)，可以为1->2->3->4->5。
接下来来具体实现一下(存储结构使用临接矩阵，当然也可以用临接表)。
以下均使用C++实现
建立一个头文件(Graph_Define_Matrix.h)里面给出图的定义

//临接矩阵定义
#pragma once
#ifndef _GRAPH_CREATE_
#define _GRAPH_CREATE
//顶点
typedef char VertexType;
//边
typedef float EdgeType;
//最大边数
#define MAXVEX 100
//没有连线
#define INFINITY 65535
//临接矩阵
typedef struct {
    //顶点表
    VertexType vertex[MAXVEX];
    //边表
    EdgeType edge[MAXVEX][MAXVEX];
    //边的数量和顶点的数量
    int  numVertex;
    int numEdge;
}MGraph;
#endif // !_GRAPH_CREATE_

再强调一下这个65535指的是两点间没距离。
以下为建立有向图的代码
引入头文件

#include<iostream>
#include"Graph_Define_Matrix.h"
#include<queue>
using namespace std;

然后建图:

//有向图
MGraph CreateGraph_Direction() {
    //cout << "请输入您要建立的图的边数和顶点数:" << endl;
    MGraph mGraph;
    cout << "请输入您要建立的图的顶点数:" << endl;
    cin >> mGraph.numVertex;
    cout << "请输入您要建立的图的边数:" << endl;
    cin >> mGraph.numEdge;
    cout << "请输入顶点:" << endl;
    //char
    VertexType vertex;
    for (int i = 0;i < mGraph.numVertex;i++) {
        cin >> vertex;
        mGraph.vertex[i] = vertex;
    }

    //初始化边表
    for (int i = 0;i < mGraph.numVertex;i++) {
        for (int j = 0;j < mGraph.numVertex;j++) {
            if (i == j) {
                mGraph.edge[i][j] = 0;
            }
            else
            {
                mGraph.edge[i][j] = INFINITY;
            }
        }
    }
    //char
    int vertex1, vertex2;
    //边的权值
    EdgeType weight;
    //输入边
    for (int i = 0;i < mGraph.numEdge;i++) {
        cout << "输入两个顶点及其权值:" << endl;
        cin >> vertex1 >> vertex2 >> weight;
        mGraph.edge[vertex1][vertex2] = weight;
    }
    return mGraph;
}

建立我刚刚举例子的那个图，如果有距离距离就设置为1，当然权值可以用户自定,先可以自己画出临接矩阵进行验证:

为了验证正确性，我们再写一个打印函数，来正确结果

void ReadGraph(MGraph mGraph) {
    cout << "输出图:" << endl;
    for (int i = 0;i < mGraph.numVertex;i++) {
        for (int j = 0;j < mGraph.numVertex;j++) {
            cout << "点" << mGraph.vertex[i] << "->点" << mGraph.vertex[j] << "距离为:" << mGraph.edge[i][j]<<endl;
        }
    }
}

主函数运行

运行结果如下:

以下为遍历操作:
1.BFS（广度优先遍历）
借助队列例子从1出发(那两根横线为队列):
第一步:

第二步:

1出队，与1相连的2和3入队
第三步:

2出队，与2相连的4入队
第四步:

3出队与3相连的5入队
第五步:
最后4,5出队
得到序列为1 2 3 4 5
具体代码如下(visit数组很重要)

//广度优先遍历--从a出发
void BFS(MGraph mGraph) {
    //判断是否被访问过
    bool visit[MAXVEX];
    for (int i = 0;i < mGraph.numVertex;i++) {
      //均初始置为未访问
        visit[i] = false;
    }
    cout << "使用广度优先遍历遍历此图得到的点的顺序为:" << endl;
    //初始化一个队列——BFS依赖于队列
    queue<VertexType>line;
    for (int i = 0;i < mGraph.numVertex;i++) {
        //从未访问过
        if (visit[i]==false) {
            //置为真
            visit[i] =true;
            cout << mGraph.vertex[i] << "->";
            line.push(mGraph.vertex[i]);
            //当队列不为空时
            while (!line.empty())
            {
                //得到对头元素
                VertexType note = line.front();
                line.pop();
                //有顶点和此顶点相连
                for (int j = 0;j < mGraph.numVertex;j++) {
                    //表示之间有边还要注意这个节点要没访问过
                    /*
                    重要的事说三遍没访问过没访问过没访问过
                    */
                    if (mGraph.edge[i][j] != 0 && mGraph.edge[i][j] != 65535&&visit[j]==false) {
                      //访问此节点
                        visit[j] = true;
                        cout << mGraph.vertex[j] << "->";
                        //入队
                        line.push(mGraph.vertex[j]);
                    }
                }
            }
        }
    }
}

运行代码得到的结果为:

2.DFS（深度优先遍历）
废话不多说，直接上代码:

bool visit1[MAXVEX];
//深度优先递归,可控制从第几个顶点开始
void DFS(MGraph mGraph,int begin) {
    //判断数组
    //bool visit[MAXVEX];
    visit1[begin] = true;
    //访问相邻节点
    int next;
    cout << mGraph.vertex[begin] << "->";
    //访问相邻节点
    /*
    重要的事说三遍这个节点没有被访问过
    */
    for (next = 0;next < mGraph.numVertex;next++) {
        if (mGraph.edge[begin][next] != 0 && mGraph.edge[begin][next] != 65535&&visit1[next]==false) {
            DFS(mGraph, next);
        }
    }
}

有递归知识的理解这个代码应该不难，我们控制从第一个顶点开始遍历

运行结果如下:

说了这么多再回到题目，其实就是一个DFS的问题，直接解决:

void DFS(vector<vector<int>>& isConnected, vector<int>& visit, int i) {
        int Nums = isConnected.size();
        //vector<int>visit(Nums);
        for (int j = 0;j < Nums;j++) {
            if (isConnected[i][j] == 1 && !visit[j]) {
                //置为访问过
                visit[j] = 1;
                DFS(isConnected, visit, j);
            }
        }
    }
    //DFS
    int findCircleNum(vector<vector<int>>& isConnected) {
        int Num = isConnected.size();
        //Num个0
        vector<int>visit(Num);
        int count = 0;
        for (int i = 0;i < Num;i++) {
            if (!visit[i]) {
                DFS(isConnected, visit, i);
                count++;
            }
        }
        return count;
    }

这个题临接矩阵对角线元素为1，没有交点则为0。
以题中给的例子

主函数如下:

运行结果如下:

提交:

水平实在有限，希望大佬勿喷。
最后说明一下，我遇到的一个问题，在使用C++ STL库的vector时，当vector出现在函数的形参时一定要加&,比如

个人的理解是不加的话这个visit就是一个常量，再递归的时候每次调用DFS，这个visit数组是会变得而如果不加&就会使visit不变，得到的最后结果count就恒等于图的结点数。我也在这里纠结了很久。
以上只是个人观点，本人水平也有限，可能会有出错的地方，请大佬指正。