抚州 提供网站建站 公司,山西常见网站建设推荐优化,外贸产品销量排名,中国住房城乡和城乡建设部网站目录
一,图的概念
1,图的定义
2,图的基本术语
二,图的存储结构
1,邻接矩阵
2,邻接表
三,图的遍历
1,深度优先搜索
2,广度优先搜素
四,生成树和最小生成树
1,生成树的特点:
2,最小生成树
(1)普利姆算法Prim
(2)普里姆算法思路
五,最短路径
1,Dijkstra算法
2,Fl…目录
一,图的概念
1,图的定义
2,图的基本术语
二,图的存储结构
1,邻接矩阵
2,邻接表
三,图的遍历
1,深度优先搜索
2,广度优先搜素
四,生成树和最小生成树
1,生成树的特点:
2,最小生成树
(1)普利姆算法Prim
(2)普里姆算法思路
五,最短路径
1,Dijkstra算法
2,Floyd算法
六,拓扑排序
七,关键路径 一,图的概念
1,图的定义
在图G中如果代表边的顶点对是无序的则称G为无向图。用圆括号 序偶表示无向边。如果表示边的顶点对是有序的则称G为有向图。用尖括号序偶表示 有向边。
2,图的基本术语
1,端点和连接点无向图若点若 存在一条边(ij) 顶点i和顶点j为端点它们互为邻接有向图若 存在一条边ij 顶点i为起始端点简称为起点 顶点j为终止端点简称终点它们互为邻接点。2,顶点的度、入度和出度无向图以顶点 i为端点的边数称为该顶点的度。有向图 以顶点i为终点的入边的数目称为该 顶点的入度。以顶点i为始点的出边的数目称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。3、完全图无向图每 两个顶点之间都存在着一条边称为完全无向图包含有 n(n-1)/2条边。有向图每 两个顶点之间都存在着方向相反的两条边称为完全有向 图包含有n(n-1)条边。4、子图设有两个图G(VE)和G(VE)若V是V的子集 且E是E的子集则称G是G的子图。5, 路径长度路径长度是指一条路径上经过的边的数目。6,简单路径若一条路径上除开始点和结束点可以相同外其余顶点均不相同则称 此路径为简单路径。7、回路或环若一条路径上的开始点与结束点为同一个顶点则此路径被称为回 路或环。开始点与结束点相同的简单路径被称为简单回路或简单环。8、连通、连通图和连通分量 无向图 (1)若从顶点i到顶点j有路径则称顶点i和j是连通的。 (2)若图中任意两个顶点都连通则称为连通图否则称为非连通图。 (3)无向图G中的极大连通子图称为G的连通分量。显然任何连通图的连 通分量只有一个即本身而非连通图有多个连通分量。 有向图 (1)若从顶点i到顶点j有路径则称从顶点i到j是连通的。 (2)若图G中的任意两个顶点i和j都连通即从顶点i到j和从顶点j到i都存在 路径则称图G是强连通图。 (3)有向图G中的极大强连通子图称为G的强连通分量。显然强连通图 只有一个强连通分量即本身。非强连通图有多个强连通分量。 9、权和网图中每一条边都可以附带有一个对应的数值这种与边相关的数 值称为权。边上带有权的图称为带权图也称作网。 寻找非强连通图的强连通分量: ① 在图中找有向环。 ② 扩展该有向环如果某个顶点到该环中任一顶点有路径并且该环 中任一顶点到这个顶点也有路径则加入这个顶点。 二,图的存储结构
1,邻接矩阵
1如果G是无向图则 A[i][j]1若(i,j)∈E(G) 0:其他2如果G是有向图则 A[i][j]1若∈E(G) 0:其他3如果G是带权无向图则 A[i][j] wij 若i≠j且(i,j)∈E(G) 0ij ∞其他4如果G是带权有向图则 A[i][j] wij 若i≠j且∈E(G) 0ij ∞其他
结论:无向图的邻接矩阵是对称的,顶点i的度第i行(列)中1的个数
特别:完全图的邻接矩阵中,对角线元素为0,其余元素为1 结论:有向图的邻接矩阵可能是不对称的,顶点的出度第i行元素之和;顶点的入度第i列元素之和 邻接矩阵的存储需要用到两个表,一个表位顶点表,用一维数组表示,里面存储顶点.第二个表表示邻接矩阵,用二维数组表示
#define MAXInt 32767 //表示无穷大
#define MVNum 100 //最大顶点数
typedef char VerTexType;//顶点的数据类型为char
typedef int ArcType;//设置边的权值为整型typedef struct {VerTexType vexs[MVNum];//顶点表ArcType arcs[MVNum][MVNum];//邻接矩阵int vexnum, arcnum; //图当前的顶点数和边数
}AMGraph;
无网图初始化:
//无向网
Status CreateUDN(AMGraph G)
{ /采用邻接矩阵表示法创建无向网G
cinG.vexnumG.arcnum; /输入总顶点数总边数 for(i 0; iG.vexnum; i) cinG.vexs[i]; /依次输入点的信息 for(i 0; iG.vexnum;i) /初始化邻接矩阵 for(j0;jG.vexnum;j) G.arcs[i][j] Maxlnt; /边的权值均置为极大值 for(k 0; kG.arcnum;k)
{ /构造邻接矩阵 cinv1v2w; /输入一条边所依附的顶点及边的权值 i LocateVex(G, v1);j LocateVex(G, v2); /确定v1和v2在G中的位置 G.arcs[i][j]W; /边v1,v2的权值置为w G.arcs[j][i] G.arcs[i][j]; /置v1, v2的对称边v2,v1的权值为w
} return OK;
}
邻接矩阵的主要特点:
一个图的邻接矩阵表示是唯一的。特别适合于稠密图的存储。邻接矩阵的存储空间为O(n2)优点:只管,简单,好理解,方便寻找任意两顶点之间是否存在边,方便计算顶点的度缺点:不便于增加和删除顶点,如果为稀疏图,就会有大量的无效元素,浪费空间;统计边数,浪费时间
2,邻接表
分为两种节点,一种是头节点,头节点分为两个部分一部分是顶点信息,另一部分是指向第一条依附于该顶点的边的指针.边节点,第一部分是该边所指向的顶点的位置,第二部分是指向下一条边的指针,第三部分是边的相关信息,例如权,顶点,按照编号的顺序将顶点数据储存在一维数组中,相关联的的边,用线性链表进行连接 无向图: 邻接表并不唯一,边节点的顺序不唯一,若无向图有n个顶点,e条边,则邻接表需要n个头节点和2e个边节点,所以空间复杂度为O(n2e)
无向图中的顶点v1的度为第i个单链表中的节点数
有向图:如果为邻接表,那么头节点指向的是该顶点的出度边,逆邻接表头节点指向的是该顶点的入度边.
由此,邻接表出度为第i单链表中的节点数,找出度容易,找入度难需要遍历整个图才可知. 逆邻接表入度为第i单链表中的节点数,找入度容易,出度困难 有向图和网空间复杂度为O(ne)
#define MVNum 100 //最大顶点数typedef struct VNode {VerTexType deta;ArcNode* firstarc;
}VNode,AdjList[MVNum];typedef int OtherInfo;typedef struct ArcNode { //边节点int adjvex; //该边所指向的顶点的位置struct ArcNode* nextarc;//指向下一条边的指针OtherInfo info;//和边相关的信息,例如:权
}ArcNode;
typedef struct {AdjList vertices;int vexnum, arcnum;//图当前的顶点数和边数
}ALGraph;
无向网的初始化:
//无向图
Status CreateUDG(ALGraph G){ /采用邻接表表示法创建无向图G
cinG.vexnumG.arcnum; /输入总顶点数总边数 for(i 0; iG.vexnum; i) /输入各点构造表头结点表
{ cin G.vertices[i].data; /输入顶点值G.vertices[i].firstarcNULL;
}for(k 0; kG.arcnum;k){ cinV1v2; /输入一条边依附的两个顶点i LocateVex(G, v1); j LocateVex(G, v2);p1new ArcNode; /生成一个新的边结点p1p1-adjvexj; /邻接点序号为j p1-nextarcG.vertices[i].firstarc; G.vertices[i].firstarcp1; /将新结点p1插入顶点vi的边表头部p2new ArcNode; /生成另一个对称的新的边结点p2-adjvexi; /邻接点序号为i p2-nextarc G.vertices[j].firstarc; G.vertices[j].firstarcp2; /将新结点p2插入顶点vj的边表头部
}
邻接表的主要特点:
优点:方便找任意顶点的邻接点,节约稀疏图的空间,需要有向图:(ne),无向图:(n2e)的空间 缺点:有向图,不方便统计度的总数
联系:邻接表中的一行对应邻接矩阵中的一行,邻接表中的节点个数等于邻接矩阵中一行非零元素的个数区别:邻接矩阵空间复杂度为O(n^2),邻接表的空间复杂度为O(n1)邻接矩阵是唯一的,但是邻接表不是唯一的邻接矩阵适用于稠密图,邻接表适用于稀疏图
三,图的遍历
1,深度优先搜索
■在访问图中某一起始顶点 v后由 v出发访问它的任一邻接顶点 w;
■再从 w 出发访问与 w邻接但还未被访问过的顶点 W2;
■然后再从 w2出发进行类似的访问…
■ 如此进行下去直至到达所有的邻接顶点都被访问过的顶点 u 为止。
■ 接着退回一步退到前一次刚访问过的顶点看是否还有其它没有被访问的邻接顶点。
■ 如果有则访问此顶点之后再从此顶点出发进行与前述类似的访问
■如果没有就再退回一步进行搜索。重复上述过程直到连通图中 搜索 所有顶点都被访问过为止。
创建一个visited数组,用来储存该顶点是否被访问过:visited[i]0表示顶点i没有访问visited[i]1表示顶点i已经访问过。
void DFS (AMGraph G,int v)
{coutv;visitd[v]true;for(w0;wG.vexnum;W){if(G.arcs[v][w]!0(!visited[w]))DFS(G,w);}
邻接矩阵来扫描时间复杂度为O(n^2)
void DFS(ALGraph *Gint v){ArcNode *p; int w;visited[v]1; //置已访问标记printf(%d v); //输出被访问顶点的编号pG-Adjlist[v].firstarc; //p指向顶点v的第一条边的边头节点while (p!NULL){wp-adjvex;if (visited[w]0)DFS(Gw); //若w顶点未访问递归访问它pp-nextarc; //p指向顶点v的下一条边的边头节点}}
邻接表来扫描,时间复杂度为O(ne)
2,广度优先搜素
方法从图的某一结点出发首先依次访问该结点的所有邻点 Vi, Vib, …, Vi再按这些顶点被访问的先后次序依次访问与它们相邻接的所有未被访问的顶点 重复此过程直至所有顶点均被访问为止。
邻接表的BFS算法
void BFS(ALGraph *Gint v){ArcNode *p; int wi;int queue[MAXV]front0rear0; //定义循环队列int visited[MAXV];for (i0;iG-n;i)visited[i]0; //访问标志数组初始化printf(%2dv); //输出被访问顶点的编号visited[v]1; //置已访问标记rear(rear1)%MAXV;queue[rear]v;//v进队while (front!rear) //队列不空时循环{front(front1)%MAXV;wqueue[front];//出队并赋给wpG-adjlist[w].firstarc; //找w的第一个的邻接点while (p!NULL){if (visited[p-adjvex]0){printf(“%2d”p-adjvex); //访问之visited[p-adjvex]1;rear(rear1)%MAXV; //相邻顶点进队queue[rear]p-adjvex;}pp-nextarc;}}}DFS算法和BFS算法比较:
空间复杂度相同,都是O(n)前者借用了堆栈,后者借用了队列时间复杂度只与存储结构(邻接矩阵/邻接表)有关,与搜索路径无关
四,生成树和最小生成树
1,生成树的特点:
一个图有许多不同的生成树 生成树的顶点树与图的顶点数相同 生成树是图的极小连通子图,去掉一条边则非连通,再加一条边必然形成回路有n个顶点的连通图的生成树有n-1条边生成树中任意两个顶点之间的路径是唯一的
深度优先生成树/广度优先生成树
广度优先生成树高度 ≤ 深度优先生成树高度 2,最小生成树
对于带权连通图G,其中权 值之和最小的生成树称为图的最小生成树。最小生成树可能不唯一.
(1)普利姆算法Prim
初始化U{v}。v到其他顶点的所有边为候选边重复以下步骤n-1次使得其他n-1个顶点被加入到U中 从候选边中挑选权值最小的边输出设该边在V-U中的顶点是k将 k加入U中考察当前V-U中的所有顶点j修改候选边若(jk)的权值小于原来和顶点k关联的候选边则用(kj)取代后者作为候选边。 (2)克鲁斯卡尔算法
设连通网 N(V,E)令最小生成树初始状态为只有 n个顶点而无边的非连通图7(V, ()),每个顶点自成一个连通分量。 在E中选取代价最小的边若该边依附的顶点落在 T中不同的连通分量上即不能形成环则将此边加入到T中否则舍去此边选取下一条代价最小的边。 依此类推直至7中所有顶 寿島大 点都在同一连通分量上为止。 普利姆算法克鲁斯卡尔算法算法思想选择点选择边时间复杂度O(n^2)O(elog2e)适应范围稠密图稀疏图
五,最短路径
从源点到终点可能不止一条路径把路径长度最短的那条路径 称为最短路径。
1,Dijkstra算法
1,单源最短路径(Dijkstra算法)
1初始化先找出从源点v0到各终点vk的直达路径Vo.Vk), 即通过一条弧到达的路径。
2选择从这些路径中找出一条长度最短的路径Vo,u)。
3更新然后对其余各条路径进行适当调整 若在图中存在弧u,vk)且Vo,U)(U.Vk)(Vo,Vk), 则以路径Vo,u,Vk代替Vo.v)。 在调整后的各条路径中再找长度最短的路径 依此类推。
按长度递增的顺序求出图的某顶点到其余顶点的最短路径 时间复杂度O(n2)
2,Floyd算法
所有顶点间的最短路径(Floyd算法)
逐个顶点试探,从vi到vj的所以可能存在的路径中选出一条最短路径 时间复杂度O(n3)
六,拓扑排序
设G(VE)是一个具有n个顶点的有向图(AOV/AOE)V中顶点序列v1 v2 …vn 称为一个拓扑序列当且仅当该顶点序列满足下列条件 若是图中的边或从顶点i-j有一条路径:则在拓扑序列中顶点i必须排在顶点j之前。在一个有向图中找一个拓扑序列的过程称为拓扑排序[有向图中不允许又回路]
拓扑排序步骤(AOV):
(1)在有向图中选一个没有前驱的顶点且输出
(2)从图中删除该顶点和所有以它为尾的弧
(3)重复上述两步,直到全部的顶点均已输出,或者图中不存在无前驱的顶点为止(代表有向图中有环) 七,关键路径
AOE网: 用一个带顶点权有向图DAG描述工程的预计进度。 表示事件有向边表示活动边e的权c(e)表示完成活动e所需的 时间比如天数。 图中入度为0的顶点表示工程的开始事件如开工仪式出度为0的 顶点表示工程结束事件
关键路径:从AOE网中源点到汇点的最长路径具有最大长度的路径叫 关键路径。
事件v最早开始时间规定源点事件的最早开始时间为0。定义图中任 一事件v的最早开始时间early eventee(v)事件v最迟开始时间定义在不影响整个工程进度的前提下事件v必 须发生的时间称为v的最迟开始时间late event 记作le(v)。活动a的最早开始时间e(a)指该活动起点x事件的最早开始时间活动a的最迟开始时间l(a)指该活动终点y事件的最迟开始时间与该 活动所需时间之差
计算公式:
事件v最早开始时间ee(v)MAX{ee(x)aee(y)bee(z)c}事件v最迟开始时间le(v)MIN{le(x)-ale(y)-ble(z)-c}活动a的最早开始时间e(a)ee(x)活动a的最迟开始时间l(a)le(y)-c关键活动:d(a)l(a)-e(a)若d(a)为0则称活动a为关键活动 在AOE网中可能存在多条关键路径关键活动不按期完成就会影响整个工程的完成时间所有关键活动都提前完成整个工程也将提前完成
