|
#include <stdio.h>
#include <stdlib.h>
#define QUEUE_MAX 10
typedef struct list
{
int num;//1-7
struct list* next;
}LIST;
typedef struct queue
{
int front;
int rear;
int num[QUEUE_MAX];
}QUEUE;
void init_queue(QUEUE* Q)
{
Q->front = 0;
Q->rear = 0;
}
int IS_EMPTY(QUEUE* Q)
{
if(Q->rear==Q->front)
return 1;
else
return 0;
}
int IS_FULL(QUEUE* Q)
{
if((Q->rear+1)%QUEUE_MAX==Q->front)
return 1;
else
return 0;
}
void en_queue(QUEUE* Q, int num)
{
if(IS_FULL(Q))
return;
Q->num[Q->rear] = num;
Q->rear = (Q->rear+1)%QUEUE_MAX;
}
int de_queue(QUEUE* Q)
{
if(IS_EMPTY(Q))
return -1;
int num;
num = Q->num[Q->front];
Q->front = (Q->front+1)%QUEUE_MAX;
return num;
}
void init_list_head(LIST** L)
{
*L = (LIST*)malloc(sizeof(LIST));
(*L)->num = 0;
(*L)->next = NULL;
}
LIST* create_new_node()
{
LIST* p = (LIST*)malloc(sizeof(LIST));
p->num = 0;
p->next = NULL;
return p;
}
void add_new_node(LIST* L, LIST* p)
{
p->next = L->next;
L->next = p;
}
int create_adjacency_matrix( LIST* L[7], int A[7][7])
{
int i;
int j;
for(i=0;i<7;i++)
{
init_list_head(&L[i]);
for(j=0;j<7;j++)
{
if(A[i][j]!=0)
{
LIST* p = create_new_node();
p->num = j+1;
add_new_node(L[i], p);
}
}
}
}
void print_adjacency_matrix(LIST* L[7])
{
int i;
LIST* p = NULL;
for(i=0;i<7;i++)
{
p = L[i]->next;
if(p!=NULL)
printf("%d:\t",i+1);
else
{
printf("%d:\n",i+1);
continue;
}
while(p!=NULL)
{
if(p->next!=NULL)
printf("%d->",p->num);
else
printf("%d\n",p->num);
p = p->next;
}
}
}
void count_in_degree(int in_degree[7], LIST* L[7])
{
int i;
LIST* p;
for(i=0;i<7;i++)
in_degree[i] = 0;
for(i=0;i<7;i++)
{
p = L[i]->next;
if(p==NULL)
continue;
while(p!=NULL)
{
in_degree[p->num-1]++;
p = p->next;
}
}
}
void print_array(int in_degree[7])
{
int i;
for(i=0;i<7;i++)
{
printf("%d:\t%d\n", i+1, in_degree[i]);
}
}
int find_zero_indegree(int in_degree[7])
{
int i;
for(i=0;i<7;i++)
{
if(in_degree[i]==0)
{
in_degree[i]--;
return i;
}
}
return -1;
}
void update_indegree(int i, LIST* L[7], int indegree[7])
{
LIST* p = L[i]->next;
while(p!=NULL)
{
indegree[p->num-1]--;
p = p->next;
}
}
int* count_top_sort(LIST* L[7], int in_degree[7])
{
int i;
int ret;
int* top_sort = (int*)malloc(sizeof(int)*7);
for(i=0;i<7;i++)
{
ret = find_zero_indegree(in_degree);
if(ret == -1)
{
printf("sorry\n");
return NULL;
}
update_indegree(ret, L, in_degree);
top_sort[i] = ret+1;
}
return top_sort;
}
int* bfs(LIST* L[7], int num)
{
QUEUE* Q = (QUEUE*)malloc(sizeof(QUEUE));
init_queue(Q);
en_queue(Q,num);
int currdist = 0;
int flag = 0;
int i = 0;
int ret = 0;
int* length = (int*)malloc(sizeof(int)*7);
int known[7];
for(i=0;i<7;i++)
{
length[i] = 0;
known[i] = 0;
}
for(i=0;i<7;i++)
{
ret = de_queue(Q);
LIST* p = L[ret-1]->next;
if(p == NULL)
continue;
currdist++;
while(p!=NULL)
{
en_queue(Q,p->num);
if(known[p->num-1] == 0)
{
flag++;
length[p->num-1] = currdist;
known[p->num-1] = 1;
}
p = p->next;
if(flag == 6)
return length;
}
}
}
int main(int argc, char *argv[])
{
int A[7][7] = {
{0,1,1,1,0,0,0},
{0,0,0,1,1,0,0},
{0,0,0,0,0,1,0},
{0,0,1,0,0,1,1},
{0,0,0,1,0,0,1},
{0,0,0,0,0,0,0},
{0,0,0,0,0,1,0}
};
LIST** L = (LIST**)malloc(sizeof(LIST)*7);
create_adjacency_matrix( L, A);
print_adjacency_matrix(L);
int* in_degree = (int*)malloc(sizeof(int)*7);
count_in_degree(in_degree, L);
printf("the in degrees are:\n");
print_array(in_degree);
int* topsort = count_top_sort(L, in_degree);
printf("the topsort are:\n");
print_array(topsort);
int B[7][7] = {
{0,1,0,1,0,0,0},
{0,0,0,1,1,0,0},
{1,0,0,0,0,1,0},
{0,0,1,0,1,1,1},
{0,0,0,0,0,0,1},
{0,0,0,0,0,0,0},
{0,0,0,0,0,1,0}
};
//LIST** LL = (LIST**)malloc(sizeof(LIST)*7);
create_adjacency_matrix( L, B);
printf("matrix B's adjacency is:\n");
print_adjacency_matrix(L);
int* dist = bfs(L, 3);
printf("the dist are:\n");
print_array(dist);
system("PAUSE");
return 0;
}
|
