C++ Program to Find Number of Articulation points in a Graph

«
»
This C++ program displays the articulation points present inside a graph. An articulation point inside a graph is the vertex whose removal increases the number of connected components.

Here is the source code of the C++ program to display the nodes which are considered to be articulation points. This C++ program is successfully compiled and run on DevCpp, a C++ compiler.The program output is given below.

  1. /*
  2.  * C++ Program to Find Number of Articulation points in a Graph
  3.  */
  4. #include<iostream>
  5. #include<conio.h>
  6. using namespace std;
  7. int cnt = 0;
  8. struct node_info
  9. {
  10.     int no;
  11. }*q = NULL, *r = NULL;
  12. struct node
  13. {
  14.     node_info *pt;
  15.     node *next;
  16. }*top = NULL, *p = NULL, *np = NULL;
  17. void push(node_info *ptr)
  18. {
  19.     np = new node;
  20.     np->pt = ptr;
  21.     np->next = NULL;
  22.     if (top == NULL)
  23.     {
  24.         top = np;
  25.     }
  26.     else
  27.     {
  28.         np->next = top;
  29.         top = np;
  30.     }
  31. }
  32. node_info *pop()
  33. {
  34.     if (top == NULL)
  35.     {
  36.         cout<<"underflow\n";
  37.     }
  38.     else
  39.     {
  40.         p = top;
  41.         top = top->next;
  42.         return(p->pt);
  43.         delete(p);
  44.     }
  45. }           
  46. int topo(int *v, int am[][7], int i)
  47. {
  48.     q = new node_info;
  49.     q->no = i;
  50.     push(q);
  51.     v[i] = 1;
  52.     for (int j = 0; j < 7; j++)
  53.     {
  54.         if (am[i][j] == 0  || (am[i][j] == 1 && v[j] == 1))
  55.             continue;
  56.         else if(am[i][j] == 1 && v[j] == 0)
  57.         {
  58.             cnt++;
  59.             topo(v, am, j);
  60.         }
  61.     }
  62.     q = pop();
  63. }
  64. void addEdge(int am[][7], int src, int dest)
  65. {
  66.      am[src][dest] = 1;
  67.      am[dest][src] = 1;
  68.      return;
  69. }
  70. int main()
  71. {
  72.     int v[7], am[7][7], amt[7][7], c = 0, a, b, x = 0;
  73.     for (int i = 0; i < 7; i++)
  74.     {
  75.         v[i] = 0;
  76.     }
  77.     for (int i = 0; i < 7; i++)
  78.     {
  79.         for (int j = 0; j < 7; j++)
  80.         {
  81.             am[i][j] = 0;
  82.         }
  83.     }
  84.     while (c < 9)
  85.     {
  86.         cout<<"Enter the source and destination\n";
  87.         cin>>a>>b;
  88.         addEdge(am, a, b);
  89.         c++;
  90.     }
  91.     for (int i = 0; i < 7; i++)
  92.     {
  93.         for (int j = 0; j < 7; j++)
  94.         {
  95.             amt[i][j] = am[i][j];
  96.         }
  97.     }
  98.     for (int i = 0; i < 7; i++)
  99.     {
  100.         for(int j = 0; j < 7; j++)
  101.         {
  102.             am[i][j] = 0;
  103.             am[j][i] = 0;
  104.         }
  105.         if (i < 6)
  106.         {
  107.             topo(v, am, i + 1);
  108.         }
  109.         else
  110.         {
  111.             topo(v, am, 0);
  112.         }
  113.         if (cnt < 5)
  114.         {
  115.             cout<<endl<<i<<" is an articulation point"<<endl;
  116.         }
  117.         cnt = 0;
  118.         for (int j = 0; j < 7; j++)
  119.         {
  120.             am[i][j] = amt[i][j];
  121.             am[j][i] = amt[j][i];
  122.             v[j] = 0;
  123.         }
  124.         while (top != NULL)
  125.         {
  126.               pop();
  127.         }
  128.     }
  129.     getch();
  130. }

advertisement
Output:
 
Enter the source and destination
0
1
Enter the source and destination
0
5
Enter the source and destination
5
4
Enter the source and destination
4
6
Enter the source and destination
0
6
Enter the source and destination
6
2
Enter the source and destination
2
0
Enter the source and destination
3
5
Enter the source and destination
4
3
 
0 is an articulation point

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn