(造轮子)C 创建队列和图实现广度优先算法(BFS)

C 通过链表、队列和图实现BFS算法(造轮子) 1、队列的链式存储结构

  队列的链式表示称为链队列，它实际上是一个同时带有队头指针和队尾指针的单链表。头指针指向队头节点，尾指针指向队尾节点，即单链表的最后一个节点(与顺序表存储结构不同)。
  队列链式存储类型描述：

struct Node{
    int data;
    struct Node* next;
};
typedef struct Node iNode;
struct Queue{
    iNode * front, *rear;
};
typedef struct Queue iQueue;

  链式队列基本 *** 作：

//初始化队列
void initQueue(iQueue * queue);
//判断是否为空
bool isQEmpty(const iQueue * queue);
//元素入队
void enQueue(iQueue * queue, int adddata);
//元素出队
bool deQueue(iQueue * queue, int * popdata);
//显示队列
void showQueue(const iQueue *queue);

2、图的邻接表法存储结构

  当一个图为稀疏图时，使用邻接矩阵显然要浪费大量的存储空间，而图的邻接表法结合了顺序存储和链式存储方法，大大减少不必要的空间的浪费。所谓邻接表，是指对图G中的每个顶点Vi建立一个单链表，第i个单链表的结点表示依附于顶点Vi的边表(对于有向图则成为出边表)。边表的头指针和顶点的数据信息采用顺序存储(称为顶点表)，所以在邻接表中存在两种节点：顶点表结点和边表结点。图的邻接表存储结构定义：

#define MaxVertexNum 20
struct Node{
    int data;
    struct Node* next;
};
typedef struct Node iNode;
struct Vertex{
    bool visittag ;
    iNode * head ;
};
typedef struct Vertex iVertex ;
struct Graph{
    iVertex graphVertex[MaxVertexNum];
    int vexnum;
};
typedef struct Graph iGraph ;

  图的邻接表存储方法有以下特点：

1. 若G为无向图，则所需的存储空间为O(|V| + 2|E|)；若G为有向图，所需的存储空间为O(|V| + |E|)。前者的倍数2是由于无向图中，每条边在邻接表中出现了两次。
2. 对于稀疏图，采用邻接表表示将极大的节省存储空间。
3. 在邻接表中，给定一节点，能很容易地找出它的所有临边，因为只需要读取它的邻接表。在邻接矩阵中，相同的 *** 作则需要扫描一行，花费的时间为O(n)。但是，若要确定给定的两个顶点间是否存在边，则在邻接矩阵中可以迅速查到，而在邻接表中则需要在相应结点对应的边表中查找另一个结点，效率较低。
4. 在有向图的邻接表表示中，求一个给定顶点的出度，只需计算其邻接表中的结点个书；但求其顶点的入度则需要遍历全部的邻接表。因此也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。
5. 图的邻接表表示并不唯一，因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，它取决于建立邻接表的算法及边的输入次序。

  图的一些基本 *** 作

//从文件读边的信息 建立邻接表结构的图
void initGraph(const char * filename, iGraph* graph);
//显示邻接表
void showGraph(const iGraph * graph);
//根据将图的结点的相邻节点，以读入顺序方向存储
void reverseGraph(iGraph* graph);
//释放图分配的的空间
void freeGraph(iGraph * graph);

3、线性表的链式表示：

  线性表的链时存储又称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为建立数据元素之间的线性关系,对每个链表结点，除存放元素自身的元素外，还需要存放一个指向其后继的指针单链表结构中data为数据域，存放数据元素；next为指针域，存放其后继结点的地址。
  单链表中结点类型的描述如下：

struct Node{
    int data;
    struct Node* next;
};

  单链表的基本 *** 作：

//显示链表元素
void showList(iNode * head);
//采用递归反向输出列表元素&&另一种方法：列表元素入栈然后出栈
void showBackListDigui(iNode * head);
//将单链表逆置(辅助空间复杂度为O(1))
iNode * reversList(iNode * head);
//释放链表空间
void freeList(iNode * head);

完整的程序：

#include
#include
#include

#define bool	_Bool
#define true	1
#define false	0
#define nullptr NULL
#define MaxVertexNum 20

struct Node{
    int data;
    struct Node* next;
};
typedef struct Node iNode;
struct Queue{
    iNode * front, *rear;
};
typedef struct Queue iQueue;
struct Vertex{
    bool visittag ;
    iNode * head ;
};
typedef struct Vertex iVertex ;
struct Graph{
    iVertex graphVertex[MaxVertexNum];
    int vexnum;
};
typedef struct Graph iGraph ;


void showList(iNode * head);
void showBackListDigui(iNode * head);
iNode * reversList(iNode * head);
void freeList(iNode * head);
void initGraph(const char * filename, iGraph* graph);
void showGraph(const iGraph * graph);
void reverseGraph(iGraph* graph);
void freeGraph(iGraph * graph);
void initQueue(iQueue * queue);
bool isQEmpty(const iQueue * queue);
void enQueue(iQueue * queue, int adddata);
bool deQueue(iQueue * queue, int * popdata);
void showQueue(const iQueue *queue);
void freeQueue(iQueue * queue);
void GraphBFS(iGraph * graph, iQueue *queue,int start);
void visitVertext(int n);
void addListToQueue(const iGraph * graph, iQueue* queue,iNode* head);

int main() {
    const char * filename = "/home/wang/projects/workspace/main/data-bfs-test";
    iGraph *graph = (iGraph *)malloc(sizeof(iGraph));
    initGraph(filename,graph);
    iQueue * queue = (iQueue *)malloc(sizeof(iQueue));
    initQueue(queue);
    showGraph(graph);
    reverseGraph(graph);
    showGraph(graph);
    GraphBFS(graph,queue,0);
    freeGraph(graph);
    freeQueue(queue);
}
 /*假设图所有节点都是连通的
  *广度优先算法BFS*/
void GraphBFS(iGraph* graph, iQueue * queue, int start)
{
    printf("BFS............\n");
    visitVertext(start);
    graph->graphVertex[start].visittag = true;
    enQueue(queue,start);
    while(!isQEmpty(queue)){
        int popdata;
        deQueue(queue,&popdata);
        iNode * curr = graph->graphVertex[popdata].head;
        while(curr){
            if(!graph->graphVertex[curr->data].visittag){
                visitVertext(curr->data);
                graph->graphVertex[curr->data].visittag = true;
                enQueue(queue,curr->data);
            }
            curr = curr->next;
        }
    }
    printf("\n");
}

/*  实现链表节点的反转
 *用到3个iNode指针nodea, nodeb, head*/
iNode * reversList(iNode* lhead)
{
    if(!lhead || !lhead->next){
//         printf("no need reverse\n");
        return lhead;
    }
    iNode *head = lhead;
    iNode *nodea = head->next;
    iNode * nodeb = head->next;
    head->next = nullptr;
    while(nodea){
        nodeb = nodea->next;
        nodea->next = head;
        head = nodea;
        nodea = nodeb;
    }
    return head;
}

/*  通过递归 反向输出链表中每个节点的值*/
void showBackListDigui(iNode* head)
{
    if(head->next)
        showBackListDigui(head->next);
    if(head) visitVertext(head->data);
}
/*visit节点n，打印节点值*/
void visitVertext(int nVertex)
{
    printf("%d ",nVertex);
}

/*  没什么大的作用，把图的某个节点的所有相邻节点放到队列中*/
void addListToQueue(const iGraph * graph, iQueue* queue, iNode* head)
{
    showList(head);
    iNode * lhead = head;
    while(lhead){
        if(!graph->graphVertex[lhead->data].visittag)
            enQueue(queue,lhead->data);
        lhead = lhead->next;
    }
    showQueue(queue);
}

/* 显示list元素的值 */
void showList(iNode* head)
{
    iNode * currnode = head;
    while(currnode){
        printf("%d ",currnode->data);
        currnode = currnode->next;
    }
    printf("\n");
}

/*从文本中读取图节点信息并建图
 *以邻接表的形式保存图信息*/
void initGraph(const char* filename, iGraph* graph)
{
    graph->vexnum = MaxVertexNum;
    int i =0 ;
    while(i < graph->vexnum){
        graph->graphVertex[i].head = nullptr;
        graph->graphVertex[i++].visittag = false;
    }
    int vernum, adjnum;
    FILE * filep = fopen(filename, "r");
    if(filep){
        while(fscanf(filep, "%d %d" ,&vernum,&adjnum)!= EOF){
            iNode * addadjnode = (iNode *)malloc(sizeof(iNode));
            if(addadjnode){
                addadjnode->data = adjnum;
                addadjnode->next = graph->graphVertex[vernum].head;
                graph->graphVertex[vernum].head = addadjnode;
            }
        }
        graph->vexnum = vernum ;
    }
    else printf("file erro");
    fclose(filep);
}
/* 显示构建的图的值 */
void showGraph(const iGraph* graph)
{
    int i = 0;
    printf("graph vertex %d\n",graph->vexnum);
    while(i < graph->vexnum){
        printf("vertex %d：",i);
        showList(graph->graphVertex[i].head);
        i++;
    }
}

/*  将图所有Vetex的相邻节点值的列表反转 */
void reverseGraph(iGraph* graph)
{
    int i = 0;
    while(i < graph->vexnum){
        graph->graphVertex[i].head = reversList(graph->graphVertex[i].head);
        i++;
    }
}

/*  释放Graph分配的空间 */
void freeGraph(iGraph* graph)
{
    printf("free graph\n");
    int i = 0;
    while(i < graph->vexnum){
        freeList(graph->graphVertex[i].head);
        i++;
    }
    free(graph);
}

/*  释放List的分配的空间*/
void freeList(iNode * head){
    printf("free list\n") ;
    iNode * curnode ;
    while(head){
        curnode = head;
        head = head->next ;
        free(curnode);
    }
}

/* 队列非空时d出front指向的节点
 * 将节点data传给popdata
 *释放队列d出的值的空间*/ 
bool deQueue(iQueue* queue, int* popdata)
{
    if(isQEmpty(queue))
        return false;
    iNode * qhead = queue->front->next;
    *popdata = qhead->data;
    queue->front ->next = qhead->next;
    if (qhead == queue->rear)
        queue->rear = queue->front;
    free(qhead);
    return true;
}
/* 将adddata入队列queue
 * 创建节点插入到队尾*/
void enQueue(iQueue* queue, int adddata)
{
    iNode * addnode = (iNode *)malloc(sizeof(iNode));
    addnode->next = nullptr;
    addnode->data = adddata;
    queue->rear->next = addnode;
    queue->rear = addnode;
}

/*  判断队列queue是否为空
 *空->true    非空->false*/
bool isQEmpty(const iQueue* queue)
{
    return (queue->front==queue->rear)?true:false;
}

/*  初始化队列queue */
void initQueue(iQueue* queue)
{
    iNode * ihead = (iNode *) malloc (sizeof(iNode));
    ihead->data = rand()%10;
    ihead->next = nullptr;
    queue->front = ihead;
    queue->rear = ihead;
}

/*显示当前Queue的值
 *queue 为空显示 queue empty
 * 非空传入头节点，作为链表输出元素值*/
void showQueue(const iQueue* queue)
{
    if(isQEmpty(queue))
        printf("queue empty\n");
    else {
        showList(queue->front->next);
    }
}

/*  释放Queue分配的空间 */
void freeQueue(iQueue * queue){
    iNode *head ;
    printf("free queue\n");
    freeList(queue->front);
    free(queue);
}

程序运行结果：

测试数据：

0 1
0 4
0 7
0 2
0 3
0 6
1 0
1 2
1 3
2 1
2 3
2 7
3 1
3 2
4 0
4 5
4 6
5 4
6 4
7 0
7 2