前言

根据分类，图的搜索分类可以分为

BFS和DFS

记忆化搜索（基于深搜）

双向广搜

二分状态搜索

启发式搜索

与或树搜索

博弈树搜索(α-β剪枝)(极大极小过程搜索)

A*搜索

IDA搜索

先看BFS和DFS，因为这是最基础的搜索策略了，BFS是按照深度进行搜索，DFS则是按照广度进行搜索；

其实只要你理解了树的DFS和BFS，那么图的话，只是在其基础上加了判断结点是否访问过，是否联通而已；

深度优先搜索

简介

先看一幅有向图

可以发现，其遍历的顺序为

0->3->1->2->4

其的概念就是一条路走到黑

图的表示方法包括邻接表，邻接矩阵等，邻接矩阵表示的是用一个二维数组表示图的联通，其中i行j列表示了i结点和j结点的联通情况，如果其为1，说明是联通的，如果其为0，反之；邻接表表示的是一个一维数组，但是数组中每个列表包含着是链表；

看个图加深理解：

其中a是有向图／原图，b是邻接表表示图，c是邻接矩阵表示图；

伪代码

递归实现

1. 访问数组初始化：visited[n] = 02. 访问顶点：visited[v] = 13. 取v的第一个邻接点w；4. 循环递归：    while(w存在)        if(w未被访问过)            从顶点w出发递归执行;        w = v的下一个邻接点;

非递归实现

1. 栈初始化：visited[n] = 02. 访问顶点：visited[v] = 13. 入栈4. while(栈不为空)    x = 栈的顶元素，并且出栈;    if (存在并找到未被访问的x的邻接点w)        访问w：visited[w] = 1        w进栈

上面的寻找下一个邻接点，需要根据图是邻接表还是邻接矩阵进行循环判断；

实现

由于图的表示有几种，所以实现的代码包括了用邻接矩阵的图和邻接表的图；

.h文件

typedef struct edge {    int vertex;    struct edge* next;}Edge;class DFS {public:    DFS();    ~DFS();    void Test_M();    void Test_L();private:    // 邻接矩阵    void createGraph_M(int (*edge)[VERTEXNUM], int start, int end);    void displayGraph_M(int (*edge)[VERTEXNUM]);    void DFT_M(int (*edge)[VERTEXNUM], int* vertexStatusArr);    void DFTCore_M(int (*edge)[VERTEXNUM], int i, int* vertexStatusArr);        // 邻接表    void createGraph_L(Edge** edge, int start, int end);    void displayGraph_L(Edge** edge);    void delGraph_L(Edge** edge);    void DFT_L(Edge** edge, int* vertextStatusArr);    void DFTCore_L(Edge** edge, int i, int* vertexStatusArr);    };void DFSTest_M();void DFSTest_L();

.cpp文件

DFS::DFS() {    }DFS::~DFS() {        }/*----------------------------邻接矩阵--------------------------*//** *  创建图 * *  @param edge <#edge description#> */void DFS::createGraph_M(int (*edge)[VERTEXNUM], int start, int end) {    edge[start][end] = 1;}/** *  打印存储的图 * *  @param edge <#edge description#> */void DFS::displayGraph_M(int (*edge)[VERTEXNUM]) {    for (int i = 0; i < VERTEXNUM; i++) {        for (int j = 0; j < VERTEXNUM; j++) {            std::cout << edge[i][j];        }        std::cout << std::endl;    }}/** *  深度优先遍历 * *  @param edge <#edge description#> */void DFS::DFT_M(int (*edge)[VERTEXNUM], int* vertexStatusArr) {    for (int i = 0; i < VERTEXNUM; i++) {        DFTCore_M(edge, i, vertexStatusArr);    }    std::cout << std::endl;}void DFS::DFTCore_M(int (*edge)[VERTEXNUM], int i, int* vertexStatusArr) {    if (vertexStatusArr[i] == 1) return; // 顶点访问过则不再访问        std::cout << i << "->";    vertexStatusArr[i] = 1;        // 存在边的对应关系，才递归    for (int j = 0; j < VERTEXNUM; j++) {        if (edge[i][j] == 1) {            DFTCore_M(edge, j, vertexStatusArr);        }    }}void DFS::Test_M() {    std::cout << "--------------邻接矩阵表示-----------------" << std::endl;        //动态创建存放边的二维数组    int (*edge)[VERTEXNUM] = (int (*)[VERTEXNUM])malloc(sizeof(int) * VERTEXNUM * VERTEXNUM);        for (int i = 0; i < VERTEXNUM; i++) {        for (int j = 0; j < VERTEXNUM; j++) {            edge[i][j] = 0;        }    }        // 存放顶点的遍历状态；0:未遍历，1:已遍历    int *vertexStatusArr = (int*)malloc(sizeof(int)*VERTEXNUM*VERTEXNUM);    for (int i = 0; i < VERTEXNUM; i++) {        vertexStatusArr[i] = 0;    }        std::cout << "after init.." << std::endl;    displayGraph_M(edge);        //创建图    createGraph_M(edge, 0, 3);    createGraph_M(edge, 0, 4);    createGraph_M(edge, 3, 1);    createGraph_M(edge, 3, 2);    createGraph_M(edge, 4, 1);        std::cout << "after create.." << std::endl;    displayGraph_M(edge);        // 遍历    std::cout << "traversal.." << std::endl;    DFT_M(edge, vertexStatusArr);        free(edge);}/*----------------------------邻接表--------------------------*/void DFS::createGraph_L(Edge** edge, int start, int end) {    Edge* nedge = (Edge*)malloc(sizeof(Edge));    nedge->vertex = end;    nedge->next = nullptr;    edge = edge + start;    while (*edge != nullptr) {        edge = &((*edge)->next);    }    *edge = nedge;}void DFS::displayGraph_L(Edge** edge) {    Edge* nedge;    int edgeCount = 0;    for (int i = 0; i < VERTEXNUM; i++) {        nedge = *(edge + i);        std::cout << i << ":";        while (nedge != nullptr) {            std::cout << nedge->vertex << ",";            nedge = nedge->next;            edgeCount++;        }        std::cout << std::endl;    }    std::cout <<"edge count is " << edgeCount << std::endl;}void DFS::delGraph_L(Edge** edge) {    Edge *p, *del;    for (int i = 0; i < VERTEXNUM; i++) {        p = *(edge + i);        while (p != nullptr) {            del = p;            p = p->next;            free(del);        }        edge[i] = nullptr;    }    free(edge);}void DFS::DFT_L(Edge** edge, int* vertextStatusArr) {    for (int i = 0; i < VERTEXNUM; i++) {        DFTCore_L(edge, i, vertextStatusArr);    }    std::cout << std::endl;}void DFS::DFTCore_L(Edge** edge, int i, int* vertexStatusArr) {    if (vertexStatusArr[i] == 1) {        return;    }    std::cout << i << "->";    vertexStatusArr[i] = 1;    Edge *p = *(edge + i);    while (p != nullptr) {        DFTCore_L(edge, p->vertex, vertexStatusArr);        p = p->next;    }}void DFS::Test_L() {    std::cout << "--------------邻接表表示-----------------" << std::endl;        // 动态创建存放边的指针数组    Edge **edge = (Edge**)malloc(sizeof(Edge*)*VERTEXNUM);    for (int i = 0; i < VERTEXNUM; i++) {        edge[i] = nullptr;    }        // 存放顶点的遍历状态：0：未遍历，1:已遍历    int *vertexStatusArr = (int*)malloc(sizeof(int)*VERTEXNUM);    for (int i = 0; i < VERTEXNUM; i++) {        vertexStatusArr[i] = 0;    }        std::cout << "after init.." << std::endl;    displayGraph_L(edge);        //创建图    createGraph_L(edge, 0, 3);    createGraph_L(edge, 0, 4);    createGraph_L(edge, 3, 1);    createGraph_L(edge, 3, 2);    createGraph_L(edge, 4, 1);        std::cout << "after create.." << std::endl;    displayGraph_L(edge);        // 深度优先遍历    DFT_L(edge, vertexStatusArr);        // 释放邻接表占用的内存    delGraph_L(edge);    edge = nullptr;    free(vertexStatusArr);    vertexStatusArr = nullptr;}

总结：代码有很强的C的风格，抱歉；这里面主要看遍历过程；

广度优先遍历

简介

先看一幅有向图

可以发现，其遍历的顺序为

0->3->4->1->2

其的概念就是左看看右看看，雨露均沾

伪代码

非递归实现

1. 初始化队列：visited[n] = 02. 访问顶点：visited[v] = 13. 顶点v加入队列4. 循环：    while(队列是否为空)        v = 队列头元素        w = v的第一个邻接点        while(w存在)            if(如果w未访问)                visited[w] = 1;                顶点w加入队列                w = 顶点v的下一个邻接点

上面的寻找下一个邻接点，是寻找之前结点的下一个邻接点，而不是当前的，否则就变成DFS了；

实现

.h文件

typedef struct bedge {    int vertex;    struct bedge* pre;    struct bedge* next;}BEdge;template 
    
     class Queue {private:    T *arr;    int front;    int rear;    int size;    int length;public:    Queue();    ~Queue();        void Push(T value);    T Pop();    int Size();    int Length();    bool Empty();    bool Full();};class BFS {private:    BEdge *front;    BEdge *rear;    public:    BFS();    ~BFS();        void Test_M();    void Test_L();        void createGraph_M(int (*edge)[VERTEXNUM], int start, int end);    void displayGraph_M(int (*edge)[VERTEXNUM]);    void BFT_M(int (*edge)[VERTEXNUM], int *vertexStatusArr);    void BFTCore_M(int (*edge)[VERTEXNUM], int i, int *vertexStatusArr);        void createGraph_L(BEdge** edge, int start, int end);    void displayGraph_L(BEdge** edge);    void delGraph_L(BEdge** edge);    void BFT_L(BEdge** edge, int* vertextStatusArr);    void BFTCore_L(BEdge** edge, int i, int* vertexStatusArr);};void BFSTest_M();void BFSTest_L();

.cpp文件

template 
    
     Queue
     
      ::Queue() {    size = 10;    arr = new T[size];    front = rear = length = 0;}template 
      
       Queue
       
        ::~Queue() {    delete [] arr;}template 
        
         void Queue
         
          ::Push(T value) { // 大于原数组长度，创建新数组，赋值给新数组 if (length == size) { int nsize = size * 2; int * narr = new T(nsize); int i = 0; for (; i < length; i++) { narr[(front + i) % nsize] = arr[(front + i) % size]; } rear = (front + i) % nsize; arr = narr; size = nsize; } arr[rear] = value; rear = (rear + 1) % size; ++length;}template 
          
           T Queue
           
            ::Pop() { T temp = arr[front]; front = (front + 1) % size; // 原来的内存块没有做到真正的删除 --length; return temp;}template 
            
             int Queue
             
              ::Size() { return size;}template 
              
               int Queue
               
                ::Length() { return length;}template 
                
                 bool Queue
                 
                  ::Empty() { return length == 0;}template 
                  
                   bool Queue
                   
                    ::Full() { return length == size;}BFS::BFS() { }BFS::~BFS() { }void BFS::createGraph_M(int (*edge)[VERTEXNUM], int start, int end) { edge[start][end] = 1;}void BFS::displayGraph_M(int (*edge)[VERTEXNUM]) { for (int i = 0; i < VERTEXNUM; i++) { for (int j = 0; j < VERTEXNUM; j++) { std::cout << edge[i][j]; } std::cout << std::endl; }}void BFS::BFT_M(int (*edge)[VERTEXNUM], int *vertexStatusArr) { for (int i = 0; i < VERTEXNUM; i++) { BFTCore_M(edge, i, vertexStatusArr); } std::cout << std::endl;}void BFS::BFTCore_M(int (*edge)[VERTEXNUM], int i, int *vertexStatusArr) { Queue
                    
                      queue; queue.Push(i); while (!queue.Empty()) { int t = queue.Pop(); if (vertexStatusArr[t] == 0) { std::cout << t << "->"; vertexStatusArr[t] = 1; for (int i = 0; i < VERTEXNUM; i++) { if (edge[t][i] == 1) { queue.Push(i); } } } }}void BFS::Test_M() { std::cout << "--------------邻接矩阵表示-----------------" << std::endl; //动态创建存放边的二维数组 int (*edge)[VERTEXNUM] = (int (*)[VERTEXNUM])malloc(sizeof(int) * VERTEXNUM * VERTEXNUM); for (int i = 0; i < VERTEXNUM; i++) { for (int j = 0; j < VERTEXNUM; j++) { edge[i][j] = 0; } } // 存放顶点的遍历状态；0:未遍历，1:已遍历 int *vertexStatusArr = (int*)malloc(sizeof(int)*VERTEXNUM*VERTEXNUM); for (int i = 0; i < VERTEXNUM; i++) { vertexStatusArr[i] = 0; } std::cout << "after init.." << std::endl; displayGraph_M(edge); //创建图 createGraph_M(edge, 0, 3); createGraph_M(edge, 0, 4); createGraph_M(edge, 3, 1); createGraph_M(edge, 3, 2); createGraph_M(edge, 4, 1); std::cout << "after create.." << std::endl; displayGraph_M(edge); // 遍历 std::cout << "traversal.." << std::endl; BFT_M(edge, vertexStatusArr); free(edge); }void BFS::createGraph_L(BEdge** edge, int start, int end) { BEdge* nedge = (BEdge*)malloc(sizeof(BEdge)); nedge->vertex = end; nedge->next = nullptr; edge = edge + start; while (*edge != nullptr) { edge = &((*edge)->next); } *edge = nedge;}void BFS::displayGraph_L(BEdge** edge) { BEdge* nedge; int edgeCount = 0; for (int i = 0; i < VERTEXNUM; i++) { nedge = *(edge + i); std::cout << i << ":"; while (nedge != nullptr) { std::cout << nedge->vertex << ","; nedge = nedge->next; edgeCount++; } std::cout << std::endl; } std::cout <<"edge count is " << edgeCount << std::endl;}void BFS::delGraph_L(BEdge** edge) { BEdge *p, *del; for (int i = 0; i < VERTEXNUM; i++) { p = *(edge + i); while (p != nullptr) { del = p; p = p->next; free(del); } edge[i] = nullptr; } free(edge);}void BFS::BFT_L(BEdge** edge, int* vertextStatusArr) { for (int i = 0; i < VERTEXNUM; i++) { BFTCore_L(edge, i, vertextStatusArr); } std::cout << std::endl;}void BFS::BFTCore_L(BEdge** edge, int i, int* vertexStatusArr) { Queue
                     
                       queue; queue.Push(i); while (!queue.Empty()) { int t = queue.Pop(); if (vertexStatusArr[t] == 0) { std::cout << t << "->"; vertexStatusArr[t] = 1; BEdge* p = *(edge + t); while (p != nullptr) { queue.Push(p->vertex); p = p->next; } } }}void BFS::Test_L() { std::cout << "--------------邻接表表示-----------------" << std::endl; // 动态创建存放边的指针数组 BEdge **edge = (BEdge**)malloc(sizeof(BEdge*)*VERTEXNUM); for (int i = 0; i < VERTEXNUM; i++) { edge[i] = nullptr; } // 存放顶点的遍历状态：0：未遍历，1:已遍历 int *vertexStatusArr = (int*)malloc(sizeof(int)*VERTEXNUM); for (int i = 0; i < VERTEXNUM; i++) { vertexStatusArr[i] = 0; } std::cout << "after init.." << std::endl; displayGraph_L(edge); //创建图 createGraph_L(edge, 0, 3); createGraph_L(edge, 0, 4); createGraph_L(edge, 3, 1); createGraph_L(edge, 3, 2); createGraph_L(edge, 4, 1); std::cout << "after create.." << std::endl; displayGraph_L(edge); // 深度优先遍历 BFT_L(edge, vertexStatusArr); // 释放邻接表占用的内存 delGraph_L(edge); edge = nullptr; free(vertexStatusArr); vertexStatusArr = nullptr;}