图的存储—数组

#include
#include
#include

#define N 5

typedef struct _node_
{
 int vertex;
 struct _node_ *next;
} linknode, *linklist;

typedef struct
{
 linklist front, rear;
} linkqueue;

linkqueue *CreateEmptyQueue()
{
 linkqueue *lq;

 lq = (linkqueue *)malloc(sizeof(linkqueue));
 lq->front = lq->rear = (linklist)malloc(sizeof(linknode));
 lq->front->next = NULL;

 return lq;
}

int EmptyQueue(linkqueue *lq)
{
 return (lq->front == lq->rear);
}

void EnQueue(linkqueue *lq, int vertex)
{
 lq->rear->next = (linklist)malloc(sizeof(linknode));
 lq->rear = lq->rear->next;
 lq->rear->vertex = vertex;
 lq->rear->next = NULL;

 return;
}

int DeQueue(linkqueue *lq)
{
 linklist q;

 q = lq->front;
 lq->front = q->next;
 free(q);

 return lq->front->vertex;
}

int FirstAdj(int array[][N], int u)
{
 int j;

 for (j=0; j {
  if (array[u][j] == 1) return j;
 }

 return 0;
}

int NextAdj(int array[][N], int u, int v)
{
 int j;

 for (j=v+1; j {
  if (array[u][j] == 1) return j;
 }

 return -1;
}

 

//深度优先算法实现

void DFS(int array[][N], int s[N], int v)
{
 int u;

 printf("V%d ", v);
 s[v] = 1;
 u = FirstAdj(array, v);
 while (u >= 0)
 {
  if (s[u] == 0) DFS(array, s, u);
  u = NextAdj(array, v, u);
 }

 return;
}

 

//广度优先算法实现

void BFS(int array[][N], int s[N], int v)
{
 int u;
 linkqueue *lq;

 lq = CreateEmptyQueue();
 printf("V%d ", v);
 s[v] = 1;
 EnQueue(lq, v);

 while ( ! EmptyQueue(lq) )
 {
  v = DeQueue(lq);
  u = FirstAdj(array, v);
  while (u >= 0)
  {
   if (s[u] == 0)
   {
    printf("V%d ", u);
    s[u] = 1;
    EnQueue(lq, u);
   }
   u = NextAdj(array, v, u);
  }
 }

 return;
}

int main()
{
 int i, j, s[N] = {0};
 int array[N][N] = {{0}};

 while (scanf("%d,%d", &i, &j) == 2)
 {
  array[i][j] = array[j][i] = 1;
 }

 for (i=0; i {
  printf("V%d : ", i);
  for (j=0; j  {
   if (array[i][j] == 1) printf("V%d ", j);
  }
  printf("\n");
 }

 printf("DFS : ");
 DFS(array, s, 2);
 printf("\n");

 bzero(s, sizeof(s));
 printf("BFS : ");
 BFS(array, s, 2);
 printf("\n");

 return 0;
}