1 .图的定义
图(Graph )由顶点(vertex )的有穷非空集合和顶点之间的边) edge )的集合组成，通常表示为g ) v，e )。 在此，g表示一个图表，v是图表g中的顶点的集合，e是图表g中的边的集合
a .如果顶点之间Vi和Vj之间没有方向，则没有有向边，用无序偶对(Vi，Vj )表示
b .顶点之间有Vi和Vj之间的方向时，是有向边(也称为弧)，相对于Vi，Vj用有序偶对表示，Vi是弧的末尾，Vj是弧的开头
2 .图的基本概念
)1)简图
图中没有吊环也没有多条边，也就是说是简单的图
)2)无向图
如果图表的任意两个顶点之间的边是无向边，即没有方向的边，则图表称为无向图
)3)有向图
如果图表中任意两个顶点之间的边缘是有向边缘(简而言之，是有向边缘)，则该图表被称为有向图
)4)完整图
无向图：在有向图中，当任意2个顶点之间存在边时，该图称为无向图。 )包含n个顶点的有向图是(n(n-1 ) ) /有两条边) ) ) ) ) ) ) ) ) )。
在有向图中，
顶点的度—TD(v ) :是指该顶点附带的边的数量，在n个顶点e条边的无向图中以下公式：成立
权网
在图中，权重(weight )通常是赋予对边的有意义的数值量，将边上具有权重的图称为网或网络图)
3.图的抽象数据类型定义ADT Graph
有DATA顶点的穷非空集合和边的集合
InitGraph
前置条件：图不存在
输入：无
功能：图的初始化
无输出：
后置条件：建立空图
存放图形
前置条件：图已经存在
输入：无
功能：销毁图
无输出：
后条件：释放图所占的存储区域
GetVex
前置条件：图已经存在
输入：顶点v
在功能：图中查找顶点v的数据信息
输出：顶点v的数据信息
后置条件：图不变
putVex
前置条件：图已经存在
输入：顶点v、顶点信息value
功能：在图中搜索顶点v，并且将值分配给顶点v
无输出：
无后置条件：
InsertVex
前置条件：图已经存在
输入：顶点v
在功能：图中插入顶点
如果输出：插入失败，则抛出异常
后置条件：插入成功后，将在图中添加一个顶点
deleteVex
前置条件：图已经存在
输入：顶点v
从功能：图中删除顶点
如果输出：删除失败，则抛出异常
后置条件：删除成功后，图上减少了一个顶点
内部
前置条件：图已经存在
输入：顶点u、顶点v和顶点u和v之间的边的信息
功能：在图上插入边
如果输出：插入失败，则抛出异常
后置条件：插入成功后，会在图中添加边
删除arc
前置条件：图已经存在
输入：顶点u、顶点v
从功能：图中删除顶点u和v之间的边缘
如果输出：删除失败，则抛出异常
后置条件：删除成功后，图上减少了一个顶点
DFSTraverse
前置条件：图已经存在
输入：导线测量的开始顶点v
功能：从顶点v开始深度优先遍历
输出：图顶点的线性排序
后置条件：图保持不变
BFSTraverse
前置条件：图已经存在
输入：导线测量的开始顶点v
功能：从顶点v开始扩展优先遍历
输出：图顶点的线性排序
后置条件：图保持不变
4 .遍历有向图1题：以哪个顶点作为开始顶点
1答案：顶点全部平等，可以选择任意顶点，可以从号码小的顺序开始
问题：图有电路，几个顶点构成一个圆环。 反复访问，有可能陷入死循环
2答：在顶点设置访问标志。 visited[n]，n是图中的顶点数量，未访问标志0，顶点被访问时标志1
深度优先遍历：
基本想法：
1 .访问顶点v
2 .从v的未被访问的邻接点中选择1个顶点w，从w开始进行深度优先的遍历
3 .重复上述两个步骤，直到所有与图中v相连的顶点都被访问
伪代码: (如木头般的超前遍历) ) )。
1 .访问顶点，visited[v]=1；
2.w=顶点v的第一个相邻点
3.while(w ) {
从if(w未被访问)顶点w递归地执行该算法
w=顶点v的下一个相邻点
}
广度优先遍历：
基本想法：
1 .访问顶点v
2 .依次访问v的未被访问的各邻接点V1、V2、V3……VK
3.v1、V2、V3……VK分别从出发点按顺序访问他们未访问过的相邻点，使“先前访问过的顶点的相邻点”先于“后来访问过的顶点的相邻点”访问，直到访问了与图中的顶点v通过路径的所有顶点为止
伪代码: (类似于树的分层扫描) ) ) ) ) ) ) ) ) ) )。
1 .初始化队列q
2 .访问顶点v，visited[v]=1，顶点入队q；
3.while ()队列q不为空)。
v=队列q的团队领导要素离开团队
w=顶点v的第一个相邻点
wile(w存在) {
if(w未访问) {
访问顶点w，visited[w]=1； 顶点w排队q
}
w=顶点v的下一个相邻点
}
}