Graph

Topic

Graph Representation

using vector for graph representation

class Graph
{
    int V; //No. of vertices
    //vector of vector representing edges
    vector<vector<int>> adj(V);
    //adding edges
    void addEdge(int v, int w)
    {
        adj[v].push_back(w); // Add w to v’s list.
    }
}

using STL list for graph representation

class graph
{
    int V; //No. of vertices
    //vector of vector representing edges
    list<adj> *adj;
    //adding edges
    void addEdge(int v, int w)
    {
        adj[v].push_back(w); // Add w to v’s list.
    }
}

using vector for graph node representation

class Node{
public:
    int val; //node's value
    vector<Node*> neighbors; //adjacent nodes that connected to this node
}

DFS and BFS

Depth First Search for a Graph

void Graph::DFSUtil(int v , bool visited[]) {
    visited[v] = true;
    cout << v << " ";
    
    for (auto it = adj[v].begin(); it != adj[v].end(); ++it) {
        if (!visited[*it]) {
            DFSUtil(*it, visited);
        }
    }
}

void Graph::DFS(){
    
    // Mark all the vertices as not visited
    bool *visited = new bool[V];
    for(int i = 0; i < V; i++)
        visited[i] = false;
    //run DFS from all unvisited nodes including disconnected graph
    for(int i = 0; i < V; i++)
        if(visited[i] == false)
            DFSUtil(i, visited);
}

133 Clone Graph(Q:A)
323 Number of Connected Components in an Undirected Graph(Q:A)

Using hashmap to deep copy current graph.

Breadth First Search for a Graph

void Graph::BFS(){
    bool *visited = new bool[V];
    for(int i = 0; i < V; i++)
        visited[i] = false;
    q.push(0);
    visited[0]=true;
    while(!q.empty()){
        for (auto it = adj[q.top()].begin(); it != adj[q.top()].end(); ++it) {
            if (!visited[*it]) {
                q.push(*it);
                cout<<*it<<" ";
                visited[*it]=true;
            }
        }
        q.pop();
    }
}

Detect Cycle & Topological Sort

Detect cycle in directed Graph using Topological Sort

1.create graph matrix 2.push all 0 degree nodes to queue 3.for each front node[index]: 3.1 pop this node 3.2 decrease degree from every node that has prerequisite node[index] 3.3 if degree is zero after decreased, then push this node to queue

vector<int> canFinish(int numCourses, vector<vector<int>>& prerequisites) {
                vector<vector<int>> edges(numCourses,vector<int>());
        queue<int> nodes;
        vector<int> indegrees(numCourses,0);
        vector<int> res;
        //x[0] courses to be taken, x[1] courses taken before x[0]
        for(auto x:prerequisites){
            edges[x[1]].push_back(x[0]);
            ++indegrees[x[0]];
        }

        //push all nodes that do not need prerequiste to the queue
        for(int i=0;i<indegrees.size();i++){
            if(indegrees[i]==0){
                nodes.push(i);
            }
        }
        //count number of nodes that can be learned 
        int visit_node=0;
        
        while(!nodes.empty()){
            int index=nodes.front();
            nodes.pop();
            visit_node++;

            res.push_back(index);
            for(auto i:edges[index]){
                indegrees[i]--;
                if(indegrees[i]==0){
                    nodes.push(i);
                }
            }
        }

        return visit_node==numCourses?res:vector<int>();
    }

207 Course Schedule(Q:A)
208 Course Schedule(Q:A)
310 Minimum Height Trees(Q:A)

Detect cycle in undirected Graph

bool checkCycle(vector<vector<int>> &graph, int index, vector<bool> &visited, int parent){
    visited[index]=true;
    for(int i=0;i<graph[index].size();i++){
        if(visited[graph[index][i]]!=true){
            if(checkCycle(graph,graph[index][i],visited,index)){
                return true;
            }
        }else{
            if(graph[index][i]!=parent){
                return true;
            }
        }
    }
    return false;
}

261 Graph Valid Tree(Q:A)