浙大数据结构:图的定义及表示方法
2021/9/4 23:10:33
本文主要是介绍浙大数据结构:图的定义及表示方法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
还是按照习惯,先附上PPT讲解,文章后面是代码部分。
一、图的定义以及数据集
二、图的邻接矩阵表示法
三、图的邻接表表示法
邻接表的表示方法不唯一,而且所占空间较多,所以一定要够稀疏才合算。
四、图的邻接矩阵表示法代码
#include<iostream> using namespace std; #include<stdlib.h> #define MAXN 100 int G[MAXN][MAXN], Nv, Ne; void BuildGraph() { int i, j, v1, v2, w; cout << "请输入需要插入的顶点数:"; cin>>Nv;//初始化定点数 // 初始化图 for (i = 0;i < Nv;i++) for (j = 0;j < Nv;j++) G[i][j] = 0; cout << "请输入需要插入的边数:"; cin >> Ne; // 插入边 for (i = 0;i < Ne;i++) { cout << "请输入需要连接的两个顶点的编号以及权重(可设置为1):"; cin >> v1 >> v2 >> w; G[v1][v2] = w; G[v2][v1] = w; } } // 遍历图 void print() { int i, j; for (i = 0;i < Nv;i++) { for (j = 0;j < Nv;j++) cout << G[i][j] << ' '; cout << endl; } } int main() { BuildGraph(); print(); return 0; }
五、图的邻接表表示法代码
//02 图的邻接表表示法 #include<stdio.h> using namespace std; #include<stdlib.h> #pragma warning(disable:4996) #define MaxVertexNum 100 typedef struct AdjVNode* AdjList; struct AdjVNode { int weight; // 权值 int adjv; // 下标 AdjList next; // 其后一个 }; AdjList Graph[MaxVertexNum]; int Ne, Nv; // 建图 void BuildGraph() { int i; int v1, v2, w; AdjList NewNode; scanf("%d", &Nv); for (i = 0;i < Nv;i++) { Graph[i] = (AdjList)malloc(sizeof(struct AdjVNode)); Graph[i]->adjv = i; Graph[i]->next = NULL; } scanf("%d", &Ne); for (i = 0;i < Ne;i++) { scanf("%d %d %d", &v1, &v2, &w); NewNode = (AdjList)malloc(sizeof(struct AdjVNode)); NewNode->adjv = v1; NewNode->weight = w; NewNode->next = Graph[v2]->next; Graph[v2]->next = NewNode; NewNode = (AdjList)malloc(sizeof(struct AdjVNode)); NewNode->adjv = v2; NewNode->weight = w; NewNode->next = Graph[v1]->next; Graph[v1]->next = NewNode; } } void print() { AdjList tmp; int i; for (i = 0;i < Nv;i++) { tmp = Graph[i]; while (tmp) { printf("%d ", tmp->adjv); tmp = tmp->next; } printf("\n"); } } int main() { BuildGraph(); print(); return 0; }
这篇关于浙大数据结构:图的定义及表示方法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-22揭秘 Fluss:下一代流存储,带你走在实时分析的前沿(一)
- 2024-12-20DevOps与平台工程的区别和联系
- 2024-12-20从信息孤岛到数字孪生:一本面向企业的数字化转型实用指南
- 2024-12-20手把手教你轻松部署网站
- 2024-12-20服务器购买课程:新手入门全攻略
- 2024-12-20动态路由表学习:新手必读指南
- 2024-12-20服务器购买学习:新手指南与实操教程
- 2024-12-20动态路由表教程:新手入门指南
- 2024-12-20服务器购买教程:新手必读指南
- 2024-12-20动态路由表实战入门教程