Adjaceny Matrix OR Indegree Outdegree & Adjacency List & BFS or DFS

Adjacency Matrix & Indegree Out degree & Adjacency List & BFS or DFS

CODE

👇

1. #include<stdio.h>
2. #include<stdlib.h>
3. #define MAXSIZE 20
4. typedef struct node
5. {
6. int vertex;
7. struct node * next;
8. }NODE;
9. 
   
10. NODE *list[10];
11. 
    
12.    typedef struct 
13.     {
14.     int front, rear;
15.     int info[MAXSIZE];
16.     }QUEUE;
17.     
18.     void addq(QUEUE *pq, int n)
19.     {
20.     pq->info[++pq->rear] = n;
21.     }
22. 
    
23.     void initq(QUEUE *pq)
24.     {
25.     pq->front = pq->rear = -1;
26.     }
27. 
    
28. 
    
29.     int removeq(QUEUE *pq)
30.     {
31.     return pq->info[++pq->front];
32.     }
33. 
    
34.     int isempty(QUEUE *pq)
35.     {
36.     return (pq->front == pq->rear);
37.     }
38. 
    
39. void createmat(int m[10] [10], int n)
40. {
41. int i, j;
42. //char ans;
43. for(i=0; i<n; i++)
44. for(j=0;j<n; j++)
45. {
46. m[i] [j] = 0;
47. if(i != j)
48. {
49. printf("Is there an edge between %d->%d (1/0) :",i+1, j+1);
50. scanf("%d", &m[i][j]);
51. }
52. }
53. }
54. 
    
55. void dismat( int m[10][10], int n)
56. {
57. int i, j;
58. printf("\n The Adjacency Matrix is:\n");
59. for(i=0; i<n; i++)
60. {
61. for(j=0; j<n; j++)
62. printf("\t%d", m[i] [j]);
63. printf("\n");
64. }
65. }
66. 
    
67. void createlist( int m [10] [10], int n)
68. {
69. int i, j;
70. NODE *temp, *nn;
71. for(i=0; i<n; i++)
72. {
73. list[i] = NULL;
74. for(j=0; j<n; j++)
75. {
76. if(m[i][j] == 1)
77. {
78. nn=(NODE *)malloc(sizeof(NODE));
79. nn->vertex=j+1;
80. nn->next=NULL;
81. if(list[i] == NULL)
82. list[i] = temp = nn;
83. else
84. {
85. temp->next=nn;
86. temp=nn;
87. }
88. }
89. }
90. }
91. }
92. 
    
93. void dislist(int m[10] [10], int n)
94. {
95. NODE *temp;
96. int i;
97. printf("\n\nThe Adjacency list is:");
98. for(i=0; i<n; i++)
99. {
100. printf("\nv%d->",i+1);
101. temp=list[i];
102. while(temp)
103. {
104. printf("v%d ->",temp->vertex);
105. temp = temp->next;
106. }
107. printf("NULL");
108. }
109. }
110. 
     
111. void inout(int m[10] [10], int n)
112. {
113. int sumin, sumout, v, i, j;
114. printf("\n\nVertex  Indegree    Outdegree   Total Degree \n");
115. for(v=0; v<n; v++)
116. {
117. sumin = sumout = 0;
118. for(i=0; i<n; i++)
119. {
120. sumin = sumin + m[i][v]; //sum of column v
121. sumout = sumout + m[v][i]; //sum of row v
123. }
124. printf("  %d\t   %d\t\t%d\t   %d\n", v+1, sumin, sumout, sumin+sumout);
125. }
126. }
127. 
     
128. void recdfs(int m[10][10], int n, int v)
129. {
130. int w;
131. static int visited[20]={0};
132. visited[v]=1;
133. printf("v%d ",v+1);
134. for(w=0; w<n; w++)
135. {
136. if((m[v][w] == 1) && (visited[w] == 0))
137. recdfs(m, n, w);
138. }
139. }
140. 
     
141. void bfs(int m[10][10], int n)
142. {
143. int  v, w;
144. int visited[20] = {0};
145. QUEUE q;
146. initq(&q);
147. v=0; //starting vertex is 0
148. visited[v]=1;
149. addq(&q,v);
150. while(!isempty(&q))
151. {
152. v=removeq(&q);
153. printf("v%d ",v+1);
154. for(w=0; w<n; w++)
155. if((m[v][w] == 1) && (visited[w] == 0) )
156. {
157. addq(&q, w);
158. visited[w] = 1;
159. }
160. }
161. }
162. 
     
163. void main()
164. {
165. int m[10][10], n,w;
166. printf("\n Enter the number of vertices:");
167. scanf("%d",&n);
169. createmat(m,n);
170. dismat(m,n);
173. inout(m,n);
175. createlist(m,n);
176. dislist(m,n);
178. printf("\n\nThe Depth First Search Traversal  is:\t");
179. recdfs(m,n,w);
181. printf("\n\nThe Breadth First Traversal is:\t");
182. bfs(m,n);
183. }

//OUTPUT

/*

Enter the number of vertices:4

Is there an edge between 1->2 (1/0) :1

Is there an edge between 1->3 (1/0) :1

Is there an edge between 1->4 (1/0) :0

Is there an edge between 2->1 (1/0) :0

Is there an edge between 2->3 (1/0) :1

Is there an edge between 2->4 (1/0) :1

Is there an edge between 3->1 (1/0) :0

Is there an edge between 3->2 (1/0) :0

Is there an edge between 3->4 (1/0) :1

Is there an edge between 4->1 (1/0) :0

Is there an edge between 4->2 (1/0) :0

Is there an edge between 4->3 (1/0) :0

 The Adjacency Matrix is:

        0       1       1       0

        0       0       1       1

        0       0       0       1

        0       0       0       0

Vertex  Indegree    Outdegree   Total Degree

  1               0                   2                   2

  2               1                   2                   3

  3               2                   1                   3

  4              2                    0                   2

The Adjacency list is:

v1->v2 ->v3 ->NULL

v2->v3 ->v4 ->NULL

v3->v4 ->NULL

v4->NULL

The Depth First Search Traversal  is:   v1 v2 v3 v4

The Breadth First Traversal is:     v1 v2 v3 v4

*/

                                                     //ThE ProFessoR