Γράφος με πίνακα
Υλοποίηση με πίνακα για μη κατευθυνόμενο γράφο
Στην υλοποίηση με πίνακα, αντιστοιχούμε έναν γράφο με κορυφές έστω Ν σε έναν πίνακα ΝxN.
Για κάθε ακμή ανάμεσα έστω στις κορυφές x και y θέτω την τιμή 1 στα στοιχεία του πίνακα (x,y) και (y,x).
Στις κορυφές που δεν υπάρχει ακμή η αντίστοιχη τιμή στα στοιχεία του πίνακα είναι 0.
Στο παρακάτω παράδειγμα για την ακμή (2,3) η αντίστοιχη τιμή στον πίνακα (2,3) και (3,2) είναι 1.
#include <stdio.h> #include <stdlib.h> #define MAX 5 /* * defines a struct named Graph * the variable 'vertices' holds the number of current vertices */ typedef struct { int pinax[MAX][MAX]; int vertices; } Graph; /* * creates a new graph * sets vertices = 0 */ void create(Graph *g) { int i, j; for(i = 0; i < MAX; i++) { for(j = 0; j < MAX; j++) { g->pinax[i][j] = 0; } } g->vertices = 0; } /* * checks whether a graph is empty * returns 1 if yes 0 otherwise */ int isEmpty(Graph g) { if(g.vertices == 0) return 1; else return 0; } /* * checks whether a graph is full * returns 1 if yes or else 0 */ int isFull(Graph g) { if(g.vertices == MAX) return 1; else return 0; } /* * checks whether a vertex is part of a graph * returns 1 if successful or else 0 */ int isVertex(Graph g, int p) { if(p>0 && p <= g.vertices) return 1; else return 0; } /* * adds vertex at the end of the graph * returns index of vertex if successful or else returns 0 */ void addVertex(Graph *g) { g->vertices++; g->pinax[g->vertices - 1][g->vertices - 1] = 1; } /* * deletes last vertex of the graph * returns index of vertex if successful or else 0 */ void delLastVertex(Graph *g) { int i; for(i=0; i<MAX; i++) { g->pinax[g->vertices - 1][i] = 0; g->pinax[i][g->vertices - 1] = 0; } g->vertices--; } /* * adds edge between vertices x and y * must have been checked whether vertices belong to the graph */ void addEdge(Graph *g, int x, int y) { g->pinax[x-1][y-1] = 1; g->pinax[y-1][x-1] = 1; } /* * deletes edge between vertices x and y * must have been checked whether vertices belong to the graph */ void delEdge(Graph *g, int x, int y) { g->pinax[x-1][y-1] = 0; g->pinax[y-1][x-1] = 0; } /* * checks whether two vertices are connected * returns 1 if true, 0 if not */ int isNeighbor(Graph g, int x, int y) { if((g.pinax[x - 1][y - 1] == 1) && (g.pinax[y - 1][x - 1] == 1)) return 1; else return 0; } /* * returns the number of nodes */ int getNumOfVertices(Graph g) { return g.vertices; } /* * prints graph as a table */ void printGraph(Graph g) { int i, j; for(i = 0; i < MAX; i++) { for(j = 0; j < MAX; j++) { printf("%d\t", g.pinax[i][j]); } printf("\n"); /* line break */ } } int main() { Graph g; create(&g); int temp, temp1, temp2; int i=100; do { puts("1. Create New Graph"); puts("2. Add Vertex at End"); /* adds a new node at the end of the graph */ puts("3. Delete Last Vertex"); /* deletes last Vertices of the graph */ puts("4. Add Edge Between"); /* adds a new Edge between two vertices */ puts("5. Delete Edge Between"); /* deletes Edge between two vertices */ puts("6. Get Number of Vertices"); /* gets number of Vertices */ puts("7. Check if Vertex Exists"); /* Check if Vertex Exists */ puts("8. Check if Neighbors"); /* Check if Neighbors */ puts("9. Print Table"); /* prints the table */ puts("0. Exit\n"); scanf("%d", &i); //system("clear"); /* UNIX */ //system("cls"); /* DOS */ switch(i) { case 1: /* creates a graph */ create(&g); break; case 2: /* adds a new node at the end of the graph */ if(isFull(g)) { puts("oops, Graph is full\n"); } else { addVertex(&g); puts("Vertex added\n"); } break; case 3: if(isEmpty(g)) { puts("oops, graph is empty\n"); break; } else { delLastVertex(&g); puts("Vertex deleted"); } break; case 4: /* adds a new Edge between two vertices */ printf("Give first vertex: "); scanf("%d", &temp1); if(!isVertex(g, temp1)) { printf("oops, Vertex %d does not exist\n", temp1); break; } printf("Give second vertex: "); scanf("%d", &temp2); if(!isVertex(g, temp2)) { printf("oops, Vertex %d does not exist\n", temp2); break; } addEdge(&g, temp1, temp2); break; case 5: /* deletes Edge between two vertices */ printf("Give first vertex: "); scanf("%d", &temp1); if(!isVertex(g, temp1)) { printf("oops, Vertex %d does not exist\n", temp1); break; } printf("Give second vertex: "); scanf("%d", &temp2); if(!isVertex(g, temp2)) { printf("oops, Vertex %d does not exist\n", temp2); break; } delEdge(&g, temp1, temp2); break; case 6: /* gets number of Vertices */ printf("Number of Vertices: %d\n", getNumOfVertices(g)); break; case 7: /* Check if Vertex Exists */ printf("Give vertex to check: "); scanf("%d", &temp); if(isVertex(g, temp)) printf("Vertex %d exists.\n", temp); else printf("Vertex %d does NOT exist.\n", temp); break; case 8: /* Check if Neighbors */ printf("Give first vertex: "); scanf("%d", &temp1); if(!isVertex(g, temp1)) { printf("oops, Vertex %d does not exist\n", temp1); break; } printf("Give second vertex: "); scanf("%d", &temp2); if(!isVertex(g, temp2)) { printf("oops, Vertex %d does not exist\n", temp2); break; } if(isNeighbor(g, temp1, temp2)) { printf("yes, they are neighbors\n"); } else { printf("oops, they are NOT neighbors\n"); } break; case 9: //printGraph(g); break; case 0: i=0; break; default: break; } puts("------------------------------------"); printGraph(g); puts("------------------------------------\n"); } while(i>0 && i<10); getchar(); return 0; }