当前位置：文档之家 › 图(Graph)是一种较线性表和树更为复杂的非线性结构在线

图(Graph)是一种较线性表和树更为复杂的非线性结构在线

  • 格式：ppt
  • 大小：111.00 KB
  • 文档页数：28

下载文档原格式

  / 28

合集下载

第七章图状结构

第七章图状结构

图的应用非常广泛。
2
7.1 图的类型定义
7.2 图的存储表示
7.3 图的遍历
7.4 最小生成树 7.5 两点之间的最短路径问题 7.6 拓扑排序
7.7 关键路径
3
图的结构定义:
图是由一个顶点集 V 和一个弧集 R构 成的数据结构。 Graph = (V , R ) 其中，R＝{<v,w>| v,w∈V 且 P(v,w)} <v,w>表示从 v 到 w 的一条弧，并称 v 为弧尾，w 为弧头。
4
由于“弧”是有方向的，因此称由顶 点集和弧集构成的图为有向图。
例如: G1 = (V1, VR1)
A
B C D E
其中 V1={A, B, C, D, E} VR1={<A,B>, <A,E>,
<B,C>, <C,D>, <D,B>, <D,A>, <E,C> }
5
若<v, w>VR 且<w, v>VR, 则称 (v,w) 为顶点v 和顶点 w 之间存在一条边。 例如: G2=(V2,VR2) V2={A, B, C, D, E, F} VR2={(A,B), (A,E),
0 0 0 1 0 1
0 0 1 0 0 1
1 1 0 0 0 0
0 1 1 1 0 0
24
无向图邻接矩阵表示法特点：
1）无向图邻接矩阵是对称矩阵 2）顶点v的度 3）判断两顶点v、u是否为邻接点 4）顶点不变，在图中增加、删除边 5）适用于边稠密的图；
25
有向图的邻接矩阵 为非对称矩阵
0 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 0

最短路径算法及其应用

最短路径算法及其应用

湖北大学本科毕业论文（设计）题目最短路径算法及其应用姓名学号专业年级指导教师职称2011年 4月 20 日目录绪论 (1)1 图的基本概念 (1)1.1 图的相关定义 (1)1.2 图的存储结构 (2)1.2.1 邻接矩阵的表示 (2)1.2.2 邻接矩阵的相关结论 (3)2 最短路径问题 (3)2.1 最短路径 (4)2.2 最短路径算法 (4)2.2.1Dijkstra算法 (4)2.2.2Floyd算法 (5)3 应用举例 (5)3.1 Dijkstra算法在公交网络中的应用 (5)3.1.1 实际问题描述 (5)3.1.2 数学模型建立 (5)3.1.3 实际问题抽象化 (6)3.1.4 算法应用 (6)3.2 Floyd算法在物流中心选址的应用 (7)3.2.1 问题描述与数学建模 (7)3.2.2 实际问题抽象化 (7)3.2.3 算法应用 (8)参考文献 (10)附录 (11)最短路径算法及其应用摘要最短路径算法的研究是计算机科学研究的热门话题，它不仅具有重要的理论意义，而且具有重要的实用价值。

最短路径问题有广泛的应用，比如在交通运输系统、应急救助系统、电子导航系统等研究领域。

最短路径问题又可以引申为最快路径问题、最低费用问题等，但它们的核心算法都是最短路径算法。

经典的最短路径算法——Dijkstra和Floyd算法是目前最短路径问题采用的理论基础。

本文主要对Dijkstra和Floyd算法进行阐述和分析，然后运用这两个算法解决两个简单的实际问题。

【关键字】最短路径 Dijkstra算法 Floyd算法图论Shortest path algorithms and their applicationsAbstractThe research about the shortest path is a hot issue in computer science. It has both important theoretical significance and important utility value. The shortest path problem has broad application area, such as transport system, rescue system, electronic navigation system and so on. The shortest path problem can be extended to the problem of the fastest path problem and the minimum cost problem. But their core algorithms are all both the shortest path algorithms. The classical algorithms for the shortest path——Dijkstra and Floyd are the theoretical basis for solving the problems of the shortest path. The article mainly through the demonstration and analysis of the Dijkstra and Floyd algorithms, then use the algorithms to solve the two simple practical problems.【keywords】shortest path Dijkstra algorithm Floyd algorithm graph绪论随着知识经济的到来，信息将成为人类社会财富的源泉，网络技术的飞速发展与广泛应用带动了全社会对信息技术的需求，最短路径问题作为许多领域中选择最优问题的基础，在电子导航，交通旅游，城市规划以及电力，通讯等各种管网，管线的布局设计中占有重要的地位。

图(Graph)是一种复杂的非线性结构在人工智能.ppt

图(Graph)是一种复杂的非线性结构在人工智能.ppt

例
❖ 例】下图中无向图G5和有向图G6的邻接矩阵 分别为Al和A2。
A C D B
无向图的邻接矩阵
❖ 是对称矩阵 ❖ 每条边在矩阵中出现2次 ❖ 每和之和和每列之和相等，和代表顶点的度 ❖ 把矩阵的各元素求和/2，边数 ❖ 一个优点. A[2][3]==0 ❖ 缺点：插入一个顶点，删除一个顶点，比较麻烦
有向图中，以顶点v为始点的边的数目，称 为v的出度(Outdegree)，记为OD(v) 【例】上图G1中顶点v2的出度为2
注意：
❖ ①有向图中，顶点v的度定义为该顶点的入度和 出度之和，即D(v)=ID(v)+OD(v)。
e与n之间的关系
❖ ②无论有向图还是无向图，顶点数n、边数e和度 数之间有如下关系：
6．有根图和图的根
❖ 在一个有向图中，若存在一个顶点v，从该顶点 有路径可以到达图中其它所有顶点，则称此有向 图为有根图，v称作图的根。
连通图和连通分量
1．顶点间的连通性
❖ 在无向图G中，若从顶点vi到顶点vj有路径(当然从 vj到vi也一定有路径)，则称vi和vj是连通的。
2．连通图
❖ 若V(G)中任意两个不同的顶点vi和vj都连通(即有路径)， 则称G为连通图(Con-nected Graph)。 【例】图G2，和G3是连通图。
注意：
❖ 在以下讨论中，不考虑顶点 到或则其<要v自求l，身vv12≠的>v是2边。E。此(G即外)中若，的(不v一1，允条v许2边) ， 一条边在图中重复出现，即 只讨论简单的图。
完全图
❖ 无向图的完全图：每二个顶点之间都有边相连： 边数=n(n-1)/2，n为顶点个数
❖ 有向图的完全图：边数=n(n-1)，n是顶点个数。

数据结构答案 第8章 图学习指导

数据结构答案 第8章 图学习指导

第8章图8.1 知识点分析1．图的定义图（Graph）是由非空的顶点（V ertices）集合和一个描述顶点之间关系——边（Edges）的有限集合组成的一种数据结构。

可以用二元组定义为：G＝（V，E）其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

2．图的相关术语（1）无向图在一个图中，如果每条边都没有方向，则称该图为无向图。

（2）有向图在一个图中，如果每条边都有方向，则称该图为有向图。

（3）无向完全图在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图。

在一个含有n个顶点的无向完全图中，有n(n-1)/2条边。

（4）有向完全图在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图。

在一个含有n个顶点的有向完全图中，有n (n-1) 条弧。

（5）顶点的度在无向图中，一个顶点拥有的边数，称为该顶点的度。

记为TD(v)。

在有向图中，一个顶点拥有的弧头的数目，称为该顶点的入度，记为ID(v)；一个顶点拥有的弧尾的数目，称为该顶点的出度，记为OD(v)；一个顶点度等于顶点的入度+出度，即：TD(v)=ID(v)＋OD(v)。

（6）权图的边或弧有时具有与它有关的数据信息，这个数据信息就称为权（Weight）。

（7）网边（或弧）上带权的图称为网（Network）。

（8）路径、路径长度顶点v i到顶点v j之间的路径（Path）是指顶点序列v i,v i1,v i2, …, v im,v j.。

其中，（v i,v i1），(v i1,v i2)，…,(v im,.v j)分别为图中的边。

路径上边的数目称为路径长度。

（9）回路、简单路径在一条路径中，如果其起始点和终止点是同一顶点，则称其为回路或者环（Cycle）。

如果一条路径上所有顶点除起始点和终止点外彼此都是不同的，则称该路径为简单路径。

(10）子图对于图G=（V，E），G’=（V’，E’），若存在V’是V的子集，E’是E的子集，则称图G’是G的一个子图。

《数据结构》填空作业题(答案)

《数据结构》填空作业题(答案)

《数据结构》填空作业题答案第1章绪论（已校对无误）1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。

2．程序包括两个内容：数据结构和算法。

3. 数据结构的形式定义为：数据结构是一个二元组： Data Structure =（D，S）。

4. 数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。

5. 数据的逻辑结构可以分类为线性结构和非线性结构两大类。

6. 在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。

7. 在树形结构中，数据元素之间存在一对多的关系。

8. 数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。

9. 数据的逻辑结构包括线性结构、树形结构和图形结构 3种类型，树型结构和有向图结构合称为非线性结构。

10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。

11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑关系由附加的指针域来体现。

12. 数据的存储结构可用4种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。

13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。

14. 数据结构在物理上可分为顺序存储结构和链式存储结构。

15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数据的实现方法。

16. 数据元素可由若干个数据项组成。

17. 算法分析的两个主要方面是时间复杂度和空间复杂度。

18. 一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的存储空间的大小来度量的。

19. 算法具有如下特点：有穷性、确定性、可行性、输入、输出。

20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切的定义，并在有穷时间内计算出结果。

数据结构题库多选题

数据结构题库多选题

数据结构题库多选题1 . 以下说法正确的是（) A . 二叉树的特点是每个结点至多只有两棵子树。

B . 二叉树的子树无左右之分。

C . 二叉树只能进行链式存储。

D . 树的结点包含一个数据元素及若干指向其子树的分支。

答案：A，D解析：2 . 算法设计的要求包括____。

A . 正确性 B . 可读性 C . 健壮性 D . 确定性答案：A，B，C解析：“确定性”属于算法特性而非要求。

3 . 下列属于算法的重要特征的是： A . 有穷性 B . 确定性 C . 可行性 D . 输入和输出答案：A，B，C，D解析： ABCD4 . 图的四中存储结构 A . 邻接矩阵 B . 邻接表 C . 邻接多重表 D . 十字链表答案：A，B，C，D解析：5 . 依据所有数据成员之间的逻辑关系的不同，数据结构分为（）A . 非线性结构B . 逻辑结构C . 物理结构D . 线性结构答案：A，D解析：6 . 图的应用算法有（） A . 克鲁斯卡尔算法 B . 哈弗曼算法C . 迪杰斯特拉算法D . 拓扑排序算法答案：A，C，D解析：7 . 计算机算法必须具备________________等特性。

A . 可行性、确定性 B . 可行性、可移植性 C . 输入、输出 D . 有穷性 E . 易读性 F . 稳定性答案：A，C，D解析：8 . 下列数据结构中，属于线性数据结构的是____ A . 栈 B . 队列 C . 树 D . 图答案：A，B解析：9 . 下列说法正确的有： A . 算法和程序原则上没有区别，在讨论数据结构时二者通用 B . 从逻辑关系上讲，数据结构分为两大类：线性结构和非线性结构 C . 所谓数据的逻辑结构是指数据元素之间的逻辑关系 D . 同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数相等 E . 数据的逻辑结构与数据元素本身的内容和形式无关 F . 数据结构是指相互之间存在一种或多种关系的数据元素的全体答案：B，C，E解析：10 . 线性表的特点正确的（） A . 存在唯一的一个被称作”第一个“的数据元素。

常用数据结构有哪些

常⽤数据结构有哪些1、数据元素相互之间的关系称为结构。

有四类基本结构：集合、线性结构、树形结构、图状结构。

集合结构:除了同属于⼀种类型外，别⽆其它关系线性结构:元素之间存在⼀对⼀关系常见类型有: 数组,链表,队列,栈,它们之间在操作上有所区别。

例如:链表可在任意位置插⼊或删除元素,⽽队列在队尾插⼊元素,队头删除元素,栈只能在栈顶进⾏插⼊,删除操作。

树形结构:元素之间存在⼀对多的关系,常见类型有:树(有许多特例:⼆叉树、平衡⼆叉树、查找树等)图形结构:元素之间存在多对多的关系,图形结构中每个结点的前驱结点数和后续结点多个数可以任意常⽤数据结构：数组（静态数组、动态数组）、线性表、链表（单向链表、双向链表、循环链表）、队列、栈、树（⼆叉树、查找树、平衡树、线索、堆）、图等的定义、存储和操作。

2、数据结构是计算机存储、组织数据的⽅式。

数据结构是指相互之间存在⼀种或多种特定关系的数据元素的集合。

通常情况下，精⼼选择的数据结构可以带来更⾼的运⾏或者存储效率。

数据结构往往同⾼效的检索算法和索引技术有关。

在计算机科学中，数据结构是⼀门研究⾮数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间的关系和运算等的学科，⽽且确保经过这些运算后所得到的新结构仍然是原来的结构类型。

“数据结构”作为⼀门独⽴的课程在国外是从1968年才开始设⽴的。

1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第⼀卷《基本算法》是第⼀本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。

“数据结构”在计算机科学中是⼀门综合性的专业基础课。

数据结构是介于数学、计算机硬件和计算机软件三者之间的⼀门核⼼课程。

数据结构这⼀门课的内容不仅是⼀般程序设计（特别是⾮数值性程序设计）的基础，⽽且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。

常⽤的数据结构有：数组 (Array)在程序设计中，为了处理⽅便，把具有相同类型的若⼲变量按有序的形式组织起来。

数据结构 图

2）依次访问 vi 的所有未被访问的邻接点； 3）从这些邻接点出发，访问它们的所有未被访问的 邻接点; 依此类推，直到图中所有的顶点的邻接 点都被访问。 例 求图G 的以V0起点的的广度优先序列 V0,V1,V2,V3,V4,V5,V6,V7 V V
0 0
由于没有规定 访问邻接点的顺序， 广度优先序列不唯一。
则图的所有顶点的度数之和 = 2*e
V2
V3
（每条边对图的所有顶点的度数之和 “贡献” 2度）
3 路径、回路(环)
无向图G1=（V1，E1）中的顶点序列v1,v2,… ,vk,若 (vi,vi+1)E1 ( i=1,2,…k-1), v =v1, u =vk, 则称该序 列是从顶点v到顶点u的路径；若v=u，则称该序 列为回路；在G1中，v0,v1,v2,v3 是v0到v3的路径； v0,v1,v2,v3 , v0是回路； 有向图G2=（V2，E2）中的顶点序列v1,v2,… ,vk, <vi,vi+1>E2 (i=1,2,…k-1),若v =v1, u =vk,则称该 序列是从顶点v到顶点u的路径；若v=u，则称该序 V0 V1 V1 列为回路；在G2中， V0 V2 v0, v2, v3是v0到v3的路径 v0,v2,v3,v0是回路； V3 V4 V2 V3 无向图G1 有向图G2
V2
V3
非 强 连 通 图
5 子图
设有两个图G=（V，E）、G1= （V1，E1）， 若V1 V，E1 E，E1关联的顶点都在V1中， 则称 G1是G的子图；
例
V0 V2 V3 (a) V4 V3 (b) V1
下列 (b)、(c) 是 (a) 的子图
V0 V2 V4 V3 (c) V1

数据结构第七章1


} ADT Graph
详见p156~157。
7.2 图的存储结构
图的存储结构比较复杂，其复杂性主要表现在：
◆ 任意顶点之间可能存在联系，无法以数据元素 在存储区中的物理位置来表示元素之间的关系。
◆ 图中顶点的度不一样，有的可能相差很大，若 按度数最大的顶点设计结构，则会浪费很多存储单 元，反之按每个顶点自己的度设计不同的结构，又 会影响操作。 图的常用的存储结构有：邻接矩阵、邻接链表、十 字链表、邻接多重表。
图7-8 带权有向图的数组存储
⑶ 有向图邻接矩阵的特性
有向完全图：对于有向图，若图中顶点数为n ，
用e表示弧的数目，则e[0，n(n-1)] 。具有n(n-1)条边的 有向图称为有向完全图。
完全有向图另外的定义是：
对于有向图G=(V，E)，若vi，vjV ，当vi ≠vj时， 有<vi ,vj>E∧<vj , vi >E ，即图中任意两个不同的顶点 间都有一条弧，这样的有向图称为有向完全图。 有很少边或弧的图（e<n㏒n）的图称为稀疏图，反 之称为稠密图。
wij 若<vi,vj>E，即vi , vj邻接，权值为wij
∞ 若<vi,vj>E，即vi , vj不邻接时
a
2
6 3 1
b 3
4 5
e
c
d
vexs a b c d e
(b) 顶点矩阵
∞ ∞ ∞ ∞ ∞
6 2 ∞∞ 3 ∞ 4 ∞ ∞∞
∞ ∞ 1 ∞ ∞
∞ 3 ∞ 5 (v,v’)E，则称顶点v和v’ 互为邻接点，即v和w相 邻接。边(v,v’)依附(incident)与顶点v和v’ 。
对于有向图G=(V ，E)，若有向弧<v,w>E，则称 顶点v “邻接到”顶点w，顶点w “邻接自”顶点v ，弧 <v,w> 与顶点v和w “相关联” 。

图1


v1
v2
v3 o
o v4
v3
v4
子图
有 两 个 图 G 和 H ， 若 V(H)V(G) ， E(H)
E(G)，则称H是G的子图，G是H的母图。
如果H是G的子图，并且V(H)＝V(G)，则称
H是G的支撑子图。
V1
V1 V1 V3 V2 V3 V5 V1 V3 V4 V5 V2
V2
V4
V2
V5
mark ivex ilink jvex jlink
顶点结点： data; 存与顶点有关的信息 firstedge; 指向第一条依附于该顶点的边
data firstedge
例
a c d
b
e
1 2 3 4 5
a b
c d e
1 3 5
2 2 2 ^
1 ^ 3
3 ^
4 ^ 4
5 ^
第七章 图
图（Graph）是一种较线性表和树更为复杂的 非线性结构。在图结构中，对结点（图中常称 为顶点）的前趋和后继个数都是不加限制的，
即结点之间的关系是任意的。图中任意两个结
点之间都可能相关。图状结构可以描述各种复
杂的数据对象。
图的应用极为广泛，特别是近年来的迅速发展，
已渗透到诸如语言学、逻辑学、物理、化学、
V1 V3 V4
V2
V5
Graph2
0 1 0 1 0
1 0 1 0 1
0 1 0 1 1
1 0 1 0 0
0 1 1 0 0
邻接表
定义:邻接表是图的一种链式存储结构。对图的每个 顶点建立一个单链表（n个顶点建立n个单链表），第i 个单链表中的结点包含顶点Vi的所有邻接顶点。由顺 序存储的顶点表和链接存储的边链表构成的图的存储 结构被称为邻接表。 权图中边结点结构为（VerAdj, cost, link）. 非权图中边结点结构为（VerAdj, link）
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

在邻接表(或逆邻接表)表示中，每个边表对应于 邻接矩阵的一行(或一列)，边表中结点个数等 于一行(或一列)中非零元素的个数。对于一个 具有n个顶点e条边的图G，若G是无向图，则 它的邻接表表示中有n个顶点表结点和2e个边 表结点；若G是有向图，则它的邻接表表示或 逆邻接表表示中均有n个顶点表结点和e个边表 结点。因此邻接表或逆邻接表表示的空间复杂 度为S(n，e)＝O(n+e)。若图中边的数目远远小 于n2(即e＜＜n2)，此类图称作稀疏图(Sparse Graph)，这时用邻接表表示比用邻接矩阵表示 节省存储空间；若e接近于n2 (准确地说，无向 图e接近于n(n-1)／2，有向图e接近于n(n-1))， 此类图称作稠密图(Dense Graph)，考虑到邻接 表中要附加链域，则应取邻接矩阵表示法为宜。
1：若（vi , v j）或 vi , v j 是E（G）中的边 Ai, j 0：若（vi , v j）或 vi , v j 不是E（G）中的边
• 用邻接矩阵表示法表示图，除了存储用于表示顶点间 相邻关系的邻接矩阵外，通常还需要用一个顺序表来 存储顶点信息。其形式说明如下： • # define n 6 / * 图的顶点数 * / • # define e 8 / * 图的边（弧）数 */ • typedef char vextype； / * 顶点的数据类型 * / • typedef float adjtype； / * 权值类型 * / • typedef struct • {vextype vexs[n]； • adjtype arcs[n][n]； • }graph；
若(vi，vj)是一条无向边，则称顶点vi和vj互为邻接点 (Adjacent)，或称vi和vj相邻接；称(vi，vj)关联(Incident) 于顶点vi和vj，或称(vi，vj)与顶点vi和vj相关联。如图71中G2，与顶点vl相邻接的顶点是v2，v3和v4，而关联于 顶点v2的边是(vl，v2)，(v2，v3)和(v2，v4)。若＜vi，vj ＞是一条有向边，则称顶点vi邻接到vj,顶点vj邻接于顶 点vi,并称边＜vi，vj＞关联于vi和vj或称＜vi，vj＞与顶 点vi和vj相关联。如图7-1中Gl，关联于顶点v2的边是＜ v1，v2＞，＜v2，vl＞和＜v2,v3＞。 无向图中顶点v的度(Degree)是关联于该顶点的边的数 目，记为D(v)。若G为有向图，则把以顶点v为终点的 边的数目，称为v的人度(1ndegree)，记为ID(v)；把以 顶点v为始点的边的数目，称为v的出度(outdegree)，记 为OD(v)；顶点v的度则定义为该顶点的入度和出度之 和，即D(v)＝ID(v)十OD(v)。
在无向图G中，若存在一个顶点序列vp,vi1,vi2…，vin，vq， 使得(vp，vil)，(vi1,vi2)，…，(vin，vq)均属于E(G)，则 称顶点vp到vq存在一条路径(Path)。若G是有向图，则 路径也是有向的，它由E(G)中的有向边＜vp，vil＞，＜ vil，vi2＞，…，＜vin，vq＞组成。路径长度定义为该路 径上边的数目。若一条路径上除了vp和vq可以相同外； 其余顶点均不相同，则称此路径为一条简单路径。起 点和终点相同(vp＝vq)的简单路径称为简单回路或简单 环(Cycle)。例如，在图G2中顶点序列vl,v2，v3，v4是一 条从顶点vl到顶点v4的长度为3的简单路径；顶点序列 vl,v2，v4，vl，v3是一条从顶点vl到顶点v3的长度为4的 路径，但不是简单路径；顶点序列vl，v2，v4，vl是一 个长度为3的简单环。在有向图Gl中，顶点序列vl，v2， vl是一个长度为2的有向简单环。
邻接表
这种表示法类似于树的孩子链表表示法。 对于图G中的每个顶点vi，该方法把所有邻接于vi的顶 点vj链成一个单链表，这个单链表就称为顶点vi的邻接 表(Adjacency List)。邻接表中每个表结点均有两个域， 其一是邻接点域(Adjvex)，用以存放与vi相邻接的顶点 vj的序号；其二是链域(Next)，用来将邻接表的所有表 结点链在一起。并且为每个顶点vi的邻接表设置一个具 有两个域的表头结点：一个是顶点域(vertex)，用来存 放顶点vi的信息；另一个是指针域(Link)，用于存入指 向vi的邻接表中第一个表结点的头指针。为了便于随机 访问任一顶点的邻接表，将所有邻接表的表头结点顺 序存储在一个向量中，这样，图G就可以由这个表头向 量来表示。
深度优先搜索(Depth-First-Search)遍历类似于树的前序遍历。假设给 定图G的初态是所有顶点均未访问过，在G中任选一顶点vi为初始 出发点，则深度优先搜索可定义如下：首先，访问出发点vi，并 将其标记为已访问过，然后，依次从vi出发搜索vi的每一个邻接点 vj,若vj未曾访问过，则以vj为新的出发点继续进行深度优先搜索。 显然上述搜索法是递归定义的，它的特点是尽可能先对纵深方向 进行搜索，故称之为深度优先搜索。例如，设x是刚访问过的顶点， 按深度优先搜索方法，下一步将选择一条从x出发的未检测过的边 (x，y)。若发现顶点y已被访问过，则重新选择另一条从x出发的 未检测过的边。若发现顶点y未曾访问过，则沿此边从x到达y，访 问y并将其标记为已访问过，然后从y开始搜索，直到搜索完从y出 发的所有路径，才回溯到顶点x，然后再选择一条从x出发的未检 测过的边。上述过程直至从x出发的所有边都已检测过为止。此时， 若x不是初始出发点，则回溯到在x之前被访问过的顶点；若x是初 始出发点，则整个搜索过程结束。显然这时图G中所有和初始出 发点有路径相通的顶点都已被访问过。因此，若G是连通图，则 从初始出发点开始的搜索过程结束，也就意味着完成了对图G的 遍历。
•
• • • • • • • • • • • • • • • • •
若图中顶点信息是0至n-1的编号，则仅需令权值为1，存储一个邻接矩阵就可以表 示图。若是网络，则adjtype为权的类型。由于无向图或无向网络的邻接矩阵是对 称的，故可采用压缩存储的方法，仅存储下三角阵(不包括对角线上的元素)中的 元素即可。显然，邻接矩阵表示法的空间复杂度S(n)＝O(n2)。 CREATGRAPH(ga) ／* 建立无向网络 * ／ Graph * ga； { int i，j，k； float w； for(i＝0；i＜n；i++) ga ->vexs[i]＝getchar()；／* 读入顶点信息，建立顶点表 *／ for(i＝0；i＜n；i++) for(j＝0；j＜n；j++) ga ->arcs[i][j]＝0； ／* 邻接矩阵初始化*／ for(k＝0；k＜e；k++) ／* 读入e条边 *／ (scanf(”％d％d％f”，&I,&j，&w)；／*读入边(vi，vj)上的权w *／ ga ->arcs[i][j]＝w； ga - >arcs[j][i]＝w； } }／*CREATGRAPH *／ 该算法的执行时间是O(n+n2+e)，其中O(n2)的时问耗费在邻接矩阵的初始化操作上。 因为e＜n2，所以，算法的时间复杂度是O(n2)。
图的遍历
和树的遍历类似，图的遍历也是从某个顶点出发， 沿着某条搜索路径对图中所有顶点各作一次访 问。若给定的图是连通图，则从图中任一顶点 出发顺着边可以访问到该图的所有顶点。然而， 图的遍历比树的遍历复杂得多，这是因为图中 的任一顶点都可能和其余顶点相邻接，故在访 问了某个顶点之后，可能顺着某条回路又回到 了该顶点。为了避免重复访问同一个顶点，必 须记住每个顶点是否被访问过。为此，可设置 一个布尔向量visited[n]，它的初值为false，一 旦访问了顶点vi，便将visited[i-1]置为TRUE。
图
图（Graph）是一种较线性表和树更为复杂的非线性结 构。在线性结构中，结点之间的关系是线性关系，除开 始结点和终端结点外，每个结点只有一个直接前趋和直 接后继。在树形结构中，结点之间的关系实质上是层次 关系，同层上的每个结点可以和下一层的零个或多个结 点（即孩子）相关，但只能和上一层的一个结点（即双 亲）相关（根结点除外）。然而在图结构中，对结点 （图中常称为顶点）的前趋和后继个数都是不加限制的， 即结点之间的关系是任意的。图中任意两个结点之间都 可能相关。由此，图的应用极为广泛，特别是近年来的 迅速发展，已渗透到诸如语言学、逻辑学、物理、化学、 电讯工程、计算机科学以及数学的其它分支中。
若将图的每条边都赋上一个权，则称这种带权图为网 络(Network)。通常权是具有某种意义的数.
它们可以表示两个顶点 之间的距离，耗费等
图的存储结构
• 邻接矩阵(Adjacency Matrix)是表示顶点之 间相邻关系的矩阵。 设G＝(V，E)是具有n 个顶点的图，则G的 邻接语
• 若图G中的每条边都是有方向的，则称G为有向图 （Digraph）。在有向图中，一条有向边是由两个顶点 组成的有序对，有序对通常用尖括号表示。例如，＜vi， vj＞表示一条有向边，vi是边的始点（起点），vj是边 的终点。因此，＜vi，vj＞和＜vj，vi＞是两条不同的有 向边。有向边也称为弧（Arc），边的始点称为弧尾 （Tail），终点称为弧头（Head）。 • 图G由两个集合V和E组成，记为G＝(V，E)，其中v是 顶点的有穷非空集合，E是V中顶点偶对（称为边）的 有穷集。通常，也将图G的顶点集和边集分别记为V(G) 和E(G)。E(G)可以是空集，若E(G)为空，则图G只有顶 点而没有边，称为空图。
在无向图中求顶点的度，邻接矩阵及邻接表两种存储结构都很容易 做到：邻接矩阵中第i行(或第i列)上非零元素的个数即为顶点vi的 度；在邻接表表示中，顶点vi的度则是第i个边表中的结点个数。 在有向图中求顶点的度。采用邻接矩阵表示比邻接表表示更方便： 邻接矩阵中的第i行上非零元素的个数是顶点vi的出度OD(vi)，第i 列上非零元素的个数是顶点vi 的入度ID(vi)，顶点vi 的度即是二者 之和；在邻接表表示中，第i个边表(即出边表)上的结点个数是顶 点vi的出度，求vi的入度较困难，需遍历各顶点的边表。若有向图 采用逆邻接表表示，则与邻接表表示相反，求顶点的入度容易， 而求顶点出度较难。 在邻接矩阵表示中，很容易判定(vi，vj)或＜vi，vj＞是否是图的一 条边，只要判定矩阵中的第i行第j列上的那个元素是否为零即可； 但是在邻接表表示中，需扫描第i个边表，最坏情况下要耗费O(n) 时间。 在邻接矩阵中求边的数目e，必须检测整个矩阵，所耗费的时间是 0(n2)，与e的大小无关；而在邻接表表示中，只要对每个边表的结 点个数计数即可求得e，所耗费的时间是0(e+n)。因此，当e＜＜n2 时，采用邻接表表示更节省时间。