数据结构–图
数据结构–图
于2020年11月1日2020年11月1日由Sukuna发布
1.图的定义和术语
1.图 图G由顶点集V和关系集E组成,记为:G=(V,E),V是顶点(元素)的有穷非空集，E是两个顶点之间的关系的集合。 若图G任意两顶点a,b之间的关系为有序对,∈E, 则称为从a到b的一条弧/有向边；其中： a是的弧尾，b是的弧头；称该图G是有向图。 若图G的任意两顶点a,b之间的关系为无序对(a,b), 则称(a,b)为无向边(边）,称该图G是无向图。 无向图可简称为图。 2.完全图 3.网:带权的图 4.子图:对图 G=(V,E)和G’=(V’,E’)， 若V’
V 且 E’
E，则称G’是G的一个子图 5.度:与顶点x相关联的边(x,y)的数目,称为x的度，记作TD(x) 或D(x) 以顶点x为弧尾的弧的数目,称为x的出度，记作OD(x)。 以顶点x为弧头的弧的数目,称为x的入度，记作ID(x)。 6.图的连通性质 对无向图G： ● 若从顶点vi到vj有路径,则称vi和vj是连通的。 ● 若图G中任意两顶点是连通的,则称G是连通图。 ● 若图G’是G的一个极大连通子图,则称G’是G的一个连通分量。(连通图的连通分量是自身) 对有向图G ● 若在图G中,每对顶点vi和vj之间, 从vi到vj,且从 vj到vi都存在路径,则称G是强连通图。 ● 若图G’是G的一个极大强连通子图,则称G’是G的一个强连通分量。(强连通图的强连通分量是自身) ●设G=(V,E),G’=(V’,E’),V=V’,若G是连通图,G’是G的一个极小连通子图, 则G’是G的一棵生成树。 ● 若有向图G有且仅有一个顶点的入度为0，其余顶点的入度 为1,则G是一棵有向树。
2.图的存储形式
1.数组表示法/邻接矩阵 顶点数组—用一维数组存储顶点(元素) 邻接矩阵—用二维数组存储顶点(元素)之间的关系(边或弧) 无向图的邻接矩阵是对称的由0-1构成
列和和行和都是i的度
有向图中
表示从i到j有n条边,列和就是入度,行和是出度
对于网来说道理亦同
2.邻接表: 无向图:把与头结点相连的所有元素都存进对应的链表里 有向图的邻接表:它指向的元素存进链表 有向图的逆邻接表:指向它的元素存进链表
如果把图改成了网,那就把每个指向的结点加上一个权重空间
3.有向图的十字链表 其实也很简单,每一个边结点加上弧尾和弧头,第一个指针下一个弧头一样的结点,第二个指针指向下一个弧尾一样结点 点结点就是两个指针:第一个指针指向第一个弧头为该结点的边结点;第二个指针就指向第一个弧尾为该结点的边结点
4.邻接多重表 点结点:就是data和第一个含有这个顶点的边 边结点,mark—-标志域，可用以标记该条边是否被搜索过； vi和vj—-该条边依附的两个顶点在图中的位置； vilink—-指向下一条依附于顶点vi的边； vjlink—-指向下一条依附于顶点vj的边。
找不到下一个没有被指的边了,那就赋值为NULL,没有被指就是链接下来,该结点是最后一个没有被指的结点
3.图的遍历
1.深度优先搜索:一直往下走,如果没有没被搜索到的结点,就搜索上一个被搜索的结点(Stack)
2.广度优先搜索:无论如何先把该结点的每个儿子先遍历了(队列)
4.最小生成树
1.DFS和BFS的生成树
生成森林:对图的每个联通分枝进行生成树搜索
5.网的最小生成树: 在网G的各生成树中，其中各边的权之和最小的生成树称为G的最小生成树 MST性质：设G=（V，E）是一个连通图，通过某种算法构造其最小生成树,T=（U，TE）是正在构造的最小生成树。如果边（u,v)是G中所有一端在U中（即u∈U）而另一端在V-U中（即v∈V-U）具有最小值的一条边，则必存在一棵包含边（u,v)的最小生成树。
6.Prim算法: 对n个顶点的连通网，初始时， T=（U，TE），U为一个开始顶点，TE=φ，以后根据MST性质，每次增加一个顶点和一条边，重复n-1次。Ｕ不断增大，Ｖ－Ｕ不断减小直到为空。
初始化:把进入点标记为U集合,每个节点到进入点的距离标记为V-U中各顶点到U的最短直接路径,相邻结点数组标记为A
进入Prim算法:遍历一遍V-U中各顶点到U的最短直接路径,发现V集合中1是最小的,C进入U集
接着遍历与C连接的的点,更新V-U中各顶点到U的最短直接路径,我们发现C到F的距离为8,比无穷大小,更新值为8,把F中的相邻结点记为C
注意:在找最小的结点时,要忽略已经进入U集的结点的值,这是B进入结点,遍历一遍B到每个结点的距离,发现5<6,更新数据集,D的邻接结点为B
/* 邻接矩阵存储 - Prim最小生成树算法 */
Vertex FindMinDist( MGraph Graph, WeightType dist[] )
{ /* 返回未被收录顶点中dist最小者 */
Vertex MinV, V;
WeightType MinDist = INFINITY;
for (V=0; V<Graph->Nv; V++) {
if ( dist[V]!=0 && dist[V]<MinDist) {
/* 若V未被收录，且dist[V]更小 */
MinDist = dist[V]; /* 更新最小距离 */
MinV = V; /* 更新对应顶点 */
}
}
if (MinDist < INFINITY) /* 若找到最小dist */
return MinV; /* 返回对应的顶点下标 */
else return ERROR; /* 若这样的顶点不存在，返回-1作为标记 */
}
int Prim( MGraph Graph, LGraph MST )
{ /* 将最小生成树保存为邻接表存储的图MST，返回最小权重和 */
WeightType dist[MaxVertexNum], TotalWeight;
Vertex parent[MaxVertexNum], V, W;
int VCount;
Edge E;
/* 初始化。默认初始点下标是0 */
for (V=0; V<Graph->Nv; V++) {
/* 这里假设若V到W没有直接的边，则Graph->G[V][W]定义为INFINITY */
dist[V] = Graph->G[0][V];
parent[V] = 0; /* 暂且定义所有顶点的父结点都是初始点0 */
}
TotalWeight = 0; /* 初始化权重和 */
VCount = 0; /* 初始化收录的顶点数 */
/* 创建包含所有顶点但没有边的图。注意用邻接表版本 */
MST = CreateGraph(Graph->Nv);
E = (Edge)malloc( sizeof(struct ENode) ); /* 建立空的边结点 */
/* 将初始点0收录进MST */
dist[0] = 0;
VCount ++;
parent[0] = -1; /* 当前树根是0 */
while (1) {
V = FindMinDist( Graph, dist );
/* V = 未被收录顶点中dist最小者 */
if ( V==ERROR ) /* 若这样的V不存在 */
break; /* 算法结束 */
/* 将V及相应的边<parent[V], V>收录进MST */
E->V1 = parent[V];
E->V2 = V;
E->Weight = dist[V];
InsertEdge( MST, E );
TotalWeight += dist[V];
dist[V] = 0;
VCount++;
for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
if ( dist[W]!=0 && Graph->G[V][W]<INFINITY ) {
/* 若W是V的邻接点并且未被收录 */
if ( Graph->G[V][W] < dist[W] ) {
/* 若收录V使得dist[W]变小 */
dist[W] = Graph->G[V][W]; /* 更新dist[W] */
parent[W] = V; /* 更新树 */
}
}
} /* while结束*/
if ( VCount < Graph->Nv ) /* MST中收的顶点不到|V|个 */
TotalWeight = ERROR;
return TotalWeight; /* 算法执行完毕，返回最小权重和或错误标记 */
}2.克鲁斯卡尔: 需要将边按递增次序排列以供选择。选择权重最小的边,然后保证没有环 怎么保证没有环?度!
4.有向无环图应用
一个无环的有向图称为有向无环图（directed acycline graph), 简称DAG图。
1.拓扑排序: AOV网（Activity On Vertex network:以顶点表示活动，弧表示活动之间的优先关系的DAG图。
拓扑排序算法思想：重复下列操作，直到所有顶点输出完。 （1）在有向图中选一个没有前驱的顶点输出(选择入度为0的顶点)； （2）从图中删除该顶点和所有以它为尾的弧(修改其它顶点入度) 。
2.AOE网 AOE网研究的问题： （1） 完成整项工程至少需要多少时间； （2） 哪些活动是影响工程进度的关键。
1.(顶点）事件vi的最早发生时间ve(vi)：从开始点到vi的最长路径长度。（ve(v1)=0）,既表示事件vi的最早发生时间，也表示所有以vi为尾的弧所表示的活动ak的最早发生时间e(k)。 如果结点只有一个前驱结点:那就是前驱结点ve+到这个结点的边 有多个前驱结点:前驱结点ve+到这的边求最大值 2.活动最早开始时间ee(e)=所连接的弧尾的标记值 3.(顶点）事件vi允许的最迟开始时间vl(vi) = 完成点（汇点）vn的的最早发生时间ve(vn)减去vk到vn的最长路径长度。 如果有多个后继结点,对每个结点的值求最小即可 4.确定了顶点vi的最迟开始时间后，确定所有以vi为弧头的活动ak的最迟开始时间l(k)：表示在不推迟整个工程完成的前提下，活动ak最迟必须开始的时间。 l(ak)=vl(ak弧头对应顶点)-活动ak的持续时间
5 最短路径
算法1（Dijkstra算法）： 以每一个顶点为源点，重复执行Dijkstra算法n次，即可求出每一对顶点之间的最短路径。
/* 邻接矩阵存储 - 有权图的单源最短路算法 */
Vertex FindMinDist( MGraph Graph, int dist[], int collected[] )
{ /* 返回未被收录顶点中dist最小者 */
Vertex MinV, V;
int MinDist = INFINITY;
for (V=0; V<Graph->Nv; V++) {
if ( collected[V]==false && dist[V]<MinDist) {
/* 若V未被收录，且dist[V]更小 */
MinDist = dist[V]; /* 更新最小距离 */
MinV = V; /* 更新对应顶点 */
}
}
if (MinDist < INFINITY) /* 若找到最小dist */
return MinV; /* 返回对应的顶点下标 */
else return ERROR; /* 若这样的顶点不存在，返回错误标记 */
}
bool Dijkstra( MGraph Graph, int dist[], int path[], Vertex S )
{
int collected[MaxVertexNum];
Vertex V, W;
/* 初始化：此处默认邻接矩阵中不存在的边用INFINITY表示 */
for ( V=0; V<Graph->Nv; V++ ) {
dist[V] = Graph->G[S][V];
if ( dist[V]<INFINITY )
path[V] = S;
else
path[V] = -1;
collected[V] = false;
}
/* 先将起点收入集合 */
dist[S] = 0;
collected[S] = true;
while (1) {
/* V = 未被收录顶点中dist最小者 */
V = FindMinDist( Graph, dist, collected );
if ( V==ERROR ) /* 若这样的V不存在 */
break; /* 算法结束 */
collected[V] = true; /* 收录V */
for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
/* 若W是V的邻接点并且未被收录 */
if ( collected[W]==false && Graph->G[V][W]<INFINITY ) {
if ( Graph->G[V][W]<0 ) /* 若有负边 */
return false; /* 不能正确解决，返回错误标记 */
/* 若收录V使得dist[W]变小 */
if ( dist[V]+Graph->G[V][W] < dist[W] ) {
dist[W] = dist[V]+Graph->G[V][W]; /* 更新dist[W] */
path[W] = V; /* 更新S到W的路径 */
}
}
} /* while结束*/
return true; /* 算法执行完毕，返回正确标记 */
}
Source:ZJU算法2（Floyd算法）： 算法思想： 假设求Vi到Vj的最短路径，如果从Vi到Vj有弧，则存在一条长度为arcs[i][j]的路径，该路径不一定是最短路径，尚需进行n次试探。
首先考虑(Vi,V0,Vj)是否存在（即判断(Vi,V0)和( V0,Vj)是否存在)，如果存在，比较(Vi, Vj)和(Vi,V0)+( V0,Vj)，取长度较短的为从Vi到Vj的中间顶点序号不大于0的最短路径。
再考虑路径上再增加一个顶点V1，如果考虑(Vi,…V1)和(V1,….Vj)， (Vi,…V1)和(V1,….Vj)都是中间顶点序号不大于0的最短路径。 (Vi,…V1，….Vj)可能是从Vi到Vj的中间顶点序号不大于1的最短路径。 比较Vi到Vj的中间顶点序号不大于0的最短路径和(Vi,…V1)+(V1,….Vj)，取长度较短的为从Vi到Vj的中间顶点序号不大于1的最短路径。
bool Floyd( MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum] )
{
Vertex i, j, k;
/* 初始化 */
for ( i=0; i<Graph->Nv; i++ )
for( j=0; j<Graph->Nv; j++ ) {
D[i][j] = Graph->G[i][j];
path[i][j] = -1;
}
for( k=0; k<Graph->Nv; k++ )
for( i=0; i<Graph->Nv; i++ )
for( j=0; j<Graph->Nv; j++ )
if( D[i][k] + D[k][j] < D[i][j] ) {
D[i][j] = D[i][k] + D[k][j];
if ( i==j && D[i][j]<0 ) /* 若发现负值圈 */
return false; /* 不能正确解决，返回错误标记 */
path[i][j] = k;/*记录I和j之间的中间结点*/
}
return true; /* 算法执行完毕，返回正确标记 */
}腾讯云开发者
