图
1.图的定义和表示
图的定义
图G由集合V和集合E组成，记作G=(V,E),其中：
1、V是顶点元素的有限集合；
2、E是顶点间关系——边的有限集合。
3、边是顶点的无序对或有序对。
无向图和有向图：
无向图
由没有方向的边构成的图。
无向图中的边由顶点的无序对组成。（用圆括号表示）
邻接点：无向图中，若存在一条边(Vi,Vj)，则称Vi和Vj互为邻接点。
上图中的边是无方向的，即(V1,V2)和(V2,V1)表示同一条边。
有向图
由有方向的边构成的图。
弧：有向图中的边由顶点的有序对组成，也称为弧。（用尖括号表示）
有向图中，顶点的有序对<Vi,Vj>表示从Vi指向Vj的一条有向边，其中Vi是起点，Vj是终点。
上图中的边是有方向的，<V1,V2>和<V2,V1>表示两条不同的边。
图的表示
上图G1中：
V(G1)={1,2,3,4,5,6,7}
E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}
上图G2中：
V(G2)={1,2,3,4,5,6}
E(G2)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}
完全图与子图
完全图：图中任意两项点间均有边直接相连。
无向完全图：有n个顶点和n(n-1)/2条边的无向图。
有向完全图：有n个顶点和n(n-1)条弧的有向图。
子图：对于图G=(V,E)和图G'=(V',E')，若存在V'∈V且E'∈E，则称图G'是图G的子图。
2.图的相关概念
顶点的度
无向图中，顶点的度是与每个顶点相连的边数。
有向图中，顶点的度分成入度与出度。
入度：以该顶点为终点的弧的数目
出度：以该顶点为起点的弧的数目
路径与回路
路径：从Vi出发，经过一系列的边或弧能够到达Vj，则称Vi到Vj所经过的顶点序列为从Vi到Vj的路径。
路径长度：路径经过的边的数目或各边权值之和。
回路：起点和终点相同的路劲。
简单路径：序列中顶点不重复出现的路径。
简单回路：除了起点和终点外，其余顶点不重复出现的回路。
连通图
连通：顶点Vi到Vj有一条路径（不要求直达）则Vi和Vj是连通的。
连通图：图中任意两个顶点都是连通的。
连通分量：非连通图的每一个极大连通子图。
强连通图：有向图中任意不同的顶点Vi和Vj，从Vi到Vj和从Vj到Vi都存在路劲。
连通图
强连通图
非连通图的两个连通分量
邻接矩阵
表示顶点间相邻关系的矩阵。
设G=(V,E)是有n(n>0)个顶点的图，G的邻接矩阵A是具有以下性质的n阶方阵：
特点：
无向图的邻接矩阵沿对角线对称。
有向图的邻接矩阵不一定对称。
示例：
无向图的邻接矩阵
有向图的邻接矩阵
权与网
权：图中边或弧上附带的数值称为权(w)。
网：带权的图称为网。
3.图的存储结构与实现
邻接表
邻接表：有顶点表和边表组成，是链式存储结构。
顶点表
存放图中每个顶点的信息以及指向该顶点边表的头指针。顶点表通常采用顺序存储结构。
顶点表的结点结构：data——head
顶点域data存放顶点信息，head为边表头指针。
边表
为图中的每个顶点建立的单链表，单链表中存放与同一个顶点相邻接的邻接点，相当于邻接矩阵中的一行。
边表的结点结构：adjVex——next
邻接点域adjVex存放邻接点在顶点表中的序号，next为指向下一个邻接点的指针。
示例：无向图的邻接表
逆邻接表
结构与邻接表完全相同，只是边表中每个 结点存放的是每条弧的弧尾顶点。
4.图的遍历方法
深度优先遍历（DFS）
1、从图的某一顶点v出现（起点任选），访问此顶点；
2、选择一个与顶点v相邻且未被访问过的顶点w，再从w出发进行深度优先遍历（递归），直至图中所有和v连通的顶点都被访问过为止；
3、若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问为止。
深度优先遍历过程
为图的顶点设置一个访问标记数组visited[n]，其中相应顶点的元素值为0表示为访问，为1表示已访问。
该图的深度优先搜索的输出序列为：ABCFEGDHI
示例：深度优先遍历无向图
深度遍历：V1->V2->V4->V8->V5->V6->V3->V7
示例：深度优先遍历有向图
深度遍历：V1->V2->V4->V8->V3->V6->V7->V5
广度优先遍历（BFS）
1、从图的某一项顶点V出发（起点任选），访问顶点；
2、访问V的所有未被访问过的邻接点V1,V2,...,Vt，按照V1,V2,...,Vt的次序，访问每一个顶点的所有未被访问过的邻接点。依此类推，直至图中所有和V连通的顶点都未被访问过为止；
3、若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作为起点，重复上述过程，直至图中所有顶点都被访问为止。
广度优先遍历过程
该图的广度优先搜索的输出序列为：ABEDCGFHI
示例：广度优先遍历无向图
广度遍历：V1->V2->V3->V4->V5->V6->V7->V8
示例：广度优先遍历有向图
广度遍历：V1->V2->V3->V4->V6->V7->V8->V5
