数据结构--图及其应用--图的遍历

àì夳堔傛蜴生んèń 2023-07-03 14:28 57阅读 0赞

# 数据结构–图及其应用–图的遍历 #

## 【实验目的】 ##

使学生深入了解图结构的特点，掌握创建图的各种存储结构的方法；同时深刻理解图的dfs和bfs遍历过程。

## 【实验内容及要求】 ##

１、问题描述：很多涉及图上操作的算法都是以图的遍历操作为基础的。请以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历两个遍历算法。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列和相应生成树的边集。  
2、测试数据：教科书图7.19。  
3、实现提示：每个结点用一个英文字母来表示（从A开始）。通过输入图的全部边输入一个图，每条边为一个字母对，可以对边的输入顺序作出某种限制，注意，生成树的边是有向边，端点顺序不能颠倒。

## 【实验数据】 ##

#include<iostream>
    using namespace std;
    
    #define MAXNUM  100
    
    char visited[MAXNUM];
    
    typedef struct ArcNode   //边节点
    {
        
        int adjvex;
        struct ArcNode *nextarc;
    
    } ArcNode;
    
    typedef struct    //顶点信息
    {
        
        char data;
        ArcNode *firstarc;
    } AdjList[MAXNUM];
    
    typedef struct      //邻接表
    {
        
        AdjList vertices;
        int vexnum,arcnum;
    } ALGraph;
    
    int LocateVex(ALGraph G,char v)
    {
        
        for(int i = 0; i < G.vexnum; i++)
        {
        
            if(G.vertices[i].data == v)return i;
        }
        return -1;
    }
    
    
    int CreateUDG(ALGraph &G)  //创建无向图
    {
        
        char v1,v2;
        cout<<"请输入顶点数和边数：";
        cin>>G.vexnum>>G.arcnum;
    
        cout<<"请依次输入顶点：";
        for(int i = 0; i < G.vexnum; i++)
        {
        
            cin>>G.vertices[i].data;
            G.vertices[i].firstarc = NULL;
        }
    
        cout<<"请依次输入邻接边："<<endl;
        for(int k= 0; k < G.arcnum; k++)
        {
        
            cin>>v1>>v2;
            int i = LocateVex(G,v1);
            int j = LocateVex(G,v2);
    
            ArcNode *p1 = new ArcNode;
            p1->adjvex = j;
            p1->nextarc = G.vertices[i].firstarc;
            G.vertices[i].firstarc = p1;
    
            ArcNode *p2 = new ArcNode;
            p2->adjvex = i;
            p2->nextarc = G.vertices[j].firstarc;
            G.vertices[j].firstarc = p2;
        }
        return 1;
    
    }
    
    void DFT_AL(ALGraph G,int i)  //深度优先遍历邻接表
    {
        
        cout<<G.vertices[i].data;
        visited[i] = 1;
        ArcNode *p = G.vertices[i].firstarc;
        int j;
        while(p)
        {
        
            j = p->adjvex;
            if(!visited[j])DFT_AL(G,j);
            p = p->nextarc;
        }
    }
    
    int main()
    {
        
        ALGraph G;
        CreateUDG(G);
        cout<<"输出：";
        DFT_AL(G,1);
        return 0;
    }

## 【实验结果】 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200207114200914.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1dYX3RpbWk=,size_16,color_FFFFFF,t_70