☰

Γράφος με πίνακα

Υλοποίηση με πίνακα για μη κατευθυνόμενο γράφο

Στην υλοποίηση με πίνακα, αντιστοιχούμε έναν γράφο με κορυφές έστω Ν σε έναν πίνακα Ν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;
}