割点和桥

2025年3月17日 | 阅读 3 分钟

关节点：移除某个特定顶点可能会导致其图数据结构中与其分量关联的边数增加。这些点称为关节点。

它们代表提供给机器用于遍历或预测的每个网络中的漏洞。为了使用暴力方法检查漏洞，我们手动选择并检查每个顶点，并查看它是否是关节点，或者分量的总数是否比顶点增加。

伪代码算法，返回关节点的总数

# Here, we are writing down the algorithm to demonstrate the concept of 
# Articulation Points and Bridges with their edge cases, functions, and algorithmic
# loops included articulating the brute force approach 
function find_articulation_points(adj[][], V)
    count = 0
    for i = 0 to V
        visited[i] = false
    initial_val = 0 
    for i = 0 to V
        if visited[i] == false
            DFS(adj, V, visited, i)
            initial_val = initial_val+1
# the below for loop code snippet help us with looping over the entire graph
    for i=0 to V
        for j = 0 to V
            visited[j] = false
            copy[j] = adj[i][j]
            adj[i][j]=adj[j][i]=0
# for loop code snippet helping us with mapping the visited nodes in a graph
        nval = 0
        for j= 0 to V
            if visited[j] == false AND j != i
                nval = nval + 1
                DFS(adj, n, visited, j)
# edge case shielding for the visited nodes in a graph data structure algorithm
        if nval > initial_val
            count = count + 1
        for j= 0 to V
            adj[i][j] = adj[j][i] = copy[j]
            # after the traversal, it returns us the number of articulation points
            # of the given graph structure
    return count
    # end of the Pseudocode algorithm of articulation points 
    # in a graph data structure

伪代码

# Here, we are writing down the algorithm to demonstrate the concept of 
# Articulation Points and Bridges with their edge cases, functions, and algorithmic
# loops included articulating the brute force approach     
time = 0
function DFS(adj[][], disc[], low[], visited[], parent[], AP[], vertex, V)
        visited[vertex] = true
        disc[vertex] = low[vertex] = time+1
        child = 0
    # the below for loop code snippet help us with looping over the entire graph
        for i = 0 to V
                if adj[vertex][i] == true
                        if visited[i] == false
                                child = child + 1
# for loop code snippet helping us with mapping the visited nodes in a graph
                                parent[i] = vertex
                                DFS(adj, disc, low, visited, parent, AP, i, n, time+1)
                                low[vertex] = minimum(low[vertex], low[i])
                                if parent[vertex] == nil and child > 1
                                        AP[vertex] = true
                                if parent[vertex] != nil and low[i] >= disc[vertex]
                                        AP[vertex] = true
# edge case shielding for the visited nodes in a graph data structure algorithm
                        else if parent[vertex] != i
                                low[vertex] = minimum(low[vertex], disc[i])
# after the traversal, it returns us the number of articulation points
# of the given graph structure
# end of the Pseudocode algorithm of articulation points 
# in a graph data structure

桥

桥是任意两个顶点（例如 x 和 y）之间的图。它被称为关节点。当连接/桥被移除时，它没有剩余的遍历路径。它也可能代表提供给机器或系统的每个网络中的漏洞。与关节点一样，我们还需要遍历整个图数据结构中的每个顶点，以暴力检查通过移除和检查顶点之间是否存在连接来获取可用路径。

伪代码

# Here, we are writing down the algorithm to demonstrate the concept of 
# Articulation Points and Bridges with their edge cases, functions, and algorithmic
# loops included articulating the brute force approach     
function find_bridges(adj[][], V, Edge[], E, isBridge[])
    for i = 0 to E
        adj[Edge[i].u][Edge[i].v]=adj[Edge[i].v][Edge[i].u]=0
        for j = 0 to V
            visited[j] = false
        Queue.Insert(Edge[i].u])
        visited[Edge[i].u] = true
        check = false
        while Queue.isEmpty() == false
            x = Queue.top()
            if x == Edge[i].v
                check = true
                BREAK
            Queue.Delete()
# the below for loop code snippet help us with looping over the entire graph
            for j = 0 to V
                if adj[x][j] == true AND visited[j] == false
                    Queue.insert(j)
                    visited[j] = true
        adj[Edge[i].u][Edge[i].v]=adj[Edge[i].v][Edge[i].u]=1
        if check == false
            isBridge[i] = true
# end of the Pseudocode algorithm of articulation points, bridges
    # in a graph data structure

下一主题使用 ++ 运算符执行 printf

割点和桥

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C 语言教程

C 语言控制语句

C 语言函数

C 语言数组

C 语言指针

C 语言动态内存

C 语言字符串

C 语言数学

C 语言结构体和联合体

C 语言文件处理

C 语言预处理器

C 语言命令行

C 语言程序

C 语言面试

选择题

C 语言编程测试

C 语言基础测试

C 语言控制语句测试

C 语言函数测试

C 语言数组测试

C 语言指针测试

C 语言字符串测试

C 语言结构体测试

C 语言预处理器测试

数学

C 语言杂项

割点和桥

相关帖子

阿姆斯特朗数

C 语言库函数

C 语言 itoa 函数

C 语言整数提升

C 语言 strdup() 函数

C 语言 strchr() 函数

ASCII vs Unicode

C 语言 isalnum() 函数

C 语言静态函数

C 语言 Fabs() 函数

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器