首先,我们来看一下涉及的知识点:
图:图 G=(V,E) 由顶点集 V 和边集 E 组成。每条边对应一个点对 (v,w),其中 v,w 属于 V 。如果图中的点对是有序的,那么该图就是有向图,反之为无向图。
邻接点:若顶点 v 与 w 之间存在一条边,则认为顶点 v 与 w 邻接。
权:图中的每条边都可以对应一个数值,这种与边相关的数值称为权。
路径:在图 G 中,顶点 v1 到 vk 的路径是一个顶点序列 v1,v2,···,vk。
连通图:在无向图 G 中,若两个顶点之间存在路径,则认为这两个顶点是连通的。如果在无向图 G 中,任意两个顶点都是连通的,则称 G 是连通图。
完全图:若图中任意两个顶点之间都存在一条边,则该图为完全图。
稀疏图和稠密图:当图中边的数量比较少时,称该图为稀疏图;而当图接近完全图时,称该图为稠密图。
1、邻接矩阵
邻接矩阵就是运用二维数组,对于图中的每条边 (v,w) ,设置 A[v][w] 等于该权值;若不存在边(v,w),则 A[v][w]=0 。
基本数据结构:
typedef struct VexType { //顶点类型
int code; //顶点编号
char data; //顶点信息
}VexType;
typedef struct Graph { //邻接矩阵类型
int arcs[maxn][maxn]; //邻接矩阵
int vexnum, arcnum; //顶点数和边的个数
VexType vexs[maxn]; //顶点信息
int type; //邻接矩阵的类型(1.无向图 2.有向图)
}Graph;
创建邻接矩阵(以带权的图为例):
void Create_Graph(Graph& G) //创建
{
cout << "请输入图的类型(1.无向图 2.有向图):";
cin >> G.type;
cout << "顶点的个数:";
cin >> G.vexnum;
cout << "请输入各顶点的名称:";
for (int i = 0; i < G.vexnum; i++) {
cin >> G.vexs[i].data;
G.vexs[i].code = i; //按顺序为点编号
}
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
G.arcs[i][j] = 0; //邻接矩阵初始化,将所有元素的初始值设为0
}
}
cout << "请输入边的个数:";
cin >> G.arcnum;
cout << "请输入各边起点和终点的编号及权重:" << endl;
int x, y, w; //x:起始点,y:终点,w:权重
for (int i = 0; i < G.arcnum; i++) {
cin >> x >> y >> w;
if (G.type == 1) { //如果是无向图,对称边也要赋值为权重
G.arcs[x][y] = w;
G.arcs[y][x] = w;
}
else {
G.arcs[x][y] = w;
}
}
}
全部代码:
# include <iostream>
# include <iomanip>
# include <queue>
# define maxn 20
using namespace std;
typedef struct VexType { //顶点类型
int code; //顶点编号
char data; //顶点信息
}VexType;
typedef struct Graph { //邻接矩阵类型
int arcs[maxn][maxn]; //邻接矩阵
int vexnum, arcnum; //顶点数和边的个数
VexType vexs[maxn]; //顶点信息
int type; //邻接矩阵的类型(1.无向图 2.有向图)
}Graph;
void Create_Graph(Graph& G) //创建
{
cout << "请输入图的类型(1.无向图 2.有向图):";
cin >> G.type;
cout << "顶点的个数:";
cin >> G.vexnum;
cout << "请输入各顶点的名称:";
for (int i = 0; i < G.vexnum; i++) {
cin >> G.vexs[i].data;
G.vexs[i].code = i; //按顺序为点编号
}
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
G.arcs[i][j] = 0; //邻接矩阵初始化,将所有元素的初始值设为0
}
}
cout << "请输入边的个数:";
cin >> G.arcnum;
cout << "请输入各边起点和终点的编号及权重:" << endl;
int x, y, w; //x:起始点,y:终点,w:权重
for (int i = 0; i < G.arcnum; i++) {
cin >> x >> y >> w;
if (G.type == 1) { //如果是无向图,对称边也要赋值为权重
G.arcs[x][y] = w;
G.arcs[y][x] = w;
}
else {
G.arcs[x][y] = w;
}
}
}
void Print_Graph(Graph G) //打印邻接矩阵
{
cout << "\n该图的邻接矩阵为:" << endl;
cout.setf(ios::left); //输出左对齐
cout << setw(4) << "";
for (int i = 0; i < G.vexnum; i++) {
cout << setw(4) << G.vexs[i].data;
}
cout << endl;
for (int i = 0; i < G.vexnum; i++) {
cout << setw(4) << G.vexs[i].data;
for (int j = 0; j < G.vexnum; j++) {
cout << setw(4) << G.arcs[i][j];
}
cout << endl;
}
cout << endl;
}
int main()
{
Graph G;
Create_Graph(G); //创建
Print_Graph(G); //打印邻接矩阵
cout << endl;
return 0;
}
运行结果:
请输入图的类型(1.无向图 2.有向图):1
顶点的个数:8
请输入各顶点的名称:A B C D E F G H
请输入边的个数:9
请输入各边起点和终点的编号及权重:
0 1 3
0 2 12
1 3 5
1 4 6
2 3 7
2 4 10
5 6 9
5 7 4
6 7 13
该图的邻接矩阵为:
A B C D E F G H
A 0 3 12 0 0 0 0 0
B 3 0 0 5 6 0 0 0
C 12 0 0 7 10 0 0 0
D 0 5 7 0 0 0 0 0
E 0 6 10 0 0 0 0 0
F 0 0 0 0 0 0 9 4
G 0 0 0 0 0 9 0 13
H 0 0 0 0 0 4 13 0
采用邻接矩阵表示图的优点是非常简单,但他的空间复杂度为O(n^2),n表示图中顶点的数目。若图是稠密图,则邻接矩阵是合适的表示方法;但如果图是稀疏图,就不适合采用邻接矩阵了。此时,一种更好的解决办法是使用邻接表。
2、邻接表
邻接表是图的一种链式存储结构。他用 n 个带头结点的单链表代替邻接矩阵的 n 行,并对图中的每个顶点 v 建立一个带头结点的单链表,将顶点 v 的相关信息存放在表头,表中其余的结点用来存放与顶点 v 相关的边的信息。此时的空间需求是O(n+e)(e表示图中包含的边的数目)。
基本数据结构:
typedef struct ArcNode { //边的结点结构类型
int adjvex; //该边的终点编号
int weight; //该边的权值
struct ArcNode* nextarc; //指向下一条边的指针
}ArcNode;
typedef struct VexNode { //顶点结构
char data;
ArcNode* firstarc; //指向第一条与该顶点有关的边的指针
}VexNode;
typedef struct Graph { //邻接表结构类型
VexNode* VNode; //定义邻接表
int vexnum, arcnum; //顶点数和边的个数
int type; //图的种类
int size; //邻接表的大小
}Graph;
创建邻接表:
void Create_Graph(Graph& G) //创建
{
cout << "请输入图的类型(1.无向图 2.有向图):";
cin >> G.type;
cout << "顶点的个数:";
cin >> G.vexnum;
G.VNode = (VexNode*)malloc(SIZE * sizeof(VexNode));
G.size = SIZE;
while (G.size < G.vexnum) { //根据点的个数动态分配空间
G.VNode = (VexNode*)realloc(G.VNode, (G.size + NEWSIZE) * sizeof(VexNode));
G.size += NEWSIZE;
}
Visit = (int*)malloc((G.size + 10) * sizeof(int));
cout << "请输入各顶点的名称:";
for (int i = 0; i < G.vexnum; i++) {
cin >> G.VNode[i].data;
G.VNode[i].firstarc = NULL; //邻接表初始化,所有单向链表均为空表
}
cout << "请输入边的个数:";
cin >> G.arcnum;
cout << "请输入各边起点和终点的编号及权重:" << endl;
int x, y, w; //x:起始点,y:终点,w:权重
ArcNode* p, * q;
for (int i = 0; i < G.arcnum; i++) {
cin >> x >> y >> w;
p = (ArcNode*)malloc(sizeof(ArcNode)); //创建一个用于存放当前边的结点p
p->nextarc = NULL;
p->adjvex = y;
p->weight = w;
q = G.VNode[x].firstarc;
//将边按顺序插入到链表末尾
if (q == NULL) {
G.VNode[x].firstarc = p;
}
else {
while (q->nextarc != NULL) {
q = q->nextarc;
}
q->nextarc = p;
}
if (G.type == 1) { //如果是无向图,要再创建一个表示对称边的结点p
p = (ArcNode*)malloc(sizeof(ArcNode));
p->nextarc = NULL;
p->adjvex = x;
p->weight = w;
q = G.VNode[y].firstarc;
if (q == NULL) {
G.VNode[y].firstarc = p;
}
else {
while (q->nextarc != NULL) {
q = q->nextarc;
}
q->nextarc = p;
}
}
}
}
全部程序:文章来源:https://www.toymoban.com/news/detail-463394.html
# include <iostream>
# include <queue>
# define SIZE 20
# define NEWSIZE 20
using namespace std;
typedef struct ArcNode { //边的结点结构类型
int adjvex; //该边的终点编号
int weight; //该边的权值
struct ArcNode* nextarc; //指向下一条边的指针
}ArcNode;
typedef struct VexNode { //顶点结构
char data;
ArcNode* firstarc; //指向第一条与该顶点有关的边的指针
}VexNode;
typedef struct Graph { //邻接表结构类型
VexNode* VNode; //定义邻接表
int vexnum, arcnum; //顶点数和边的个数
int type; //图的种类
int size; //邻接表的大小
}Graph;
void Create_Graph(Graph& G) //创建
{
cout << "请输入图的类型(1.无向图 2.有向图):";
cin >> G.type;
cout << "顶点的个数:";
cin >> G.vexnum;
G.VNode = (VexNode*)malloc(SIZE * sizeof(VexNode));
G.size = SIZE;
while (G.size < G.vexnum) { //根据点的个数动态分配空间
G.VNode = (VexNode*)realloc(G.VNode, (G.size + NEWSIZE) * sizeof(VexNode));
G.size += NEWSIZE;
}
Visit = (int*)malloc((G.size + 10) * sizeof(int));
cout << "请输入各顶点的名称:";
for (int i = 0; i < G.vexnum; i++) {
cin >> G.VNode[i].data;
G.VNode[i].firstarc = NULL; //邻接表初始化,所有单向链表均为空表
}
cout << "请输入边的个数:";
cin >> G.arcnum;
cout << "请输入各边起点和终点的编号及权重:" << endl;
int x, y, w; //x:起始点,y:终点,w:权重
ArcNode* p, * q;
for (int i = 0; i < G.arcnum; i++) {
cin >> x >> y >> w;
p = (ArcNode*)malloc(sizeof(ArcNode)); //创建一个用于存放当前边的结点p
p->nextarc = NULL;
p->adjvex = y;
p->weight = w;
q = G.VNode[x].firstarc;
//将边按顺序插入到链表末尾
if (q == NULL) {
G.VNode[x].firstarc = p;
}
else {
while (q->nextarc != NULL) {
q = q->nextarc;
}
q->nextarc = p;
}
if (G.type == 1) { //如果是无向图,要再创建一个表示对称边的结点p
p = (ArcNode*)malloc(sizeof(ArcNode));
p->nextarc = NULL;
p->adjvex = x;
p->weight = w;
q = G.VNode[y].firstarc;
if (q == NULL) {
G.VNode[y].firstarc = p;
}
else {
while (q->nextarc != NULL) {
q = q->nextarc;
}
q->nextarc = p;
}
}
}
}
int main()
{
Graph G;
Create_Graph(G); //创建
cout << endl;
return 0;
}
以上是我的个人学习成果,很高兴与大家分享。文章来源地址https://www.toymoban.com/news/detail-463394.html
到了这里,关于图的创建(详解邻接矩阵和邻接表)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!