How to create adjacency matrix?
- We can represent the graph with adjacency matrix.
- It is 2 dimensional array.
- It represents presence of edges between vertices.
- This is the implementation of Adjacency matrix as a 2D array.
- If the edge between vertices – we fill the value with 1
- If no edge, we insert 0 into that location.
- If the number of vertices are ‘n’.
- Then maximum number of edges are n*(n-1).
| #include<stdio.h> #define max 10 int adj[max][max]; int n; void create(); void display(); int main() { create(); display(); return 0; } void create() { int src, dest, edges, i; printf(“Enter number of nodes : “); scanf(“%d”, &n); edges = n*(n-1); for(i=1 ; i<=edges ; i++) { printf(“Enter Edge %d(0 0)to Quit : “, i); scanf(“%d %d”, &src, &dest); if(src==0 && dest==0) break; if(src>n || dest>n || src<1 || dest<1) { printf(“Invalid edge \n”); i–; } else { adj[src][dest] = 1; } } } void display() { int i, j; for(i=1 ; i<=n ; i++) { for(j=1 ; j<=n ; j++) { printf(“%4d”, adj[i][j]); } printf(“\n”); } } |
| #include<stdio.h> int cost[10][10]; int visited[10] = {0}; int min=0, min_cost=0; int n, ne=1, a=0, b=0, u=0, v=0, i, j; int main(){ printf(“Enter number of vertices in Graph : “); scanf(“%d”, &n); printf(“Enter Matrix with weights : \n”); for(i=1 ; i<=n ; i++){ for(j=1 ; j<=n ; j++) { scanf(“%d”, &cost[i][j]); if(cost[i][j]==0){ cost[i][j] = 999; } } } visited[1] = 1; while(ne < n){ for(i=1, min=999 ; i<=n ; i++){ for(j=1 ; j<=n ; j++){ if(cost[i][j] < min){ if(visited[i] != 0){ min = cost[i][j]; a=u=i; b=v=j; } } } } if(visited[u]==0 || visited[v]==0){ printf(“Edge %d : (%d to %d) cost : %d \n”, ne++, a, b, min); min_cost = min_cost + min; visited[b]=1; } cost[a][b] = cost[b][a] = 999; } printf(“Minimum cost : %d \n”, min_cost); return 0; } |