程序员经验分享-hwhale

图的构建和遍历

2023-10-27

图是一种包括节点和边的数据结构，本文对图的构建、图的遍历给出详细的代码。其中，

图的表示方法有：

  • 邻接矩阵
  • 邻接表

图的遍历方法有：

  • 深度优先搜索（DFS）
  • 广度优先搜索（BFS）

1. 图的表示

1.1 邻接矩阵

#include <iostream>
#include <vector>
using namespace std;

#define maxNodeNum 100 //最大顶点数

//定义图
struct GraphNode{
    int nodeNum; //顶点数
    int edgeNum; //边数
    vector<vector<int>> graph;
    /*vector<int> data; //多数情况下顶点无数据*/
    GraphNode(): nodeNum(0),edgeNum(0),graph(maxNodeNum,vector<int>(maxNodeNum,0)){}
    GraphNode(int n,int m): nodeNum(n),edgeNum(m),graph(maxNodeNum,vector<int>(maxNodeNum,0)){}
};

class Solution{
public:
    GraphNode* buildGraph(){
        GraphNode* g = new GraphNode();
        cin>>g->nodeNum; //输入顶点数
        cin>>g->edgeNum; //输入边数
        if(g->edgeNum!=0){ //如果有边
            //输入边，建图
            for(int i=0;i<g->edgeNum;i++){
                int node1,node2; //边连接的两个节点
                int weight; //边权重，可以设为1，表示有连接，0表示无连接
                cin>>node1>>node2>>weight;
                g->graph[node1][node2] = weight; //插入边
                g->graph[node2][node1] = weight; //此处模拟无向图
            }
        }
        /*//如果有顶点数据的话，读入数据
        for(int i=0;i<g->nodeNum;i++){
            cin>>g->data[i];
        }*/
        return g;
    }

    //遍历图
    void printGraph(GraphNode* g){
        for(int i=0;i<g->nodeNum;i++){
            for(int j=0;j<g->nodeNum;j++){
                cout<<g->graph[i][j]<<" ";
            }
            cout<<endl;
        }
    }
};

int main(){
    Solution s;
    GraphNode* g = s.buildGraph();
    s.printGraph(g);
    return 0;
}

/**
输入：
    0 17
    0 1 1
    0 3 1
    1 2 1
    1 3 1
    1 5 1
    2 4 1
    2 5 1
    3 6 1
    3 7 1
    4 5 1
    4 9 1
    5 6 1
    5 8 1
    5 9 1
    6 7 1
    6 8 1
    8 9 1
输出：
    0 1 0 1 0 0 0 0 0 0
    1 0 1 1 0 1 0 0 0 0
    0 1 0 0 1 1 0 0 0 0
    1 1 0 0 0 0 1 1 0 0
    0 0 1 0 0 1 0 0 0 1
    0 1 1 0 1 0 1 0 1 1
    0 0 0 1 0 1 0 1 1 0
    0 0 0 1 0 0 1 0 0 0
    0 0 0 0 0 1 1 0 0 1
    0 0 0 0 1 1 0 0 1 0
*/

1.2 邻接表

#include <iostream>
#include <vector>
using namespace std;

#define maxNodeNum 100 //最大顶点数

//图节点定义
struct VNode{
    int nodeVal; //邻接点下标
    int weight; //边权重
    /*int data; //存顶点数据，这里省略*/
    VNode* next; //指向下一个邻接点的指针

    VNode():nodeVal(-1),weight(0),next(NULL){} // 这里的-1是随便设的
    VNode(int node,int w,VNode* ptr):nodeVal(node),weight(w),next(ptr){}
};

//图定义
struct GraphNode{
    int nodeNum;  //顶点数
    int edgeNum; //边数
    vector<VNode*> graph; //邻接表
    //下面的初始化逻辑是错误的，graph(maxNodeNum,new VNode())的意思是maxNodeNum个指针全都指向new Node()开辟的一个空间
    //导致插入节点时都是在一个头节点上进行插入
    GraphNode(): nodeNum(0),edgeNum(0){
        for(int i=0;i<maxNodeNum;i++){
            VNode* init = new VNode();
            graph.push_back(init);
        }
    }
    GraphNode(int n,int m): nodeNum(n),edgeNum(m),graph(maxNodeNum){
        for(int i=0;i<maxNodeNum;i++){
            VNode* init = new VNode();
            graph.push_back(init);
        }
    }
};

class Solution{
public:
    //插入边
    void insertEdge(GraphNode* g,int node1,int node2,int weight){
        VNode* newNode1 = new VNode();
        /*插入边<node1,node2>*/
        newNode1->nodeVal = node2;
        newNode1->weight = weight;
        //将node2插入node1的头节点
        newNode1->next = g->graph[node1]->next;
        g->graph[node1]->next = newNode1;

        /*若是无向图，插入边<node2,node1>*/
        VNode* newNode2 = new VNode();
        newNode2->nodeVal = node1;
        newNode2->weight = weight;
        //将node1插入node2的头节点
        newNode2->next = g->graph[node2]->next;
        g->graph[node2]->next = newNode2;
    }
    //构建图
    GraphNode* buildGraph(){
        GraphNode* g = new GraphNode();
        cin>>g->nodeNum;
        cin>>g->edgeNum;
        if(g->edgeNum!=0){ //边数不为零时
            for(int i=0;i<g->edgeNum;i++){
                int node1,node2; //边节点
                int weight; //边权重
                cin>>node1>>node2>>weight;
                insertEdge(g,node1,node2,weight);
            }
        }
        // 如果顶点有数据的话，读入数据

        return g;
    }
    void printGraph(GraphNode* g){
        VNode* cur;
        for(int i=0;i<g->nodeNum;i++){
            cout<<i<<" ";
            cur = g->graph[i]->next;
            while(cur){
                cout<<cur->nodeVal<<" ";
                cur = cur->next;
            }
            cout<<endl;
        }
    }
};

int main(){
    Solution s;
    GraphNode* g = s.buildGraph();
    s.printGraph(g);
    return 0;
}

/*
输入：
    10 17
    0 1 1
    0 3 1
    1 2 1
    1 3 1
    1 5 1
    2 4 1
    2 5 1
    3 6 1
    3 7 1
    4 5 1
    4 9 1
    5 6 1
    5 8 1
    5 9 1
    6 7 1
    6 8 1
    8 9 1
输出：
    0 3 1
    1 5 3 2 0
    2 5 4 1
    3 7 6 1 0
    4 9 5 2
    5 9 8 6 4 2 1
    6 8 7 5 3
    7 6 3
    8 9 6 5
    9 8 5 4
 */

2. 图的遍历

2.1 深度优先搜索

深度优先遍历图的方法是，从图中某顶点v出发：

  1. 访问顶点v；
  2. 依次从v的未被访问的邻接点出发，对图进行深度优先遍历，直至图中和v有路径相通的顶点都被访问；
  3. 若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

深度优先搜系类似于树的先序遍历，伪代码如下所示：

void DFS(Vertex V)
{ 
    visited[V] = true;
    for(V的每个邻接点W)
        if (!visited[W])
            DFS(W) ;
}

若有N个顶点、E条边，时间复杂度：

  • 用邻接表存储图，为 O ( N + E ) O (N+E) O(N+E)
  • 用邻接矩阵存储图，为 O ( N 2 ) O ( N^2 ) O(N2)

2.2 广度优先搜索

广度优先搜索的基本过程：BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。

在这里插入图片描述

广度优先搜索类似于树的层序遍历，伪代码如下所示：

void BFS(Vertex V)
{ 
    visited[V] = true;
    Enqueue(V, Q);
    while(!IsEmpty (Q)){
        V = Dequeue(Q);
        for (V的每个邻接点W){
			if(!visited[W]){
                visited[W]= true;
                Enqueue (W, Q);
            }
		}   
    }
}

若有N个顶点、E条边，时间复杂度：

  • 用邻接表存储图，为 O ( N + E ) O (N+E) O(N+E)
  • 用邻接矩阵存储图，为 O ( N 2 ) O ( N^2 ) O(N2)

3. 图的遍历代码

3.1 邻接矩阵的遍历

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define maxNodeNum 100 //最大顶点数

//定义图
struct GraphNode{
    int nodeNum; //顶点数
    int edgeNum; //边数
    vector<vector<int>> graph;
    /*vector<int> data; //多数情况下顶点无数据*/
    GraphNode(): nodeNum(0),edgeNum(0),graph(maxNodeNum,vector<int>(maxNodeNum,0)){}
    GraphNode(int n,int m): nodeNum(n),edgeNum(m),graph(maxNodeNum,vector<int>(maxNodeNum,0)){}
};

class Solution{
public:
    GraphNode* buildGraph(){
        GraphNode* g = new GraphNode();
        cin>>g->nodeNum; //输入顶点数
        cin>>g->edgeNum; //输入边数
        if(g->edgeNum!=0){ //如果有边
            //输入边，建图
            for(int i=0;i<g->edgeNum;i++){
                int node1,node2; //边连接的两个节点
                int weight; //边权重，可以设为1，表示有连接，0表示无连接
                cin>>node1>>node2>>weight;
                g->graph[node1][node2] = weight; //插入边
                g->graph[node2][node1] = weight; //此处模拟无向图
            }
        }
        /*//如果有顶点数据的话，读入数据
        for(int i=0;i<g->nodeNum;i++){
            cin>>g->data[i];
        }*/
        return g;
    }
};

vector<bool> visit(maxNodeNum,false);
//深搜,类似于二叉树的递归遍历
void dfs(GraphNode* g,int val){
    visit[val] = true;
    cout<<"正在访问节点"<<val<<endl;
    for(int i=0;i<g->nodeNum;i++){
        if(!visit[i] && g->graph[val][i]){
            dfs(g,i);
        }
    }
}

//广搜，类似于二叉树的层序遍历
void bfs(GraphNode* g,int val){
    queue<int> que;
    que.push(val);
    visit[val] = true;
    cout<<"正在访问节点"<<val<<endl;
    while(!que.empty()){
        int curVal = que.front();
        que.pop();
        for(int i=0;i<g->nodeNum;i++){
            if(!visit[i] && g->graph[curVal][i]){
                que.push(i);
                visit[i] = true;
                cout<<"正在访问节点"<<i<<endl;
            }
        }
    }
}

int main(){
    Solution s;
    GraphNode* g = s.buildGraph();
    dfs(g,0);
    for(int i=0;i<maxNodeNum;i++){
        visit[i] = false;
    }
    bfs(g,0);
    return 0;
}

/*
输入：
    10 17
    0 1 1
    0 3 1
    1 2 1
    1 3 1
    1 5 1
    2 4 1
    2 5 1
    3 6 1
    3 7 1
    4 5 1
    4 9 1
    5 6 1
    5 8 1
    5 9 1
    6 7 1
    6 8 1
    8 9 1
输出：
    正在访问节点0
    正在访问节点1
    正在访问节点2
    正在访问节点4
    正在访问节点5
    正在访问节点6
    正在访问节点3
    正在访问节点7
    正在访问节点8
    正在访问节点9
    正在访问节点0
    正在访问节点1
    正在访问节点3
    正在访问节点2
    正在访问节点5
    正在访问节点6
    正在访问节点7
    正在访问节点4
    正在访问节点8
    正在访问节点9 
 */

3.2 邻接表的遍历

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define maxNodeNum 100 //最大顶点数

//图节点定义
struct VNode{
    int nodeVal; //邻接点下标
    int weight; //边权重
    /*int data; //存顶点数据，这里省略*/
    VNode* next; //指向下一个邻接点的指针

    VNode():nodeVal(-1),weight(0),next(NULL){} // 这里的-1是随便设的
    VNode(int node,int w,VNode* ptr):nodeVal(node),weight(w),next(ptr){}
};

//图定义
struct GraphNode{
    int nodeNum;  //顶点数
    int edgeNum; //边数
    vector<VNode*> graph; //邻接表
    //下面的初始化逻辑是错误的，graph(maxNodeNum,new VNode())的意思是maxNodeNum个指针全都指向new Node()开辟的一个空间
    //导致插入节点时都是在一个头节点上进行插入
    GraphNode(): nodeNum(0),edgeNum(0){
        for(int i=0;i<maxNodeNum;i++){
            VNode* init = new VNode(i,0,NULL);
            graph.push_back(init);
        }
    }
    GraphNode(int n,int m): nodeNum(n),edgeNum(m),graph(maxNodeNum){
        for(int i=0;i<maxNodeNum;i++){
            VNode* init = new VNode();
            graph.push_back(init);
        }
    }
};

class Solution{
public:
    //插入边
    void insertEdge(GraphNode* g,int node1,int node2,int weight){
        VNode* newNode1 = new VNode();
        /*插入边<node1,node2>*/
        newNode1->nodeVal = node2;
        newNode1->weight = weight;
        //将node2插入node1的头节点
        newNode1->next = g->graph[node1]->next;
        g->graph[node1]->next = newNode1;

        /*若是无向图，插入边<node2,node1>*/
        VNode* newNode2 = new VNode();
        newNode2->nodeVal = node1;
        newNode2->weight = weight;
        //将node1插入node2的头节点
        newNode2->next = g->graph[node2]->next;
        g->graph[node2]->next = newNode2;
    }
    //构建图
    GraphNode* buildGraph(){
        GraphNode* g = new GraphNode();
        cin>>g->nodeNum;
        cin>>g->edgeNum;
        if(g->edgeNum!=0){ //边数不为零时
            for(int i=0;i<g->edgeNum;i++){
                int node1,node2; //边节点
                int weight; //边权重
                cin>>node1>>node2>>weight;
                insertEdge(g,node1,node2,weight);
            }
        }
        // 如果顶点有数据的话，读入数据

        return g;
    }
    void printGraph(GraphNode* g){
        VNode* cur;
        for(int i=0;i<g->nodeNum;i++){
            cout<<i<<" ";
            cur = g->graph[i]->next;
            while(cur){
                cout<<cur->nodeVal<<" ";
                cur = cur->next;
            }
            cout<<endl;
        }
    }
};

vector<bool> visit(maxNodeNum,false);
//深搜，类似于二叉树的递归遍历
void dfs(GraphNode* g,int val){
    cout<<"正在访问顶点"<<val<<endl;
    visit[val] = true;
    VNode* curNode = g->graph[val]->next;
    while(curNode){
        if(!visit[curNode->nodeVal]){
            dfs(g,curNode->nodeVal);
        }
        curNode = curNode->next;
    }
}

//广搜，类似于二叉树的层序遍历
void bfs(GraphNode* g,int val){
    queue<VNode*> que;
    que.push(g->graph[val]);
    cout<<"正在访问节点"<<val<<endl;
    visit[val] = true;
    while(!que.empty()){
        VNode* curNode = que.front();
        que.pop();
        VNode* nextNode = curNode->next;
        while(nextNode){
            if(!visit[nextNode->nodeVal]){
                que.push(g->graph[nextNode->nodeVal]);
                cout<<"正在访问节点"<<nextNode->nodeVal<<endl;
                visit[nextNode->nodeVal] = true;
            }
            nextNode = nextNode->next;
        }
    }
}


int main(){
    Solution s;
    GraphNode* g = s.buildGraph();
    dfs(g,0);
    cout<<"=============="<<endl;
    for(int i=0;i<maxNodeNum;i++){
        visit[i] = false;
    }
    bfs(g,0);
    return 0;
}

/**
输入：
    10 17
    0 1 1
    0 3 1
    1 2 1
    1 3 1
    1 5 1
    2 4 1
    2 5 1
    3 6 1
    3 7 1
    4 5 1
    4 9 1
    5 6 1
    5 8 1
    5 9 1
    6 7 1
    6 8 1
    8 9 1
输出：
    正在访问顶点0
    正在访问顶点3
    正在访问顶点7
    正在访问顶点6
    正在访问顶点8
    正在访问顶点9
    正在访问顶点5
    正在访问顶点4
    正在访问顶点2
    正在访问顶点1
    ==============
    正在访问节点0
    正在访问节点3
    正在访问节点1
    正在访问节点7
    正在访问节点6
    正在访问节点5
    正在访问节点2
    正在访问节点8
    正在访问节点9
    正在访问节点4
 */

参考

  1. 数据结构（四）—— 图（1）：什么是图
  2. 数据结构（四）—— 图（2）：图的遍历
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

c

图

图的构建和遍历 的相关文章

随机推荐

  • GPT分区规划与各分区作用解析

    1 GPT分区规划 安装用EFI引导的Windows 10前 手动为硬盘分区 推荐方案如下 序号 分区名 起始柱面 磁头 扇区 容量 MBR保留扇区 GPT分区表 1MB 0 ESP分区 0 32 33 96MB 空白 预留给扩展ESP时使

  • 【H5】 svg画贝塞尔曲线方法

    H5 svg画贝塞尔曲线方法 d属性M 起始坐标 L 结束坐标 H 水平线 V 垂直线 A 圆弧 Z 闭合路劲 C S Q T贝塞尔曲线大写为绝对坐标 具体的坐标位置 小写为相对坐标 相对起始坐标点的具体长度 A命令x 径y半径角度弧长 0

  • 关于虚拟机.vmdk与.ovf 磁盘装载问题

    与 vmdk磁盘装载相关的两种方式 0 前言 1 只有 vmdk文件 2 带有 ovf vmdk文件 0 前言 提一嘴 现在用的比较多的虚拟机创建或者拷贝方式有两种 第一种是iso光盘映像装载 第二种是OVF导入 分别为 ISO的装载方式最

  • build JAX from source code

    Building from source JAX documentation

  • visual studio：不能加载.vdproj

    总结 下载后关闭所有vs项目 重新打开目标工程 需要完成次扩展的后续安装任务 参考 https www cnblogs com hofmann p 11183457 htm

  • 122FPS，51.9mAP 超轻量关键点检测算法PP-TinyPose来啦！

    在人机交互场景中 机器可以识别人的手势 肢体动作 表情 你可知背后的核心技术是什么吗 没错 就是关键点检测技术 它能帮你实现精准的人机交互任务 如手势控制 智能健身 体感游戏等 还可以识别交通违规 打架斗殴 违规操作等异常行为 话不多说 我

  • DVWA——XSS(Dom low&medium)

    此文章只用于学习 请勿用作其他违法犯罪行为 以下部分文字内容以图片形式展示 因为JS代码打不上去 目录 前言 XSS攻击流程 XSS的危害 XSS的漏洞类型 JS基本语句 XSS Dom Low XSS Dom Medium 前言 XSS被

  • Ubantu扩展SWAP区，使用gparted，以及死机非热启动解决方法

    Ubantu扩展SWAP区 使用gparted 以及死机非热启动解决方法 Swap分区 强制重启 扩充SWAP Swap分区 Swap分区是用来扩展内存的 即使用一部分硬盘空间作为交换 个人认为电脑内存大于16G即不需要分配Swap空间 我

  • Python字符串替换的3种方法

    Python字符串替换笔记主要展示了如何在Python中替换字符串 Python中有以下几种替换字符串的方法 本文主要介绍前三种 replace方法 常用 translate方法 re sub方法 字符串切片 根据Python字符串切片方法

  • springboot + redis多数据源 + jedis集群模式

    最近有个项目需要redis支持多个集群 网上搜了下 发现有个开源的项目spring boot starter dynamic redis 代码写的挺好 可惜只有单机版的 于是fork了他的代码改了下 支持jedis集群模式 新代码昨天已提交

  • 如何用人工智能预测股票(完整项目)

    本文由 沈庆阳 所有 转载请与作者取得联系 前言 十分钟实现人工智能股价预测 是一个深度学习的练习项目 其通过机器学习算法 根据过去几年与某只股票相关的K线走势 公司相关报道的情感分析作为数据集 通过训练来得到可以预测股价的机器学习模型 并

  • VS2008, MFC 文件的操作4 - CFile类, CFileDialog类 方式 文本方式打开

    接上一节笔记 VS2008 MFC 文件的操作3 Win32 API 方式 文本方式打开 1 代码 及 点击 子菜单项 WriteFile 时候的可选文件 void Cvs2008 SX jiaocheng12View OnFileWrit

  • 【vscode代码片段增加和删除】

    目录 一 概述 二 详解 三 实例 一 概述 项目开发中 存在很多重复代码 可将其抽取出来定义成自己的代码片段 提高编码效率 实现快捷开发 二 详解 详解1 选择并打开代码片段文件 详解2 删除代码片段文件 代码片段文件创建后会一直保存在本

  • Java7对资源释放操作的简化

    学会使用finally释放资源 public class TryCatchResourceDemo public static void main String args try 这里面只能放置资源对象 用完会自动关闭 自动调用资源对象的c

  • 童年回忆——超级玛丽（内含源码inscode一键运行）

    前言 作者主页 雪碧有白泡泡 个人网站 雪碧的个人网站 推荐专栏 java一站式服务 React从入门到精通 前端炫酷代码分享 从0到英雄 vue成神之路 uniapp 从构建到提升 从0到英雄 vue成神之路 解决算法 一个专栏就够了 架

  • RuoYi-Cloud版本限制一个账户只能在一个地方登陆

    RuoYi Cloud版本限制一个账户只能在一个地方登陆 一 前言 二 参考 三 代码实现 三 一 在ruoyi auth模块下的bootstrap yml文件下新增一个配置soloLogin用于限制多终端同时登录 三 二 我是在Cache

  • GUI编程（二）

    Swing Swing是GUI 图形用户界面 开发工具包 早期的AWT 抽象窗口工具包 组件开发的图形用户界面 要依赖本地系统 当把AWT组件开发的应用程序移植到其他平台的系统上运行时 不能保证其外观风格 因此AWT是依赖于本地系统平台的

  • 简单上手Raspberry Pi Pico（macOS+MicroPython）

    昨天写了Ubuntu安装Thonny并连接Pico进行开发的文章 https blog csdn net MacwinWin article details 113097180 今天就来说说在macOS上如何安装Thonny并连接Pico

  • Kubernetes 自动化诊断工具：k8sgpt-operator

    背景 在 Kubernetes 上 从部署 Deployment 到正常提供服务 整个流程可能会出现各种各样问题 有兴趣的可以浏览 Kubernetes Deployment 的故障排查可视化指南 2021 中文版 从可视化指南也可能看出这

  • 图的构建和遍历

    图是一种包括节点和边的数据结构 本文对图的构建 图的遍历给出详细的代码 其中 图的表示方法有 邻接矩阵 邻接表 图的遍历方法有 深度优先搜索 DFS 广度优先搜索 BFS 1 图的表示 1 1 邻接矩阵 include

热门标签