C++知识点（四）

C++的输入输出总结

C++中的输入输出都是通过流来进行的.
C++把输入输出看作字节流,输入时从字节流中抽取字节,输出时把字节插入到字节流中.

使用cin进行输入

cin>>input,输入一个字符串,当遇到空白格、换行、制表之类的,输入都会停止.这里所谓的停止不是指停止键入,而是指停止从字节流中抽取字节.

cin.get()

cin的方法get()是专门用于单字符的输入.在有参数或者没有参数的情况下,get函数读取一个输入字符,不管这个字符空白、换行和制表都可以直接读进去.要注意get不会忽略换行符,所以要注意换行符被不小心读进去的情况.

cin.get()与cin.get(ch)的比较

注意使用cin.get(若干参数或者没有)，get()函数在遇到换行符读取完字符时并不会读取换行符或者是本来的默认分界符，而这些东西都只会留在原始流之内，

cin.get()可以给定参数,限定从流中提取的数目,以及碰到什么时候会结束.

char input[10]
char ch;
cin.get(input,10,'a');
cout << input << endl;
cin.get(ch);
cout<<ch<<endl;

//输入sdsdsda  
//输出sdsdsd
//a

(不丢弃,保留在流中)

getline()函数

与get函数不同,getline()函数会自动丢弃换行符等分界符.

char input[10]
char ch;
cin.getline(input,10,'a');
cout << input << endl;
cin.get(ch);
cout<<ch<<endl;
\\ 输入 sdsdsda  
\\输出sdsdsd

(丢弃,不保留在流中)

gets()

不能写为m=gets()

看cin与gets的区别

#include<iostream>
using namespace std;
int main()
{
      char str[20];
      cin>>str;
      cout<<str<<endl;
      return 0;


}
//输入：abc abc
//输出：abc

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
      char str[20];
      gets(str);
      cout<<str<<endl;
      return 0;
}
//输入：abc abc
//输出：abc abc

cin不接受空格、TAB、换行等的输入,但gets则接收这些输入.
gets可以无限读取,不会判断上线,以回车或EOF结束读取,并将读取的结果存放在buffer指针所指向的字符数组中.换行符不作为读取串的内容.

getchar()

getchar()是以字符为单位对输入的数据进行读取.
注意:
在控制台中通过键盘输入数据时，以回车键作为结束标志。当输入结束后，键盘输入的数据连同回车键一起被输入到输入缓冲区中。在程序中第一次调用getchar()函数从输入缓冲区中读取一个字节的数据。需要注意的是，如果此时在程序中第二次调用getchar()函数，因为此时输入缓冲区中还有回车键的数据没有被读出，第二个getchar()函数读出的是回车符。

char test1 = getchar();

char test2 = getchar();

此时在控制台中输入字符“a”并且按下回车键，test1的值是字符“a”，而test2的值是“\n”，如图1所示。

C++ Map

上面是Map接口的几个实现方式。

1. TreeMap是基于树（红黑树）的实现方式，即添加到一个有序列表，在O(log n)的复杂度内通过key值找到value，优点是空间要求低，但在时间上不如HashMap。C++中Map的实现就是基于这种方式
2. HashMap是基于HashCode的实现方式，在查找上要比TreeMap速度快，添加时也没有任何顺序，但空间复杂度高。C++ unordered_Map就是基于该种方式。
3. HashTable与HashMap类似，只是HashMap是线程不安全的，HashTable是线程安全的，现在很少使用

Hash map的原理

Hash map说白了就是数据结构里的哈希表.

哈希表最大的长处。就是把数据的存储和查找消耗的时间大大减少，差点儿能够看成是常数时间；而代价不过消耗比較多的内存。然而在当前可利用内存越来越多的情况下，用空间换时间的做法是值得的。另外，编码比較easy也是它的特点之中的一个。

其基本原理是：使用一个下标范围比較大的数组来存储元素。能够设计一个函数（哈希函数，也叫做散列函数），使得每个元素的keyword都与一个函数值（即数组下标，hash值）相相应，于是用这个数组单元来存储这个元素。也能够简单的理解为。依照keyword为每个元素“分类”，然后将这个元素存储在相应“类”所相应的地方，称为桶。

可是不可以保证每一个元素的keyword与函数值是一一相应的。因此极有可能出现对于不同的元素。却计算出了同样的函数值，这样就产生了“冲突”。换句话说，就是把不同的元素分在了同样的“类”之中。 总的来说。“直接定址”与“解决冲突”是哈希表的两大特点。

hash_map，首先分配一大片内存。形成很多桶。是利用hash函数，对key进行映射到不同区域（桶）进行保存。

其插入过程是：

1. 得到key
2. 通过hash函数得到hash值
3. 得到桶号(一般都为hash值对桶数求模)
4. 存放key和value在桶内。
   其取值过程是:
5. 得到key
6. 通过hash函数得到hash值
7. 得到桶号(一般都为hash值对桶数求模)
8. 比較桶的内部元素是否与key相等，若都不相等，则没有找到。
9. 取出相等的记录的value。

**hash_map中直接地址用hash函数生成，解决冲突，用比較函数解决。这里能够看出。假设每一个桶内部仅仅有一个元素，那么查找的时候仅仅有一次比較。当很多桶内没有值时，很多查询就会更快了(指查不到的时候).

由此可见，要实现哈希表, 和用户相关的是：hash函数和比較函数。这两个參数刚好是我们在使用hash_map时须要指定的參数。**

hash map的使用

hash_map类在头文件hash_map中，和全部其他的C++标准库一样。头文件没有扩展名。例如以下声明：

#include <hash_map>  
using namespace std;  
using namespace stdext;

hash_map是一个聚合类，它继承自_Hash类，包含一个vector。一个list和一个pair。当中vector用于保存桶，list用于进行冲突处理，pair用于保存key->value结构，简要地伪码例如以下：

class hash_map<class _ Tkey, class _ Tval>  
{  
private:  
    typedef pair<_ Tkey, _ Tval> hash_pair;  
    typedef list<hash_pair>    hash_list;  
    typedef vector<hash_list>  hash_table;  
};

hash_map和map的差别

1. 构造函数：hash_map需要hash函数(等于函数).map仅仅需要比较函数(小雨函数)

2. 存储结构.hash_map采用hash表存储,而map一般采用红黑树(RB Tree)实现.因此其memory数据结构是不一样的.

3. 什么时候须要用hash_map，什么时候须要用map?
   整体来说，hash_map 查找速度会比map快。并且查找速度基本和数据数据量大小，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n)小，hash还有hash函数的耗时。明确了吧，假设你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash_map可能会让你陷入尴尬。特别是当你的hash_map对象特别多时，你就更无法控制了，并且hash_map的构造速度较慢。

如今知道怎样选择了吗？权衡三个因素: 查找速度, 数据量, 内存使用。

恶心的double(也包括float)

对于浮点数问题,在计算机中并不能精确的表示浮点数.
用”==”来比较两个double应该相等的类型,返回的布尔型值是不确定的.同理,使用>和<判断也是同样的道理。
所以有些时候我们可以这么做
考虑一个常数epsilon,他来表示精度.
if(abs(x1-x2).想用一个map来存储double型值出现的次数.问题就出在map是用一个红黑树来实现的.进行map映射有点像是查找结点.但是这个结点的key是一个double型的,在查找的过程中需要进行比较,而double的比较就会出现上述问题,所以遍历打印的时候会出现重复的key.
同理如果用set也是一样会出现上述问题,set的目的是不希望有重复的value,这里的value是double型的,同样会因为精度问题而有重复的出现.

动态规划(Dynamic Programming)

动态规划求解的一般思路:
判断问题的子结构(也可看作状态),当具有最优子结构时,动态规划可能适用.
求解重叠子问题.一个递归算法不断地调用同一问题,递归可以转化为查表从而利用子问题地解.分治法则不同,每次递归产生新的问题.重新构造一个最优解.

动态规划要注意几个点：

1. 分析问题,构造状态转移方程
2. 空间换时间

例题1：硬币找零

假设有几种硬币，如1、3、5，并且数量无限。请找出能够组成某个数目的找零所使用最少的硬币数。

思路:
用待找零的数值k描述子结构/状态，记作sum[k]，其值为所需的最小硬币数。对于不同的硬币面值coin[0…n]，有sum[k] = min(sum[k-coin[0]] , sum[k-coin[1]], …)+1。对应于给定数目的找零total，需要求解sum[total]的值。

typedef struct {
    int nCoin; //使用硬币数量
    //以下两个成员是为了便于构造出求解过程的展示
    int lastSum;//上一个状态
    int addCoin;//从上一个状态达到当前状态所用的硬币种类
} state;

state *sum = malloc(sizeof(state)*(total+1));

//init
for(i=0;i<=total;i++)
    sum[i].nCoin = INF;
sum[0].nCoin = 0;
sum[0].lastSum = 0;

for(i=1;i<=total;i++)
    for(j=0;j<n;j++)
        if(i-coin[j]>=0 && sum[i-coin[j]].nCoin+1<sum[i].nCoin)
        {
            sum[i].nCoin = sum[i-coin[j]].nCoin+1;
            sum[i].lastSum = j;
            sum[i].addCoin = coin[j];
        }

    if(sum[total].nCoin == INF)
    {
        printf("can't make change.\n");
        return 0;
    }
    else
        //output
　　　　;

通过sum[total].lastSum和sum[total].addCoin，很容易通过循环逆序地或者编写递归调用的函数正序地输出从结束状态到开始状态使用的硬币种类。以下各题输出状态转换的方法同样，不再赘述。下面为了方便起见，有的题没有在构造子结构的解时记录状态转换，如果需要请类似地完成。

例题2 字符串相似度/编辑距离（edit distance）

对于序列S和T，它们之间距离定义为：对二者其一进行几次以下的操作(1)删去一个字符；(2)插入一个字符；(3)改变一个字符。每进行一次操作，计数增加1。将S和T变为同一个字符串的最小计数即为它们的距离。给出相应算法。

解法:
将S和T的长度分别记为len(S)和len(T)，并把S和T的距离记为m[len(S)][len(T)]，有以下几种情况：

1. 如果末尾字符相同，那么m[len(S)][len(T)]=m[len(S)-1][len(T)-1]；
2. 如果末尾字符不同，有以下处理方式:
   　　修改S或T末尾字符使其与另一个一致来完成,m[len(S)][len(T)]=m[len(S)-1][len(T)-1]+1；
   　　在S末尾插入T末尾的字符，比较S[1…len(S)]和S[1…len(T)-1]；
   　　在T末尾插入S末尾的字符，比较S[1…len(S)-1]和S[1…len(T)]；
   　　删除S末尾的字符，比较S[1…len(S)-1]和S[1…len(T)]；
   　　删除T末尾的字符，比较S[1…len(S)]和S[1…len(T)-1]；

总结为，对于i>0,j>0的状态(i,j),m[i][j] = min( m[i-1][j-1]+(s[i]==s[j])?0:1 , m[i-1][j]+1, m[i][j-1] +1)。

这里的重叠子结构是S[1…i]，T[1…j]。

#include<iostream>
#include<string>
using namespace std;
int L[1001][1001];//备份的二维数组
int a,b,c;
void LED(int m, int n, string x, string y)//生成最优解的函数
{
    for(int i=0;i<m+1;i++)
    {
        L[i][0] = i;
    }//当一个x字符串为0时，最小编辑距离为y字符串的长度
    for(int i=0;i<n+1;i++)
    {
        L[0][i] = i;
    }}//当一个y字符串为0时，最小编辑距离为x字符串的长度

    for(int i=1;i<m+1;i++)
    {
        for(int j=1;j<n+1;j++)
        {
            a = L[i-1][j] + 1;//case1：删掉X[i]
            b = L[i][j-1] + 1;//case2：添加X[i+1]
            c = L[i-1][j-1] + (x[i] == y[j] ? 0:1);
            //case3:改变x[i],其中若X[i]==y[i]则赋0，否则赋1
            L[i][j] = min(c,min(a,b));//L[i][j]为最小的一个
        }
    }

}


int main()
{
    int m,n;
    string x,y;
    while(cin >> m >> x)
    {
        cin >> n >> y;
        memset(L,0,sizeof(L));
//对x，y进行预处理，使得X[i]为字符串的第i个元素，使得算法易于理解。
        x = " "+x;
        y = " "+y;
        LED(m,n,x,y);
        cout << L[m][n] << endl;
    }
}

例题3 最长公共子序列

和2类似，对于X[1…m]和Y[1…n]，它们的任意一个lcs是Z[1…k]。
　　(1)如果X[m]=Y[n]，那么Z[k]=X[m]=Y[n],且Z[1…k-1]是X[1…m-1]和Y[1…n-1]的一个lcs；
　　(2)如果X[m]!=Y[n]，那么Z[k]!=X[m]时Z是X[1…m-1]和Y的一个lcs；
　　(3)如果X[m]!=Y[n]，那么Z[k]!=Y[n]时Z是X和Y[1…n-1]的一个lcs；
　　下面是《算法导论》上用伪码描述的lcs算法。其中c[i][j]记录当前lcs长度，b[i][j]记录到达该状态的上一个状态。

最长公共子序列
这篇博客里的图描述的已经很清晰了.
公共子序列并没有要求连续,而公共子串会要求连续.

例题4 最长公共子串

同样也可以采用上述的方法来做.不同的是创建数组的迭代公式不同,
如果X[i]=Y[j],则b[i][j]=b[i-1][j-1]+1
如果X[i]!=Y[j],则b[i][j]=0
因为往往我们认为X[i]与Y[j]的后缀存在公共子串,若X[i],Y[j]最后一个元素不能匹配,则在数组中置为0.

#include<iostream>
#include<string.h>
using namespace std;

//dp[i][j]:串(x1,x2,...,xi)与串(y1,y2,...,yj)，
//d[i][j]表示这两个串结与最长公共子串结尾相同时，最长公共子串的长度

//状态转移方程如下：
//若i=0或j=0，则dp[i][j] = 0
//否则：
//		若A[i]==B[j]，则dp[i][j] = dp[i-1][j-1] + 1
//		若A[i]!=B[j]，则dp[i][j] = 0


//用于打印的函数，后面才用到
void print_substring(string str, int end, int length)
{
	int start = end - length + 1;
	for(int k=start;k<=end;k++)
		cout << str[k];
	cout << endl;
}

int main()
{
	string A,B;
	cin >> A >> B;
	int x = A.length();
	int y = B.length();
	A = " " + A;//特殊处理一下，便于编程
	B = " " + B;

	//回忆一下dp[][]的含义？
	int ** dp = new int* [x+1];
	int i,j;
	for(i=0;i<=x;i++)
	{
		dp[i] = new int[y+1];
		for(j=0;j<=y;j++)
			dp[i][j] = 0;
	}


	//下面计算dp[i][j]的值并记录最大值
	int max_length = 0;
	for(i=1;i<=x;i++)
		for(j=1;j<=y;j++)
			if(A[i]==B[j])
			{
				dp[i][j] = dp[i-1][j-1] + 1;
				if(dp[i][j]>max_length)
					max_length = dp[i][j];
			}
			else
				dp[i][j] = 0;


	//LCS的长度已经知道了，下面是根据这个最大长度和dp[][]的值，
	//找到对应的 LCS具体子串， 注意：可能有多个
	int const arr_length = (x>y?x:y) + 1;
	int end_A[arr_length];	//记录LCS在字符串A中结束的位置
	int num_max_length = 0;	//记录LCS的个数

	for(i=1;i<=x;i++)
		for(j=1;j<=y;j++)
			if(dp[i][j] == max_length)
				end_A[num_max_length++] = i;

	cout << "the length of LCS(substring) is : " << max_length  << endl << " nums: " << num_max_length << endl << "they are (it is): " << endl;
	for(int k=0;k<num_max_length;k++)	//输出每个具体的子串
		print_substring(A, end_A[k], max_length);

	return 0;
}

例题5 最长递增子序列（Longest Increasing Subsequence,lis）

1. 解法一：转化为求最长公共子序列
   其实可以把 求最长递增子序列问题 转化为 求最长公共子序列的问题。

设数组 { 3， 5， 7， 1， 2， 8 } 为 A
对数组 A 排序，排序后的数组为 B = { 1， 2， 3， 5， 7， 8 }。
于是，求数组 A 的最长递增子序列，就是求数组 A 与数组 B 的最长公共子序列。

1. 解法二:动态规划法
   虽然解法一也是使用动态规划，但是与解法一不同的是，解法二不进行转化，而是直接在原问题上采用动态规划法。

设长度为N的数组为{a0，a1, a2, …an-1)，则假定以aj结尾的数组序列的最长递增子序列长度为L(j)，则L(j)={ max(L(i))+1, i<j且a[i]<a[j] }。也就是说，我们需要遍历在j之前的所有位置i(从0到j-1)，找出满足条件a[i]<a[j]的L(i)，求出max(L(i))+1即为L(j)的值。最后，我们遍历所有的L(j)（从0到N-1），找出最大值即为最大递增子序列。时间复杂度为O(N^2)。

例如给定的数组为{5，6，7，1，2，8}，则L(0)=1, L(1)=2, L(2)=3, L(3)=1, L(4)=2, L(5)=4。所以该数组最长递增子序列长度为4，序列为{5，6，7，8}。算法代码如下：

#include <iostream>  
using namespace std;  
#define len(a) (sizeof(a) / sizeof(a[0])) //数组长度  
int lis(int arr[], int len)  
{  
    int longest[len];  
    for (int i=0; i<len; i++)  
        longest[i] = 1;  

    for (int j=1; j<len; j++) {  
        for (int i=0; i<j; i++) {  
            if (arr[j]>arr[i] && longest[j]<longest[i]+1){ //注意longest[j]<longest[i]+1这个条件，不能省略。  
                longest[j] = longest[i] + 1; //计算以arr[j]结尾的序列的最长递增子序列长度  
            }  
        }  
    }  

    int max = 0;  
    for (int j=0; j<len; j++) {  
        cout << "longest[" << j << "]=" << longest[j] << endl;  
        if (longest[j] > max) max = longest[j];  //从longest[j]中找出最大值  
    }  
    return max;  
}  

int main()  
{  
    int arr[] = {1, 4, 5, 6, 2, 3, 8}; //测试数组  
    int ret = lis(arr, len(arr));  
    cout << "max increment substring len=" << ret << endl;  
    return 0;  
}

1. 解法三: 最长上升子序列nlogn算法
   假设存在一个序列d[1..9] = 2 1 5 3 6 4 8 9 7，可以看出来它的LIS长度为5。n
   下面一步一步试着找出它。
   我们定义一个序列B，然后令 i = 1 to 9 逐个考察这个序列。
   此外，我们用一个变量Len来记录现在最长算到多少了

首先，把d[1]有序地放到B里，令B[1] = 2，就是说当只有1一个数字2的时候，长度为1的LIS的最小末尾是2。这时Len=1

然后，把d[2]有序地放到B里，令B[1] = 1，就是说长度为1的LIS的最小末尾是1，d[1]=2已经没用了，很容易理解吧。这时Len=1

接着，d[3] = 5，d[3]>B[1]，所以令B[1+1]=B[2]=d[3]=5，就是说长度为2的LIS的最小末尾是5，很容易理解吧。这时候B[1..2] = 1, 5，Len＝2

再来，d[4] = 3，它正好加在1,5之间，放在1的位置显然不合适，因为1小于3，长度为1的LIS最小末尾应该是1，这样很容易推知，长度为2的LIS最小末尾是3，于是可以把5淘汰掉，这时候B[1..2] = 1, 3，Len = 2

继续，d[5] = 6，它在3后面，因为B[2] = 3, 而6在3后面，于是很容易可以推知B[3] = 6, 这时B[1..3] = 1, 3, 6，还是很容易理解吧？ Len = 3 了噢。

第6个, d[6] = 4，你看它在3和6之间，于是我们就可以把6替换掉，得到B[3] = 4。B[1..3] = 1, 3, 4， Len继续等于3

第7个, d[7] = 8，它很大，比4大，嗯。于是B[4] = 8。Len变成4了

第8个, d[8] = 9，得到B[5] = 9，嗯。Len继续增大，到5了。

最后一个, d[9] = 7，它在B[3] = 4和B[4] = 8之间，所以我们知道，最新的B[4] =7，B[1..5] = 1, 3, 4, 7, 9，Len = 5。

于是我们知道了LIS的长度为5。

!!!!! 注意。这个1,3,4,7,9不是LIS，它只是存储的对应长度LIS的最小末尾。有了这个末尾，我们就可以一个一个地插入数据。虽然最后一个d[9] = 7更新进去对于这组数据没有什么意义，但是如果后面再出现两个数字 8 和 9，那么就可以把8更新到d[5], 9更新到d[6]，得出LIS的长度为6。

然后应该发现一件事情了：在B中插入数据是有序的，而且是进行替换而不需要挪动——也就是说，我们可以使用二分查找，将每一个数字的插入时间优化到O(logN)~于是算法的时间复杂度就降低到了O(NlogN)～！

#define MAX 1000010
#define cmp(a,b) ((a)>(b))
int n,num[MAX],len_min[MAX];
int binary_search(int a,int b,int k)
{
 int mid;
 while(a<b)
 if(cmp(k,len_min[mid=(a+b)>>1])) a=mid+1;
 else b=mid;
 return a;
}
int LIS()
{
 int a=0,b=0,k;
 for(int i=0;i<n;i++)
 {
 if(len_min[k=binary_search(a,b-1,num[i])]>=num[i]) len_min[k]=num[i];
 else len_min[b++]=num[i];
 }
 return b;
}

algorithm 里的sort

一般需要排序的地方我都会用到algorithm里的sort

这里sort往往是针对序列容器类而言,比如vector,string,list,deque等.
往往的形式是
sort(A.begin(),A.end());
而有些时候我们需要变形排序方法.
则会定义一个排序判别函数:

bool cmp(A a,A b){
  return a>b;
}

则会返回从大到小排列.

这里要特别提一下map的排序.
由于map本身是由红黑树实现的,map本身就会按key排序.即在创建的过程中,map就已经排好了序
而这里我们要强调的是map按value的排序
但之前提过sort只能针对序列容器排序,而对map,set这种集合容器是不能排序的.
所以如果我们要对map按value进行sort要想办法将其转化为vector的形式.
这里用到了vector

//map数据按照值来排序
void MapSortOfValue(vector<pair<int,string> >& vec,map<string,int>& m)
{
    for (map<string, int>::iterator it = m.begin(); it != m.end(); it++)
        vec.push_back(make_pair(it->second, it->first));
    sort(vec.begin(), vec.end());
}

C++ pair

pair<T1, T2> p1;            //创建一个空的pair对象（使用默认构造），它的两个元素分别是T1和T2类型，采用值初始化。
pair<T1, T2> p1(v1, v2);    //创建一个pair对象，它的两个元素分别是T1和T2类型，其中first成员初始化为v1，second成员初始化为v2。
make_pair(v1, v2);          // 以v1和v2的值创建一个新的pair对象，其元素类型分别是v1和v2的类型。
p1 < p2;                    // 两个pair对象间的小于运算，其定义遵循字典次序：如 p1.first < p2.first 或者 !(p2.first < p1.first) && (p1.second < p2.second) 则返回true。
p1 == p2；                  // 如果两个对象的first和second依次相等，则这两个对象相等；该运算使用元素的==操作符。
p1.first;                   // 返回对象p1中名为first的公有数据成员
p1.second;                 // 返回对象p1中名为second的公有数据成员

可以利用make_pair创建新的pair对象：

atoi,atol,atof

注意这里string转数值,要用S.c_str()转成char型先.

1. atoi(): int atoi ( const char * str );
   说明：Parses the C string str interpreting its content as an integral number, which is returned as an int value.
   参数：str ： C string beginning with the representation of an integral number.
   返回值：1. 成功转换显示一个Int类型的值. 2. 不可转换的字符串返回0. 3.如果转换后缓冲区溢出,返回 INT_MAX orINT_MIN

2. aotl(): long int atol ( const char * str );
   说明：C string str interpreting its content as an integral number, which is returned as a long int value（用法和atoi函数类似，返回值为long int）

3. atof(): double atof ( const char * str );
   参数：C string beginning with the representation of a floating-point number.
   返回值：1. 转换成功返回doublel类型的值 2.不能转换，返回0.0。 3.越界，返回HUGE_VAL

将数值型转成string;
to_string(a);

BFS与DFS

BFS

BFS是图中的一种搜索算法,广度优先搜索算法.

如果从1开始进行搜索的话，BFS的步骤就是，先搜索所有和1相连的，也就是2和5被找到了，然后再从2开始搜索和他相连的，也就是3被找到了，然后从5搜，也就是4被找到了，然后从3开始搜索，4被找到了，但是4之前已经被5找到了，所以忽略掉就行。然后3开始搜索，忽略4所以啥都没搜到，然后从4开始，6被找到了。。。

BFS:

#include<iostream>
#include<queue>
#include<vector>
#include<string.h>
using namespace std;

int E[100][100]={0};
bool vis[100];
void BFS(int root){
    queue<int> Q;
    memset(vis,0,sizeof(vis));
    Q.push(root);
    vis[root]=true;
    while(!Q.empty()){
        int h=Q.front();
        cout<<"vis:"<<h<<endl;
        Q.pop();
        for(int i=0;i<100;i++){
            if(E[h][i]==1&&!vis[i]){
                Q.push(i);
                vis[i]=true;
            }
        }
    }
}


int main(){
    E[1][2]=1;
    E[2][1]=1;
    E[1][5]=1;
    E[5][1]=1;
    E[2][5]=1;
    E[5][2]=1;
    E[2][3]=1;
    E[3][2]=1;
    E[3][4]=1;
    E[4][3]=1;
    E[4][5]=1;
    E[5][4]=1;
    E[4][6]=1;
    E[6][4]=1;
    BFS(1);
}

这里用的存储矩阵比较麻烦,用的是二维数组的形式,有很多位置是没有用到的但是意思是一样的

m=[0 for i in range(10)]
E=[m.copy() for i in range(10)]#默认直接赋值就是对象的引用(别名)
def BFS(root):
    Q=[]
    Q.append(root)
    vis[root]=True
    while(len(Q)!=0):
        h=Q[0]
        Q.pop(0)
        print(h)
        for i in range(10):

            if(E[h][i]==1 and vis[i]==False):
                Q.append(i)
                vis[i]=True
if __name__=="__main__":
  E[1][2]=1
  E[2][1]=1
  E[1][5]=1
  E[5][1]=1
  E[2][5]=1
  E[5][2]=1
  E[2][3]=1
  E[3][2]=1
  E[3][4]=1
  E[4][3]=1
  E[4][5]=1
  E[5][4]=1
  E[4][6]=1
  E[6][4]=1
  vis=[False for i in range(100)]
  BFS(1)

这里要注意的就是那个copy

1. 直接赋值:就是对象的引用(别名)
2. 浅拷贝(copy):拷贝父对象,不会拷贝对象的内部的子对象
3. 深拷贝(deepcopy):copy模块的deepcopy,直接拷贝父对象及其子对象

例如：
a={1:[1,2,3]}

1. b=a:赋值引用,a和b都指向同一个对象,如下图:
   
2. b=a.copy():浅拷贝,a和b是一个独立的对象,但它们的子对象还是指向统一对象(是引用),如下图:
   
3. b=copy.deepcopy(a):需要导入copy模块,深度拷贝,a和b完全拷贝了父对象及其子对象,两者是完全独立的,如下图：
   
   总结：
   1、赋值：简单地拷贝对象的引用，两个对象的id相同。
   2、浅拷贝：创建一个新的组合对象，这个新对象与原对象共享内存中的子对象。
   3、深拷贝：创建一个新的组合对象，同时递归地拷贝所有子对象，新的组合对象与原对象没有任何关联。虽然实际上会共享不可变的子对象，但不影响它们的相互独立性。

   DFS

   DFS 就是像走迷宫一样一条路走到头直到走不通才回到前一个换一条路
   DFS需要一个栈,每次都是搜到之后不停的往下搜，符合先进后出。但是一般来说不用栈，而是直接通过函数的递归就行了。

   #include<iostream>
   #include<queue>
   #include<vector>
   #include<stack>
   #include<string.h>
   using namespace std;
   int E[100][100]={0};
   bool vis[100];
   void DFS(int root){
       int h=root;
       vis[root]=true;
       cout<<"vis:"<<root<<endl;
       for(int i=0;i<100;i++){
           if(E[root][i]==1&&vis[i]==false){
               DFS(i);
           }
       }
   }
   int main(){
       E[1][2]=1;
       E[2][1]=1;
       E[1][5]=1;
       E[5][1]=1;
       E[2][5]=1;
       E[5][2]=1;
       E[2][3]=1;
       E[3][2]=1;
       E[3][4]=1;
       E[4][3]=1;
       E[4][5]=1;
       E[5][4]=1;
       E[4][6]=1;
       E[6][4]=1;
       memset(vis,0,sizeof(vis));
       DFS(1);
   }

def DFS(root):
    h=root
    vis[h]=True
    print(root)
    for i in range(10):
        if E[h][i]==1 and vis[i]==False:
            DFS(i)

if __main__=="__main__":
  m=[0 for i in range(10)]
  E=[m.copy() for i in range(10)]
  E[1][2]=1
  E[2][1]=1
  E[1][5]=1
  E[5][1]=1
  E[2][5]=1
  E[5][2]=1
  E[2][3]=1
  E[3][2]=1
  E[3][4]=1
  E[4][3]=1
  E[4][5]=1
  E[5][4]=1
  E[4][6]=1
  E[6][4]=1
  vis=[False for i in range(100)]
  DFS(1)

总结

DFS和BFS主要是运用于对于图和树的搜索，但是绝大部分问题模型都是可以建模变成一个图或者树的，所以差不多不少问题都会涉及到这两个。

参考文献

1. https://cloud.tencent.com/developer/article/1086657