即墨网站优化,邢台企业做网站哪家好,做网站是怎么赚钱吗,合合肥网站建设图 1. 定义1.1 无向图和有向图1.2 度、入度和出度1.3 图的若干定义1.4 几种特殊的图 2. 图的存储2.1 邻接矩阵-顺序存储#xff08;数组#xff09;2.2 邻接表-顺序存储链式存储#xff08;数组链表#xff09;2.3 十字链表-适用于有向图2.4 邻接多重表-适用于无向图 3. 图… 图 1. 定义1.1 无向图和有向图1.2 度、入度和出度1.3 图的若干定义1.4 几种特殊的图 2. 图的存储2.1 邻接矩阵-顺序存储数组2.2 邻接表-顺序存储链式存储数组链表2.3 十字链表-适用于有向图2.4 邻接多重表-适用于无向图 3. 图的基本操作EdgeExist(G,v,w)AllAdjVex(G,v)InsertVex(G,v)DeleteVex(G,v)InsertEdge(G,v,w) 4. 图的遍历4.1 广度优先搜索(BFS)4.2 深度优先搜索(DFS) 1. 定义
图Graph是一种比线性表和树更复杂的数据结构。在线性表中数据元素之间是一对一的关系每个数据元素只有一个直接前驱和一个直接后继。在树形结构中数据元素之间有明显的层次关系上一层的数据元素结点和下一层的数据元素结点是一对多的关系。而在图形结构中数据元素之间的关系是任意的是多对多的关系。 在图中数据元素通常称作顶点(Vertex)简称V是有穷非空的集合记为 V { v 1 , v 2 , . . . v n } V\{v_1,v_2,...v_n\} V{v1,v2,...vn}|V|表示顶点个数。两个顶点之间的关系称作边(Edge)简称E是有穷的集合记为 E ( u , v ) ∣ u ∈ V , v ∈ V E{(u,v)|u\in{V},v\in{V}} E(u,v)∣u∈V,v∈V,|E|表示边的条数。 图简称G由顶点集V和边集E组成记作G(V,E) 第三幅图不是图的数据结构
1.1 无向图和有向图 图G1中每条边是没有方向的无向边则图G1是无向图。 图中的边是顶点的无序对例如顶点V1和V2之间的边记作(V1,V2)或(V2,V1)都可以。 G1V1,E1 V1{V1,V2,V3,V4,V5} E1{(V1,V2),(V1,V3),(V2,V4),(V3,V5)} 图G2中每一条边是有方向的(有向边)则图G2是有向图 图中的边是顶点的有序对例如顶点V2和V1之间的边只能记作V2,V1 G2{V2,E2} V2{V1,V2,V3,V4,V5} E2{V2,V1,V1,V3,V3,V5,V5,V3} 有向边也称为弧V2,V1称为顶点V2到顶点V1的弧。V2是弧尾初始点V1是弧头终端点。顶点V2邻接到顶点V1。 简单图不存在重复的边不存在顶点到自身的边
1.2 度、入度和出度
无向图
顶点的度与该顶点关联的边的条数。图G1中TD(V1)2TD(V2)2…无向图中全部顶点的度的和边数X2
有向图
入度以该顶点为终点的边的条数ID(V1) 1,TD(V2)0出度以该顶点为起点的边的条数OD(V1)1,OD(V2)1度顶点的度是该顶点的入度和出度之和TD(V1)ID(V1)OD(V1)2有向图中全部顶点的入度之和等于出度之和
1.3 图的若干定义
路径从顶点Vx到Vy的顶点序列 回路第一个顶点和最有一个顶点相同的路径成为回路或环 简单路径在路径的序列中顶点没有重复出现 简单回路除第一个顶点和最后一个顶点外其他顶点没有重复出现 路径长度路径上边的条数 顶点到顶点的距离顶点之间最短路径的长度如果不存在路径记为无穷 ∞ \infin ∞ 在无向图中如果顶点Vx到顶点Vy有路径表示Vx和Vy是连通的。 在有向图中如果顶点Vx到顶点Vy和顶点Vy到顶点Vx都有路径表示Vx和Vy是强连通的。 连通图任意两个顶点都是连通的。 强连通图任意两个顶点都是强连通的。 生成子图生成子图包含了原图的全部顶点和若干条边 连通分量无向图中极大的连通子图称之为连通分量是连通子图 每个连通子图尽可能包含更多的顶点和边 强连通分量有向图中极大的强连通子图称之为强连通分量是强连通子图 每个强连通子图金肯包含更多的顶点和边 生成树无向连通图中生成树是指包含了全部顶点的极小连通子图连通图 全部顶点 边最少 带权图在一个图中边可以表示某种含义的数值例如顶点之间的距离该数值称为边的权值。如果图的边上带了权值那么该图称为带权图或网。带权图中某条路径上全部边的权值之和称为该路径的带权路径长度。
1.4 几种特殊的图
完全图 无向完全图图中任意两个顶点都存在一条边有向完全图图中任意两个顶点都存在方向相反的两条边 稀疏图和稠密图边很少的图称为稀疏图反之称为稠密图树不存在回路的连通无向图有向树有且仅有一个结点的入度为0除树根外的结点入度为1从树根到任一结点有一条有向通路
2. 图的存储
图的存储方式有四种邻接矩阵、邻接表、十字链表、邻接多重表
2.1 邻接矩阵-顺序存储数组
图的邻接矩阵Adjacency Matrix存储方式是用两个数组来表示图。一个一维数组存储顶点信息一个二维数组称为邻接矩阵存储图中的边或弧的信息。
对于图结点之间有连接则边表中对应项记为1无连接则记为0。但是无向图是A-C和C-A都有然而有向图则只有C-A没有A-C需要看清方向。在无向图的邻接矩阵中顶点的度为该顶点所在行或列中非零元素的个数。在有向图的邻接矩阵中顶点的出度为该顶点所在行中的非零元素的个数入度为该顶点所在列中的非零元素个数。顶点的度出度入度 对于A顶点无向图的度3有向图的度123对于带权图把每条边的权值存入邻接矩阵如果顶点之间不存在边存入无穷表示
// 利用邻接矩阵存储图
typedef char VertType; // 定义顶点的数据类型
typedef int EdgeType; // 定义边权的数据类型
#define MAXVNUM 100 // 顶点的最大数值
#define INFINITY 65536 // 无穷常量也可以用边的权值不可能出现的值struct MGraph
{VertType vexs[MAXVNUM]; // 顶点表EdgeType edges[MAXVNUM][MAXVNUM]; // 带权边表邻接矩阵int vexnum, arcnum; // 顶点数|V|和边数|E|
};2.2 邻接表-顺序存储链式存储数组链表
顶点的信息存放在一维数组中每个顶点的边的信息存放在边链表中。
// 边链表结构体
struct ENode
{int adjvex; // 邻接点域存储该顶点对应的下标EdgeType info; // 存储权值ENode* next; // 指针域指向下一个邻接顶点
};
// 顶点结构体
struct VNode
{VertType data; // 数据域存储顶点信息ENode* first; // 边表头指针
};
// 图的结构体
struct AdjListGraph
{VNode vexs[MAXVNUM]; //顶点数组int vexnum,arcnum; // 顶点数和边数
};2.3 十字链表-适用于有向图
十字链表就是有两个边链表的邻接表。
2.4 邻接多重表-适用于无向图
1边链表结点有冗余无向图中对于A-B之间的边在A的边链表中有B在B的边链表中有A只需要一个就能表达含义了。 2删除边和顶点操作很麻烦时间复杂度高。
3. 图的基本操作
EdgeExist(G,v,w)
判断图G中是否存在从顶点v到顶点w的边(v,w)或v,w如(G,C,D)。
邻接矩阵检查C行D列是否为1。邻接表中检查C顶点的边链表中是否有顶点D。
AllAdjVex(G,v)
列出图G中与顶点v邻接的边如(G,C) 对于无向图
邻接矩阵检查C整行列输出为1对应的顶点邻接表检查顶点C的边链表输出顶点。
对于有向图邻接的边包括出边和入边
邻接矩阵检查C整行输出为1对应的顶点出边检查C整列输出为1对应的顶点入边。邻接表访问顶点C对应的边链表输出顶点出边依次访问每个顶点除C自身的边链表如果有C则输出该顶点入边。
InsertVex(G,v)
在图G中插入顶点v此时不需要插入边只用插入顶点。
DeleteVex(G,v)
从图G中删除顶点v如(G,C)。删除顶点C。真删除和伪删除 对于无向图
邻接矩阵删除顶点表中的C后续元素前移邻接矩阵中删除C对应的行列并移动元素邻接表删除顶点表中的C以及对应的边链表。还要遍历其他顶点删除边链表中的C
InsertEdge(G,v,w)
在图G中插入一条从顶点v到w的边。如(G,C,D) 无向图
邻接矩阵C行D列和D行C列都需要置为1邻接表顶点C的边链表中插入新结点D顶点D的边链表中插入新结点C。 有向图邻接矩阵C行D列置为1邻接表顶点C的边链表中插入新结点D
4. 图的遍历
4.1 广度优先搜索(BFS)
图的广度优先搜索类似于树的层次遍历需要使用一个辅助队列和辅助数组用于记录已经访问过的数组来实现 图的遍历可以从任意一个结点开始假设从顶点2开始。顶点2入队并查找visited数组中对应的下标是否已经访问没有置为true。 出队队头元素并将其邻接点未访问顶点入队包括5,6,3,1 出队队头元素并将其邻接点未访问顶点入5出队后没有入队6出队后入队7 出队队头元素并将其邻接点未访问顶点入3出队后没有元素入队1出队后入队4 出队队头元素并将其邻接点未访问顶点入7出队后没有元素入队4出队后入队89 出队队头元素89。队列为空遍历完成。
4.2 深度优先搜索(DFS)
图的深度优先搜索与图的先序遍历类似。可以利用递归或者栈的形式实现。具体就不在这里展开了。
