有哪些信誉好的足球投注网站- 1、本文档共32页，可阅读全部内容。
- 2、有哪些信誉好的足球投注网站（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
查看更多
1
1.3.3 图
一、图的定义和术语
1、定义：
由非空的顶点有穷集和边的有穷集组成。
记为G（V，E） V：顶点集，非空 E：边集，可以是空集 (此时，只有顶点没有边)
V1
V2
V3
V4
V5
★图中数据元素之间的关系可以是任意的！
2
2、术语：
●有向图与无向图
有向图： 图中每条边都有方向 有向边以Vi ，Vj表示 又称为弧，弧尾： Vi 弧头： Vj
V2
V3
V4
V1
V5
V2
V3
V4
V1
V5
无向图：
由无向边组成 以(Vi ，Vj )表示
Vi
Vj
Vi
Vj
有向图
无向图
3
●邻接：若(Vi，Vj)∈E，则Vi与Vj互为邻接；
若为有向边Vi ，Vj，则Vj是Vi的邻接点。
●顶点的度D(Vi)：
有向图：
出度：以该顶点为弧尾的弧的数目
入度：以该顶点为弧头的弧的数目
顶点的度 = 出度+入度
无向图：以该顶点为一个端点的边的条数。
总边数 ＝
2
1
∑D(Vi)
i=1
n
4
●路径：从一个顶点到另一个顶点的顶点序列
如图中V1到V4的路径有：
V1——V2 —— V3 —— V4
V1—— V3 —— V4
V1—— V5 —— V4
第一个顶点与最后一个顶点相同的的路径称为环，如：
V1—— V2 —— V3 ——V1
V1
V2
V3
V4
V5
5
●连通与连通图：
在图中若两个顶点之间有路径，则称这两个顶点是连通的。任意两个顶点都连通的图称为连通图。
强连通图：有向图的每一对顶点之间相互都存在路径。
V2
V3
V4
V1
V5
V2
V3
V4
V1
V5
连通图
非连通图
6
●权与网：
图中边或弧所具有的相关数称为权，表明从一个顶点到另一个顶点的距离或耗费。
带权的图称为网（或网络）。
V2
V3
V4
V1
V5
3
4
2
8
9
5
7
二、图的存储
1.邻接矩阵法(数组实现)：
①给顶点编号
②建立关系矩阵： aij的值表示j号顶点是否为i号顶点邻接点。
V2
V3
V4
V1
V5
0 1 0 0 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0
12345
A=
有向图的邻接矩阵
顶点的出度为该行的元素之和
顶点的入度为该列的元素之和
8
V2
V3
V4
V1
V5
0 1 0 1 1 1 0 1 0 0 0 1 0 1 1 1 0 1 0 0 1 0 1 0 0
12345
A=
无向图的邻接矩阵
无向图的邻接矩阵是对称矩阵， 顶点Vi的度是i行（或列）的元素之和。
9
V2
V3
V4
V1
V5
3
4
2
8
9
5
权值图的邻接矩阵：
aij的值表示边或弧aij的权。
∞ 3 ∞ ∞ 2 ∞ ∞ 4 ∞ ∞ ∞ ∞ ∞ ∞ 9
8 ∞ 5 ∞ ∞
∞ ∞ ∞ ∞ ∞
12345
A=
10
★图的邻接矩阵C语言描述：
#define MAXNUM 20
typedef struct{
elemtype node[MAXNUM];
int arcs[MAXNUM][MAXNUM];
}graph;
MAXNUM：图中顶点的最大个数
node[ ]：表示顶点集
arcs[ ][ ]：表示邻接矩阵
11
★邻接矩阵的优点：
增减边的操作简单，修改arcs[i][j]的值就行了；
★邻接矩阵的缺点：
增减顶点的操作需搬移大量元素；
存储空间的浪费：
若边 顶点2 ，则邻接矩阵为稀疏矩阵
12
2.邻接表法（链式存储）：
每个顶点建立一个单链表：
单链表中的结点是该顶点的所有邻接顶点
V2
V3
V4
V1
V5
data
1
2
4
^
5
data
2
1
^
3
data
3
2
4
^
5
data
4
1
^
3
data
5
1
^
3
用一维数组存储头结点
13
邻接表中包含两种结点：
data
i
头结点：
每个顶点对应一个头结点
邻接结点：
j
与头结点邻接的顶点
★邻接表的优点：
节省空间、操作较简便
14
图的存储（课堂练习）
请写出下面这副图的邻接表
1、给顶点编号
2、建立顶点数组
3、建立各顶点的邻接链表
注意，此图为有向图
2
1
3
4
5
1
文档评论（0）