IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 数据结构实验五(图的遍历) -> 正文阅读

[数据结构与算法]数据结构实验五(图的遍历)

题目描述:
分别用邻接矩阵和邻接表实现图的深度优先遍历和广度优先遍历。
下面邻接矩阵和邻接表均以下图为例,其中已标注了正确的dfs,bfs顺序图和相关的表示法。
几句话明白深度与广度搜索:深度优先就像你被困在了迷宫里面,想要出去必须一路走到底,直到走不通了才回溯,重点是回溯。而广度优先就像你丢了眼镜,看不清的时候满地寻找,辐射范围大
上次实验四哈夫曼树全部完整代码此处
已经上传深搜和广搜的专训题目每一题都涉及2种解法,更加全方位地展现其中的不同。详情点击此处
在这里插入图片描述

邻接矩阵存储图
MGraph.cpp

#include <iostream>
#include <queue>


using namespace std;

typedef struct{
    int v[500];
    int e[500][500];
    int vsum,esum;
    bool visit[500];
}MGraph;

/*创建邻接矩阵*/
void Create(MGraph &g){
    cout<<"请输入图的顶点总数和边数"<<endl;
    cin>>g.vsum>>g.esum;
    cout<<"输入图中节点信息"<<endl;
    for(int i=0;i<g.vsum;i++){
        cin>>g.v[i];
    }
    for(int i=0;i<g.vsum;i++){
        g.visit[g.v[i]]=false;
        for(int j=0;j<g.vsum;j++){
            g.e[g.v[i]][g.v[j]]=-1;
        }
    }
    cout<<"输入图中各边的两个顶点和边长"<<endl;
    for(int i=0;i<g.esum;i++){
        int v1,v2,w;
        cin>>v1>>v2>>w;
        g.e[v1][v2]=w;
        g.e[v2][v1]=w;
    }
}

void dfs(MGraph &g,int start,string &str){
    str+=(start+48);//转换字符
    str+="->";
    g.visit[start]=true;
    for(int i=0;i<g.vsum;i++){
        int temp=g.v[i];
        if(g.visit[temp]==false&&g.e[start][temp]!=-1){
            dfs(g,temp,str);
        }
    }
}

void bfs(MGraph &g,int start,string &str){
    queue<int> q;
    q.push(start);
    g.visit[start]=true;
    while(!q.empty()){
        int top=q.front();
        q.pop();
        str+=(top+48);
        str+="->";
        for(int i=0;i<g.vsum;i++){
            int temp=g.v[i];
            if(g.e[top][temp]!=-1&&g.visit[temp]==false){
                q.push(temp);
                g.visit[temp]=true;
            }
        }
    }
}

void traver1(MGraph &g){
    for(int i=0;i<g.vsum;i++){
        g.visit[g.v[i]]=false;
    }
    cout<<"\n广度搜索遍历:"<<endl;
    string m="";
    bfs(g,1,m);
    m=m.substr(0,m.length()-2);
    cout<<m<<endl;
}

void traver2(MGraph &g){
    for(int i=0;i<g.vsum;i++){
        g.visit[g.v[i]]=false;
    }
    cout<<"深度搜索遍历:"<<endl;
    string m="";
    dfs(g,1,m);
    m=m.substr(0,m.length()-2);
    cout<<m<<endl;
}

int main(){
    MGraph g;
    Create(g);
    traver1(g);
    traver2(g);
}

结果示意图
在这里插入图片描述

邻接表存储图
AGraph.cpp

#include <iostream>
#include <queue>
#include <cstring>
#include <string>

using namespace std;

bool visit[500];

/*边结点*/
typedef struct ArcNode{
    int adv;
    struct ArcNode *nextArc;
    int  data;
}ArcNode;

typedef struct VNode{
    ArcNode *first;
    string  data;
}AdVlist;

/*邻接表*/
typedef struct ALGraph{
    AdVlist vts[500];
    int v,e;
}ALGraph;

int find(ALGraph &g,string  x){
    for(int i=0;i<g.v;i++){
        if(x==g.vts[i].data)
            return i;
    }
    return -1;
}

void Create(ALGraph &g){
    string  v1,v2;
    cout<<"输入图的顶点数和边数"<<endl;
    cin>>g.v>>g.e;
    cout<<"输入图中结点信息"<<endl;
    for(int i=0;i<g.v;i++){
        cin>>g.vts[i].data;
        g.vts[i].first=NULL;
    }
    cout<<"输入图中两个顶点(起点和终点)"<<endl;
    for(int i=0;i<g.e;i++){
        cin>>v1>>v2;
        int j,k;
        j=find(g,v1);
        k=find(g,v2);
        ArcNode *p1=new ArcNode;
        ArcNode *p2=new ArcNode;
        p1->adv=k;
        p1->nextArc=g.vts[j].first;
        g.vts[j].first=p1;
        p2->adv=j;
        p2->nextArc=g.vts[k].first;
        g.vts[k].first=p2;
    }
}

void dfs(ALGraph &g,int n){
    cout<<g.vts[n].data;
    visit[n]=false;
    ArcNode *p=g.vts[n].first;
    while(p){
        if(visit[p->adv]){
            cout<<"->";
            dfs(g,p->adv);
        }
        p=p->nextArc;
    }
}

void bfs(ALGraph &g,int n){
    queue<int> q;
    q.push(n);
    while(!q.empty()){
        if(q.front()!=0) cout<<"->";
        cout<<g.vts[q.front()].data;
        visit[q.front()]=true;
        ArcNode *p=g.vts[q.front()].first;
        while(p){
            if(!visit[p->adv]){
                visit[p->adv]=true;
                q.push(p->adv);
            }
            p=p->nextArc;
        }
        q.pop();
    }
}


int main(){
    ALGraph g;
    Create(g);
    memset(visit,true,sizeof(visit));
    cout<<"深度优先遍历:"<<endl;
    dfs(g,0);
    cout<<"\n广度优先遍历:"<<endl;
    bfs(g,0);
    return 0;
}

结果运行图
注意看我上述图的说明,注意指针的位置,不是根据矩阵法的dfs/bfs,而是看我写的邻接表的图。
在这里插入图片描述

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-11-14 21:58:23  更:2021-11-14 21:59:44 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2025年1日历 -2025/1/9 1:05:53-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码