前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >图算法-LeetCode 133、207(拓扑排序,邻接表建立)

图算法-LeetCode 133、207(拓扑排序,邻接表建立)

作者头像
算法工程师之路
发布2019-09-30 14:26:17
1.2K0
发布2019-09-30 14:26:17
举报
文章被收录于专栏:算法工程师之路

点击上方“算法工程师之路”,选择“星标”公众号

重磅干货,第一时间送达

作者:TeddyZhang,公众号:算法工程师之路

贪心算法问题:LeetCode #133 #207

编程题

【LeetCode #133】克隆图

给定无向连通图中一个节点的引用,返回该图的深拷贝(克隆)。图中的每个节点都包含它的值 val(Int) 和其邻居的列表(list[Node])。

解释: 节点 1 的值是 1,它有两个邻居:节点 2 和 4 。 节点 2 的值是 2,它有两个邻居:节点 1 和 3 。 节点 3 的值是 3,它有两个邻居:节点 2 和 4 。 节点 4 的值是 4,它有两个邻居:节点 1 和 3 。

提示:

  • 节点数介于 1 到 100 之间。
  • 无向图是一个简单图,这意味着图中没有重复的边,也没有自环。
  • 由于图是无向的,如果节点 p 是节点 q 的邻居,那么节点 q 也必须是节点 p 的邻居。
  • 必须将给定节点的拷贝作为对克隆图的引用返回。

解题思路:

克隆图,并且是无向连通图,因此可以使用map来保存两个节点之间的连接关系,如果在map中没有该节点tmp,则新建节点tmp_copy将该节点存入map中,然后遍历该节点的所有邻居,并递拷贝其所有邻居节点至tmp_copy的邻居数组中。

C++代码:

代码语言:javascript
复制
/*
// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;

    Node() {}

    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
public:
    map<Node*,Node*> mp;
    Node* cloneGraph(Node* node) {
        if(!node)   return nullptr;
        if(mp.count(node))  return mp[node];  // 如果存在,就不用新建了
        Node* tmp = new Node(node -> val);
        mp[node] = tmp;
        for(int i = ; i < node -> neighbors.size(); ++ i){
            if(node -> neighbors[i])    tmp -> neighbors.push_back(cloneGraph(node -> neighbors[i]));
        }
        return tmp;
    }
};

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/clone-graph

【LeetCode #207】课程表

现在你总共有 n 门课需要选,记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件,判断是否可能完成所有课程的学习?

示例 1: 输入: 2, [[1,0]] 输出: true 解释: 总共有 2 门课程。学习课程 1 之前,你需要完成课程 0。所以这是可能的。 示例 2: 输入: 2, [[1,0],[0,1]] 输出: false 解释: 总共有 2 门课程。学习课程 1 之前,你需要先完成课程 0;并且学习课程 0 之前,你还> 应先完成课程 1。这是不可能的。

说明:

输入的先决条件是由边缘列表表示的图形,而不是邻接矩阵。详情请参见图的表示法。 你可以假定输入的先决条件中没有重复的边。

解题思路:

由于本题目中的每个课程之间都有相应的联系,因此我们可以根据课程关系来构建一个有向图,如果在这个有向图中存在一个循环,那么则不能学完所有的课程,因为每个课程都需要每个先决条件的课程。一个很简单的思路是使用拓扑排序算法,可以判断一个循环是否存在于一个有向图中。

拓扑排序算法:计算图中所有节点的入度,如果某些节点的入度为零,则压入到队列todo中,接着循环弹出队列中的节点(即入读为零的节点),同时将下一个节点中入度为零的节点压入队列中,如果最后图都可以分离开,也就在此过程中,每个节点在分离时都可能入度为零。说明这个有向图中没有循环,否则则有循环。

C++代码(拓扑排序):

代码语言:javascript
复制
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        std::unordered_map<int, int> indegree;
        for(auto& v : prerequisites) {
            indegree[v[]]++;
        }
        queue<int> que;
        for(int i=; i<numCourses; ++i) {
           if(indegree[i] == ) {
               que.push(i);
           }
        }
        int cnt = ;
        while(!que.empty()) {
            int k = que.front();
            que.pop();
            cnt++;
            for(auto& v : prerequisites) {
                if(k == v[]) {
                    if(--indegree[v[]] == ) {
                        que.push(v[]);
                    }
                }
            }
        }
        if(cnt != numCourses)
            return false;
        return true;

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/course-schedule

文章来源:公众号 (算法工程师之路)

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-09-27,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法工程师之路 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 作者:TeddyZhang,公众号:算法工程师之路
  • 文章来源:公众号 (算法工程师之路)
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档