图遍历大抵分为两种：

深度优先遍历&广度优先遍历

分别对应：树的前序遍历&树的层次遍历

或许，在开始之前，你会想知道什么是遍历？

遍历：访问图中的所有顶点且无重复访问

深度优先搜索（DFS）

简述：先将当前顶点的所有邻接点遍历完成后再进行下一同级顶点的遍历，直至遍历所有顶点

注意事项：通过对已访问的节点进行标记从而规避重复访问的情况

举例：

假设同级遍历的顺序为从小到大，则DFS遍历的顺序为：

1->2->3->4 5->6->7

（出现两支为正常现象，可看为两棵深度优先生成树组成了一个深度优先生成森林，对于不同的同级遍历顺序，遍历的结果也不尽相同）

DFS的实现

下面直接上代码，（前面很大一部分都是图的存储的实现，这里采用的是邻接链表实现方式，只看dfs的话直接拉到底往上看就行）

其中的注释可以选择性的看一些，有自问自答的，有亿些精分

//DFS深度优先遍历
#include 
using namespace std;
//图的存储：采用邻接表存储方式
class adjMatrixGraph
{
public:
    adjMatrixGraph(int vsize,char d[]);//构造函数 vsize代表顶点数，d[]数组表示顶点的名称A，B……
    void insert(char x,char y,int w);//插入函数，插入一条由x指向y的有向边
    void remove(char x,char y);//删除函数，删除一条由x指向y的有向边
    bool exist(char x,char y);//判断x，y之间是否有一条由x指向y的有向边
    void dfs();//深度优先搜索公有函数
    ~adjMatrixGraph();//析构函数
private:
    int vers,edges;//vers代表顶点数，edges代表边数
    struct edgeNode//创建边表结构体，end代表顶点下标，weight代表指向下一条边的权重，next指针指向下一个连通的顶点
    {
        int end;//起始点
        int weight;
        edgeNode *next;//指向点
        edgeNode(int e,int w,edgeNode *n=NULL)//写一个构造函数方便后续使用
        {
            end=e;
            weight=w;
            next=n;
        }
    };
    struct verNode//邻接表头即节点表的结构体，ver代表顶点名称A，B……，head指针指向当前顶点指向的下一个节点（是由边表节点edgeNode表示的）
    {
        char ver;
        edgeNode *head;
        verNode(edgeNode *h=NULL) {head=h;}
    };
    verNode *verList;//创建数组形式的节点表
    int find(char v)//通过顶点名称找到顶点下标
    {
        for(int i=0;ivers;i++)
            if(verList[i].ver==v) return i;
    }
    void dfs(int v,bool visited[]);
};
//构造函数
adjMatrixGraph::adjMatrixGraph(int vsize, char *d)
{
    vers=vsize;//一般不进行顶点的删除与添加，只进行边的删除与添加
    edges=0;
    verList=new verNode[vsize];//给verList指针分配vsize大小的空间放顶点
    for(int i=0;inext;//p此时为当前的顶点的边表头结点，将边表头结点的下一个指向节点赋值给当前顶点的边表头结点，此时整个边表连跳过了p节点，也就是之前的顶点的head指向的节点
            //目的就是将之前的head节点剥离出来，以p表示，之后再通过删除p进而删除掉节点
            delete p;
        }
    }
    delete [] verList;//将verList后面的边表尾巴全都删除干净之后就可以一次性删除掉所有的verList动态数组了
}
//插入函数
void adjMatrixGraph::insert(char x, char y, int w)
{
    int u=find(x),v=find(y);//找到x，y顶点对应的下标
    verList[u].head=new edgeNode(v,w,verList[u].head);//从链表的脖子处插入，即新插入的节点紧跟在表头后面，当前顶点的head作为更新后的顶点的head的next
    //但是有一个问题：如果插入的边节点也有它的next怎么办啊，这不是会被当成其他人的next吗？？先继续往下看
    //嗷嗷不会，因为在这里存储的就只是当前顶点的指向顶点，全都是直通路径，不会存储当前顶点的下一个顶点的下一个顶点
    ++edges;//插入边后，边的个数加1
}
//删除函数
void adjMatrixGraph::remove(char x, char y)
{
    int u= find(x),v= find(y);
    edgeNode *p=verList[u].head,*q;//这里和析构函数的操作是相似的，但是需要通过一顿操作找到指向y的特定的边进行定点爆破，而析构里面的删除操作是一通乱杀，只要有就删
    //先把verList[u].head赋值给p是减少后面的多种情况下对p赋值，反正最后都是要赋值的，那就先赋值好了，省的下面每种情况都要赋值一遍
    
    //下面给一下保证输入合法的情况下的简化写法
    while(p!=NULL&&p->end!=v)p=p->next;
    if(p==NULL) return;
    q=p;
    p=q->next;
    delete q;
    --edges;
    return;
}
//判断x，y之间是否有边
bool adjMatrixGraph::exist(char x, char y)
{
    int u= find(x),v= find(y);
    edgeNode *p=verList[u].head;
    while(p->next!=NULL&&p->end!=v)p=p->next;//和上一个删除操作里面是一样的
    if(p==NULL) return false;
    else return true;
}
//上面全都是图的存储操作，以下是遍历操作的函数
void adjMatrixGraph::dfs()
{
    bool *visited=new bool[vers];
    for(int i=0;iend]==false)
            dfs(p->end,visited);
        p=p->next;
    }
}
int main() {
    char a[]={'A','B','C','D','E','F','G'};
    adjMatrixGraph graph(7,a);
    graph.insert('A','B',1);
    graph.insert('B','C',1);
    graph.insert('B','D',1);
    graph.insert('C','A',1);
    graph.insert('D','C',1);
    graph.insert('E','G',1);
    graph.insert('E','F',1);
    graph.insert('F','B',1);
    graph.insert('G','D',1);
    graph.insert('G','F',1);
    //由于插入时总是在勃颈处插入，所以插入顺序会影响最终的搜索顺序
    graph.dfs();
    return 0;
}

DFS时间性能分析

采用不同的表示方法来表示图会得到不同的时间复杂度

邻接表表示：O(|V|+|E|)，|V|为顶点数，|E|为边数，因为DFS要对所有的点和边都访问一遍

邻接矩阵表示：O（|V|^2），因为DFS需要遍历邻接矩阵

广度优先搜索（BFS）

简述：类似树的层次遍历，将同级的顶点遍历完之后，再进行顶点的邻接点的遍历

注意：这里需要建立一个队列来放置需要遍历的顶点，以保证广度优先遍历的顺序

在队列弹出顶点时，将未被访问的所有邻接顶点存储进队列中等待访问

假设同级遍历的顺序为从小到大，则DFS遍历的顺序为：

1->2->3->4 5->6->7

（虽然和深度搜索的结果相同，但这里只是巧合，其本质上的搜索思想与方式是不一样的）

BFS的实现

也是直接上代码吧，（前面是图的存储，如有需要，可选择性看看）

//BFS广度优先遍历
//我不想写队列的数据结构啦，用STL的vector代替一下吧
#include
using namespace std;
class adjMatrixGraph
{
public:
    adjMatrixGraph(int vsize,char d[]);//构造函数 vsize代表顶点数，d[]数组表示顶点的名称A，B……
    void insert(char x,char y,int w);//插入函数，插入一条由x指向y的有向边
    void remove(char x,char y);//删除函数，删除一条由x指向y的有向边
    bool exist(char x,char y);//判断x，y之间是否有一条由x指向y的有向边
    void bfs();//广度优先搜索公有函数
    ~adjMatrixGraph();//析构函数
private:
    int vers,edges;//vers代表顶点数，edges代表边数
    struct edgeNode//创建边表结构体，end代表顶点下标，weight代表指向下一条边的权重，next指针指向下一个连通的顶点
    {
        int end;//起始点
        int weight;
        edgeNode *next;//指向点
        edgeNode(int e,int w,edgeNode *n=NULL)//写一个构造函数方便后续使用
        {
            end=e;
            weight=w;
            next=n;
        }
    };
    struct verNode//邻接表头即节点表的结构体，ver代表顶点名称A，B……，head指针指向当前顶点指向的下一个节点（是由边表节点edgeNode表示的）
    {
        char ver;
        edgeNode *head;
        verNode(edgeNode *h=NULL) {head=h;}
    };
    verNode *verList;//创建数组形式的节点表
    int find(char v)//通过顶点名称找到顶点下标
    {
        for(int i=0;ivers;i++)
            if(verList[i].ver==v) return i;
    }
};
//构造函数
adjMatrixGraph::adjMatrixGraph(int vsize, char *d)
{
    vers=vsize;//一般不进行顶点的删除与添加，只进行边的删除与添加
    edges=0;
    verList=new verNode[vsize];//给verList指针分配vsize大小的空间放顶点
    for(int i=0;inext;//p此时为当前的顶点的边表头结点，将边表头结点的下一个指向节点赋值给当前顶点的边表头结点，此时整个边表连跳过了p节点，也就是之前的顶点的head指向的节点
            //目的就是将之前的head节点剥离出来，以p表示，之后再通过删除p进而删除掉节点
            delete p;
        }
    }
    delete [] verList;//将verList后面的边表尾巴全都删除干净之后就可以一次性删除掉所有的verList动态数组了
}
//插入函数
void adjMatrixGraph::insert(char x, char y, int w)
{
    int u=find(x),v=find(y);//找到x，y顶点对应的下标
    verList[u].head=new edgeNode(v,w,verList[u].head);//从链表的脖子处插入，即新插入的节点紧跟在表头后面，当前顶点的head作为更新后的顶点的head的next
    //但是有一个问题：如果插入的边节点也有它的next怎么办啊，这不是会被当成其他人的next吗？？先继续往下看
    //嗷嗷不会，因为在这里存储的就只是当前顶点的指向顶点，全都是直通路径，不会存储当前顶点的下一个顶点的下一个顶点
    ++edges;//插入边后，边的个数加1
}
//删除函数
void adjMatrixGraph::remove(char x, char y)
{
    int u= find(x),v= find(y);
    edgeNode *p=verList[u].head,*q;//这里和析构函数的操作是相似的，但是需要通过一顿操作找到指向y的特定的边进行定点爆破，而析构里面的删除操作是一通乱杀，只要有就删
    //先把verList[u].head赋值给p是减少后面的多种情况下对p赋值，反正最后都是要赋值的，那就先赋值好了，省的下面每种情况都要赋值一遍
    
    //下面给一下保证输入合法的情况下的简化写法
    while(p!=NULL&&p->end!=v)p=p->next;
    if(p==NULL) return;
    q=p;
    p=q->next;
    delete q;
    --edges;
    return;
}
//判断x，y之间是否有边
bool adjMatrixGraph::exist(char x, char y)
{
    int u= find(x),v= find(y);
    edgeNode *p=verList[u].head;
    while(p->next!=NULL&&p->end!=v)p=p->next;//和上一个删除操作里面是一样的
    if(p==NULL) return false;
    else return true;
}
//上面全都是图的存储操作，以下是遍历操作的函数，层次遍历操作不需要递归操作
void adjMatrixGraph::bfs()
{
    bool *visited=new bool[vers];//创建访问数组
    int currentNode;
    vector q(vers);//这里创建队列，存储要访问的节点的下标
    edgeNode *p;
    for(int i=0;iend]==false) q.insert(q.begin(),p->end);//如果有邻接点的话就将其放入队列等待访问
                p=p->next;
            }
        }
        cout< 
BFS时间性能分析 
与DFS时间复杂度情况相同，这里不再讨论。