DFS,BFS以及图的遍历搜索

 1)DFS的基本写法：

/**
 * \1) DFS的基本写法，可做模板使用
 */

/**
DFS(int index,int nowK,int sum)
{
    if(满足条件)
        return;
    if(nowK,sum的取值是满足条件的情况下不可能的值)
        return;
    if(judge(index))
    {
        这里可以加一些约束条件，已经访问了这个节点，就将这个节点设置为已访问；
        DFS(index+1);
        在这儿可以进行回溯；
    }
}
*/

2) BFS的基本写法

/**
   2) BFS的基本写法
*/

/**
BFS(int index)
{
    queue<int> q;
    q.push(index);
    inq[index]=true;  //这儿需要注意，inq是结点是否入队，而不是是是否访问，否则会造成
    while(!q.empty())   //多个相同的结点入队，这与DFS的vis函数是有区别的；
    {
        int top=q.front();
        q.pop();
        for(...)
        {
            将top的下一层结点的元素入队；
            将入队的元素设置为已入队；
        }
    }
}
*/

3)图的深度优先遍历搜索(DFS)

/**
    3)图的深度优先遍历搜索(DFS)
*/

/**
邻接矩阵版：
int G[maxv][maxv],maxn;
bool vis[maxv];

void DFS(index) //index为当前访问的顶点标号
{
    vis[index]=true;    //将index设置为已访问
    for(int i=0;i<maxn;++i) //访问与index联通的点
    {
        if(G[index][i]!=INF&&vis[i]!=true)
            DFS(i);
    }
}

void DFSTrave()
{
    for(int i=0;i<maxn;++i)
        if(vis[i]==false)
            DFS(i);
}
*/

/**
邻接表版：
int maxn,maxv;
vector<int> adj[maxv];
bool vis[maxv];

void DFS(index) //index为当前访问的顶点标号
{
    vis[index]=true;    //将index设置为已访问
    for(int i=0;i<adj[index].size();++i)
    {
        int v=adj[index][i];    //注意这里是取得是adj[index]里的值
        if(vis[v]==false)
            DFS(v);
    }
}

void DFSTrave()
{
    for(int i=0;i<maxn;++i)
        if(vis[i]==false)
            DFS(i);
}
*/

4) 图的广度优先搜索算法

/**
   4) 图的广度优先搜索算法
*/

/**
邻接矩阵版：
int G[maxv][maxv],maxn;
bool inq[maxv];

void BFS(index) //遍历index所在的连通块
{
    queue<int> q;
    q.push(index);
    inq[index]=true;
    while(!q.empty())
    {
        int top=q.front();
        q.pop();
        for(int i=0;i<maxn;++i)
        {
            if(G[index][i]!=INF&&inq[i]==false)
            {
                q.push(i);
                inq[i]=true;
            }
        }
    }
}

void DFSTrave() //遍历图G
{
    for(int i=0;i<maxn;++i)
        if(inq[i]==false)
            DFS(i);
}
*/


/**
邻接表版：
int maxn,maxv;
vector<int> adj[maxv];
bool inq[maxv];

void BFS(index) //遍历index所在的连通块
{
    queue<int> q;
    q.push(index);
    inq[index]=true;
    while(!q.empty())
    {
        int top=q.front();
        q.pop();
        for(int i=0;i<adj[index].size();++i)
        {
            int v=adj[index][i];        //注意这里是取得是adj[index]里的值
            if(inq[v]==false)
            {
                q.push(v);
                inq[v]=true;
            }
        }
    }
}

void DFSTrave() //遍历图G
{
    for(int i=0;i<maxn;++i)
        if(vis[i]==false)
            DFS(i);
}
*/