데이터 구조 - 그림 - 총화

18555 단어 기초 - 도
Is Graph Bipartite?
Description
Given an undirected  graph , return  true  if and only if it is bipartite.
Recall that a graph is bipartite if we can split it's set of nodes into two independent subsets A and B such that every edge in the graph has one node in A and another node in B.
The graph is given in the following form:  graph[i]  is a list of indexes  j  for which the edge between nodes  i  and  j  exists. Each node is an integer between  0  and  graph.length - 1 . There are no self edges or parallel edges:  graph[i]  does not contain  i , and it doesn't contain any element twice.
  • graph  will have length in range  [1, 100] .
  • graph[i]  will contain integers in range  [0, graph.length - 1] .
  • graph[i]  will not contain  i  or duplicate values.
  • The graph is undirected: if any element  j  is in  graph[i] , then  i  will be in  graph[j] .

  • Have you met this question in a real interview?  Yes
    Example
    Example 1:
    Input: [[1,3], [0,2], [1,3], [0,2]]
    Output: true
    Explanation: 
    The graph looks like this:
    0----1
    |    |
    |    |
    3----2
    We can divide the vertices into two groups: {0, 2} and {1, 3}.
    
    Example 2:
    Input: [[1,2,3], [0,2], [0,1,3], [0,2]]
    Output: false
    Explanation: 
    The graph looks like this:
    0----1
    | \  |
    |  \ |
    3----2
    We cannot find a way to divide the set of nodes into two independent subsets.

    해법 1: 넓이 우선
    class Solution {
    public:
        /**
         * @param graph: the given undirected graph
         * @return:  return true if and only if it is bipartite
         */
        bool isBipartite(vector> &graph) {
            // Write your code here
            int n = graph.size();
            vector visit(n, 0);
            queue qu;
            int levelcount = 0;
            for (int i = 0; i < n; i++) {
                if (visit[i] != 0) {
                    continue;
                }
                qu.push(i);
                visit[i] = 1;
                levelcount = 1;
                while (!qu.empty()) {
                    int nextlevelcount = 0;
                    while (levelcount > 0) {
                        int m = qu.front();
                        qu.pop();
                        levelcount--;
                        for (int j = 0; j < graph[m].size(); j++) {
                            if (visit[graph[m][j]] != 0) {
                                if (visit[graph[m][j]] == visit[m]) {
                                    return false;
                                } else {
                                    continue;
                                }
                            } else {
                                visit[graph[m][j]] = 0 - visit[m];
                                qu.push(graph[m][j]);
                                nextlevelcount++;
                            }
                        }
                    }
                    levelcount = nextlevelcount;
                }
            }
            return true;
        }
    };

    2. 깊이 우선
    특별히 남 의 코드 를 배우 고 간결 하 다
    class Solution {
    public:
        /**
         * @param graph: the given undirected graph
         * @return:  return true if and only if it is bipartite
         */
        bool isBipartite(vector> &graph) {
            // Write your code here
            int m = graph.size();
            if (m == 0) {
                return true;
            }
    
            vector visit(m, 0);
            // not connected tree
            for (int i = 0; i < m; i++) {
                if (visit[i] == 0) {
                    visit[i] = 1;
                    if (DFS(graph, i, 1, visit) == false) {
                        return false;
                    }
                }
            }
            return true;
        }
        
        bool DFS(vector> &graph, int lastnode, int lastcolor,
                 vector &visit) {
            for (int i = 0; i < graph[lastnode].size(); i++) {
                if (visit[graph[lastnode][i]] != 0) {
                    if (visit[graph[lastnode][i]] != 0 - lastcolor) {
                        return false;
                    } else {
                        continue;
                    }
                } else {
                    visit[graph[lastnode][i]] = 0 - lastcolor;
                    if(DFS(graph, graph[lastnode][i], 0 - lastcolor, visit) == false) {
                        return false;
                    }
                }
            }
            return true;
        }
        /*
        bool isBipartite(vector>& graph) {
            vector colors(graph.size());
            for (int i = 0; i < graph.size(); ++i) {
                if (colors[i] == 0 && !valid(graph, 1, i, colors)) {
                    return false;
                }
            }
            return true;
        }
        bool valid(vector>& graph, int color, int cur, vector& colors) {
            if (colors[cur] != 0) return colors[cur] == color;
            colors[cur] = color;
            for (int i : graph[cur]) {
                if (!valid(graph, -1 * color, i, colors)) {
                    return false;
                }
            }
            return true;
        }
        */
    };

     
    Topological Sorting
    Description
    Given an directed graph, a topological order of the graph nodes is defined as follow:
  • For each directed edge  A -> B  in graph, A must before B in the order list.
  • The first node in the order can be any node in the graph with no nodes direct to it.

  • Find any topological order for the given graph.
    You can assume that there is at least one topological order in the graph.
    Have you met this question in a real interview?  
    /**
     * Definition for Directed graph.
     * struct DirectedGraphNode {
     *     int label;
     *     vector neighbors;
     *     DirectedGraphNode(int x) : label(x) {};
     * };
     */
    
    class Solution {
    public:
        /*
         * @param graph: A list of Directed graph node
         * @return: Any topological order for the given graph.
         */
        vector topSort(vector& graph) {
            // write your code here
            vector res;
            //if (hascycle(graph)) {
            //    return res;
            //}
            unordered_set visit;
            stack reverseres;
            for (int i = 0; i < graph.size(); i++) {
                if (visit.find(graph[i]) == visit.end()) {
                    DFS(graph[i], visit, reverseres);
                }
            }
            while (!reverseres.empty()) {
                res.push_back(reverseres.top());
                reverseres.pop();
            }
            return res;
        }
        vector BFS(vector& graph) {
            vector res;
            int n = graph.size();
            if (n == 0) {
                return res;
            }
            unordered_map status;
            for (int i = 0; i < n; i++) {
                status[graph[i]] = 0;
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < graph[i]->neighbors.size(); j++) {
                    status[graph[i]->neighbors[j]]++;
                }
            }
            // find first null input nodes
            queue qu;
            for (int i = 0; i < n; i++) {
                if (status[graph[i]] == 0) {
                    qu.push(graph[i]);
                }
            }
            while(!qu.empty()) {
                DirectedGraphNode* tmp = qu.front();
                qu.pop();
                res.push_back(tmp);
                for (int j = 0; j < tmp->neighbors.size(); j++) {
                    status[tmp->neighbors[j]]--;
                    if (status[tmp->neighbors[j]] == 0) {
                        qu.push(tmp->neighbors[j]);
                    }
                }
            }
            return res;
        }
        vector BFS2(vector& graph) {
            vector res;
            int n = graph.size();
            if (n == 0) {
                return res;
            }
            unordered_map status;
            for (int i = 0; i < n; i++) {
                status[graph[i]] = 0;
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < graph[i]->neighbors.size(); j++) {
                    status[graph[i]->neighbors[j]]++;
                }
            }
            stack st;
            for (int i = 0; i < n; i++) {
                if (status[graph[i]] == 0) {
                    st.push(graph[i]);
                }
            }
            while (!st.empty()) {
                DirectedGraphNode* node = st.top();
                st.pop();
                res.push_back(node);
    
                for (int j = 0; j < node->neighbors.size(); j++) {
                    status[node->neighbors[j]]--;
                    if (status[node->neighbors[j]] == 0) {
                        st.push(node->neighbors[j]);
                    }
                }
            }
            return res;
        }
        void DFS(DirectedGraphNode* node, unordered_set& visit,
                 stack& reverseres) {
            visit.insert(node);
            for (int j = 0; j < node->neighbors.size(); j++) {
                if (visit.find(node->neighbors[j]) == visit.end()) {
                    DFS(node->neighbors[j], visit, reverseres);
                }
            }
            reverseres.push(node);
        }
        bool hascycle(vector& graph) {
            unordered_set topset;
            for (int i = 0; i < graph.size(); i++) {
                if (topset.find(graph[i]) != topset.end()) {
                    continue;
                }
                unordered_set localset;
                stack st;
                st.push(graph[i]);
                while (!st.empty()) {
                    DirectedGraphNode* node = st.top();
                    st.pop();
                    localset.insert(node);
                    topset.insert(node);
                    for (int j = 0; j < node->neighbors.size(); j++) {
                        if (localset.find(node->neighbors[j]) != localset.end()) {
                            return true;
                        }
                        st.push(node->neighbors[j]);
                    }
                }
            }
            return false;
        }
    };

     
    Shortest Path in Undirected Graph
    Description
    Give an  undirected graph , in which each edge's length is  1 , and give  two  nodes from the graph. We need to find the  length  of  the shortest path  between the given  two  nodes.
    Have you met this question in a real interview?  Yes
    Example
    Given graph =  {1,2,4#2,1,4#3,5#4,1,2#5,3} , and nodeA =  3 , nodeB =  5 .
    1------2  3
     \     |  | 
      \    |  |
       \   |  |
        \  |  |
          4   5
    

    return  1 .
    /**
     * Definition for Undirected graph.
     * struct UndirectedGraphNode {
     *     int label;
     *     vector neighbors;
     *     UndirectedGraphNode(int x) : label(x) {};
     * };
     */
    class Solution {
    public:
        /**
         * @param graph: a list of Undirected graph node
         * @param A: nodeA
         * @param B: nodeB
         * @return:  the length of the shortest path
         */
        int shortestPath(vector graph, UndirectedGraphNode* A, UndirectedGraphNode* B) {
            // Write your code here
            return specialSolution(graph, A, B);
        }
        int specialSolution(vector graph, UndirectedGraphNode* A, UndirectedGraphNode* B) {
            int n = graph.size();
            if (n == 0) {
                return 0;
            }
            unordered_map visit;
            queue qu;
            // init visit
            for (int i = 0; i < n; i++) {
                visit[graph[i]] = false;
            }
            
            // visit source
            qu.push(A);
            visit[A] = true;
            int level = -1;
            int levelcount = 1;
            
            // visit other nodes
            while (!qu.empty()) {
                level++;
                int newlevelcount = 0;
                while (levelcount > 0) {
                    UndirectedGraphNode* node = qu.front();
                    qu.pop();
                    if (node == B) {
                        return level;
                    }
                    int m = node->neighbors.size();
                    for (int i = 0; i < m; i++) {
                        if (visit[node->neighbors[i]] == true) {
                            continue;
                        }
                        qu.push(node->neighbors[i]);
                        newlevelcount++;
                    }
                    levelcount--;
                }
                levelcount = newlevelcount;
            }
            return 0;
        }
        int generalSolution(vector graph, UndirectedGraphNode* A, UndirectedGraphNode* B) {
            int n = graph.size();
            if (n == 0) {
                return 0;
            }
            unordered_map dist;
            unordered_map visit;
            int visitcount = 0;
            // init dist, visit
            for (int i = 0; i < n; i++) {
                dist[graph[i]] = INT_MAX;
                visit[graph[i]] = false;
            }
    
            // visit source node
            dist[A] = 0;
            visit[A] = true;
            visitcount = 1;
            int m = A->neighbors.size();
            for (int i = 0; i < m; i++) {
                if (visit[A->neighbors[i]] == true) {
                    continue;
                }
                dist[A->neighbors[i]] = 1;
            }
    
            // visit other nodes
            while (visitcount <= n) {
                // find min path
                UndirectedGraphNode * minnode = NULL;
                int minpath = INT_MAX;
                for (int i = 0; i < n; i++) {
                    if (visit[graph[i]] == true) {
                        continue;
                    }
                    if (dist[graph[i]] < minpath) {
                        minpath = dist[graph[i]];
                        minnode = graph[i];
                    }
                }
                if (minnode == NULL) {
                    break;
                } else {
                    int s = minnode->neighbors.size();
                    for (int i = 0; i < s; i++) {
                        if (visit[minnode->neighbors[i]] == true) {
                            continue;
                        }
                        if (dist[minnode] + 1 < dist[minnode->neighbors[i]]) {
                            dist[minnode->neighbors[i]] = dist[minnode] + 1;
                        }
                    }
                    visit[minnode] = true;
                    visitcount++;
                }
            }
            return (dist[B] == INT_MAX ? 0 : dist[B]);
        }
    };

     
    Clone Graph
    Description
    Clone an undirected graph. Each node in the graph contains a  label  and a list of its  neighbors .
    How we serialize an undirected graph:
    Nodes are labeled uniquely.
    We use  #  as a separator for each node, and  ,  as a separator for node label and each neighbor of the node.
    As an example, consider the serialized graph  {0,1,2#1,2#2,2} .
    The graph has a total of three nodes, and therefore contains three parts as separated by  # .
  • First node is labeled as  0 . Connect node  0  to both nodes  1  and  2 .
  • Second node is labeled as  1 . Connect node  1  to node  2 .
  • Third node is labeled as  2 . Connect node  2  to node  2  (itself), thus forming a self-cycle.

  • Visually, the graph looks like the following:
       1
      / \
     /   \
    0 --- 2
         / \
         \_/

    Have you met this question in a real interview?  Yes
    Example
    return a deep copied graph.
    /**
     * Definition for undirected graph.
     * struct UndirectedGraphNode {
     *     int label;
     *     vector neighbors;
     *     UndirectedGraphNode(int x) : label(x) {};
     * };
     */
    
    
    class Solution {
    public:
        /*
         * @param node: A undirected graph node
         * @return: A undirected graph node
         */
        UndirectedGraphNode* cloneGraph(UndirectedGraphNode* node) {
            // write your code here
            if (node == NULL) {
                return NULL;
            }
            unordered_map status;
            queue qu;
            // create new nodes pairs
            qu.push(node);
            while (!qu.empty()) {
                UndirectedGraphNode* tmp = qu.front();
                qu.pop();
                UndirectedGraphNode* newnode = new UndirectedGraphNode(tmp->label);
                status[tmp] = newnode;
                for (int i = 0; i < tmp->neighbors.size(); i++) {
                    if (status.find(tmp->neighbors[i]) == status.end()) {
                        qu.push(tmp->neighbors[i]);
                    }
                }
            }
            // build graph
            unordered_map::iterator it;
            for (it = status.begin(); it != status.end(); it++) {
                UndirectedGraphNode* tmp = it->first;
                for (int i = 0; i < tmp->neighbors.size(); i++) {
                    status[tmp]->neighbors.push_back(status[tmp->neighbors[i]]);
                }
            }
            return status[node];
        }
    };

     
     
     

    좋은 웹페이지 즐겨찾기