图的广度优先遍历，基于邻接链表实现

不念不忘少年蓝@ 2022-08-24 14:06 136阅读 0赞

#include <iostream>
    #include <queue>
    #include <stack>
    
    
    using namespace std;
    
    
    /***************************************
     *  * 图的深度优先遍历
     *   * 基于邻接链表的非递归实现
     *    **************************************/
    
    
    typedef char vertex_t;  //结点数据类型
    
    
    //边结点
    typedef struct _tag_edge_node_t
    {
        int node_num;  //边终点所在数组序号
        _tag_edge_node_t* next_node;  //下一条边
    }edge_node_t;
    
    
    //顶点结点
    typedef struct _tag_head_node_t
    {
        vertex_t data;  //结点数据
        edge_node_t* first_edge;  //第一条边
    }head_node_t;
    
    
    #define MAX_NUMBER 20  //图中最大结点数目
    
    
    //图结构
    typedef struct _tag_graph_t
    {
        head_node_t head_data[MAX_NUMBER];  //顶点数组
        unsigned int head_node_count;  //顶点数目
    }graph_t;
    
    
    void create_adjacency_list(graph_t* graph)
    {
        edge_node_t* p_edge = NULL;
        if (graph == NULL)
            return;
    
    
        graph->head_node_count = 6;
        for (unsigned int i = 0; i < graph->head_node_count; ++i)
        {
            graph->head_data[i].data = 'A' + i;
            graph->head_data[i].first_edge = NULL;
        }
    
    
        graph->head_data[0].first_edge = new edge_node_t;
        p_edge = graph->head_data[0].first_edge;
        p_edge->node_num = 2;
    
        p_edge->next_node = new edge_node_t;
        p_edge = p_edge->next_node;
        p_edge->node_num = 4;
    
    
        p_edge->next_node = new edge_node_t;
        p_edge = p_edge->next_node;
        p_edge->node_num = 5;
        p_edge->next_node = NULL;
    
    
        graph->head_data[1].first_edge = new edge_node_t;
        graph->head_data[1].first_edge->node_num = 2;
        graph->head_data[1].first_edge->next_node = NULL;
    
    
        graph->head_data[2].first_edge = new edge_node_t;
        graph->head_data[2].first_edge->node_num = 3;
        graph->head_data[2].first_edge->next_node = NULL;
    
    
        graph->head_data[3].first_edge = new edge_node_t;
        graph->head_data[3].first_edge->node_num = 5;
        graph->head_data[3].first_edge->next_node = NULL;
    
    
        graph->head_data[4].first_edge = new edge_node_t;
        graph->head_data[4].first_edge->node_num = 1;
        graph->head_data[4].first_edge->next_node = 
            new edge_node_t;
    
        p_edge = graph->head_data[4].first_edge->next_node;
        p_edge->node_num = 3;
        p_edge->next_node = new edge_node_t;
    
        p_edge = p_edge->next_node;
        p_edge->node_num = 5;
        p_edge->next_node = NULL;
    }
    
    void breadth_first_search(graph_t *graph, int start_pos)
    {
        queue<int> visit_queue;  //访问队列
        bool is_visit[MAX_NUMBER];  //访问标志数组
        for (int i = 0; i < MAX_NUMBER; ++i)
            is_visit[i] = false;
    
        for (unsigned int i = 0; i < graph->head_node_count; 
                ++i)
        {
            if (!is_visit[i])  //该结点没有被访问
                visit_queue.push(i);
    
            while (!visit_queue.empty())
            {
                //出队
                int n_pos = visit_queue.front();
                visit_queue.pop();
                if (!is_visit[n_pos])
                {
                    cout<<graph->head_data[n_pos].data<<endl;
                    is_visit[n_pos] = true;
    
                    //将该结点下所有未被访问的边入队
                    edge_node_t *next = 
                        graph->head_data[n_pos].first_edge;
                    while (next != NULL)
                    {
                        if (!is_visit[next->node_num])
                            visit_queue.push(next->node_num);
                        next = next->next_node;
                    }
                }
            }
        }
    }
    
    void depth_first_search(graph_t* graph, int start_pos)
    {
        stack<int> visit_node;
        bool is_visit[MAX_NUMBER];  //访问标志数组
        for (int i = 0; i < MAX_NUMBER; ++i)
            is_visit[i] = false;
    
    
        cout<<graph->head_data[start_pos].data<<endl;
        is_visit[start_pos] = true;
        visit_node.push(start_pos);  //将第一个元素压栈
        while (!visit_node.empty())
        {
            int num = visit_node.top();
            edge_node_t* next = graph->head_data[num].first_edge;
            for (; next != NULL; next = next->next_node)  //存在边，且该边的终点未被访问
            {
                if (!is_visit[next->node_num])
                {
                    cout<<graph->head_data[next->node_num].data<<endl;
                    is_visit[next->node_num] = true;
                    visit_node.push(next->node_num);
                    break;
                }
            }
            if (next == NULL)  //以该结点为起点的所有终点访问完毕
                visit_node.pop();
        }
    }
    
    int main(int argc, char* argv[])
    {
        graph_t graph;
        create_adjacency_list(&graph);
        //depth_first_search(&graph, 0);
        breadth_first_search(&graph, 0);
        return 0;
    }