【C++数据结构——图】图的邻接矩阵和邻接表的存储(头歌实践教学平台习题)【合集】

简介: 本任务要求编写程序实现图的邻接矩阵和邻接表的存储。需掌握带权有向图、图的邻接矩阵及邻接表的概念。邻接矩阵用于表示顶点间的连接关系,邻接表则通过链表结构存储图信息。测试输入为图的顶点数、边数及邻接矩阵,预期输出为Prim算法求解结果。通关代码提供了完整的C++实现,包括输入、构建和打印邻接矩阵与邻接表的功能。

目录😋

任务描述

相关知识

1. 带权有向图

2. 图的邻接矩阵

3. 图的邻接表

测试说明

通关代码

测试结果


任务描述

本关任务:编写一个程序实现图的邻接矩阵和邻接表的存储。

相关知识

为了完成本关任务,你需要掌握:

  1. 带权有向图
  2. 图的邻接矩阵,
  3. 图的邻接表

1. 带权有向图

针对有向图的邻接矩阵和邻接表的存储,如下列图形:

image.gif 编辑

image.gif 编辑

2. 图的邻接矩阵

若 G 为带权有向图,其邻接矩阵 A 中的元素 Aij 遵循以下规则进行赋值:

  1. 当 i≠j,并且存在从顶点 i 指向顶点 j 的有向边,即 <i, j>∈E (G) 时,此时 Aij 的值等于该有向边的权值 wij;
  2. 当 i = j 时,Aij 的取值为 0,这表示顶点到自身的权值为 0;
  3. 而在其他情况下,也就是不存在从顶点 i 指向顶点 j 的有向边时,Aij 的值设定为无穷大(通常用特定的极大数值来表示,例如在程序实现中可以采用类似 INT_MAX 这样能表示极大值的常量来表示无穷大的概念)。

示例代码如下:

if (g.edges[i][j]!=INF)
     printf("%d ",g.edges[i][j]);
 else
     printf("%s ","∞");
image.gif

(INF表示无穷大,表示整数:32767)

3. 图的邻接表

邻接表结点由三个域组成:

  1. adjvex指示与顶点vi邻接的点在图中的位置,
  2. nextarc指示下一条边或弧的结点,
  3. info存储与边或弧的权值。

表头结点由两个域组成:

  1. data存储顶点vi的名称或其他信息,
  2. firstarc指向链表中第一个结点。

示例代码如下:

for (int i=0;i<G->n;i++)
     {
         p=G->adjlist[i].firstarc;
         printf("%3d: ",i);
         while (p!=NULL)
         {
             printf("%3d[%d]→",p->adjvex,p->weight);
             p=p->nextarc;
         }
         printf("∧\n");
     }
image.gif

测试说明

平台会对你编写的代码进行测试:

测试输入:( 输入图的顶点数和边数,再输入图的邻接矩阵。)

6 10 0 5 32767 7 32767 32767 32767 0 4 32767 32767 32767 8 32767 0 32767 32767 9 32767 32767 5 0 32767 6 32767 32767 32767 5 0 32767 3 32767 32767 32767 1 0
image.gif

预期输出:(Prim算法求解结果)

边(0,5)权为:3
边(5,4)权为:1
边(0,1)权为:5 
边(1,2)权为:4
边(4,3)权为:5
image.gif

开始你的任务吧,祝你成功!


通关代码

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;
const int MAX_VERTICES = 6; // 最大顶点数
const int INF = 32767;      // 表示无穷大
// 邻接矩阵表示的图
struct GraphMatrix {
  int n;                     // 顶点数
  vector<vector<int>> edges; // 邻接矩阵
};
// 邻接表的边节点
struct ArcNode {
  int adjvex;       // 邻接点在图中的位置
  int weight;       // 边的权重
  ArcNode *nextarc; // 指向下一条边
};
// 邻接表
struct VNode {
  int data;          // 顶点信息
  ArcNode *firstarc; // 指向第一条边
};
struct GraphList {
  int n;                 // 顶点数
  vector<VNode> adjlist; // 邻接表
};
// 输入邻接矩阵并构建图
void inputGraphMatrix(GraphMatrix &g) {
  cin >> g.n; // 读入顶点数
  int e;      // 边数
  cin >> e;   // 读入边数
  g.edges.resize(g.n, vector<int>(g.n, INF));
  for (int i = 0; i < g.n; ++i) {
    g.edges[i][i] = 0; // 对角线元素为0
  }
  // 读入邻接矩阵
  for (int i = 0; i < g.n; ++i) {
    for (int j = 0; j < g.n; ++j) {
      cin >> g.edges[i][j];
    }
  }
}
// 输出邻接矩阵
void printGraphMatrix(const GraphMatrix &g) {
  cout << "(1)图G的邻接矩阵:" << endl;
  for (int i = 0; i < g.n; ++i) {
    for (int j = 0; j < g.n; ++j) {
      if (g.edges[i][j] == INF) {
        cout << "∞ ";
      } else {
        cout << g.edges[i][j] << " ";
      }
    }
    cout << endl;
  }
}
// 构建邻接表
void buildGraphList(const GraphMatrix &gm, GraphList &gl) {
  gl.n = gm.n;
  gl.adjlist.resize(gl.n);
  for (int i = 0; i < gm.n; ++i) {
    gl.adjlist[i].data = i;           // 存储顶点
    gl.adjlist[i].firstarc = nullptr; // 初始化第一条边
  }
  // 从邻接矩阵构建邻接表
  for (int i = 0; i < gm.n; ++i) {
    for (int j = 0; j < gm.n; ++j) {
      if (gm.edges[i][j] != INF && gm.edges[i][j] != 0) {
        ArcNode *arc = new ArcNode(); // 动态分配新边
        arc->adjvex = j;              // 指向邻接点
        arc->weight = gm.edges[i][j]; // 边的权重
        arc->nextarc = nullptr;       // 初始化下一条边为nullptr
        // 将新节点插入已排序的链表中
        if (gl.adjlist[i].firstarc == nullptr ||
            gl.adjlist[i].firstarc->adjvex > j) {
          arc->nextarc = gl.adjlist[i].firstarc; // 插入到链表头
          gl.adjlist[i].firstarc = arc;
        } else {
          ArcNode *p = gl.adjlist[i].firstarc;
          while (p->nextarc != nullptr && p->nextarc->adjvex < j) {
            p = p->nextarc; // 寻找插入位置
          }
          arc->nextarc = p->nextarc; // 插入
          p->nextarc = arc;
        }
      }
    }
  }
}
// 输出邻接表
void printGraphList(const GraphList &gl) {
  cout << "(2)图G的邻接表:" << endl;
  for (int i = 0; i < gl.n; ++i) {
    cout << "  " << i << ": ";
    ArcNode *p = gl.adjlist[i].firstarc;
    while (p != nullptr) {
      cout << "  " << p->adjvex << "[" << p->weight << "]→";
      p = p->nextarc;
    }
    cout << "∧" << endl;
  }
}
int main() {
  GraphMatrix gm;
  inputGraphMatrix(gm);
  printGraphMatrix(gm);
  GraphList gl;
  buildGraphList(gm, gl);
  printGraphList(gl);
  return 0;
}

image.gif


测试结果

image.gif 编辑

image.gif

目录
相关文章
|
1月前
|
消息中间件 缓存 NoSQL
Redis各类数据结构详细介绍及其在Go语言Gin框架下实践应用
这只是利用Go语言和Gin框架与Redis交互最基础部分展示;根据具体业务需求可能需要更复杂查询、事务处理或订阅发布功能实现更多高级特性应用场景。
187 86
|
5月前
|
监控 算法 数据处理
基于 C++ 的 KD 树算法在监控局域网屏幕中的理论剖析与工程实践研究
本文探讨了KD树在局域网屏幕监控中的应用,通过C++实现其构建与查询功能,显著提升多维数据处理效率。KD树作为一种二叉空间划分结构,适用于屏幕图像特征匹配、异常画面检测及数据压缩传输优化等场景。相比传统方法,基于KD树的方案检索效率提升2-3个数量级,但高维数据退化和动态更新等问题仍需进一步研究。未来可通过融合其他数据结构、引入深度学习及开发增量式更新算法等方式优化性能。
152 17
|
9月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
355 77
|
9月前
|
C++ 芯片
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
178 19
|
8月前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
4月前
|
人工智能 机器人 编译器
c++模板初阶----函数模板与类模板
class 类模板名private://类内成员声明class Apublic:A(T val):a(val){}private:T a;return 0;运行结果:注意:类模板中的成员函数若是放在类外定义时,需要加模板参数列表。return 0;
104 0
|
4月前
|
存储 编译器 程序员
c++的类(附含explicit关键字,友元,内部类)
本文介绍了C++中类的核心概念与用法,涵盖封装、继承、多态三大特性。重点讲解了类的定义(`class`与`struct`)、访问限定符(`private`、`public`、`protected`)、类的作用域及成员函数的声明与定义分离。同时深入探讨了类的大小计算、`this`指针、默认成员函数(构造函数、析构函数、拷贝构造、赋值重载)以及运算符重载等内容。 文章还详细分析了`explicit`关键字的作用、静态成员(变量与函数)、友元(友元函数与友元类)的概念及其使用场景,并简要介绍了内部类的特性。
176 0
|
6月前
|
编译器 C++ 容器
【c++11】c++11新特性(上)(列表初始化、右值引用和移动语义、类的新默认成员函数、lambda表达式)
C++11为C++带来了革命性变化,引入了列表初始化、右值引用、移动语义、类的新默认成员函数和lambda表达式等特性。列表初始化统一了对象初始化方式,initializer_list简化了容器多元素初始化;右值引用和移动语义优化了资源管理,减少拷贝开销;类新增移动构造和移动赋值函数提升性能;lambda表达式提供匿名函数对象,增强代码简洁性和灵活性。这些特性共同推动了现代C++编程的发展,提升了开发效率与程序性能。
198 12
|
7月前
|
设计模式 安全 C++
【C++进阶】特殊类设计 && 单例模式
通过对特殊类设计和单例模式的深入探讨,我们可以更好地设计和实现复杂的C++程序。特殊类设计提高了代码的安全性和可维护性,而单例模式则确保类的唯一实例性和全局访问性。理解并掌握这些高级设计技巧,对于提升C++编程水平至关重要。
138 16
|
8月前
|
编译器 C语言 C++
类和对象的简述(c++篇)
类和对象的简述(c++篇)

热门文章

最新文章