Data Structure堆Tree并查集图论
堆
堆这种数据结构的应用很广泛，比较常用的就是优先队列。普通的队列就是先进先出，后进后出。优先队列就不太一样，出队顺序和入队顺序没有关系，只和这个队列的优先级相关，比如去医院看病，你来的早不一定是先看你，因为病情严重的病人可能需要优先接受治疗，这就和时间顺序没有必然联系。优先队列最频繁的应用就是操作系统，操作系统的执行是划分成一个一个的时间片的，每一次在时间片里面的执行的任务是选择优先级最高的队列，如果一开始这个优先级是固定的可能就很好选，但是在操作系统里面这个优先级是动态变化的，随着执行变化的，所以每一次如果要变化，就可以使用优先队列来维护，每一次进或者出都动态着在优先队列里面变化。在游戏中也有使用到，比如攻击对象，也是一个优先队列。所以优先队列比较适合处理一些动态变化的问题，当然对于静态的问题也可以求解，比如求解1000个数字的前100位出来，最简单的方法就是排序了，，但是这样多此一举，直接构造一个优先队列，然后出的时候出一百次最大的元素即可。这个时候算法的复杂度就是
，如果使用优先队列可以降到
的级别。
入队 | 出队 | |
|---|---|---|
普通数组 | ||
顺序数组 | ||
堆 |
现在就要用堆来实现一个优先队列堆一般都是树形结构：
二叉堆就和二叉树有点相像，没一个节点都有两个子节点，而且任何一个字节点都不会大于它的父节点，当然这样构造出来的就是一个最大堆了，也可以每一个子节点不小于它的父节点，这样就是最小堆了。而且，这个二叉堆一定是一个完全二叉树，非最后一层的节点一定要是满的，最后一层的节点一定要集中在左边：
这个性质，非常好，所以可以用给一个数组来表示堆。另外，层数越高并不意味着数值就越大或者越小，可以从右边的图看的出来。
可以看的出来，每一个节点子节点都是父节点的两倍。对于一个子节点，想要找到它的父类就直接/2即可，这里用的是四舍五入的除法，所以直接就向下取整了。父节点找子节点，左孩子2i，右孩子2i+1即可。首先是建立一个堆，这个还是蛮简单的：
template<typename item>
class MaxHeap {
private:
item *data;
int count = 0;
public:
MaxHeap(int capacity){
data = new item[capacity + 1];
count = 0;
}
~MaxHeap(){
delete[] data;
}
int size(){
return count;
}
bool isEmpty(){
return count == 0;
}
};对于插入一个元素其实也很简单，直接放到最后然后再一步一步的浮上来。新加入的那个元素和他的父亲对比，如果是大于它父亲那么就交换，只到是不大于或者是到了1。因为如果是小于父亲节点那就本身是正确的，如果不终止，再往下比那就是比较其他的元素了，但是其他元素本来就是正确的，所以不需要比较直接结束好了。
void shiftUp(int index) {
while (index > 1 && data[index / 2] < data[index]) {
swap(data[index / 2], data[index]);
index /= 2;
}
}
void insert(item number) {
assert(count + 1 <= capacity);
data[count + 1] = number;
count++;
shiftUp(count);
}这样就完成了插入。对于弹出最大的元素就有点边界问题要讨论了。这是一个完全二叉树，所以只有左节点没有右节点，所以首先先要判断是不是有做孩子，也就是越界的问题了，如果没有就继续判断有没有右孩子，有的话就左右孩子比较咯，哪个大就拿哪个出来，在把最大的拿出来和原节点比较即可。这里就需要一个额外的变量了。
void shiftDown(int index) {
while (2 * index <= count) {
int change = 2 * index;
if (change + 1 < count && data[change + 1] > data[change]) {
change++;
}
if (data[change] <= data[index]) {
break;
}
swap(data[change], data[index]);
index = change;
}
}
item pop() {
assert(count > 0);
item target = data[1];
swap(data[1], data[count]);
count--;
shiftDown(1);
return target;
}这样就完成了弹出，弹出的就是最大的数字。事实上这样是可以直接做排序操作的。 现在使用的堆数据结构，是通过不断的交换元素来达到符合堆这个数据结构的目的，但是如果堆里面的元素不是数字，而是字符串或者是很长很长的其他复杂的数据结构，那么交换起来效率就很低，而且这样的话索引起来也有难度。为了解决这些问题，于是就引入了索引堆来解决：
每一个元素加上一个索引值
交换的时候就只是需要交换索引值即可，第一个元素的索引是10，那么就是对应着索引下标的62。对于查找，也很简单，直接索引下标即可。修改起来也很简单，大致是和之前一样，只不过是修改的时候就是修改索引即可。 首先是对于索引堆的创建，我们不仅仅是要一个存储数据的数组，还要一个存储索引的数组，因为最后改变的是使用索引，索引对应下的数组是不变的。：
template<typename item>
class IndexHeap {
private:
item *indexes;
item *data;
int count;
int capacity;shiftDown和shiftUp操作其实就是变一下，把交换的对象换成索引即可：
void shiftUp(int k) {
while (k > 1 && data[indexes[k / 2]] < data[indexes[k]]) {
swap(indexes[k / 2], indexes[k]);
k /= 2;
}
}
void shitDown(int k) {
while (2 * k <= count) {
int change = 2 * k;
if (change + 1 <= count && data[indexes[change]] < data[indexes[change + 1]]) {
change++;
}
if (data[indexes[change]] <= data[indexes[k]]) {
break;
}
swap(indexes[change], indexes[k]);
k = change;
}
}弹出和插入都是一样的：
void insert(int i, item itemNumber) {
assert(count + 1 <= capacity);
assert(i + 1 >= 1 && i + 1 < capacity);
i++;
data[i] = itemNumber;
indexes[++count] = i;
shiftUp(count);
}
item extractMax(){
item num = data[indexes[1]];
swap(indexes[1], indexes[count]);
count -- ;
shitDown(1);
return num;
}主要的变化就是对于改变对应索引下的一个元素。改变了之后，我们要知道这个元素的索引是在这个堆的第几个位置才可以进行shift操作，之后还要进行shifDown和shiftUp操作，因为不知道它是可以上浮还是下沉。
void change(int i, item itemNumber){
i += 1;
data[i] = itemNumber;
for (int j = 1; j <= count; ++j) {
if (indexes[j] == i){
shiftUp(j);
shitDown(j);
return;
}
}
}但是这个种改变方法最差的情况下是
，最后还可以使用一种反向查找的方法进行改进，可以将复杂度提升到
。 堆可以解决的一些问题，首先，就是使用堆来实现优先队列，实现一些选择优先级最高的任务执行。可以作为一些低级工具来实现一些高级数据结构。
Tree
二叉树
二叉树比较常用的地方就是查找了，其实就是类似于二分查找法，把数据分成两份，使用
这样的复杂度来进行查找搜索，但是这样就要求这个数组是有序的。比较常用的实现就是查找表的实现。如果使用顺序数组进行查找，使用的复杂度是
，相对应的插入元素也是要
，因为它要遍历所有的元素找到相对应的位置然后插入。但是二分搜索树就更好一些，插入删除查找都是
的复杂度。所以，二分搜索树不仅可以查找数据，还可以高效的插入删除等等，效率很高，适合动态维护数据。而且这种方便的数据结构也可以很好的回答数据关系之间的问题。 二分搜索树首先是一颗二叉树：
每个节点的建值大于左孩子小于右孩子，而以左右孩子为根的子树仍然是二分搜索树。对于堆来说一定是要完全二叉树，但是对于一个二分搜索树来说，是不一定的，所以二叉树就不能用数组来存储了。实现二叉树的结构其实很简单，按照查找表来实现，要有一个建和一个值。
template<typename Key, typename Value>
class BST{
private:
struct Node{
Key key;
Value value;
Node *left;
Node *right;
Node(Key key, Value value){
this->key = key;
this->value = value;
this->left = this->right = NULL;
}
};
Node *root;
int count;
public:
BST(){
root = NULL;
count = 0;
}
~BST(){
//TODO
}
int size(){
return count;
}
bool isEmpty(){
return count == 0;
}
};对于插入其实也很简单。首先和当前根节点比较，如果小于就往左边递归，大于就往右边递归，当当前节点是NULL的时候就到达了递归终点，这个时候已经到头了，new一个新的节点返回当前节点即可。
void insert(Key key, Value value){
root = insert(root, key, value);
}
private:
Node *insert(Node *node, Key key, Value value){
if (node == NULL){
count ++;
return new Node(key, value);
}
if (node->key == key){
node->value = value;
} else if(key < node->key){
node->left = insert(node->left, key, value);
} else{
node->right = insert(node->right, key, value);
}
return node;
}二叉树的包含，查找其实都很类似，都是小于往左边找，大于往右边找，只是返回值不一样，操作很常规，比较复杂的是删除操作，要旋转之类的。
Value *search(Node *node, Key key){
if (NULL == node){
return NULL;
} else if(node->key == key){
return &(node->value);
} else if(key < node->key){
return search(node->left, key);
} else{
return search(node->right, key);
}
}
bool contain(Node *node, Key key){
if (NULL == node){
return false;
}
if (node->key == key){
return true;
} else if(key < node->key){
return contain(node->left, key);
} else{
return contain(node->right, key);
}
}
};以上方法都是放在了私有方法里面的，要调用只需要在public里面加上调用即可：
Value *search(Key key){
return search(root, key);
}
bool contain(Key key){
return contain(root, key);
}对于search的返回值，其实见仁见智，返回node，固定的一个值都可以。但是如果返回的是一个node，那么调用的时候就需要用户知道程序的结构，比如这道直观node节点是啥才能拿出来，这样封装性就不好了；如果返回的是一个值，那么如果为空的时候就回不来了，所以把它的指针作为返回值。 二叉树的遍历方式有三种，前序遍历，中序遍历和后续遍历。前序遍历先访问当前节点，再访问左右节点；中序遍历先访问左节点，再访问自身，最后右节点；后序遍历先访问左右子树最后才访问自身节点。
每一个节点都会存在左右子树，用三个点来表示访问时输出的顺序。
如果是前序遍历，那么输出的位置就是第一个园点的位置。中序遍历也是一样：
中序遍历就是在遍历到中间那个点的时候就输出。后序遍历自然就是最后一个位置输出：
后序遍历有一个很好的应用，就是释放内存的时候可以使用后序遍历的操作。递归实现二叉树的遍历其实很简单，就是调换几个位置就好了，结合上面的图理解一下就好。
void preOrder(Node *node){
if (node != NULL){
cout << node->value;
preOrder(node->left);
preOrder(node->right);
}
}
void inOrder(Node *node){
if (node != NULL){
inOrder(node->left);
cout << node->value;
inOrder(node->right);
}
}
void postOrder(Node * node){
if (node != NULL){
postOrder(node->left);
postOrder(node->right);
cout << node->value;
}
}没有什么难度的。注意到后序遍历是左右才到中间，所以我们可以使用这种方法来对对整棵树进行释放。
void destory(Node *node){
if (node != NULL){
destory(node->left);
destory(node->right);
delete node;
count --;
}
}之前我们遍历二叉树都是往深处遍历，都是遍历完一颗子树再遍历其他子树，所以又叫深度遍历。对于遍历方式还有另外一种，就是广度优先遍历，对应到二叉树里面就是层序遍历。先遍历完树的一层再遍历下一层。这种遍历方式没有往深处遍历到底，而是更关注广度的遍历。要实现这种遍历就需要使用到队列，事实上很多广度优先遍历都是用队列来实现，图的广度也是这样实现。
void levelOrder(){
queue<Node *> q;
q.push(root);
while (!q.empty()){
Node *p = q.front();
q.pop();
cout << p->value;
if (p->left){
q.push(p->left);
}
if (p->right){
q.push(p->right);
}
}
}这样很容易就实现了。二叉树的删除操作应该是属于二叉树操作里面比较难的部分，难的不是因为·删除本身，而是在于删除之后要怎么保持树的性质，所以是需要旋转。首先从一个最简单的问题开始，求二叉树最大值和最小值。
因为左节点是比当前节点小的，右节点是比当前节点大的，所以找左节点就是不断往左边走，直到没有左孩子为止：
Key minimum() {
assert(count != 0);
Node *node = minimum(root);
return node->key;
}
Key maximum(){
assert(count != 0);
Node *node = maximum(root);
return node->key;
}最大值和最小值都是一样。删除最小值，删除最小值有两种情况，如果这个最小值刚刚好没有任何节点，删除就很简单，如果是有的话那就需要一些操作了。
这种情况就很好删了，直接去掉即可。但是如果是有右孩子
这种情况删除最小的就需要做一些变化了，但也不是特别复杂，直接把右节点拉上来就好了，因为子树也是一颗二叉树。类似的思路删除最大值
这种情况删除最大值也是很简单的，直接扔了就好，但是如果是有左孩子的，直接把左边的子树拉上来就好了。
Node *removeMax(Node *node){
if (node->right == NULL){
Node *left = node->left;
delete node;
count --;
return left;
}
node->right = removeMax(node->right);
return node;
}
Node *removeMin(Node *node){
if (node->left == NULL){
Node *right = node->right;
delete node;
count --;
return right;
}
node->left = removeMin(node->left);
return node;
}其实差不多的。最大值只会有左孩子，最小值只有右孩子。回到删除节点，对于只有右孩子，因为右孩子本来就大于当前节点，只有左孩子也是一样的。最难的就是左右孩子都有的情况，这样就尴尬了：
如果是这种情况，我们就需要寻找当前节点的右孩子的作结点，找到
，如果59没有那么就是删除60了，很明显，就是右子树的最小值了。
Node *remove(Node *node, Key key){
if ( node == NULL){
return NULL;
} else if (key < node->key){
node->left = remove(node->left, key);
} else if (key > node->key){
node->right = remove(node->right, key);
} else{
if (node->left == NULL){
Node *right = node->right;
delete node;
count --;
return right;
} else if (node->right == NULL){
Node *left = node->left;
delete node;
count --;
return left;
} else{
Node *delNode = node;
Node *successor = new Node(minimum(node->right));
count ++;
successor->right = removeMin(node->right);
successor->left = node->left;
delete delNode;
count --;
return successor;
}
}
}首先判断一下是不是只有左子树和右子树，如果只是有一边，那么可以直接把那一边拉上去，如果是两边都有，那就需要找到右边的最小值，代替要删除的节点。这里有一个陷阱，使用successor得到最小的节点之后，后面又删除了，这样就会得到一个空指针，我们只是要得到它并不是要删除，这个时候我们应该要复制一份过来，不能直接就拉过来。 以上的操作都是把二叉树当成一个查找表来实现的，但是二叉树还有一个很好的性质，二叉树是有很好的顺序性，所以二叉树不仅仅可以用来实现查找，还可以找最小值最大值，前驱后继等等。但是二叉树并不是一成不变的，各种元素的插入顺序的不同是可以导致二叉树的结构不一样，如果数据是基本有序的，插入基本就是一个链表的形状了，退化成了一个顺序链表。改进方法后面会提到红黑树AVL树这些更加高级的数据结构。
并查集
这个数据结构并不算高级的数据结构，但是在后面的图会用到来判断是否形成环，如果两个节点的根是相同的，那么就可以判断这两个节点是同一组的了，也就是已经连在了一起。之前的堆，二叉树都是树形的结构，而这个并查集也算是一种树形结构，但是和上述的两种不太一样。并查集可以解决的问题有很多，首先就是连接问题：
想知道相邻两个点是不是连在一起的，如果这两个点是相邻的，沿着线可以很清楚的看到，但如果是一个左上角，一个右下角，那就很难看出来了。这种结构如果用并查集容易多了。连接可以应用在互联网之中好友之间的连接，一个人是否可以通过另外一个人认识另外一个人，这就是一种连接问题。 首先要知道一个并查集要支持什么操作，并查集主要支持两个操作，
，连接和查找操作。 用元素的下标是不是相同来表示这两个元素是不是连接的：
前面的一半就是一组，后面的一组又是一对。
class unionFind {
private:
int *id;
int count;
public:
unionFind(int n) {
count = n;
id = new int(n);
for (int i = 0; i < n; ++i) {
id[i] = i;
}
}
~unionFind() {
delete[] id;
}一开始大家都是各自为政，没有组团，所以都是不一样的，直接按照序列号即可。查找就是很简单了，就是直接返回id[]即可。
int find(int p) {
assert(p >= 0 && p <= count);
return id[p];
}判断是不是连在一起的，直接找到当前属于的下标再比较即可，
void unionElements(int p, int q){
int pID = find(p);
int qID = find(q);
if (pID == qID){
return;
}
for (int i = 0; i < count; ++i) {
if (id[i] == pID){
id[i] = qID;
}
}
}连接其实就是把两个堆连在一起，扫描下面的坐标相同的元素赋值即可，赋值那边赋值都可以。这种并查集查找很快，也叫quickUnion。
UF_version1::unionFind uF = UF_version1::unionFind(10);
uF.unionElements(1, 2);
uF.unionElements(5, 4);
uF.unionElements(3, 1);
cout << uF.isConnected(4, 5) << endl;上面这一种实现方法虽然实现查找的时候很快，但是实现并操作的时候很慢，需要进行遍历。并查集的另一种实现方式，而这种实现方式是后面实现并查集的一种常规实现方式。将每一个元素看成是一个节点，如果两个元素是一起的，那么这两个元素是一个指向另一个的。
这个时候2 3 1是指向了一起的，那么这三个就是一伙的，2是这个堆的根节点。
如果这两个堆要连在一起，那么只需要把他们的根连在一起就好了。
如果一个元素指向另一个元素，那么他的下标就存那个被指向的元素。把6,3或者是7,3连接一起都是一样的，因为他们的根是一样的。要修改的其实就是find而已，其他都是差不多的。
int find(int p){
assert(p >= 0 && p <= count);
while (parent[p] != p){
p = parent[p];
}
return p;
}
bool isConnected(int p, int q){
return find(p) == find(q);
}
void unionElements(int p, int q){
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot){
return;
}
parent[pRoot] = qRoot;
}不断向上找到自己的根，自己等于自己的就是当前的根了，如果不是就向下寻找，直到找到为止。这个时候的合并效率就不低了。注意到代码中的构造函数中有一个ecplicit，因为在c++中单个参数的构造函数是存在有隐式的转换的，加上这个关键字就可以禁止了，只能显示的构造，比如String = "Hello";就是一种隐式构造。 对于这种并查集，还是有优化空间的：
比如这两个堆要和在一起，如果是9合到另外一个，
这样做没有问题，但是这样查找效率不高。
效果虽然是一样的，但是查找起来确比上面那种要快很多。比较之后哪一个小的就插入到大的那个上面去。
private:
int *parent;
int *sz;
int count;增加一个sz的数组存储当前这个集合的数量，用于后面插入的比较，哪个大就插哪个。只要改变一下unionElements就好了，其他的不用变。
void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot) {
return;
}
if (sz[pRoot] < sz[pRoot]){
parent[pRoot] = qRoot;
sz[qRoot] += sz[pRoot];
} else{
parent[qRoot] = pRoot;
sz[pRoot] += sz[qRoot];
}
}其实基于数量的优化还不是最优的，如果一个堆过于分散那么合并起来的效率不是很高的，所以还有一种改进方法，就是对比两者的层数插入即可。并查集的线路压缩，以上的插入很多时候有些随机的成分，如果对这个线路的结构进行调整会快很多。这种方法就叫路径压缩。
这种路径的查找明显是效率很低的，
直观上进行调整，这样才是比较合理的。代码实现很简单，就是一句话的事情。
int find(int p) {
assert(p >= 0 && p <= count);
while (parent[p] != p) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}没了，路径压缩就这样。当前节点指向他的根就好了，而find就是找到它的根。递归求解即可。在经过了路径压缩的优化之后查找的复杂度几乎就是
复杂度了。
图论
交通运输，社交网络，互联网，工作的安排，闹区活动等等都可以用到图论处理。图可以分成两大类，一类是无向图，就是没有方向的，就好像两个人都互相认识一样，有向图就是单方面的联系，一个人认识另一个人，但是另一个人确不认识。当然，无向图也可以看成是一种特殊的有向图。图还可以根据权值分成两类，有权图和无权图，也就是边的权值，无权值只是表示了这个边存在与否而已，有权图表示的就是这个边的重要性，也可以看成是长度等等。图还有一个重要是性质，就是连通性的问题
这个图就不是连通图了。 简单图：不存在自环边和平行边的图。
后面讲最小生成树这些，自环边这些没有什么意义，直接比较权值就好了。 图的表示方法有两种，图的核心就在于每一个点以及他们相连的边，通常我们就使用两种方法来表示，邻接矩阵和邻接表。邻接矩阵就是用一个二维的矩阵来表示：
0表示不相连，0表示相连，当然了也可以表示成是True或者false，因为是一个无向图，所以这个邻接矩阵是对称的；同时也可以用邻接矩阵来表示有向图：
邻接表就是类似一个链表和数组的组合的数据结构了：
有向图也是类似。邻接表适合表示稀疏图，因为表示稀疏图所占用的空间最小，邻接矩阵适合表示稠密图，邻接矩阵的空间开好就是固定的了，不用完就浪费了，所以适合稠密图。实现就比较简单了。等等会从一个文件读进一个图再添加，首先是邻接矩阵的实现：
namespace Matrix {
class DenseGraph {
private:
int n, m;
bool directed;
vector<vector<bool>> g;
public:
DenseGraph(int n, bool directed) {
this->n = n;
this->m = 0;
this->directed = directed;
for (int i = 0; i < n; ++i) {
g.emplace_back(vector<bool>(n, false));
}
}
~DenseGraph() = default;
int V() {
return n;
}
int E() {
return m;
}
void addEdge(int v, int w) {
assert(v >= 0 && v < n);
assert(w >= 0 && w < n);
if (haveEdge(v, w)) {
return;
}
g[v][w] = true;
if (!this->directed) {
g[w][v] = true;
}
this->m++;
}
bool haveEdge(int v, int w) {
assert(v >= 0 && v < n);
assert(w >= 0 && w < n);
return g[v][w];
}
};
}点数确定，边数先为0，等等从文件读进去。使用一个vector来存储，当然创建一个二维矩阵也可以。邻接表也是一样：
namespace list {
class SparseGraph {
private:
int n, m;
bool directed;
vector<vector<int>> g;
public:
SparseGraph(int n, bool directed) {
this->n = n;
this->directed = directed;
this->m = 0;
for (int i = 0; i < n; ++i) {
g.emplace_back(vector<int>());
}
}
~SparseGraph() = default;
int V() {
return n;
}
int E() {
return m;
}
void addEdge(int v, int w) {
assert(v >= 0 && v < n);
assert(w >= 0 && w < n);
if (haveEdge(v, w)) {
return;
}
g[v].emplace_back(w);
if (v != w && !this->directed) {
g[w].emplace_back(v);
}
this->m++;
}
bool haveEdge(int v, int w) {
assert(v >= 0 && v < n);
assert(w >= 0 && w < n);
for (auto var : g[v]) {
if (var == w) {
return true;
}
}
return false;
}
};
}接下来就是图比较重要的操作，遍历操作，通过一个点来遍历相邻的邻边。通常比较常用的方法就是遍历操作，遍历每一个点，矩阵就看看是不是true，表就直接打印即可。但是这样在后面的广度遍历和深度遍历那么邻接表和邻接矩阵就要写两遍了，所以这里使用一个迭代器来操作，迭代器当做一个借口，返回当前这个点所连接的点是什么。
//interator
class adjIterator {
private:
SparseGraph &G;
int v;
int index;
public:
adjIterator(SparseGraph &graph, int v) : G(graph) {
assert(v < graph.n);
this->v = v;
this->index = 0;
}
int begin(){
if (!G.g[v].empty()){
return G.g[v][this->index];
}
return -1;
}
int next(){
index ++;
if (index < G.g[v].size()){
return G.g[v][index];
}
return -1;
}
bool end(){
return index >= G.g[v].size();
}
};写成一个类，index来指示当前遍历到哪里了。这里的构造函数由于初始化的参数是一个引用变量，所以需要列表初始化，因为引用变量的初始化一定要列表初始化才可以。begin得到第一个元素，next下一个，end判断是否结束，和for三连是一样的。
对于邻接矩阵的遍历有些许不同：
class adjIterator{
private:
DenseGraph &G;
int v;
int index;
public:
adjIterator(DenseGraph &graph, int v): G(graph){
this->v = v;
this->index = -1;
}
int begin(){
index = -1;
return next();
}
int next(){
for (index += 1; index < G.V(); index ++){
if (G.g[v][index]){
return index;
}
}
return -1;
}
bool end(){
return index >= G.V();
}
};因为这个时候是遍历所有的点，是true的就输出，不是的跳过，所以这个时候begin第一个输出的就是第一个为treu的点而不是index为0的点了。所以设成-1，通过next来找第一个为true的点即可，之后其他的同样。现在添加一个工具类，从文件读入一个图：
第一行是节点数和边数，接下来就是边的两个端点。
template <typename Graph>
class ReadGraph{
public:
ReadGraph(Graph &graph, const string &filename){
ifstream file(filename);
string line;
int V, E;
assert(file.is_open());
assert(getline(file, line));
stringstream ss(line);
ss >> V >> E;
assert(V == graph.V());
for (int i = 0; i < E; ++i) {
assert(getline(file, line));
stringstream ss(line);
int a, b;
ss >> a >> b;
graph.addEdge(a, b);
}
}
};使用模板类，是为了可以把邻接矩阵和邻接表都读进来。接下来的操作都很简单了。接下来就是图比较重要的操作了，图的遍历了。图的操作分为两种广度优先遍历，深度优先遍历。首先是深度遍历，就是从一个节点开始遍历到不能再遍历为止，图和树不一样，图是存在了环的，如果遍历过了那就必须设置已读的标记。
比如从0开始，首先第一个是0，之后就是1,2，因为这两个节点是没有连接到其他节点的，之后就是5，5连接了034，但是0已经看过了，就遍历3，3遍历4之后回来，最后就剩下和3节点相连的6了。从深度优先遍历也可以看出这个图的连通分量是多少。如果一直都是深度没有断开过，那肯定就是1了。这个时候就体现出了迭代器的好处，很好的屏蔽了底层数据结构的区别，直接复用即可。深度优先搜索还有一个性质，可以求解联通分量。如果深度一次完了之后还没有被遍历到的点那么就不属于这个联通分量了。同时也可以求解两个点是不是连在一起的，在同一个联通分量的那么肯定就是相连的了，总体来看，还是和连通分量有关系。
using namespace std;
template<typename Graph>
class Component {
private:
int *id;
Graph &G;
bool *visited;
int Ccount;
void dfs(int v) {
visited[v] = true;
id[v] = Ccount;
cout << v << " ";
typename Graph::adjIterator adj(G, v);
for (int i = adj.begin(); !adj.end(); i = adj.next()) {
if (!visited[i]){
dfs(i);
}
}
}
public:
Component(Graph &graph) : G(graph) {
visited = new bool[G.V()];
id = new int[G.V()];
Ccount = 0;
for (int i = 0; i < G.V(); ++i) {
visited[i] = false;
id[i] = -1;
}
for (int i = 0; i < G.V(); ++i) {
if (!visited[i]) {
dfs(i);
Ccount++;
}
}
}
int count(){
return Ccount;
}
bool isConnected(int v, int w){
return id[v] == id[w];
}
~Component() {
delete [] visited;
}
};count用来计算连通分量的个数，id用来计算这些点是属于哪一个连通分量的，遍历这个点的所有点，这里就用迭代器很好的屏蔽了不同数据结构实现的区别，如果没有访问过那就从这个点开始深度优先，然后递归下去。既然id就是连通分量的代号，那么直接等于count即可。判断是不是在一个连通分量里面的就直接对比id即可。
深度优先还有一个很重要的应用，就是寻路。这里的寻路只是找到一条路而已，没有说是最短路，事实上很多时候都是随机路径，因为有时候遍历的顺序不一样，得到的路径也是不一样的。
template<typename Graph>
class Path {
private:
bool *visited;
int *from;
Graph &G;
int s;
void dfs(int v) {
visited[v] = true;
typename Graph::adjIterator adj(G, v);
for (int i = adj.begin(); !adj.end(); i = adj.next()) {
if (!visited[i]) {
from[i] = v;
dfs(i);
}
}
}
public:
Path(Graph graph, int s) : G(graph) {
assert(s >= 0 && s < G.V());
visited = new bool[G.V()];
from = new int[G.V()];
for (int i = 0; i < G.V(); ++i) {
visited[i] = false;
from[i] = -1;
}
this->s = s;
dfs(s);
}
~Path() {
delete[] from;
delete[] visited;
}
void path(int w, vector<int> &vec) {
stack<int> s;
int p = w;
while (p != -1) {
s.push(p);
p = from[p];
}
vec.clear();
while (!s.empty()) {
vec.push_back(s.top());
s.pop();
}
}
bool hasPath(int w) {
assert(w >= 0 && w < G.V());
return visited[w];
}
void showPath(int w) {
for (int i = 0; i < G.V(); ++i) {
cout << visited[i] << " ";
}
vector<int> vec;
path(w, vec);
for (auto v: vec) {
cout << v << " ";
}
cout << endl;
}
};visited查看这些节点有没有被访问过，from查看这个节点是哪里来的，DFS遍历如果这个节点是没有被访问过的，那就赋值看看他是从哪个节点过来的，最后显示即可。最后需要反向查找。
深度优先遍历如果是使用邻接表，那么复杂度就是
级别的，因为表是通过直接遍历得到的，遍历到是就是有边的节点；而矩阵的复杂度是
，遍历的次数一定是平方。 图的广度优先遍历也需要用到队列。首先把这个节点周围的放入队列，如果队列不为空，那就直接出来一个把出来的那个周围的节点也塞进去，以此类推。广度优先遍历在图里面也叫层序遍历，一层一层的来，所以，先遍历到的肯定比后遍历到的距离原点要短，所以如果这个图是无权图，是可以使用这种方法来找到最短路径。每一层都加上1即可。
template <typename Graph>
class bfs{
private:
Graph &G;
int s;
bool *visited;
int *from;
int *ord;
public:
bfs(Graph &graph, int s): G(graph){
assert(s >= 0 && s < graph.V());
from = new int[graph.V()];
ord = new int[graph.V()];
visited = new bool[graph.V()];
for (int i = 0; i < graph.V(); ++i) {
visited[i] = false;
from[i] = -1;
ord[i] = -1;
}
this->s = s;
queue<int> q;
q.push(s);
ord[s] = 0;
visited[s] = true;
while (!q.empty()){
int w = q.front();
cout << w << " ";
q.pop();
typename Graph::adjIterator adj(graph, w);
for (int i = adj.begin(); !adj.end(); i = adj.next()) {
if (!visited[i] ){
q.push(i);
visited[i] = true;
from[i] = w;
ord[i] = ord[w] + 1;
}
}
}
}
void showShortPath(int w){
stack<int> s;
if (visited[w]){
int p = w;
while (p != -1){
s.push(p);
p = from[p];
}
}
vector<int> vec;
while (!s.empty()){
vec.push_back(s.top());
s.pop();
}
for (auto v: vec) {
cout << v << " ";
}
cout << endl;
}
};from就是存储上一个节点，ord存储距离起始点的距离是多少。
BFS找到的就是最短路径。DFS其实也可以找到最短路径，但是是随机的，它和你存储图的顺序有不同，和图的结构也有关系，但是BFS是一定的，而且BFS的最短路径是不止一条。