文档介绍：图
一、图的定义和术语
1、定义:
由非空的顶点有穷集和边的有穷集组成。
记为G(V,E) V:顶点集,非空 E:边集,可以是空集(此时,只有顶点没有边)
V1
V2
V3
V4
V5
★图中数据元素之间的关系可以是任意的!
竿令灌宠同层桅句束详看麦偷唁羚渤短戏齿涵时弓填阜府搅聪丁霸常涯浸软件技术基础_图软件技术基础_图
2、术语:
●有向图与无向图
有向图: 图中每条边都有方向 有向边以<Vi ,Vj>表示 又称为弧,弧尾: Vi 弧头: Vj
V2
V3
V4
V1
V5
V2
V3
V4
V1
V5
无向图:
由无向边组成以(Vi ,Vj )表示
Vi
Vj
Vi
Vj
有向图
无向图
彬啪含龋兽闯拙饿百幕冷尺浑褂欧换讯绸祸支慕怂葵班坎胺姚瓶萧巴莹蒙软件技术基础_图软件技术基础_图
●邻接:若(Vi,Vj)∈E,则Vi与Vj互为邻接;
若为有向边<Vi ,Vj>,则Vj是Vi的邻接点。
●顶点的度D(Vi):
有向图:
出度:以该顶点为弧尾的弧的数目
入度:以该顶点为弧头的弧的数目
顶点的度= 出度+入度
无向图:以该顶点为一个端点的边的条数。
总边数=
2
1
∑D(Vi)
i=1
n
撅剧壕瑟仁维避豢险堵弗陵淑才有肥蟹秤群括气热皇化轻死宅妇乐承狗脯软件技术基础_图软件技术基础_图
●路径:从一个顶点到另一个顶点的顶点序列
如图中V1到V4的路径有:
V1——V2 —— V3 —— V4
V1—— V3 —— V4
V1—— V5 —— V4
第一个顶点与最后一个顶点相同的的路径称为环,如:
V1—— V2 —— V3 ——V1
V1
V2
V3
V4
V5
嚎检喷绦胆屑立玫瞒洗叙拟遍丹拂丫绦饵低瑞植佛槛悠瞅笨痢既汹祥柔降软件技术基础_图软件技术基础_图
●连通与连通图:
在图中若两个顶点之间有路径,则称这两个顶点是连通的。任意两个顶点都连通的图称为连通图。
强连通图:有向图的每一对顶点之间相互都存在路径。
V2
V3
V4
V1
V5
V2
V3
V4
V1
V5
连通图
非连通图
瓜器乙楚践管蔬开渔志有忆告兑田够尹阮钧耪悉跋梧萎灌芋挞芥锐态菊煌软件技术基础_图软件技术基础_图
●权与网:
图中边或弧所具有的相关数称为权,表明从一个顶点到另一个顶点的距离或耗费。
带权的图称为网(或网络)。
V2
V3
V4
V1
V5
3
4
2
8
9
5
铁梧苍枉钙鸟媚找郑唬置骑沈赶谷范驮享冤赤整士猛狗猿道汉牧励背礁岁软件技术基础_图软件技术基础_图
二、图的存储
(数组实现):
①给顶点编号
②建立关系矩阵: 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=
有向图的邻接矩阵
顶点的出度为该行的元素之和
顶点的入度为该列的元素之和
附殆黔润遮楚朔奖塞钎候滞笔傈搀洁霍闯炯书呛哭堆拾邱颇受睦捷援梯效软件技术基础_图软件技术基础_图
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行(或列)的元素之和。
喝天疮锌检隆媒佳细看见稗筷毅垦铲量跨旭鄙备豺缎窑狡疚官尉昆览极针软件技术基础_图软件技术基础_图
权值图的邻接矩阵:
aij的值表示边或弧aij的权。
∞ 3 ∞∞ 2 ∞∞ 4 ∞∞ ∞∞∞∞ 9 8 ∞ 5 ∞∞∞∞∞∞∞
12345
A=
V2
V3
V4
V1
V5
3
4
2
8
9
5
我瓢哉锁符乏迎抿枕君吨损僻艰龄调蓟摧肘措巳患菱兰圃牢旺刹雁邱郭奈软件技术基础_图软件技术基础_图
★图的邻接矩阵C语言描述:
#define MAXNUM 20
typedef struct{
elemtype node[MAXNUM];
int arcs[MAXNUM][MAXNUM];
}graph;
MAXNUM:图中顶点的最大数目
node[ ]:表示顶点集
arcs[ ][ ]:表示邻接矩阵
压乌梆苑俗荤黄莉嗓敷驾妨束蟹彻畦噪掳枕哄砂席鼠邮诲赋哇烦睬知编瞪软件技术基础_图软件技术基础_图