2. ARTICULATION POINTS

PHOTO EMBED

Sun Nov 03 2024 12:41:56 GMT+0000 (Coordinated Universal Time)

Saved by @varuntej #kotlin 

Task-2
Write a program to identify the articulation points present in a graph.
Algorithm:
Algorithm Art(u, v)
// u is a start vertex for depth first search. v is its parent if any
// in the depth first spanning tree. It is assumed that the global
// array dfn is initialized to zero and that the global variable
// num is initialized to 1. n is the number of vertices in G.
{
    dfn[u] := num; L[u] := num; num := num + 1;
    for each vertex w adjacent from u do`
    {
        if (dfn[w] = 0) then
        {
            Art(w, u);     // w is unvisited.
            L[u] := min(L[u], L[w]);
        }
        else if (w ≠ v) then L[u] := min(L[u], dfn[w]);
    }
}
Program:
#include <stdio.h>

int dfn[10], a[10][10], l[10], n, num = 1, children[10];
int artp[10]; // Array to store articulation points

// Function to find the minimum of two values
int min(int a, int b) {
    return (a > b ? b : a);
}

// Depth-first search to find articulation points
void art(int u, int v) {
    dfn[u] = num;
    l[u] = num;
    num++;
    children[u] = 0;

    for (int i = 1; i <= n; i++) {
        if (a[u][i] == 1) { // Check if there is an edge from u to i
            int w = i;
            if (dfn[w] == 0) { // w is unvisited
                children[u]++;
                art(w, u);

                // Update the low value of u for parent function calls
                l[u] = min(l[u], l[w]);

                // Check articulation point conditions
                if (v != -1 && l[w] >= dfn[u]) {
                    artp[u] = 1; // Mark u as an articulation point
                }
            } else if (w != v) { // Update low value of u for back edges
                l[u] = min(l[u], dfn[w]);
            }
        }
    }
}

// Main function
int main() {
    printf("Enter no. of vertices: ");
    scanf("%d", &n);

    int s;
    printf("Enter root vertex: ");
    scanf("%d", &s);

    printf("Enter adjacency matrix:\n");
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &a[i][j]);
        }
    }

    // Initialize arrays
    for (int i = 0; i <= n; i++) {
        dfn[i] = 0;
        l[i] = 0;
        children[i] = 0;
        artp[i] = 0;
    }

    printf("Articulation points are:\n");
    
    // Run DFS from the root vertex
    art(s, -1);

    // Check if the root is an articulation point (special case)
    if (children[s] > 1) {
        printf("%d\n", s);
    }

    // Print other articulation points
    for (int i = 1; i <= n; i++) {
        if (artp[i]) {
            printf("%d\n", i);
        }
    }

    return 0;
}
Output:
/tmp/96iN6R0Irx.o
Enter no. of vertices: 6
Enter root vertex: 1
Enter adjacency matrix:
0 1 0 1 0 0
1 0 1 0 0 0
0 1 0 1 1 1
1 0 1 0 0 0
0 0 1 0 0 0
0 0 1 0 0 0
Articulation points are:
3


=== Code Execution Successful ===
content_copyCOPY