The number of connected components of a given graph after deleting the given Q vertices

After removing Q specified vertices, the number of disconnected subgraphs created by the remaining vertices in the graph is represented by the count of connected components. There are no edge connections between individual components; instead, each connected component consists of a collection of vertices connected by an edge. Due to the removal of Q vertices, some vertices may become orphaned, causing connections to collapse and new components to form. This method aims to determine how many disconnected subgraphs there will be in the end. Many applications, including network analysis, social network research, and optimization methods, require knowledge of the number of connected components.

usage instructions

• Kosaraju Algorithm

• Matrix-based method

Kosaraju algorithm

After removing Q specified vertices from the graph, Kosaraju's algorithm is used to determine the number of linked components in the network. It uses depth-first search (DFS) in two passes. It studies the original graph in the first pass to obtain the "completion time" for each vertex. In the second pass, the graph is transposed (the directions of all edges are reversed), and DFS is applied to the transformed graph starting from the vertex with the longest completion time. This method determines the number of linked components in the changed graph, exposing the number of broken subgraphs after vertex deletion by ignoring deleted Q vertices in the process.

algorithm

• To store the vertices of the initial DFS channel, create an empty stack.

• On the original graph, run the first DFS traversal:

  Use DFS to explore components of connected vertices starting from unexplored vertices.

  When all vertices surrounding a vertex have been visited, Mark accesses the vertex and pushes it onto the stack.

• Reverse the direction of each edge to transpose the shape.

• For the second DFS pass, create a boolean array to keep track of visited vertices.

• Run the modified graph through a second DFS pass:

  Remove each vertex from the stack in turn.

  Use DFS to explore the relevant components of the vertices (if none) are not accessed or destroyed (not in Q). Throughout the process, Mark visited the apex.

• After removing Q vertices, the count of connected components is equal to the number of calls to the second DFS.

• After removing Q vertices, this process generates the number of connected components in the network.

Example

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void dfs1(int vertex, vector<vector<int>>& graph, vector<bool>& visited, stack<int>& stk) {
    visited[vertex] = true;
    for (int neighbor : graph[vertex]) {
        if (!visited[neighbor])
            dfs1(neighbor, graph, visited, stk);
    }
    stk.push(vertex);
}

void dfs2(int vertex, vector<vector<int>>& transpose_graph, vector<bool>& visited) {
    visited[vertex] = true;
    for (int neighbor : transpose_graph[vertex]) {
        if (!visited[neighbor])
            dfs2(neighbor, transpose_graph, visited);
    }
}

int kosaraju(int N, vector<vector<int>>& graph, vector<vector<int>>& transpose_graph, vector<int>& Q) {
    vector<bool> visited(N + 1, false);
    stack<int> stk;

    for (int i = 1; i <= N; i++) {
        if (!visited[i])
            dfs1(i, graph, visited, stk);
    }

    fill(visited.begin(), visited.end(), false);

    for (int i = 0; i < Q.size(); i++) {
        visited[Q[i]] = true;
    }

    int count = 0;
    while (!stk.empty()) {
        int vertex = stk.top();
        stk.pop();
        if (!visited[vertex]) {
            dfs2(vertex, transpose_graph, visited);
            count++;
        }
    }

    return count;
}

int main() {
    int N = 7; 
    int M = 8; 
    int E = 2; 

    vector<vector<int>> graph(N + 1);
    vector<vector<int>> transpose_graph(N + 1);

    vector<pair<int, int>> edges = {{1, 2}, {2, 3}, {3, 1}, {2, 4}, {4, 5}, {5, 6}, {6, 4}, {7, 6}};

    for (const auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        graph[u].push_back(v);
        transpose_graph[v].push_back(u);
    }

    vector<int> Q = {3, 4};

    int result = kosaraju(N, graph, transpose_graph, Q);
    cout << result << endl;

    return 0;
}

Output

5

Matrix-based method

Adjacency matrix or adjacency list is used to represent graphs in matrix-based methods. Then remove Q specified vertices from the matrix. The number of connected components of the changed graph is then determined by using a graph traversal algorithm such as depth-first search (DFS) or breadth-first search (BFS). Records traversed vertices to prevent reprocessing. The count of connected components in the graph after removing Q vertices corresponds to the number of times the traversal method has been run. This method can efficiently compute link component counts for different graph analysis and network related applications.

algorithm

• Use adjacency matrix or adjacency list to represent the graph.

• Modify the graph by removing the specified Q vertices from the matrix or list.

• Set a variable to track the number of connected components.

• Initially iteratively updates each vertex in the graph.

• Apply a graph traversal algorithm (DFS or BFS) to each unexplored vertex.

• Mark vertices visited during the traversal to prevent reprocessing.

• Continue traversing until all vertices related to the initial vertex have been seen.

• For each unique set of interconnected vertices found, increase the number of connected components in the equation by 1.

• To access every vertex in the updated graph, repeat steps 5 through 8 as needed.

• After removing the required vertices, the total number of disconnected subgraphs in the graph is represented by the final value of the connected component count.

Example

#include <iostream>
#include <vector>
using namespace std;

void dfs(vector<vector<int>>& graph, vector<bool>& visited, int node) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(graph, visited, neighbor);
        }
    }
}

int countReachableNodes(vector<vector<int>>& graph) {
    int N = graph.size();
    vector<bool> visited(N, false);
    int count = 0;

    for (int i = 0; i < N; ++i) {
        if (!visited[i]) {
            dfs(graph, visited, i);
            count++;
        }
    }

    return count;
}

int main() {
    // Create the graph (Adjacency List representation)
    vector<vector<int>> graph = {
        {1},
        {0, 2},
        {1},
        {4},
        {3}
    };

    int reachableNodes = countReachableNodes(graph);
    cout << "Number of nodes accessible from all other nodes: " << reachableNodes << endl;

    return 0;
}

Output

Number of nodes accessible from all other nodes: 2

in conclusion

In summary, a key metric in network analysis and related fields is the number of connected components remaining in the graph after removing a certain number of vertices. Both matrix-based methods and Kosaraju's algorithm provide efficient ways to compute this count. Matrix-based methods use graph traversal algorithms such as DFS or BFS on the redesigned graph to efficiently find linked components, while the Kosaraju algorithm uses depth-first search in two traversals to identify strongly connected components. Both methods produce reliable results even after removing some vertices, helping to understand the connectivity and structural characteristics of the graph. The properties of the graph and the specific requirements of the current challenge determine the method to be used.

The above is the detailed content of The number of connected components of a given graph after deleting the given Q vertices. For more information, please follow other related articles on the PHP Chinese website!