数据结构实验之图论二：基于邻接表的广度优先搜索遍历

淡淡的烟草味﹌ 2022-07-12 06:49 97阅读 0赞

think:  
1基于邻接表的广度优先搜索遍历其实需要学会建立按照结点大小顺序建立的邻接表和广度优先搜索遍历的队列思想  
2按照结点大小顺序建立的邻接表就是建立有序链表，在建立有序链表的过程中需要考虑头结点的数据存放，我直接把开始的结点放在头结点的数据域中，这样其实可以逐渐从一个点进行突破，后面可以讲数据域从一个数据扩展到另一个数据类型，相对其它模板，这样做减少了模板的通用性，但增加了模板的可塑性，使得模板可以不断扩展  
3广度优先搜索遍历需要明白其中的队列思想和广度优先搜索那种从近到远如同花朵的逆绽放，先将花蕊部分入队，然后逐渐从花蕊进行绽放，每绽放一个花瓣，就将其入队，旧花瓣的出队伴随着此花瓣带来的新花瓣的入队

[sdut原题链接][sdut]

数据结构实验之图论二：基于邻接表的广度优先搜索遍历  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
给定一个无向连通图，顶点编号从0到n-1，用广度优先搜索(BFS)遍历，输出从某个顶点出发的遍历序列。(同一个结点的同层邻接点，节点编号小的优先遍历）

Input  
输入第一行为整数n（0< n <100），表示数据的组数。  
对于每组数据，第一行是三个整数k，m，t（0＜k＜100，0＜m＜(k-1)\*k/2，0＜ t＜k），表示有m条边，k个顶点，t为遍历的起始顶点。  
下面的m行，每行是空格隔开的两个整数u，v，表示一条连接u，v顶点的无向边。

Output  
输出有n行，对应n组输出，每行为用空格隔开的k个整数，对应一组数据，表示BFS的遍历结果。

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

Example Output  
0 3 4 2 5 1

Hint  
用邻接表存储。  
Author

以下为accepted代码

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    struct node
    {
        int Data;
        struct node *next;
    }*a[104], *p, *q;
    int visit[104], link[104], tp, op, k;
    void BFS(int m)
    {
        op++;
        p = a[m]->next;
        while(p != NULL)
        {
            if(visit[p->Data] == 0)
            {
                link[tp++] = p->Data;
                visit[p->Data] = 1;
            }
            p = p->next;
        }
        if(op <= tp)
            BFS(link[op]);
    }
    int main()
    {
        int n, m, t, i, u, v;
        scanf("%d", &n);
        while(n--)
        {
            tp = op = 0;
            memset(visit, 0, sizeof(visit));
            scanf("%d %d %d", &k, &m, &t);
            for(i = 0; i < k; i++)
                a[i] = NULL;
            for(i = 0; i < m; i++)
            {
                scanf("%d %d", &u, &v);
                if(a[u] == NULL)
                {
                    p = (struct node *)malloc(sizeof(struct node));
                    p->Data = u;
                    p->next = NULL;
                    a[u] = p;
                    p = (struct node *)malloc(sizeof(struct node));
                    p->Data = v;
                    p->next = NULL;
                    a[u]->next = p;
                }
                else
                {
                    p = (struct node *)malloc(sizeof(struct node));
                    p->Data = v;
                    q = a[u]->next;
                    if(q == NULL)
                    {
                        p->next = a[u]->next;
                        a[u]->next = p;
                    }
                    while(q != NULL)
                    {
                        if(q->next != NULL)
                        {
                            if(p->Data >= q->Data && p->Data < q->next->Data)
                            {
                                p->next = q->next;
                                q->next = p;
                                break;
                            }
                        }
                        if(q->next == NULL)
                        {
                            if(p->Data >= q->Data)
                            {
                                p->next = q->next;
                                q->next = p;
                                break;
                            }
                        }
                        q = q->next;
                    }
    
                }
                if(a[v] == NULL)
                {
                    p = (struct node *)malloc(sizeof(struct node));
                    p->Data = v;
                    p->next = NULL;
                    a[v] = p;
                    p = (struct node *)malloc(sizeof(struct node));
                    p->Data = u;
                    p->next = NULL;
                    a[v]->next = p;
                }
                else
                {
                    p = (struct node *)malloc(sizeof(struct node));
                    p->Data = u;
                    q = a[v]->next;
                    if(q == NULL)
                    {
                        p->next = a[v]->next;
                        a[v]->next = p;
                    }
                    while(q != NULL)
                    {
                        if(q->next != NULL)
                        {
                            if(p->Data >= q->Data && p->Data < q->next->Data)
                            {
                                p->next = q->next;
                                q->next = p;
                                break;
                            }
                        }
                        if(q->next == NULL)
                        {
                            if(p->Data >= q->Data)
                            {
                                p->next = q->next;
                                q->next = p;
                                break;
                            }
                        }
                        q = q->next;
                    }
                }
            }
            link[tp++] = t;
            visit[t] = 1;
            BFS(t);
            for(i = 0; i < tp; i++)
            {
                printf("%d%c", link[i], i == tp-1? '\n': ' ');
            }
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 112KB
    Submit time: 2017-02-15 11:47:30
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2012/pid/2142