图的遍历-广度优先

奥普瓯江

原理：


备注：



代码：

#include <stdio.h>
#include <stdlib.h>
#define MAX 9


typedef struct list
{
    int data;
    struct list *next;
}list, *lists;

typedef struct dack
{
    char litte;
    int Blo;
    list *happy;
}dack;
void get_list(list **happy);
//void print_list(list *happy);
void loop_list(dack OK[MAX]);
void free_list(list *temp);

void free_list(list *temp)      //释放
{
    if(!temp)
    {
        return;
    }
    free_list(temp->next);
    free(temp);
}

void loop_list(dack OK[MAX])            //广度优先遍历
{
    list *temp;                 //临时变量
    int i, S = 0;

    for(int j = 0; j < MAX; j++)           //遍历每一个节点A-I
    {
        temp = OK[j].happy;                 //把赋予temp初始变量，这个初始变量是每个节点的初始变量A的初始变狼B的初始变量等等
        i = j;
        while(1)                            //循环每个节点后的变量
        {
            if(OK[i].Blo != 1)               //如果这个节点被打印过就不对该几点进行执行输出
            {

                printf("%c", OK[i].litte);
                OK[i].Blo = 1;                //标记该节点证明其被输出过
                S++;
                if(S > MAX)                   //减少遍历次数，如果前几个节点已经全部遍历完整个图及结束函数，后面的节点就不用遍历了
                {
                    return;
                }
            }
            if(temp == NULL)                  //如果该节点以执行到最后空的位置及跳出while循环
            {
                break;
            }
            else
            {
                i = temp->data;                 //未执行到连边最后的位置则将该位置链表所包含的数据传给i使得其继续循环
            }
            temp = temp->next;                  //链表向后循环
        }
    }
}

/*void print_list(list *happy)        //打印输出
{
    while(happy)
    {
        printf("%3d", happy->data);
        happy = happy->next;
    }
}*/

void get_list(list **happy)         //生成链表及顶点
{
    list *temp, *tail;

    int A = 0;

    while(1)
    {
        scanf("%d", &A);
        if(A >= 0 && A <= 9)
        {
            temp = (list *)malloc(sizeof(list ));
            temp->data = A;
            temp->next = NULL;          //复制最后一个指针如没有数据赋值为NULL，这个赋值在first_list函数中会使用到

            if(*happy == NULL)
            {
                *happy = temp;
            }
            else
            {
                tail->next = temp;
            }
            tail = temp;

        }
        else
        {
            break;
        }

    }
}

int main()
{
    dack first[MAX];

    first[0].litte = 'A';
    first[1].litte = 'B';
    first[2].litte = 'C';
    first[3].litte = 'D';
    first[4].litte = 'E';
    first[5].litte = 'F';
    first[6].litte = 'G';
    first[7].litte = 'H';
    first[8].litte = 'I';


    for(int i = 0; i < MAX; i++)
    {
        first[i].happy = NULL;
        first[i].Blo = 0;
        get_list(&first[i].happy);
    }


    loop_list(first);       //传入的数据为first[0].happy的指针

    for(int i = 0; i < MAX; i++)
    {
        free_list(first[i].happy);
    }

    /* for(int i = 0; i < MAX; i++)
    {
        printf("%c", first[i].litte);
        print_list(first[i].happy);
        putchar('\n');
    }*/


    return 0;
}

输入输出结果：




print_list函数输入输出结果：


备注：用于印证广度遍历输出

zhangjinxuan

This word is NB!