Leetcode 课程表 C++ 图的深度搜索和广度搜索练习

蔚落 2023-02-10 07:52 4阅读 0赞

# 广度搜索（degree） #

struct GraphNode{
        
        int label;
        vector<GraphNode*> neighbours;
        GraphNode(int x):label(x){
        };
    };
    class Solution {
        
    public:
        bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        
            vector<GraphNode*> graph;
            vector<int> degree;
            for(int i = 0 ; i < numCourses;i++){
        
                graph.push_back(new GraphNode(i));
                degree.push_back(0);
            }
            queue<GraphNode*> Q;
            for(int i = 0 ;i < prerequisites.size();i++){
        
                GraphNode* first = graph[prerequisites[i][0]];
                GraphNode* second = graph[prerequisites[i][1]];
                second->neighbours.push_back(first);
                degree[prerequisites[i][0]]++;
            }
            for(int i = 0 ;i < numCourses;i++){
        
                if(degree[i] == 0) Q.push(graph[i]);
            }
            while(!Q.empty()){
        
                for(int i = 0 ; i < Q.front()->neighbours.size();i++){
        
                    degree[Q.front()->neighbours[i]->label]--;
                    if(degree[Q.front()->neighbours[i]->label] == 0){
        
                        Q.push(Q.front()->neighbours[i]);
                    }
                }
                Q.pop();
            }
            for(int i = 0 ; i < numCourses;i++){
        
                delete graph[i];
            }
            for(int i = 0 ;i < numCourses;i++){
        
                if(degree[i]) return false;
            }
            return true;
        }
    };

# 深度搜索 #

struct GraphNode{
        
        int label;
        vector<GraphNode*> neighbours;
        GraphNode(int x):label(x){
        };
    };
    class Solution {
        
    public:
        bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        
                vector<GraphNode*> graph;
                vector<int> visit;
                for(int i = 0 ;i<numCourses;i++){
        
                    graph.push_back(new GraphNode(i));
                    visit.push_back(-1);
                }
                for(int i = 0; i < prerequisites.size();i++){
        
                    graph[prerequisites[i][1]]->neighbours.push_back( graph[prerequisites[i][0]]);
                }
                for (int i = 0 ; i < numCourses;i++){
        
                    if(visit[i] == -1 && DFS_graph(graph[i],visit) == false) return false ;
                }
                for(int i = 0 ;i < numCourses;i++){
        
                    delete graph[i];
                }
                return true;
    
        }
        bool DFS_graph(GraphNode* node,vector<int>& visit){
        
            visit[node->label] = 0;
            for (int i = 0 ; i < node->neighbours.size();i++){
        
                if(visit[node->neighbours[i]->label] == -1){
        
                    if(DFS_graph(node->neighbours[i],visit) == false){
        
                        return false;
                    }
                }
                else if(visit[node->neighbours[i]->label] == 0) return false;
            }
            visit[node->label] = 1;
            return true;
        }
    };