图遍历算法的应用

图遍历算法的应用1.判断图的连通性图的遍历算法可以用来判断图的连通性。如果一个无向图是联通的,如果无向图是联通的,则从任一节点出发,仅需一次遍历就可以访问图中的所有节点。如果无向图是非联通的,则从某一节点出发,一次遍历仅能访问到该顶点所在联通分量的所有顶点,而对于图中其他联通分量的顶点,则无法通过这次遍历访问。对于有向图来说,若从初始点到图中的每个顶点都有路径,则能够访问到图中的所有顶点,否则不能访问到所有顶…

大家好,又见面了,我是你们的朋友全栈君。

1.判断图的连通性

图的遍历算法可以用来判断图的连通性。如果一个无向图是联通的,如果无向图是联通的,则从任一节点出发,仅需一次遍历就可以访问图中的所有节点。如果无向图是非联通的,则从某一节点出发,一次遍历仅能访问到该顶点所在联通分量的所有顶点,而对于图中其他联通分量的顶点,则无法通过这次遍历访问。对于有向图来说,若从初始点到图中的每个顶点都有路径,则能够访问到图中的所有顶点,否则不能访问到所有顶点。

2.遍历解答树

在问题求解时,对所有可能的问题解构成一颗树,而最优解或者符合要求的解就是该树的一条路径或一个节点。这种树称为解答树。
例1:通过深度优先搜索生成13的全排列

const int N = 13;
int d[N];//记录解
int v[N];//标记某个值是否被遍历过,没遍历过为0, 遍历过为1
int n;
void dfs(int depth){
    if(depth == N){
        for(int i = 0; i != n; i++){
            cout<<d[i]<<" ";
        }
        cout<<endl;
        return;
    }
    for(int i = 1; i <= n; ++i){
        if(!v[i]){
            v[i] = 1;
            d[depth] = i;
            dfs(depth+1);
            v[i] = 0;
        }
    }
}

int main(){
    cin>>n;
    memset(v, 0, n);
    dfs(0);
}

例2:有1分、2分、5分、10分四种硬币,每种硬币数量无限,给定Target分钱,求有多少种组合可以组合成Target分钱?

int count = 0;//统计有多少种组合
int Target = 0;
int coin[4] = {
  
  1,2,5,10};
int total = 0;
vector<int> res;
void dfs(int index){
    if(total == target){
        count++;
        cout<<count<<endl;
        for(int i =0 ; i < res.size(); ++i)
            cout<<res[i]<<" ";
        cout<<endl; 
    }
    if(total > target) return;
    for(int i = index; i < 4; ++i){
        total += coin[i];
        res.push_back(coin[i]);
        dfs(i);
        res.pop();
        total -= coin[i];
    }
}

int main(){
    count = 0;
    cin>>Target;
    dfs(0);
    cout<<count<<endl;
}

**例3:**DFS解决1到n个自然数组成的集合的所有组合等问题。

const int N=100;
int number = 3;
int x[N];//解向量
void dfs(int cur_depth){
    if(cur_depth >= number){
        bool test = false;
        for(int i = 0; i < number; ++i){
            if(x[i] != 0){
                cout<<i+1;
                test = true;
            }
        }
        if(test)
            cout<<endl;
        return;
    }
    x[cur_depth+1] = 0;
    dfs(cur_depth+1);
    x[cur_depth+1] = 1;
    dfs(cur_depth+1);
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/136479.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号