2024年软考软件设计师专题九数据结构知识.doc

专题九：数据结构知识
数据结构是计算机软件的一门基础课程,计算机科学各个领域及有关的应用软件都要用到各种数据结构．语言编译要使用栈、散列表及语法树；操作系统中用队列、存储管理表及目录树等；数据库系统利用线性表、多链表及索引树等进行数据管理；而在人工智能领域，依求解问题性质的差异将包括到各种不一样的数据结构，如广义表、集合、搜索树及各种有向图等等。学习数据结构目标是要熟悉某些最常用的数据结构，明确数据结构内在的逻辑关系，懂得它们在计算机中的存储表示，并结合各种经典应用阐明它们在进行各种操作时的动态性质及实际的执行算法，深入提升软件计和编程水平。通过对不一样存储结构和对应算法的对比，增强我们依照求解问题的性质选择合理的数据结构，并将问题求解算法的空间、时间及复杂性控制在一定范围的能力。
软件设计师考试大纲对数据结构部分的要求是纯熟掌握常用数据结构和常用算法，因此，本专题从数据结构的概述出发，对基本的概念引出常用的数据结构类型的简介和讲解，同时在讲解各种数据结构中间采取算法与数据结构相结合的方式，在算法步骤中使用数据结构，对数据结构的重点、难点进行了分析，最后讲解了与数据结构紧密有关的排序和查找算法，以及某些以往考试题的分析。
1. 数据结构概述
数据结构研究了计算机需要处理的数据对象和对象之间的关系；刻画了应用中包括到的数据的逻辑组织；也描述了数据在计算机中怎样存储、传送、转换。
学习数据结构注意的问题：
n          系统掌握基本数据结构的特点及其不一样实现。
n          了解并掌握各种数据结构上重要操作的实现及其性能（时间、空间）的分析。
n          掌握各种数据结构的使用特性，在算法设计中能够进行选择。
n          掌握常用的递归、回溯、迭代、递推等措施的设计
n          掌握自顶向下、逐渐求精的程序设计措施。
n          掌握自顶向下、逐渐求精的程序设计措施。
在学习数据结构的知识之前，我们要了解一下数据结构中的基本概念。
数据：对客观事物的符号表示，在计算机中就是指所有能输入到计算机中并被计算机程序所处理的符号的总称。
数据项：  是数据的不可分割的最小单位；
数据元素：是数据的基本单位，在计算机程序中一般作为一个整体进行处理；一个数据元素可由若干个数据项组成。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。
数据结构上的基本操作：
◆插入操作 ◆删除操作 ◆更新操作 ◆查找操作 ◆排序操作
数据结构是指数据对象及相互关系和结构措施，一个数据结构B形式上能够用一个二元组表示为B=（A，R）。其中，A是数据结构中的数据（称为结点）的非空有限集合，R是定义在A上的关系的非空有限集合。
依照数据元素之间的关系的不一样特性，一般有下列4类基本结构。
Ø         集合——结构中的数据元素除了“同属于一个集合”的关系外，别无其他关系。
Ø         线性结构——结构中的数据元素之间存在一个对一个的关系。
Ø         树形结构——结构中的元素之间存在一个对多个的关系。
Ø         图状结构或网状结构——结构中的元素之间存在多个对多个的关系。
数据结构中，结点与结点间的相互关系是数据的逻辑结构。数据结构在计算机中的表示（又称为映象）称为数据的物理结构，也称存储结构。
数据元素之间的关系在计算机中有两种不一样的表示方式：次序映象和非次序映象，并由此得到两种不一样的存储结构：次序存储结构和链式存储结构。
任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采取的存储结构。
数据的逻辑结构分为两类：
    线性结构：线性表、栈、队列和串
    非线性结构：树、图
数据的存储措施有四类：
      次序存储措施
      链接存储措施
      索引存储措施
      散列存储措施
2. 常用数据结构
2.1线性表
   在数据结构中，线性结构常称为线性表，是最简单、最常用的一个数据结构，它是由n个相同数据类型的结点组成的有限序列。
其特点是：在数据元素的非空有限集合中，
u       ◆存在唯一的一个被称做“第一个”的数据元素
u       ◆存在唯一的一个被称做“最后一个”的元素数据元素
u       ◆除第一个之外，集合中的每个数据元素均只有一个前驱
u       ◆除最后一个之外，集合中每个数据元素均只有一个后继
    一个由n个结点e0，e1…，en-1组成的线性表记为：（e0，e1…，en-1）。线性表的结点个数称为线性表的长度，长度为0的线性表称为空的线性表，简称空表。对于非空线性表，e0是线性表的第一个结点，en-1是线性表的最后一个结点。线性表的结点组成了一个序列，对序列中两个相邻结点ei和ei-1，称前者是后者的前驱结点，后者是前者的后继结点。
线性表最重要的性质是线性表中结点和相对位置是确定的。
     线性表的结点也称为表元，或称为统计，要求线性表的结点一定是同一类型的数据。线性表的结点可由若干个成份组成，其中唯一标识表元的成份成为核心字，简称键。
     线性表是一个相称灵活的数据结构，它的长度能够依照需要增加或缩短。对线性表的基本运算如下：
u       INITIATE（L）初始化操作
u       LENGTH（L）  求长度函数
u       GET（L，i）  取元素函数
u       PRIOR（L，elm）求前驱函数
u       NEXT（L，elm） 求后继函数
u       LOCATE（L，x） 定位函数
u       INSERT（L，i，b）插入操作
u       DELETE（L，i）   删除操作
有多个存储方式能将线性表存储在计算机内，其中最常用的是次序存储和链接存储。依照存储方式的不一样，其上述的运算实现也不一样样。
u◆ 次序存储：是最简单的存储方式，其特点是逻辑关系上相邻的两个元素在物理位置上也相邻。一般使用一个足够大的数组，从数组的第一个元素开始，将线性表的结点依次存储在数组中。
次序存储方式优点：能直接访问线性表中的任意结点。
线性表的第i个元素a[i]的存储位置能够使用如下公式求得： LOC（ai）=LOC（a1）+（i-1）*l
式中LOC（a1）是线性表的第一个数据元素a1的存储位置，一般称做线性表的起始位置或基地址。
次序存储的缺陷：
1)        线性表的大小固定，浪费大量的存储空间，不利于节点的增加和减少；
2)        执行线性表的插入和删除操作要移动其他元素，不够以便；
◆链式存储
线性表链接存储是用链表来存储线性表。
单链表（线性链表）：
从链表的第一个表元开始，将线性表的结点依次存储在链表的各表元中。链表的每个表元除要存储线性表结点的信息以外，还要有一个成份来存储其后继结点的指针。
线性链表的特点是：每个链表都有一个头指针，整个链表的存取必须从头指针开始，头指针指向第一个数据元素的位置，最后的节点指针为空。当链表为空时，头指针为空值；链表非空时，头指针指向第一个节点。
链式存储的缺陷：
1)       因为要存储地址指针，因此浪费空间；
2)       直接访问节点不以便；
3) 
4) 
5) 
6) 
7) 
循环链表：
循环链表是另一个形式的链式存储结构，是单链表的变形。它的特点就是表中最后一个结点的指针域指向头结点，整个链表形成一个环。因此，从表中任意一个结点出发都能够找到表中的其他结点。
循环链表和单向链表基本一致，差异仅在于算法中循环的条件不是结点的指针是否为空，而是他们的指针是否等于头指针，
循环链表最后一个结点的 link 指针不为 0 (NULL)，而是指向了表的前端。
为简化操作，在循环链表中往往加入表头结点。
循环链表的特点是：只要懂得表中某一结点的地址，就可搜寻到所有其他结点的地址。
循环链表的示例：

带表头结点的循环链表 ：

双向链表：
双向链表是另一个形式的链式结构，双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋。双向链表克服了单链表的单向性的缺陷。
前驱方向              后继方向

双向链表也能够有循环表，链表中存在两个环。一个结点的前趋的后继和该结点的后继的前趋都是指向该结点的。

p == p→lLink→rLink == p→rLink→lLink
2.2 栈
栈（Stack）是限定仅在表尾进行插入或删除操作的线性表。表尾端称栈顶（top），表头端称栈底（bottom）。
若有栈 S=（s0，s1，…，sn-1）则s0为栈底结点，sn-1为栈顶结点。一般称栈的结点插入为进栈，栈的结点删除为出栈。因为最后进栈的结点必然最先出栈，因此栈具备后进先出的特点。能够用一下一个图形来形象的表示：

栈有两种存储结构：次序栈和链栈
次序栈即栈的次序存储结构是，利用一组地址连续的存储单元依次存储自栈底到栈顶的数据元素，同时设指针top指示栈顶元素的目前位置。
栈也能够用链表实现，链式存储结构的栈简称链栈。若同时需两个以上的栈，则最佳采取这种结构。对于栈上的操作，总结如下，大家能够仔细看一下这些程序，一个大的程序都是由某些对数据结构的小的操作组成的。
次序存储的栈的基本操作如下：
判断栈满：
int stackfull(seqstack *s)
{ 
   return (s->top= =stacksize-1);
}
进栈：
void  push(seqstack *s,datatype  x)
{
   if (stackfull(s))
error(“stack verflow”);
   s->data[++s->top]=x;
}

判断栈空：
int stackempty(seqstack *s)
{
  return (s->top= = -1)
}
出栈：
datatype pop(seqstack *s)
{
if (stackempty(s))
 error(“stack underflow”);
x=s->data[top];
s->top--;
return (x);
}

链接存储栈：用链表实现的栈，链表第一个元素是栈顶元素，链表的末尾是栈底节点，链表的头指针就是栈顶指针，栈顶指针为空则是空栈。若同时需要两个以上的栈，最佳采取链表作存储结构

链接存储的栈的操作如下：
进栈：
Void push(linkstack *p,datatype x)
    {
    stacknode *q q=(stacknode*)malloc(sizeof(stacknode));
     q–>data=x;
     q–>next=p–>top;
     p–>top=q;
}
出栈：
Datatype  pop(linkstack  *p)
{
   datatype  x;
   stacknode  *q=p–>top;
    if(stackempty(p)
     error(“stack underflow.”);
     x=q–>data;
     p–>top=q–>next;
     free(q);
     return x;
 }
多栈处理 栈浮动技术：
n 个栈共享一个数组空间V[m]
n设置栈顶指针数组 t [n+1] 和 栈底指针数组 b [n+1]
，t[i]和b[i]分别指示第 i 个栈的栈顶与栈底，b[n]作为控制量，指到数组最高低标
各栈初始分派空间 s = m/n指针初始值  t[0] = b[0] = -1   b[n] = m-1 
t[i] = b[i] = b[i-1] + s,   i = 1, 2, …, n-1

2.3队列
队列是只允许在一端进行插入，另一端进行删除运算的线性表。允许删除的那一端称为队首（front），允许插入运算的另一端称为队尾（rear）。一般称队列的结点插入为进队，队列的结点删除为出队。若有队列
Q=（q0，q1，…，qn-1）则q0为队首结点，qn-1为队尾结点。因最先进入队列的结点将最先出队，因此队列具备先进先出的特性。

能够用次序存储线性表来表示队列，也能够用链表实现，用链表实现的队列称为链队列。
队列操作：
①int push(PNODE *top，int e)是进栈函数，形参top是栈顶指针的指针，形参e是入栈元素。
②int pop(PNODE *top，int oe)是出栈函数，形参top是栈顶指针的指针，形参e作为返回出栈元素使用。
③int enQueue(PNODE *tail，int e)是入队函数，形参tail是队尾指针的指针，形参e是入队元素。
④int deQueue(PNODE *tail，int *e)是出队函数，形参tail是队尾指针的指针，形参e作为返回出队元素使用。

定义结点的结构如下：
typedef struct node{
int value;
struct node *next;
}NODE，*PNODE;
[函数①]
int push(PNODE *top，int e)
{
PNODE p = (PNODE)malloc(sizeof(NODE));
if(!p)  return –1;
p->value = e;
p->next = *top; //指向栈顶指针
*top = p;
return 0;
}
[函数②]
int pop(PNODE *top，int *e)
{
PNODE p = *top;
if(p == NULL) return –1;
*e = p->value;
*top = p->next;  //栈顶指向取出的数的指针
free(p);
return 0;
}
[函数③]
int enQueue(PNODE *tail，int e)
{   PNODE p，t；
t = *tail;
p = (PNODE)malloc(sizeof(NODE))；
if(!p) return –l;
p—>value = e;
p—>next = t—>next;
t->next = p;    //将元素加在尾指针后
*tail = p;
return 0;
}
[函数④]
int deQueue(PNODE *tail，int e)
{  
PNODE p，q；
if((*tail)->next == *tail) return –1;//队列已经空
p = (*tail)->next;   //p取得尾指针
q = p->next;        
e = q->value;
p->next = q->next;  
if(*tail = q)
*tail = p ;  //尾指针指向最后节点
free(q);
return 0;
)
循环队列 (Circular Queue):
存储队列的数组被当作首尾相接的表处理。
队头、队尾指针加1时从maxSize -1直接进到0，可用语言的取模(余数)运算实现。
队头指针进1:  front = (front + 1) % maxSize;

队尾指针进1:  rear = (rear + 1) % maxSize;
队列初始化：front = rear = 0;
队空条件：front == rear;
队满条件：(rear + 1) % maxSize == front
循环队列的进队和出队:

 优先级队列：是不一样于先进先出队列的另一个队列。每次从队列中取出的是具备最高优先权的元素
2.4 串
字符串是非数值处理应用中重要的处理对象。字符串是由某字符集上的字符所组成的任何有限字符序列。
当一个字符串不包括任何字符时，称它为空字符串。一个字符串所包括的有效字符个数称为这个字符串的长度。一个字符串中任一连续的子序列称为该字符串的子串。包括子串的字符串对应称为主串。一般称该字符在序列中的序号为该字符在串中的位置。
字符串的串值必须用单引号括, ‘c1c2c3…cn起来，但单引号自身不属于串，它的作用是为了防止于变量名和数的常量混同。在C语言中，字符串常量是用一对双引号括住若干字符来表示，如“I am a student”
字符串一般存于字符数组中，每个字符串最后一个有效字符后跟一个字符串结束符“\0”.系统提供的库函数形成的字符串会自动加结束符号，而用户的应用程序中形成的字符串必须由程序自行负责添加字符串结束符号。
两个串相等当且仅当两个串的值相等，长度相等并且各个对应位置的字符都相等。
常用的字符串的基本操作有7种。
u       ASSING（s，t）和CREAT（s，ss）赋值操作
u       EQUAL（s，t）判等函数
u       LENGTH（s）求长度函数
u       CONCAT（s，t）联接函数
u       SUBSTR（s，start，len）求子串函数
u       INDEX（s，t）定位函数
u       REPLACE（s，t，v）置换函数
u       INSERT（s，pos，t）插入函数
u       DELETE（s，pos，t）删除函数
(1)求字符串长,int strlen(char s)
（2）串复制(copy)
      char *strcpy(char to,char from);
     该函数将串from复制到串to中，并且返回一个指向串to的开始处的指针。
(3)联接(concatenation)
    char  strcat(char to,char from)
   该函数将串from复制到串to的末尾，并且返回一个指向串to的开始处的指针。
(4)串比较（compare)
    int strcmp(chars1,char s2);
   该函数比较串s1和串s2的大小，当返回值小于0，等于0或不小于0时分别表示s1<s2或s1=s2或s1>s2
   例如：result=strcmp(“baker”,”Baker”)    result>0
               result=strcmp(“12”,”12”);       result=0
              result=strcmp(“Joe”,”Joseph”);    result<0
（5）字符定位(index)
     char strchr(char s,char c);
  该函数是找c在字符串中第一次出现的位置，若找到则返回该位置，否则返回NULL。
字符串的静态存储：次序存储，用一组地址连续的地址单元存储串的字符序列，尤其是在PASCAL程序语言中还能够采取紧缩数组来实现。
字符串的动态存储：采取链表的方式存储字符串，节点的大小能够不一样，即每个节点能够存储的字符数是不一样的。对于节点大小不小于1的链表，需要设置头指针和尾指针来定位和串连接。
存储密度：串值所站的存储位/实际分派的存储位
实际应用的串处理系统中采取的是动态存储结构，每个串的值各自存储在一组地址连续的存储单元中，存储地址在程序执行过程中动态分派。利用串名和串值之间的的对应关系来建立存储映象来访问串。
2.5 数组
数组是最常用的数据结构之一，在程序中，数组常用来实现次序存储的线性表。数组由固定个数的元素组成，所有元素的类型相同，元素依次次序存储。每个元素对应一个下标，数组元素按数组名和元素的下标引用，引用数组元素的下标个数称为数组的维数。
在C语言中，n个元素的数组中，第一个元素的下标为0，最后一个的下标为n-1;
数组能够分为一维、二维……N维数组，取决于引用数组元素的下标的个数；
一维数组：

二维数组和三维数组：

数组能够分为静态数组和动态数组两类，所谓静态就是指数组的空间存储分派是在使用之前还是在程序运行当中分派，静态数组就是在定义时必须进行空间分派，也就是固定数组的大小，这么就不利于数组的扩展。同样动态数组就是在程序运行过程中进行数组的赋值或者是空间的分派，动态数组一般采取链表的存储结构，而静态数组一般采取次序存储结构。
数组元素能够是任何类型的，当元素自身又是数组时，就组成多维数组。多维数组是一维数组的推广，多维数组中最常用的是二维数组。多维数组的所有元素并未排在一个线性序列里，要次序存储多维数组按需要按一定次序把所有的数组元素排在一个线性序列里，常用的排列次序有行优先次序和列优先次序。对于多维数组，C语言按行优先次序存储。
对于数组，一般只有两种操作：
u        给定一个下标，存取对应的数据元素
u        给定一组下标，修改对应数据元素的某一个或几个数据项的值。
一般用多维数组表示矩阵，详细有如下几个类型：
对称矩阵：A[i,j]= =A[j,i]
三角矩阵：以主对角线划分，三角矩阵有上三角和下三角两种。
上三角矩阵中，它的下三角（不包括主对角线）中的元素均为常数。下三角矩阵恰好相反，它的主对角线上方均为常数，在大多数情况下，三角矩阵常数为零。
三角矩阵可压缩存储到向量sa[0..n(n+1)/2]中，sa[k]和aij的对应关系是：
     k =  
3、对角矩阵
    对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其他元素皆为零。
当∣i-j∣>1时，元素a[i,j]=0。
LOC(i,j)=LOC(0,0)+[3*i-1+(j-i+1)] =LOC(0,0)+(2i+j)
4. 稀疏矩阵
简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即s≦m×n），并且分布没有一定规律。用次序存储结构的三元组对稀疏矩阵进行存储，分别统计行、列和值

十字链表：
因为非零元的位置和个数变化，因此用链表存储更恰当；在这种情况下采取十字链表来表示，每个非零元用一个节点表示，节点中有行、列尚有向下的域和线右的域；
另外还需要一个指向列链表的表头节点和指向行链表的表头节点。还能够设置一个指向整个十字链表的表头节点。还能够把列表头和行表头节点组成数组，便于操作；
各种广义表示意图

 2.6 树
2.6.1概述
树型结构是一类重要的非线性数据结构。其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构。
树是由一个或多个结点组成的有限集T，它满足如下两个条件：
I.  有一个特定的结点，成为根结点
II. 其他的结点提成m（m>=0）个互不相交的有限集T0，T1，…，Tm-1。其中每个集合又都是一棵树，称T0，T1，…，Tm-1为根结点的子树。
这里能够看出树的定义是递归的，即一棵树由子树组成，子树又由更小的子树组成。一个结点的子树数目，称为结点的度。树中各结点的度的最大值则称为树的度。树中结点的最大层次称为树的深度。
假如将树中结点的各子树当作从左到右是有次序的（即不能互换），则称该树为有序树，否则为无序树。森林是m（m>=0）棵互不相交的树的集合。
存储结构
树是非线性的结构，不能简单地用结点的线性表来表示。树有多个形式地存储结构，最常用的是标准存储形式和带逆存储形式。在树的标准存储结构中，树中的结点可提成两部分：结点的数据和指向子结点的指针。当程序需从结点返回到其父结点时，需要在树的结点中存储其父结点的位置信息，这种存储形式就是带逆存储结构。
详细使用的链表结构有：
u  ◆双亲表示法：利用每个节点只有一个双亲的特点；求节点的孩子时要遍历整个向量
u  ◆孩子表示法：把每个节点的孩子都排列起来，一单链表存储，则n个节点有n个孩子链表，而n个头指针又组成了一个线性表。
u  ◆孩子弟兄表示法（又称二叉树表示法，或二叉链表表示法）：节点两个指针分别指向该节点的第一个孩子和下一个弟兄节点。
树的遍历
     在应用树结构时，常要求按某种次序取得树中所有结点的信息，这可通过树的遍历操作来实现。常用的树的遍历措施有：
u    树的前序遍历：首先访问根结点，然后从左到右遍历根结点的各棵子树。
u    树的后序遍历：首先从左到右按后序遍历根结点的各棵子树，然后访问根结点。
u    树的层次遍历：首先访问处在0层上的根结点，然后从左到右依次访问处在1层、2层……上的结点，即自上而下从左到右逐层访问树各层上的结点。
2.6.2二叉树
n 概述
与一般的树的结构比较，二叉树在结构上更规范和更有确定性，应用也比树更为广泛。
二叉树的特点是每个结点至多只有二棵子树（即二叉树中不存在度不小于2的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。二叉树与树不一样的地方在于，首先二叉树能够为空，空的二叉树没有结点；另外，在二叉树中，结点的子树是有序的，分左右两棵子二叉树。
二叉树采取类似树的标准存储形式来存储。
二叉树的性质:
    二叉树具备下列重要特性。
u◆在二叉树的第i层至多有个结点（i>=1）。
u◆深度为k的二叉树至多有-1个结点（k>=1）。
◆对任何一棵二叉树T，假如其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
u◆具备n个结点的完全二叉树的深度为。
二叉树的遍历
树的所有遍历措施都适合用于二叉树，常用的二叉树遍历措施有3种。
#include<stdio.h>
#include<stdlib.h>
#define NULL 0
Typedef struct node{
       char data;
       struct node *lchild,*rchild;
    }TREENODE;
TREENODE *root;
前序遍历:
u        访问根结点，
u        按前序遍历根结点的左子树，
u        按前序遍历根结点的右子树。
中序遍历:
u        按中序遍历根结点的左子树，
u        访问根结点，
u        按中序遍历根结点的右子树。
中序遍历算法:                                                                              
Void inorder(TREENODE *p)
   {
if(p!=NULL)
{ inorder(p–>lchild);
printf(“%c”,p–>data)
  inorder(p–>rchild);
}
}
后序遍历:
u        按后序遍历根结点的左子树，
u        按后序遍历根结点的右子树，
u        访问根结点。
以上3种遍历措施都是递归定义的。
哈夫曼及其应用：又称为最优树，是一类带权途径长度最短的树
途径长度：从树中一个节点到另一个节点之间的分支组成的这两个节点之间的途径，途径上的分支树木就称为途径长度；
树的途径长度：从树根到每一节点的途径长度之和；
树的带权途径长度：树中所有叶子节点的带权途径长度之和；
哈夫曼树就是一棵n个叶子节点的二叉树，所有叶子节点的带权之和最小。
算法描述：
给定n个节点的集合，每个节点都带权值；
选两个权值最小的节点结构一棵新的二叉树，新二叉树的根节点的权值就是两个子节点权值之和；
从n个节点中删除刚才使用的两个节点，同时将新产生的二叉树根节点放在节点集合中。
重复2，3步，懂得只有一棵树为止。

例题：已知节点的前序序列和中序序列分别为：
前序序列：A B C D E F G
中序序列：C B E D A F G
求出整个二叉树，以及结构过程 
2.7图
基本概念:
图是一个较线性表和树更为复杂的数据结构。在图形结构中，结点之间的关系能够是任意的，图中任意两个数据元素之间都也许有关。
一个图G由非空有限的顶点集合V和有限的边的集合E组成，记为G=（V，E）。图一般分为两种类型。
u无向图
无向图的边是顶点的无序偶，用（i，j）来表示顶点i和j之间的边。
u有向图
有向图的边是顶点的有序偶，有向图的边也成为弧，用<i，j>来表示顶点i和j之间的弧。
其中，有条边的无向图称为完全图，而具备n(n-1)条弧的有向图成为有向完全图。
有时图的边或弧具备与它有关的树，这种与图的边或弧有关的数称作权。带权图也简称为网。
假犹如为无向图或同为有向图的两个图G1=（V1，E1）和G2=（V2，E2）满足
    V2V1                 E2E1  则称图G2是图G1的子图。
顶点的度就是指和顶点有关联的边的数目。在有向图中，以顶点v为头的弧的数据成为v的入度；以v为尾的弧成为v的出度。这里有一个重要的公式反应了顶点和边的关系。

其中，e表示边的数目，n表示顶点个数，TD(Vi)表示顶点Vi的度。
在图G=（V，E）中，假如存在顶点序列（v0 ，v1，…，vk），其中v0 =p，vk =q，且（v0 ，v1），（v1 ，v2）…，（vk-1 ，vk）都在E中，则称顶点p到顶点q有一条途径，并用（v0 ，v1，…，vk）表示这条途径，途径的长度就是途径上的边或弧的数目，这条途径的长度为k。     假如第一个顶点和最后一个顶点相同的途径称为回路或环。序列中顶点不重复出现的途径称为简单途径。
对无向图而言，假如从任意两个不一样顶点i和j之间都有途径，则该无向图是连通的。无向图中的极大连通子图为该图的连通分量。
对有向图而言，假如任意两个不一样顶点i到j有途径，同时j到i也有途径，则该有向图是强连通的。同样，无向图中的极大连通强子图为该图的强连通分量。
存储结构:最常用的存储结构是有两种。
邻接矩阵:
这是反应顶点间邻接关系的矩阵。定义如下：
设G=（V，E）是具备n（n≥1）个顶点的图，G的邻接矩阵M是一个n行n列的矩阵，若（i，j）或<i，j>∈E，则M[i][j]=1；否则M[i][j]=0。
邻接表:这是图的链式存储结构。
图的每个顶点都建立了一个链表，且第i个链表中的结点代表与顶点i有关联的一条边或由顶点i出发的一条弧。而这些链表的头指针则组成一个次序线性表。
另外，尚有其他的某些存储结构，如十字链表和邻接多重表，分别用来存储有向图和无向图。
图的遍历:
图的遍历是指从图中的某个顶点出发，沿着图中的边或弧访问图中的每个顶点，并且每个顶点只被访问一次。图的遍历算法是求解图的连通性问题、拓扑排序和求核心途径等算法的基础。
一般有两种措施，它们对无向图和有向图都合用。
深度优先搜索:
类似于树的先根遍历。
广度优先搜索:
类似于树的层次遍历。
 这两种算法的时间复杂度相同，不一样之处仅仅在于对顶点访问的次序不一样。
 n 图的有关算法
  包括到图的有关算法比较多，这里只简单归纳简介一下，详细算法希望大家参考有关资料。
u求最小代价生成树
设G=（V，E）是一个连通的无向图，若G1是包括G中所有顶点的一个无回路的连通子图，则称G1为G的一棵生成树。其中代价最小（各条边的权值之和最小）的生成树就称为最小代价生成树（简称最小生成树）。
这里提供两种算法来求解这一问题：普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。分别适合用于求边稠密的网的最小生成树和边稀疏的网的最小生成树，其时间复杂度分别是O(n2)和O(eloge)（e为网中边的数目）。
其中prim算法基本思想：任选一个顶点v0开始，连接与v0最近的顶点v1，得子树T1，再连接与T1最近的顶点v2，得子树T2，如此进行下去，直到所有顶点都用到为止。
L(v):v 到子树T0的直接距离。E是边集合。
输入加权连通图的带权邻接矩阵C=（Cij）n*n.
(1)     T0<-空集，C（T0）<-0,V1={v0}
(2)     对每一点v属于V-V1，L（v）<-C(v, v0);[假如(v, v0)不属于E，则C(v, v0)=无穷大]
(3)     若V1=V,则输出T0，C（T0），停机。否则转到下一步；
(4)     在V-V1中找一点u,使L（u）=min{L(v)|v属于(V-V1)},并记在V1中与u相邻的点为w,e=(w,u)
(5)     T0 <-T0，C（T0）<- C（T0）+ C（e）, V1 <-V1
(6)     对所有的v属于V-V1，若C(v, u)<L（v）,则L（v）<- C(v, u),否则L（v）不变。
(7)     转3
克鲁斯卡尔（Kruskal）算法基本思想：最初把图的n个顶点看作n个分离的部分树，每个树具备一个顶点，算法的每一步选择可连接两分离树的边中权最小的边连接两个部分树，合二为一，部分树逐渐减少，直到只有一个部分树，便得到最小生成树。
克鲁斯卡尔（Kruskal）算法步骤：
T0 :存储生成树的边的集合，初态为空；
C(T0):最小生成树的权，初值为0；
VS：部分树的顶点集合，其初值为{{v0}{ v1}……{ vn}}
输入边的端点数组A（e）,边的权值w(e);
(1)               T0 为空，C(T0)<-0;VS为空，将E中的边按从小到大的次序排列成队列Q；
(2)               对所有的v属于V，VS〈-{v};
(3)               若|VS|=1，输出T0 ，C(T0) ，停止，否则转下一步；
(4)               从Q中取出排头边（u,v），并从Q中删除（u,v）;
(5)               如u,v杂VS的同一个元素集V1 中，则转4，否则分属于两个几个V1 V2  ，进行下一步；
(6)               T0<- T0 ，V<-, C(T0)<- C(T0)+ C(u,v),转3
u求最短途径
在图中求最短途径问题有两种提法，一是求从某个源点到其他顶点的最短途径，二是求每一对顶点之间的最短途径。
对于前者，一般采取迪杰斯特拉（Dijkstra）算法，按途径长度递增的次序产生最短途径。时间复杂度为O(n2)。
迪杰斯特拉（Dijkstra）算法的基本思想：生长一棵以v0为根的最短路树，在这棵树上每一顶点与根之间的途径都是最短途径。因为网络不存在负权，最短路树的生长过程中各顶点将按照距v0的远近及顶点的相邻关系，逐次长入树中，先近后远，直至所有顶点都已经在树中。
处理背面一个问题的措施是：每次以一个顶点为源点，重复执行迪杰斯特拉算法n次。另外还能够使用一个弗洛伊德（Floyd）算法，其时间复杂度也是O(n3)。
弗洛伊德（Floyd）算法基本思想：直接在图的带权邻接矩阵中用插入顶点的措施依次结构出n个矩阵，D（1）D（2）….D（n）,使最后得到的矩阵.D（n）成为图的距离矩阵，同时也求出插入点矩阵以便得到两点见的最短途径。
u拓扑排序
拓