1、图的定义及分类
图是由一组顶点和一组能够将两个顶点相连的边组成的
一般使用数字0至V-1来表示一张含有 V 个顶点的图中的各个顶点
2、图的相关术语
相邻顶点:
当两个顶点通过一条边相连时, 我们称这两个顶点是相邻的, 并称该连接依附于这两个顶点
度数:
某个顶点的度数即为依附于它的边的总数
3、无向图的表示方法
1.邻接矩阵
我们可以使用一个 V 乘 V 的二维矩阵。 当顶点 v 和顶点 w 之间有相连接的边时, 定义 v 行 w 列的元素值为1, 否则为0。
2.邻接表
我们可以使用一个以顶点为索引的列表数组, 其中的每个元素都是和该顶点相邻的顶点列表
4、图的邻接表存储表示
我们需要定义三种结构
首先,我们要定义 边节点的结构,比如图中v3-v0这一条边,它包含了两个信息:①这条边所属的顶点 ②指向该顶点下一条边的指针
如图所示,3代表了它连接v0和v3顶点,后面的指针域代表下一条边
//边的结构
typedef struct ArcNode
{
int adjvex;//这条边所属的顶点
ArcNode *nextarc;//指向该顶点下一条边的指针
}ArcNode;
然后我们要定义表头节点,它包含了两个信息:①顶点的信息,比如顶点的权值 ②指向该顶点的第一条边
typedef struct VexNode
{
int data;//储存顶点的信息
ArcNode* firstarc;//指向该顶点的第一条边
}VexNode,AdjList[Max];
注意理解Adjlist[Max]的含义,数组类型AdjList
,它是由VexNode
类型元素构成的,数组的长度为Max
。Max表示图中顶点的个数。
换句话说,AdjList[MVNum]
是一个数组类型,包含了Max
个元素,每个元素都是VexNode
类型的结构体,我们把AdjList称为邻接表类型
最后我们再定义无向图,它包含了两个信息:①邻接表 ②图的顶点数量和边数量
//图的结构
typedef struct
{
AdjList list;
int vexnum;
int arcnum;
}AlGraph;
5、邻接表的构建
步骤:
①输入总顶点数,总边数
②输入各顶点的值
③输入各边所依附的两个顶点
④构建新的边节点(使用头插法)文章来源:https://www.toymoban.com/news/detail-757704.html
bool CreateGraph(AlGraph& G)
{
cout << "请输入总顶点数,边数" << endl;
cin >> G.vexnum >> G.arcnum;
cout << "请输入各顶点的值" << endl;
//构建邻接表的顶点
for (int i = 1; i <=G.vexnum; i++)
{
cin >> G.list[i].data;
G.list[i].firstarc = NULL;
}
cout << "请输入各边所依附的顶点" << endl;
int i,j;
int v1, v2;
//构建新的边节点
for (int k = 0; k < G.arcnum; k++)
{
cin >> v1 >> v2;//v1,v2是一条边所对应的两个顶点
//i,j表示顶点在邻接表中对应的下标
i = LocateVex(G, v1);
j = LocateVex(G, v2);
//因为是无向图,所以一条边可以依附于两个顶点,所以我们要新创建两个边节点
ArcNode* p1 = new ArcNode();
ArcNode* p2 = new ArcNode();
//头插法将新结点*p1插入顶点vi的边表头部
p1->adjvex = j;//注意区分下标,如果是插入顶点vi,那么下标就是j,反之如果插入顶点vj,那么下标就是i
p1->nextarc = G.list[i].firstarc;
G.list[i].firstarc = p1;
//头插法将新结点* p2插入顶点vj的边表头部
p2->adjvex = i;
p2->nextarc = G.list[j].firstarc;
G.list[j].firstarc = p2;
}
return true;
}
文章来源地址https://www.toymoban.com/news/detail-757704.html
到了这里,关于数据结构与算法————无向图的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!