Scribd
Upload
1 views4 pages

Daa 5

This C program identifies articulation points in a graph using Depth First Search (DFS). It initializes a graph, takes user input for vertices and edges, and then applies DFS to find and print the articulation points. The program uses arrays to track discovery times, low values, and parent nodes for each vertex.

Uploaded by

bvvsivasundar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
1 views4 pages

Daa 5

This C program identifies articulation points in a graph using Depth First Search (DFS). It initializes a graph, takes user input for vertices and edges, and then applies DFS to find and print the articulation points. The program uses arrays to track discovery times, low values, and parent nodes for each vertex.

Uploaded by

bvvsivasundar
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

#include <stdio.

h>

#include <stdbool.h>

#include <limits.h>

#define MAX 100

int graph[MAX][MAX];

int visited[MAX];

int discovery[MAX];

int low[MAX];

int parent[MAX];

bool articulation_point[MAX];

int time_counter = 0;

void DFS(int u, int n) {

visited[u] = 1;

discovery[u] = low[u] = ++time_counter;

int children = 0;

for (int v = 0; v < n; v++) {

if (graph[u][v]) {

if (!visited[v]) {

children++;

parent[v] = u;

DFS(v, n);

low[u] = (low[u] < low[v]) ? low[u] : low[v];

if (parent[u] == -1 && children > 1) {


articulation_point[u] = true;

if (parent[u] != -1 && low[v] >= discovery[u]) {

articulation_point[u] = true;

} else if (v != parent[u]) {

low[u] = (low[u] < discovery[v]) ? low[u] : discovery[v];

void findArticulationPoints(int n) {

for (int i = 0; i < n; i++) {

parent[i] = -1;

visited[i] = 0;

articulation_point[i] = false;

for (int i = 0; i < n; i++) {

if (!visited[i]) {

DFS(i, n);

}
printf("Articulation Points: ");

for (int i = 0; i < n; i++) {

if (articulation_point[i]) {

printf("%d ", i);

printf("\n");

int main() {

int n, e;

printf("Enter the number of vertices and edges: ");

scanf("%d %d", &n, &e);

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

graph[i][j] = 0;

printf("Enter the edges (u, v): \n");

for (int i = 0; i < e; i++) {

int u, v;

scanf("%d %d", &u, &v);

graph[u][v] = 1;

graph[v][u] = 1;

findArticulationPoints(n);
return 0;

You might also like