Data_Structure/作業/unit12/bfs/bfs.cpp

/* <20>ϧΪ<CFA7><CEAA>l<EFBFBD><6C>: <20>۾F<DBBE><46><EFBFBD>C<EFBFBD>P<EFBFBD>s<EFBFBD><73><EFBFBD>u<EFBFBD><75><EFBFBD>j<EFBFBD>M<EFBFBD>k(BFS)*/
#include <stdio.h>
#include <stdlib.h>
#define MAX_V 100  /*<2A>̤j<CCA4>`<60>I<EFBFBD><49>*/
#define TRUE 1
#define FALSE 0

/*<2A>w<EFBFBD>q<EFBFBD><71><EFBFBD>Ƶ<EFBFBD><C6B5>c*/
typedef struct node_tag {
    int vertex;
    struct node_tag *link;
} Node;

/*<2A>w<EFBFBD>q<EFBFBD><71><EFBFBD>C<EFBFBD><43><EFBFBD>c*/
typedef struct {
    int items[MAX_V];
    int front;
    int rear;
} Queue;

Node *adjlist[MAX_V+1];  /*<2A>ŧi<C5A7>۾F<DBBE><46><EFBFBD>C*/
int visited[MAX_V+1];    /*<2A>O<EFBFBD><4F><EFBFBD><EFBFBD><EFBFBD>I<EFBFBD>O<EFBFBD>_<EFBFBD>w<EFBFBD><77><EFBFBD>X*/
int total_vertex;

void build_adjlist(void);
void show_adjlist(void);
void bfs(int);
Node *searchlast(Node *);

/*<2A><><EFBFBD>C<EFBFBD>ާ@<40><><EFBFBD><EFBFBD>*/
Queue* createQueue() {
    Queue *q = (Queue*)malloc(sizeof(Queue));
    q->front = -1;
    q->rear = -1;
    return q;
}

int isEmpty(Queue* q) {
    return q->front == -1;
}

void enqueue(Queue* q, int value) {
    if(q->front == -1)
        q->front = 0;
    q->rear++;
    q->items[q->rear] = value;
}

int dequeue(Queue* q) {
    int item = q->items[q->front];
    if(q->front == q->rear) {
        q->front = -1;
        q->rear = -1;
    } else {
        q->front++;
    }
    return item;
}

int main()
{
    build_adjlist(); /*<2A>H<EFBFBD>۾F<DBBE><46><EFBFBD>C<EFBFBD><43><EFBFBD>ܹϧ<DCB9>*/
    show_adjlist();  /*<2A><><EFBFBD>ܦ<EFBFBD><DCA6>C<EFBFBD><43><EFBFBD><EFBFBD><EFBFBD><EFBFBD>*/
    puts("\n------Breadth First Search------");
    bfs(1);          /*<2A>ϧΤ<CFA7><CEA4>s<EFBFBD><73><EFBFBD>u<EFBFBD><75><EFBFBD>j<EFBFBD>M<EFBFBD>A<EFBFBD>H<EFBFBD><48><EFBFBD>I1<49><31><EFBFBD>ҩl<D2A9><6C><EFBFBD>I*/
    printf("\n");
    return 0;
}

void build_adjlist()
{
    FILE *fptr;
    Node *node,*lastnode;
    int vi,vj ,weight;
    fptr = fopen("dfs_1.dat", "r");
    if (fptr == NULL) {
        perror("dfs.dat");
        exit(0);
    }
    /* Ū<><C5AA><EFBFBD>`<60>I<EFBFBD>`<60><> */
    fscanf(fptr, "%d", &total_vertex);
    for (vi = 1; vi <= total_vertex; vi++) {
        /*<2A>]<5D>w<EFBFBD>}<7D>C<EFBFBD>ΦU<CEA6><55><EFBFBD>C<EFBFBD>ҩl<D2A9><6C>*/
        visited[vi] = FALSE;
        adjlist[vi] = (Node *)malloc(sizeof(Node));
        adjlist[vi]->vertex = vi;
        adjlist[vi]->link = NULL;
    }
    /* Ū<><C5AA><EFBFBD>`<60>I<EFBFBD><49><EFBFBD><EFBFBD> */
    for (vi = 1; vi <= total_vertex; vi++)
        for (vj = 1; vj <= total_vertex; vj++) {
            fscanf(fptr,"%d",&weight);
            /* <20><><EFBFBD><EFBFBD><EFBFBD>ɥH<C9A5>۾F<DBBE>x<EFBFBD>}<7D>榡<EFBFBD>x<EFBFBD>s,<2C>H1<48>N<EFBFBD><4E><EFBFBD>۾F
               0 <EFBFBD>N<EFBFBD><EFBFBD><EFBFBD><EFBFBD><EFBFBD>۾F<EFBFBD>A<EFBFBD>N<EFBFBD>۾F<EFBFBD><EFBFBD><EFBFBD>I<EFBFBD>쵲<EFBFBD>b<EFBFBD>U<EFBFBD><EFBFBD><EFBFBD>C<EFBFBD><EFBFBD> */
            if (weight != 0) {
                node = (Node *)malloc(sizeof(Node));
                node->vertex = vj;
                node->link = NULL;
                lastnode = searchlast(adjlist[vi]);
                lastnode->link = node;
            }
        }
    fclose(fptr);
}

/*<2A><><EFBFBD>ܦU<DCA6>۾F<DBBE><46><EFBFBD>C<EFBFBD><43><EFBFBD><EFBFBD><EFBFBD><EFBFBD>*/
void show_adjlist()
{
    int index;
    Node *ptr;
    puts("Head    adjacency nodes");
    puts("------------------------------");
    for (index = 1; index <= total_vertex; index++) {
        printf("V%-2d ",adjlist[index]->vertex);
        ptr = adjlist[index]->link;
        while (ptr != NULL) {
            printf("--> V%d ",ptr->vertex);
            ptr = ptr->link;
        }
        printf("\n");
    }
}

/*<2A>ϧΤ<CFA7><CEA4>s<EFBFBD><73><EFBFBD>u<EFBFBD><75><EFBFBD>j<EFBFBD>M*/
void bfs(int start)
{
    Queue* q = createQueue();
    Node* ptr;
    
    // <20>N<EFBFBD>_<EFBFBD>l<EFBFBD>`<60>I<EFBFBD>[<5B>J<EFBFBD><4A><EFBFBD>C
    enqueue(q, start);
    visited[start] = TRUE;
    
    while(!isEmpty(q)) {
        // <20>q<EFBFBD><71><EFBFBD>C<EFBFBD><43><EFBFBD>X<EFBFBD>`<60>I<EFBFBD>æL<C3A6>X
        int currentVertex = dequeue(q);
        printf("V%d ", currentVertex);
        
        // <20>N<EFBFBD>Ҧ<EFBFBD><D2A6>۾F<DBBE>B<EFBFBD><42><EFBFBD><EFBFBD><EFBFBD>X<EFBFBD><58><EFBFBD>`<60>I<EFBFBD>[<5B>J<EFBFBD><4A><EFBFBD>C
        ptr = adjlist[currentVertex]->link;
        while(ptr != NULL) {
            if(!visited[ptr->vertex]) {
                enqueue(q, ptr->vertex);
                visited[ptr->vertex] = TRUE;
            }
            ptr = ptr->link;
        }
    }
    
    free(q);
}

/*<2A>j<EFBFBD>M<EFBFBD><4D><EFBFBD>C<EFBFBD>̫<EFBFBD><CCAB>`<60>I<EFBFBD><49><EFBFBD><EFBFBD>*/
Node *searchlast(Node *linklist)
{
    Node *ptr;
    ptr = linklist;
    while (ptr->link != NULL)
        ptr = ptr->link;
    return ptr;
}