汉字释义(基本信息 基本解释 详细解释 康熙字典 说文解字)

几何学(图在几何学中的意义 定义 图的基本操作)

图的存储结构(邻接矩阵存储结构 邻接表)

图的遍历(深度优先遍历 广度优先遍历)

最小生成树问题(图的生成树和森林 最小生成树)

拓扑排序问题

定义(二元组的定义 三元组的定义)

基本术语(路径 其他)

分类(有/无向图 单图)

图像

图的遍历

重要的图

图的基本概念

汉字释义

基本信息

拼音：tú

部首：口

部外笔画：5

总笔画：8

笔顺：25354441

五笔：ltui

编码：CJK

统一汉字：U+56FE

仓颉：WHEY

四角：60303

结构：全包围

基本解释

1.用一定的色彩和线条等绘制出来的形象

2.画，绘制，绘影图形

3.谋取

详细解释

图

图 tú

〈动〉

(1) (会意。从囗，从啚。囗( wéi)，表示范围。啚( bǐ),“鄙”的本字，表示艰难。合起来表示规划一件事，需慎重考虑，相当不容易。本义:谋划,反复考虑)

(2) 同本义 [plan and contrive;consider again and again]

图,画计难也。——《说文》

是究是图。——《诗·小雅·常棣》。传:“谋也。”

君与臣图事。——《仪礼·聘礼》

君不图与。——《公羊传·庄公十三年》

而天下可图也。——《战国策·秦策》

(3) 又如:试图(打算);图计(谋划)

(4) 图谋;谋取 [sheme;seek;pursue;design]

阙秦以利 晋,唯君图之。——《左传·僖公三十年》

举其一不计其十,究其旧不图其新。——韩愈《原毁》

而后乃今将图南。——《庄子·逍遥游》

不可图也。——《三国志·诸葛亮传》

与图大事。——《资治通鉴》

图报复也。——清· 薛福成《观巴黎油画记》

以图将来。——清· 梁启超《谭嗣同传》

(5) 又如:图王(图谋王业);图功(图谋建立功业);图回(图谋运转);图全(图谋保全自身);图利(图谋私利);图私利;图一时之痛快;图名;图害(谋害);图饱私囊;图吞公款

(6) 筹划;设法对付 [plan and prepare;project]

无使滋蔓,蔓难图也。——《左传·隐公元年》

(7) 又如:图治(想办法把国家治好)

(8) 绘画 [draw]

上思股肱之美,乃图画其人于麒麟角。——《汉书·苏武传》

(9) 又如:图形(画出人的相貌);图工(善于绘画的人);图画(描绘人或物的形像)

(10) 摹拟 [imitate]

命铸铜以图其像。——《水经注》

(11) 预料,料想到。多用于否定 [expect]

子在 齐闻《韶》,三月不知肉味,曰:“不图为乐之至于斯也。”——《论语·述而》

不图子自归。——宋· 陆游《过小孤山大孤山》

词性变化

图

图 tú

〈名〉

(1) 所画的图画 [picture;drawing;chart]

至见其图,状貌如妇人好女。——《史记·留侯世家》

然不得列于名臣之图。——《汉书·苏武传》

(2) 又如:看图识字;图载(以图像表达);图障(绘有图画的屏风);图卷;图法(图录和法典);图轴(画轴;画卷);略图(简单的图画);图经(附有图画、地图的书籍或地理志);图说(兼附图画以助解说的著作)

(3) 地图 [map]

有司案图。——《史记·廉颇蔺相如列传》

河出图, 洛出书,圣人则之。——《易·系辞上》

灿若图绣。——《徐霞客游记·游黄山记》

普法交战图。—— 清· 薛福成《观巴黎油画记》

山水之图。——蔡元培《图画》

(4) 又如:图本(图样);图志(附有地图的地方志);图牒(图籍表册);图书(图籍;书籍);图式;图例;图板;图忏(古代方士或儒生编造的关于帝王受命征验一类的书,多为隐语、预言);图纬(图忏和纬书)

(5) 版图。有所有权与管辖权的领土,行使主权的领土 [domain]

州图领同谷,驿道出流沙。——唐· 杜甫《秦州杂诗》

(6) 意图;意愿 [intentions]

帝子留遗恨,曹公屈壮图。—— 杜甫《过南岳入洞庭湖》

(7) 塔,即“浮图”的简称 [tower]

南峰北岭,多结禅栖之士;东岩西谷,又是刹灵之图。——《水经注》

(8) 明清时地方区划名 [tu]

改乡为都,改里为图。——顾炎武《日知录》引《萧山县志》

(9) 书籍 [book]。如:图典(图书和经典);图史(图书和史籍)

康熙字典

〔古文〕𡈖𡇴《唐韵》《集韵》《韵会》《正韵》𠀤同都切，音徒。《说文》计画难也。从囗啚。啚，难意也。《徐锴曰》图画必先规画之也，故从囗。啚者吝啬难之意也。　又《尔雅·释诂》谋也。《书·太甲》愼乃俭德，惟怀永图。又《君牙》思其艰，以图其易，民乃宁。又《周礼·秋官·大行人》春朝诸侯而图天子之事。《注》王者春见诸侯，则图其事之可否也。　又度也。《诗·小雅》是究是图，亶其然乎。《论语》不图为乐之至於斯也。　又除治也。《左传·隐元年》无使滋蔓。蔓，难图也。　又计也。《周礼·秋官·小司寇》孟冬祀司民，献民数于王，王拜受之，以图国用，而进退之。　又河图。《易·系辞》河出图，洛出书，圣人则之。《孔安国曰》河图者，伏羲氏王，龙马出河，遂则其文以画八卦。《通鉴》汉光武帝读河图会昌符曰：赤刘之九会命岱宗。《春秋纬》河图有九篇。　又版图。《周礼·天官·宫正》为之版以待。《释文》版，名籍。图，地图也。又《地官·大司徒》以天下土地之图，周知九州之地域广轮之数。又《夏官·职方氏》掌天下之图，以掌天下之地。《注》图若今司空郡国与地图也。《史记·酇侯世家》沛公至咸阳，萧何独先入，收秦丞相御史律令图书，具知天下阸塞戸口多少强弱处。　又图谶，占验之书也。《後汉·光武纪》李通以图谶说帝。《又》中元元年，宣布图谶於天下。　又图象。《周礼·秋官·司约》小约剂书于丹图。《注》小约剂万民约也。丹图，雕器簠簋之属有图象者也。《何晏·景福殿赋》图象，古昔以当箴规。《王延寿·鲁灵光殿赋》图画天地，品类羣生。　又浮图，佛敎也。又寺塔亦曰浮图。杜甫有和高适登慈恩寺浮图诗。又《王君玉·国老谈苑》李允则守雄州，出库钱建浮图。监司劾奏，眞宗使密谕之。允则曰：非留心释氏，实为边地起望楼耳。《韩愈·王仲舒墓志》禁僧道，不得於境内立浮图，以其诳丐渔利，夺编氓之产也。　又叶他鲁切，音吐。《诗·大雅》我仪图之，惟仲山甫举之。《易林》为隶所图，与众庶伍。

说文解字

清代陈昌治刻本『说文解字』

【卷六】【囗部】图画计难也。从囗从啚。啚，难意也。同都切〖注〗徐锴曰：“规画之也。故从囗。”

清代段玉裁『说文解字注』

画计难也。左传曰。咨难为谋。画计难者，谋之而苦其难也。国语曰。夫谋必素见成事焉而後履之。谓先规画其事之始终曲折。历歴可见。出於万全。而後行之也。故引伸之义谓绘画为图。聘礼曰。君与卿图事。释诂曰。图，谋也。小雅传曰。虑，图皆谋也。从囗。规画之意。从啚。啚，逗。难意也。说从啚之意。啚者，啬也。啬者，爱濇也。愼难之意。同都切。

几何学

图在几何学中的意义

图，技术制图中的基础术语，指用点、线、符号、文字和数字等描绘事物几何特征、形态、位置及大小的一种形式。

在数学上，一个图是表示物件与物件之间的关系的方法，是图论的基本研究对象。

定义

图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。

在上面两个图结构中，一个是有向图，即每条边都有方向，另一个是无向图，即每条边都没有方向。

在有向图中，通常将边称作弧，含箭头的一端称为弧头，另一端称为弧尾，记作<vi,vj>，它表示从顶点vi到顶点vj有一条边。

若有向图中有n个顶点，则最多有n(n-1)条弧，我们又将具有n(n-1)条弧的有向图称作有向完全图。以顶点v为弧尾的弧的数目称作顶点v的出度，以顶点v为弧头的弧的数目称作顶点v的入度。在无向图中，边记作(vi,vj)，它蕴涵着存在< vi,vj>和<vj,vi>两条弧。若无向图中有n个顶点，则最多有n(n-1)/2条弧，我们又将具有n(n-1)/2条弧的无向图称作无向完全图。与顶点v相关的边的条数称作顶点v的度。

路径长度是指路径上边或弧的数目。

若第一个顶点和最后一个顶点相同，则这条路径是一条回路。

若路径中顶点没有重复出现，则称这条路径为简单路径。

在无向图中，如果从顶点vi到顶点vj有路径，则称vi和vj连通。如果图中任意两个顶点之间都连通，则称该图为连通图，否则，将其中的极大连通子图称为连通分量。

在有向图中，如果对于每一对顶点vi和vj，从vi到vj和从vj到vi都有路径，则称该图为强连通图；否则，将其中的极大连通子图称为强连通分量。

图的基本操作

（1）创建一个图结构 CreateGraph(G)

（2）检索给定顶点 LocateVex(G,elem)

（3）获取图中某个顶点 GetVex(G,v)

（4）为图中顶点赋值 PutVex(G,v,value)

（5）返回第一个邻接点 FirstAdjVex(G,v)

（6）返回下一个邻接点 NextAdjVex(G,v,w)

（7）插入一个顶点 InsertVex(G,v)

（8）删除一个顶点 DeleteVex(G,v)

（9）插入一条边 InsertEdge(G,v,w)

（10）删除一条边 DeleteEdge(G,v,w)

（11）遍历图 Traverse(G,v)

图的存储结构

邻接矩阵存储结构

1．1 有向图的邻接矩阵

具有n个顶点的有向图可以用一个n′n的方形矩阵表示。假设该矩阵的名称为M，则当<vi,vj>是该有向图中的一条弧时，M[i,j]=1；否则M[i,j]=0。第i个顶点的出度为矩阵中第i行中"1"的个数；入度为第i列中"1"的个数，并且有向图弧的条数等于矩阵中"1"的个数。

1．2 无向图的邻接矩阵

具有n个顶点的无向图也可以用一个n′n的方形矩阵表示。假设该矩阵的名称为M，则当（vi,vj）是该无向图中的一条边时，M[i,j]=M[j,i]=1；否则，M[i,j]=M[j,j]=0。第i个顶点的度为矩阵中第i 行中"1"的个数或第i列中"1"的个数。图中边的数目等于矩阵中"1"的个数的一半，这是因为每条边在矩阵中描述了两次。

在C 语言中，实现邻接矩阵表示法的类型定义如下所示：

#define MAX_VERTEX_NUM 20

typedef struct graph{

Elemtype elem[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

int n;

} Graph;

邻接表

边结点的结构为：

adjvex是该边或弧依附的顶点在数组中的下标，next是指向下一条边或弧结点的指针

elem是顶点内容，firstedge是指向第一条边或弧结点的指针。

在C语言中，实现邻接表表示法的类型定义如下所示：

#define MAX_VERTEX_NUM 30 //最大顶点个数

type struct EdgeLinklist{ //边结点

int adjvex;

struct EdgeLinklist *next;

} EdgeLinklist;

typedef struct VexLinklist{ //顶点结点

Elemtype elem;

EdgeLinklist *firstedge;

} VexLinklist,AdjList[MAX_VERTEX_NUM];

创建有向图和无向图邻接表的算法实现：

（1） 创建有向图邻接表

void Create_adj(AdjList adj, int n) {

for (i=0;i<n;i++){ //初始化顶点数组

scanf(&adj.elem);

adj.firstedge=NULL;

}

scanf(&i,&j); //输入弧

while (i) {

s=(EdgeLinklist*)malloc(sizeof(EdgeLinklist)); //创建新的弧结点

s->adgvex=j-1;

s->next=adj[i-1].firstedge; //将新的弧结点插入到相应的位置

adj[i-1].firstegde=s;

scanf(&i,&j); //输入下一条弧

}

}

（2）创建无向图的邻接表

void Create_adj(AdjList adj, int n) {

for (i=0;i<n;i++){ //初始化邻接表

scanf(&adj.elem);

adj.firstedge=NULL;

}

scanf(&i,&j); //输入边

while (i) {

s1=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));

s1->adgvex=j-1;

s2=(EdgeLinklist*)malloc(sizeof(EdgeLinklist));

s2->adgvex=i-1;

s1->next=adj[i-1].firstedge;

adj[i-1].firstegde=s1;

s2->next=adj[j-1].firstedge;

adj[j-1].firstegde=s2;

scanf(&i,&j);

}

}

图的遍历

常见的图遍历方式有两种：深度优先遍历和广度优先遍历，这两种遍历方式对有向图和无向图均适用。

深度优先遍历

深度优先遍历的思想类似于树的先序遍历。其遍历过程可以描述为：从图中某个顶点v出发，访问该顶点，然后依次从v的未被访问的邻接点出发继续深度优先遍历图中的其余顶点，直至图中所有与v有路径相通的顶点都被访问完为止。

深度优先遍历算法实现：

为了便于在算法中区分顶点是否已被访问过，需要创建一个一维数组visited[0..n-1]（n是图中顶点的数目），用来设置访问标志，其初始值visited（0≤i≤n-1）为"0"，表示邻接表中下标值为i的顶点没有被访问过，一旦该顶点被访问，将visited置成"1"。

int visited[0..n-1]={0,0,...0};

void DFS(AdjList adj,int v)

{//v是遍历起始点的在邻接表中的下标值，其下标从0开始

visited[v]=1; visite(adj[v].elem);

for (w=adj[v].firstedge;w;w=w->next)

if (!visited[w->adjvex]) DFS(adj,w->adjvex);

}

对于无向图，这个算法可以遍历到v顶点所在的连通分量中的所有顶点，而与v顶点不在一个连通分量中的所有顶点遍历不到；而对于有向图可以遍历到起始顶点v能够到达的所有顶点。若希望遍历到图中的所有顶点，就需要在上述深度优先遍历算法的基础上，增加对每个顶点访问状态的检测：

int visited[0..n-1]={0,0,...0};

void DFSTraverse(AdjList adj)

{

for (v=0;v<n;v++) if (!visited[v]) DFS(adj,v);

}

广度优先遍历

对图的广度优先遍历方法描述为：从图中某个顶点v出发，在访问该顶点v之后，依次访问v的所有未被访问过的邻接点，然后再访问每个邻接点的邻接点，且访问顺序应保持先被访问的顶点其邻接点也优先被访问，直到图中的所有顶点都被访问为止。下面是对一个无向图进行广度优先遍历的过程。

下面我们讨论一下实现广度优先遍历算法需要考虑的几个问题：

（1）在广度优先遍历中，要求先被访问的顶点其邻接点也被优先访问，因此，必须对每个顶点的访问顺序进行记录，以便后面按此顺序访问各顶点的邻接点。应利用一个队列结构记录顶点访问顺序，就可以利用队列结构的操作特点，将访问的每个顶点入队，然后，再依次出队，并访问它们的邻接点；

（2）在广度优先遍历过程中同深度优先遍历一样，为了避免重复访问某个顶点，也需要创建一个一维数组visited[0..n-1]（n是图中顶点的数目），用来记录每个顶点是否已经被访问过。

int visited[0..n-1]={0,0,...0};

void BFS(AdjList adj,int v)

{//v是遍历起始点在邻接表中的下标，邻接表中下标从0开始

InitQueue(Q); //Q是队列

visited[v]=1; visite(adj[v].elem); EnQueue(Q,v);

while (!QueueEmpty(Q)) {

DeQueue(Q,v);

for (w=adj[v].firstedge;w;w=w->next)

if (!visited[w->adjvex]) {

visited[w->adjvex]=1;

visite(adj[w->adjvex].elem);

EnQueue(Q,w->adjvex); }

}

}

最小生成树问题

图的生成树和森林

对于一个拥有n个顶点的无向连通图，它的边数一定多余n-1条。若从中选择n-1条边，使得无向图仍然连通，则由n个顶点及这 n-1条边（弧）组成的图被称为原无向图的生成树。显示了一个无向连通图的生成树，双线圈表示的顶点为生成树的根结点。

最小生成树

在一个图中，每条边或弧可以拥有一个与之相关的数值，我们将它称为权。这些权可以具有一定的含义，比如，表示一个顶点到达另一个顶点的距离、所花费的时间、线路的造价等等。这种带权的图通常被称作网。

图或网的生成树不是唯一的，从不同的顶点出发可以生成不同的生成树，但n个结点的生成树一定有n-1条边

下面我们计算一下上面两棵生成树的权值之和。第一棵生成树的权值总和是：16+11+5+6+18=56；第二棵生成树的权值是：16+19+33+18+6=92。通常我们将权值总和最小的生成树称为最小生成树。

构造最小生成树的方法：最初生成树为空，即没有一个结点和一条边，首先选择一个顶点作为生成树的根，然后每次从不在生成树中的边中选择一条权值尽可能小的边，为了保证加入到生成树中的边不会造成回路，与该边邻接的两个顶点必须一个已经在生成树中，一个则不在生成树中，若网中有n个顶点（这里考虑的网是一个连通无向图），则按这种条件选择n-1边就可以得到这个网的最小生成树了。详细的过程可以描述为：设置2个集合，U集合中的元素是在生成树中的结点，V-U集合中的元素是不在生成树中的顶点。首先选择一个作为生成树根结点的顶点，并将它放入U集合，然后在那些一端顶点在U集合中，而另一端顶点在V-U集合中的边中找一条权最小的边，并把这条边和那个不在U集合中的顶点加入到生成树中，即输出这条边，然后将其顶点添加到U集合中，重复这个操作n-1次。

下面我们考虑一下如何实现这个操作过程的算法。

分析 ：（1）它主要有两项操作：按条件选择一条边和将顶点加入到U集合中；（2）网中的每个顶点不是在U集合中，就是在V-U集合中。为了提高算法的时间、空间效率，我们将为这个算法设计一个辅助数组closedge，用来记录从集合U到集合V-U具有最小权值的边。对每个属于V-U集合的顶点，在辅助数组中存在一个相应的分量closedge[i-1]，它包括两个域，一个域用来表示在该顶点与V-U集合中某些顶点构成的边中权最小的那条边的权值，若该顶点进入U集合，则值为0；另一个域表示这条最小权值的边对应的在V-U集合中的顶点下标。其类型定义如下所示：

#define MAX_NUM 10

struct

{

int adjvex;

float lowcist;

}closedge[MAX_NUM];

整个算法的执行过程可以描述为：

{ 初始化closedge数组的内容；

选择某个顶点k作为生成树的根结点，并将它加入到U集合中；

重复下列操作n-1次：

l 选择一条满足条件的边；

l 输出这条边的两个端点；

l 修改V-U集合中的顶点信息，即与U集合中构成最小权值的边。

}

假设该网以邻接矩阵的形式给出，则完整的算法为：

void Mini_SpanTree(Graph G,int k,int n)

{//G是网的邻接矩阵，k是生成树根结点的序号，n是网的顶点数目

for (j=0;j<n;j++)

if (j!=k) closedge[j]={k,G[k][j]};

closedge[k].lowcost=0;

for (i=1;i<n;i++)

{

k=minmun(closedge);

printf(k,closedge[k].adjvex);

closedge[k].lowcost=0; //将顶点加入U集合中

for (j=0;j<n;j++)

if (closedge&&G[k][j]<closedge[j].lowcost)

closedge[j]={k,G[k][j]};

}

}

拓扑排序问题

拓扑排序是有向图的一个重要操作。在给定的有向图G中，若顶点序列vi1,vi2,...,vin满足下列条件：若在有向图G中从顶点vi到顶点vj有一条路径，则在序列中顶点vi必在顶点vj之前，便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。

举例：计算机专业的学生应该学习的部分课程及其每门课程所需要的先修课程。

拓扑排序的方法：

（1）从图中选择一个入度为0的顶点且输出之；

（2）从图中删掉该顶点及其所有以该顶点为弧尾的弧；

反复执行这两个步骤，直到所有的顶点都被输出，输出的序列就是这个无环有向图的拓扑序列。细心的读者可能会发现：在每一时刻，可能同时存在多个入度为0的顶点，选择注：表中c1~c9列表示的是每个顶点的入度。

下面我们讨论一下如何实现拓扑排序的算法。假设有向图以邻接表的形式存储。

下面给出算法实现的基本过程：

{ 将所有入度为0的顶点入栈；

当栈非空时重复执行下列操作：

从栈中退出顶点k；

（1）将k顶点的信息输出；

（2）将与k邻接的所有顶点的入度减1。

}

#define MAX_VERTEX_NUM 30 //最大顶点个数

type struct EdgeLinklist{ //边结点

int adjvex;

struct EdgeLinklist *next;

}EdgeLinklist;

typedef struct VexLinklist{ //顶点结点

Elemtype elem;

int indegree; //记录顶点的入度

EdgeLinklist *firstedge;

}VexLinklist,AdjList[MAX_VERTEX_NUM];

下面是拓扑排序的完整算法。

Status TopologicalSort(AdjList adj)

{InitStack(s);

for (i=0;i<MAX_VERTEX_NUM-1;i++)

if (adj.indegree==0) Push(s,i);

while (!StackEmpty(s)) {

Pop(s,i); printf(i);

for (p=adj.firstedge;p;p=p->next) {

adj.indegree-=1;

if (adj.indegree==0) Push(s,i);}

定义

二元组的定义

图G是一个有序二元组(V,E)，其中V称为顶集，E称为边集。它们亦可写成V(G)和E(G)。

E的元素是一个二元组数对，用(x,y)表示，其中。

三元组的定义

一个图（Graph），是指一个三元组(V,E,I)，其中V称为顶集(Vertices Set)，E称为边集(Edges set)，E与G不相交；I称为关联函数，I将E中的每一个元素映射到。如果那么称边e连接顶点u,v，而u,v则称作e的端点，u,v此时关于e相邻。同时，若两条边i,j有一个公共顶点u，则称i,j关于u相邻。

基本术语

在顶点1有一个环阶（Order）：图G中顶集V的大小称作图G的阶。

子图（Sub-Graph）：G'称作图G=<V,E>的子图，当图G'=<V',E'>，且V‘包含于V，E’包含于E。

生成子图（Spanning Sub-Graph）：指满足条件V(G') = V(G)的G的子图G。

路径

环(Loop)：若一条边的两个顶点为同一顶，则此边称作环。

路径（Path）：从u到v的一条路径是指一个序列v0,e1,v1,e2,v2,...ek,vk，其中ei的顶点为vi及vi - 1，k称作路径的长度。如果它的起止顶点相同，该路径是“闭”的，反之，则称为“开”的。一条路径称为一简单路径(simple path)，如果路径中除起始与终止顶点可以重合外，所有顶点两两不等。

行迹（Trace）：如果路径P(u,v)中边各不相同，则该路径称为u到v的一条行迹。

轨道（Track）：如果路径P(u,v)中顶各不相同，则该路径称为u到v的一条轨道。

闭的行迹称作回路（circuit），闭的轨称作圈（Cycle）。

（另一种定义是：walk对应上述的path，path对应上述的track。Trail对应trace。）

其他

桥（bridge）：若去掉一条边，便会使得整个图不连通，该边称为桥。

分类

有/无向图

如果给图的每条边规定一个方向，那么得到的图称为有向图。在有向图中，与一个节点相关联的边有出边和入边之分。相反，边没有方向的图称为无向图。

度（Degree）是一个顶点的度是指与该边相关联的边的条数，顶点v的度记作d(v)。显然有：

有向图的顶点的度可分In degree和out degree。一个顶点的In Degree是指与该边相关联的入边的条数，Out Degree则指与该边相关联的出边的条数。

单图

一个图如果

任意两顶点之间只有一条边（在有向图中为两顶点之间每个方向只有一条边）；

边集中不含环

则称为单图。图的存储表示

数组（邻接矩阵）存储表示（有向或无向）

邻接表存储表示

有向图的十字链表存储表示

无向图的邻接多重表存储表示

一个不带权图中若两点不相邻，邻接矩阵相应位置为0，对带权图(网)，相应位置为∞。一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一。在邻接表中，对图中每个顶点建立一个单链表（并按建立的次序编号），第i个单链表中的结点表示依附于顶点vi的边（对于有向图是以顶点vi为尾的弧）。每个结点由两个域组成：邻接点域(adjvex)，用以指示与vi邻接的点在图中的位置，链域(nextarc)用以指向依附于顶点vi的下一条边所对应的结点。如果用邻接表存放网（带权图）的信息，则还需要在结点中增加一个存放权值的域（info）。每个顶点的单链表中结点的个数即为该顶点的出度(与该顶点连接的边的总数)。无论是存储图或网，都需要在每个单链表前设一表头结点，这些表头结点的第一个域data用于存放结点vi的编号i，第二个域firstarc用于指向链表中第一个结点。

图像

布图中呈现的任何单个的几何图形：

(1)作为底图或布图一部分的绘制图形；

(2)投影在屏幕上或目视的光学图像，通常经过若干倍的放大或缩小；

(3)被氧化的硅片上刻蚀出的二氧化硅图像；

(4)光学掩模版上及照相基片或干板上的乳胶层中的照相图像；

(5)基片上的涂层经曝光和显影后呈现的光致抗蚀剂图形。

图像是由扫描仪、摄像机等输入设备捕捉实际的画面产生的数字图像。由像素点阵构成的位图。

图像用数字任意描述像素点、强度和颜色。描述信息文件存储量较大，所描述对象在缩放过程中会损失细节或产生锯齿。在显示方面它是将对象以一定的分辨率分辨以后将每个点的色彩信息以数字化方式呈现，可直接快速在屏幕上显示。分辨率和灰度是影响显示的主要参数。图像适用于表现含有大量细节（如明暗变化、场景复杂、轮廓色彩丰富）的对象，如：照片、绘图等，通过图像软件可进行复杂图像的处理以得到更清晰的图像或产生特殊效果。

图的遍历

图的遍历方法有深度优先搜索法和广度(宽度)优先搜索法。

深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下：

Boolean visited[MAX_VERTEX_NUM]; //访问标志数组

Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数

void DFSTraverse (Graph G, Status(*Visit)(int v)){

VisitFunc = Visit;

for(v=0; v<G.vexnum; ++v)

visited[v] = FALSE; //访问标志数组初始化

for(v=0; v<G.vexnum; ++v)

if(!visited[v])

DFS(G, v); //对尚未访问的顶点调用DFS

}

void DFS(Graph G, int v){ //从第v个顶点出发递归地深度优先遍历图G

visited[v]=TRUE; VisitFunc(v); //访问第v个顶点

for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))

//FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空(0)，//若w是v的邻接顶点，NextAdjVex返回v的（相对于w的）下一个邻接顶点。

//若w是v的最后一个邻接点，则返回空(0)。

if(!visited[w])

DFS(G, w); //对v的尚未访问的邻接顶点w调用DFS

}

图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2, …, vi t，并均标记已访问过，然后再按照vi1,vi2, …, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。其非递归算法如下：

Boolean visited[MAX_VERTEX_NUM]; //访问标志数组

Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数

void BFSTraverse (Graph G, Status(*Visit)(int v)){

VisitFunc = Visit;

for(v=0; v<G.vexnum, ++v)

visited[v] = FALSE;

initQueue(Q); //置空辅助队列Q

for(v=0; v<G.vexnum; ++v)

if(!visited[v]){

visited[v]=TRUE; VisitFunc(v);

EnQueue(Q, v); //v入队列

while(!QueueEmpty(Q)){

DeQueue(Q, u); //队头元素出队并置为u

for(w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))

if(!Visited[w]){ //w为u的尚未访问的邻接顶点

Visited[w]=TRUE; VisitFunc(w);

EnQueue(Q, w);

}

}

}

}

重要的图

树

平面图

连通图

强连通图

有向无环图

AOV网

AOE网

完全图：每一对不同顶点间都有边相连的的图，记作Kn。

二分图：顶集，且每一条边都有一个顶点在X中，而另一个顶点在Y中。

完全二分图：二分图G中若任意两个X和Y中的顶点都有边相连。若，则图G记作Km,n。

正则图：如果图中所有顶点的度皆相等，则此图称为正则图

图的基本概念

h图是一个有序对<V，E>，V是结点集，E是边集，当&frac12;V&frac12;,&frac12;E&frac12;有限时，<V,E>称为有限图；否则称无限图.

h无向边, 与无序结点(v,u)相关联的边；有向边，与有序结点<v,u>相关联的边.

h无向图，每条边都是无向边的图，记作G=<V,E>; 每条边都是有向边的图，记作D=<V,E>.

h混合图，既有有向边，也有无向边的图.

h平凡图，仅有一个结点的图；零图，边集为空集的图<V, &AElig;>，即仅有结点的图.

h自回路(环)，关联于同一个结点的边.

h无向平行边，联结相同两个结点的多于1条的无向边；有向平行边，联结两个结点之间的多于1条且方向相同的有向边.

h简单图，不含平行边和自回路的图.

h在无向图G=<V,E>中，与结点v(&Icirc;V)关联的边数，即为结点度数deg(v)或d(v).；在有向图中，结点v的出度和入度之和为度数.

h在有向图D=<V,E>中，以v(&Icirc;V)为起点的边之条数为出度deg+(v)；以v(&Icirc;V)为终点的边之条数为入度deg－(v)..

h最大度数，D(G)=max{d(v)&frac12;v&Icirc;V}；最小度数，d(G)=min{d(v)&frac12;v&Icirc;V}

h有n个结点的且每对结点都有边相连无向简单图，无向完全图Kn. 此时有 ；有n个结点的且每对结点之间都有两条方向相反的边相关连的有向简单图为有向完全图，.此时有

h设G=<V,E>, V，E的子集V&cent;,E&cent;构成的图G&cent;=<V&cent;,E&cent;>是图G的子图；若G&cent;&Iacute;G且G&cent;&sup1;G，(V&cent;&Igrave;V或E&cent;&Igrave;E)，G&cent;是G的真子图.

h生成子图，设图G=<V,E>, 若E&cent;&Iacute;E, 则图<.V,E&cent;>是<V,E>的生成子图. 即结点与原图G相同的子图，为生成子图.

h补图`G=<V,E&cent;>，设G=<V,E>, 以V为结点集，以使G成为完全图所添加的边为边集E&cent;的图，就是图G的补图G&cent;,.，即<V,E&Egrave;E&cent;>是完全图, 其中E&Ccedil;E&cent;=&AElig;.

h图的同构，设G1=<V1,E1>和G2=<V2,E2>, 存在双射f：V1&reg;V2，"(vi,vj)&Icirc;E1, 当且仅当 (f(vi),f(vj))&Icirc;E2，且(vi,vj)与 (f(vi),f(vj))的重数相同. 则G1≌G2.

同构充分条件：建立两个图的对应关系，这个关系是双射函数.

同构必要条件：①结点数相同；②边数相同；③度数相同的结点个数相同.