数据结构学习笔记(图)

一(基本概念)

1.图的定义:图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。

2.与线性表、树的比较: (1)线性表中我们把数据元素叫元素,树中将数据元素叫结点,在图中数据元素,我们则称之为顶点。 (2)线性表中可以没有数据元素,称为空表。树中可以没有结点,叫做空树。在图结构中,不允许没有顶点。 (3)线性表中,相邻的数据元素之间具有线性关系,树结构中,相邻两层的结点具有层次关系,而图中,任意两个顶点之间都可能有关系,顶点之间的逻辑关系用边来表示,边集可以是空的。

3.无向边:若顶点Vi到Vj之间的边没有方向,则称这条边为无向边,用无序偶对(Vi,Vj)来表示。如果图中任意两个顶点之间的边都是无向边,则称该图为无向图。

有向边:若从顶点Vi到Vj的边有方向,则称这条边为有向边,也称为弧。用有序偶<Vi,Vj>来表示,Vj称为弧尾,Vj称为弧头。如果图中任意两个顶点之间的边都是有向边,则称该图为有向图。

*无向边用小括号“()”表示,而有向边则用尖括号“<>”表示。

4.在图中,若不存在顶点到其自身的边,且同一条边不重复出现,则称这样的图为简单图。

5.在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。含有n个顶点的无向完全图有n*(n-1)/2条边。

6.在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图。含有n个顶点的有向完全图有n*(n-1)条边。

*对于具有n个顶点和e条边数的图,无向图0≤e≤n(n-1)/2, 有向图0≤e≤n(n-1)。

7.有很少条边或弧的图称为稀疏图,反之称为稠密图。

8.与图的边或弧相关的数叫做权。这种带权的图通常称为网。

9.顶点v的度是和v相关联的边的数目。 边数其实就是各定点度数和的一半。 以顶点v为头的弧的数目称为v的入度,以v为尾的弧的数目称为v的出度。

10.图中顶点与顶点之间的路径却是不唯一的。 路径的长度是路径上的边或弧的数目。 第一个顶点到最后一个顶点相同的路径称为回路或环。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简单环。

1.无向图中的极大连通子图称为连通分量。强调: *要是子图; *子图要是连通的; *连通子图含有极大顶点数; *具有极大顶点数的连通子图包含依附于这些顶点的所有边。

2.从Vi到Vj和从Vi到Vj都存在路径,则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。

3.一个连通图的生成树是一个极小的连通子图,它含有图中全部的n各顶点,但只有足以构成一棵树的n-1条边。

4.如果一个图有n个顶点和小于n-1条边,则是非连通图,如果它多于n-1条边,必定构成一个环。不过有n-1条边并不一定是生成树。

5.如果一个有向图恰有一个顶点的入度为0,其余顶点的入度均为1,则是一棵有向树。

6.一个有向图的生成森林由若干棵有向树组成,含有图中全部顶点,但只有足以构成若干棵不想交的有向树的弧。

三(术语总结)

1.图按照有无方向分为无向图和有向图。无向图由顶点和边构成,有向图由顶点和弧构成。弧有弧尾和弧头之分。

2.图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图,有向的叫有向完全图。若无重复的边或顶点到自身的边则叫简单图。

3.图中顶点之间有领接点、依附的概念。无向图顶点的边数叫做度,有向图顶点分为入度和出度。

4.图上的边或弧上带权则称为网。

5.图中顶点间存在路径,两顶点存在路径则说明是连通的,如果路径最终回到起始点则称为环,当中不重复叫简单路径。若任意两顶点都是连通的,则图就是连通图,有向则称强连通图。图中有子图,若子图极大连通则就是连通分量,有向则称强连通分量。

6.无向图中连通且n个顶点n-1条边叫生成树。有向图中一顶点入度为0,其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林。

四(图的存储结构)

1、图不可能用简单的顺序存储结构来表示。

2.图的五种不同的存储结构: (1)邻接矩阵:图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

*对称矩阵就是n阶矩阵的元满足aij=aji。即从矩阵的左上角到右下角的主对角线为轴,右上角的元与左下角相对应的元全都是相等的(即是无向图)。

a.判定任意两顶点是否有边无边就非常容易了。 b.要知道某个顶点的度,其实就是这个顶点Vi在邻接矩阵中第i行(或第i列)的元素之和。 c.求顶点Vi的所有邻接点就是矩阵中第i行元素扫描一遍,arc[i][j]为1就是邻接点。

*判断有向图顶点Vi到Vj是否存在弧,只需要查找矩阵中arc[i][j]为1的顶点。

*图的邻接矩阵存储结构代码: typedef char VertexType; /*顶点类型应由用户定义*/ typedef int EdgeType; /*边上的权值类型应由用户定义*/ #define MAXVEX 100 /*最大顶点数,应由用户定义*/ #define INFINITY 65535 /*用65535来表示正无穷*/ typedef struct { VertexType vexs[MAXVEX]; /*顶点表*/ EdgeType arc[MAXVEX][MAXVEX] /*邻接矩阵,可看做边表*/ int numVertexes, numEdges; /*图中当前的顶点数和边数*/ }MGraph;

*无向网图的创建代码: /*建立无向网图的邻接矩阵表示*/ void CreateMGraph(MGraph *G) { int i, j, k, w; printf("输入顶点数和边数:\n"); scanf("%d, %d", &G->numVertexes,&G->numEdges); /*输入顶点数和边数*/ for(i=0;i<G->numVertexes; i++) /*读入顶点信息,建立顶点表*/ scanf(&G->vexs[i]); for(i=0;i<G->numVertexes; i++) for(j=0;j<G->numVertexes; j++) G->arc[i][j]=INFINITY; /*邻接矩阵初始化*/ for(k=0; k<G->numEdges; k++) /*读入numEdges条边,建立邻接矩阵*/ { print("输入边(Vi,Vj)上的下标、下标j和权w:\n"); scanf("%d, %d, %d", &i, &j, &w); /*输入边(Vi,Vj)上的权w*/ G->arc[i][j]=w; G->arc[j][i]=G->arc[i][j]; /*因为是无向图,矩阵对称*/ } }

#从代码中也可以得到,n个顶点和e条边的无向网图的创建,时间复杂度为O(n+n2+e),其中对邻接矩阵Garc的初始化耗费了O(n2)的时间。

(2)邻接表:数组与链表相结合的存储方法称为邻接表。 *邻接表的处理方法是这样: 1.图中顶点用一个一维数组存储,当然,顶点也可以用单链表来存储,不过数组可以较容易地读取顶点信息,更加方便。另外,对于顶点数组中,每个数据元素还需要存储指向第一个邻接点的指针,以便于查找该顶点的边信息。 2.图中每个顶点vi的所有邻接点构成一个线性表,由于邻接点的个数不定,所以用单链表存储,无向图称为顶点Vi的边表,有向图则称为顶点Vi作为弧尾的出边表。

*顶点表的各个结点由data和first edge两个域表示,data是数据域,存储顶点的信息,firstedge是指针域,指向边表的第一个结点,即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域,存储某顶点的邻接点的顶点表中的下标,next则存储指向边表中下一个结点的指针。

*对于带权值得网图,可以在边表结点定义中再增加一个weight的数据域,存储权值信息即可。

#结点定义: typedef char VertexType; /*顶点类型应由用户定义*/ typedef int EdgeType; /*边上的权值应由用户定义*/

typedef struct EdgeNode /*边表结点*/ { int adjvex; /*邻接点域,存储该顶点对应的下标*/ EdgeType weight; /*用于存储权值,对于非网图可以不需要*/ struct EdgeNode *next; /*链域,指向下一个邻接点*/ }EdgeNode;

typedef struct VertexNode /*定义表结点*/ { VertexType data; /*顶点域,存储顶点信息*/ EdgeNode *firstedge; /*边表头指针*/ }VertexNode, AdjList[MAXVEX];

typedef struct { AdjList adjList; int numVertexes, numEdges; /*图中当前顶点数和边数*/ }GraphAdjList;

#无向图的邻接表的创建: /*建立图的邻接表结构*/ void CreateALGraph(GraphAdjList *G) { int i, j, k; EdgeNode *e; printf("输入顶点数和边数:\n"); scanf("%d, %d", &G->numVertexes, &G->numEdges); /*输入顶点数和边数*/ for (i=0; i<G->numVertexes; i++) /*读入顶点信息,建立顶点表*/ { scanf(&G->adjLIst[i].data); /*输入顶点信息*/ G->adjLIst[i].firstedge=NULL; /*将边表置为空表*/ } for(k=0; k<G->numEdges; k++) /*建立边表*/ { printf("输入边(Vi, Vj)上的顶点序号:\n"); scanf("%d, %d", &i, &j); /*输入边(Vi,Vj)上的顶点序号*/ e=(EdgeNode*)malloc(sizeof(EdgeNode)); /*向内存申请空间*/ /*生成边表结点*/ e->adjvex=j; /*邻接序号为j*/ e->next=G->adjList[i].firstedge; /*将e指针指向当前顶点指向的结点*/ G->adjList[i].firstedge=e; /*将当前顶点的指针指向e*/ e=(EdgeNode*)malloc(sizeof(EdgeNode)); /*向内存申请空间*/ /*生成边表结点*/ e-adjvex=i; /*邻接序号为i*/ e->next=G->adjList[j].firstedge; /*将e指针指向当前顶点指向的结点*/ G->adjList[j].firstedge=e; /*将当前顶点的指针指向e*/ } }

*时间复杂度为O(n+e)。

五(图的遍历)

1.概念:从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历。

2.需要在遍历过程中把访问过的顶点打上标记,以避免访问多次而不自知。具体办法是设置一个访问数组visited[n],n是图中顶点的个数,初值为0,访问过后设置为1.

3.图的遍历:深度优先遍历和广度优先遍历。 (1)深度优先遍历(DFS): 深度优先遍历其实就是一个递归的过程,相当于树的前序遍历。 从图中某个顶点v出发,访问此顶点,然后从v的未访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到。 对于非连通图,只需要对它的连通分量分别进行深度优先遍历。

**对于n个顶点e条边的图来说,邻接矩阵的方式访问需要O(n2)的时间;对于邻接表来说,需要O(n+e)时间。 显然对于点多边少的稀疏图来说,邻接表结构使得算法在时间效率上大大提高。

(2)广度优先遍历(BFS): 类似树的层序遍历。 *广度优先遍历和深度优先遍历的时间复杂度是一样的。邻接矩阵访问时间为O(n2),邻接表访问时间为O(n+e)。

比较:深度优先遍历更适合目标比较明确,以找到目标为主要目的的情况,而广度优先更适合在不断扩大遍历范围时找到相对最优解的情况。

六(最小生成树)

我们把构造连通网的最小代价生成树称为最小生成树。 找连通网的最小生成树,有两种算法:普里姆算法和克鲁斯卡尔算法。

1、普里姆算法: 以某顶点为起点逐步找各顶点上最小权值得边来构建最小生成树的。 假设N=(P,{E})是连通图,TE是N上最小生成树中边的集合。算法从U={u。}(u。属于V),TE={}开始。重复执行下述操作:在所有u属于U,v属于V-U的边(u,v)属于E中找一条代价最小的边(u。,v。)并入集合TE,同时v。并入U,直至U=V为止。此时TE中必有n-1条边,则T=(V,{TE})为N的最小生成树。 时间复杂度为O(n2)。

2.克鲁斯卡尔算法: 以边为目标去构建。 假设N=(V,{E})是连通图,则令最小生成树的初始状态为只有n个顶点而无边的非连通图T={V,{}},图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将次变加入到T中,否则舍去此边而选择下一条代价最小的边。依次类推,直至T中所有顶点都在同一连通分量上为止。 克鲁斯卡尔算法的时间复杂度为O(elog2e)。

总结:对比两个算法,克鲁斯卡尔算法主要是针对边来展开,边数少时效率会非常高,所以对于稀疏图有很大的优势;而普里姆算法对于稠密图,即边数非常多的情况会更好一些。

七(最短路径)

对于网图来说,最短路径,是指两顶点之间经过的边上权值最少的路径,并且我们称路径上的第一个顶点是源点,最后一个顶点是终点。

1.迪杰斯特拉(Dijkstra)算法: 这是一个按路径长度递增的次序产生最短路径的算法。 时间复杂度为O(n2)。 如果是图中任意一个顶点到另一顶点的距离,时间复杂度为O(n3)。

代码如下: #define MAXVEX 9 #define INFINITY 65535 typedef int Pathmatirx[MAXVEX]; typedef int ShortPathTable[MAXVEX]; typedef int ShortPathTable[MAXVEX];

void ShortestPath_Dijkstra(MGraph G, int V0, Pathmatirx *P, ShortPathTable *D) { int v, w, k, min; int final[MAXVEX]; for (v=0; v<G.numVertexes; v++) { final[v] = 0; (*D)[v] = G.matirx[v0][v]; (*p)[v] = 0; } (*D)[v0] = 0; final[v0] = 0; final[v0] = 1; for (v=1; v<G.numVertexes; v++) { mun = INFINITY; for (w=0; w<G.numVertexes; w++) { if (!final[w] && (*D)[w]<min) { k=w; min=(*D)[w]; } } final[k]=1; for (w=0; w<G.numVertexes; w++) { if(!final[w] && (min+G.matirx[k][w]<(*D)[w])) { (*D)[w] = min + G.matirx[k][w]; (*p)[w]=k; } } } }

2.弗洛伊德(Floyd)算法 比较经过顶点的权值,如果经过的顶点路径比原两点间的路径更短,将当前两点间的权值设为更小的一个。

代码如下: typedef int Pathmatirx[MAXVEX][MAXVEX]; typedef int ShortPathTable[MAXVEX][MAXVEX]; /*Floyd算法,求网图G中各顶点V到其余顶点w最短路径P[v][w]及带权长度D[v][w]*/ void ShortestPath_Floyd(MGraph G, Pathmatirx *P, ShortPathTable *D) { int v, w, k; for (v=0; v<G.numVertexes; ++w); /*初始化D与P*/ { (*D)[v][w]=G.matirx[v][w]; /*D[v][w]值即为对应点间的权值*/ (*P)[v][w]=w; } } for(k=0; k<G.numVertexes; ++k) { for(v=0; v<G.numVertexes; ++v) { for(w=0; w<G.numVertexes; ++w) { if((*D)[v][w]>(*D)[v][k] + (*D)[k][w]) { /*如果经过下标为k顶点路径比原两点间路径更短*/ /*将当前两点间权值设为更小的一个*/ (*D)[v][w]=(*D)[v][k]+(*D)[k][w]; (*P)[v][w]=(*P)[v][k]; } } } }

时间复杂度为O(n3)。

八(拓扑排序)

1.无环,即是图中没有回路的意思。

2.在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称为AOV网。

3。设G={V,E}是一个具有n个顶点的有向图,V中的顶点序列V1,V2,......,Vn,满足若从顶点Vi到Vj有一条路径,则在顶点序列中顶点Vi必在顶点Vj之前。则我们称这样的顶点序列为一个拓扑序列。

4.拓扑排序,其实就是一个有向图构造拓扑序列的过程。构造时会有两个结果,如果此网的全部顶点都被输出,则说明它是不存在环(回路)的AOV网;如果输出顶点数少了,也说明这个网存在环(回路),不是AOV网。

5.拓扑排序算法: (1)对AOV网进行拓扑排序的基本思路是:从AOV网中选择一个入度为0的顶点输出,然后删去此顶点,并删除以此顶点为尾的弧,继续重复此步骤,直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。 (2)由于拓扑排序的过程中,需要删除顶点,显然用邻接表会更加方便。

**拓扑排序的整个算发起的时间复杂度为O(n+e)。

6.在一个表示工程的带权有向图中,用顶点表示事件,用有向边表示活动,用边上的权值表示活动的持续时间,这种有向图的边表示活动的网,我们称之为AOE网。我们把AOE网中没有入边的顶点称为始点或源点,没有出边的顶点称为终点或汇点。

7.AOV网是顶点表示活动的网,它只描述活动之间的制约关系,而AOE网是用边表示活动的网,边上的权值表示活动持续的时间。

8.把路径上各个活动所持续的时间之和称为路径长度,从源点到汇点具有最大长度的路径叫关键路径。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏WD学习记录

Python数据结构与算法笔记(5)

邻接矩阵优点是简单,对于小图,很容易看到哪些节点连接到其他节点。但是大多数单元格是空的,即稀疏。

1263
来自专栏机器学习算法工程师

Tarjan算法

tarjan算法 一个关于有向图的联通性的神奇算法。 基于DFS(迪法师)算法,深度优先搜索一张有向图。 名词的储备,有备无患 强连通(strongly con...

39710
来自专栏云霄雨霁

有向图----强连通分量问题(Kosaraju算法)

1981
来自专栏个人分享

邻接矩阵学习

邻接矩阵:是表示顶点之间相邻关系的矩阵。因此,用一个一维数组存放图中所有顶点数据;用一个二维数组存放顶点间的关系(边或弧)的数据,这个二维数组称为邻接矩阵。邻接...

1101
来自专栏数据结构与算法

4768 跳石头

4768 跳石头 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 一年一度的“...

27610
来自专栏数据结构与算法

二分图相关定理

定义:若选择一个点说明选择与它相连的所有边,最小顶点覆盖就是选择最少的点来覆盖所有的边。

1133
来自专栏数据结构与算法

2039 骑马修栅栏

题目描述 Description Farmer John每年有很多栅栏要修理。他总是骑着马穿过每一个栅栏并修复它破损的地方。 John是一个与其他农民一样懒的人...

37811
来自专栏数据结构与算法

tarjan算法详解

tarjan算法讲解。 tarjan算法,一个关于 图的联通性的神奇算法。基于DFS算法,深度优先搜索一张有向图。!注意!是有向图。根据树,堆栈,打标记等种种神...

3994
来自专栏数据结构与算法

洛谷P2678 跳石头

题目背景 一年一度的“跳石头”比赛又要开始了! 题目描述 这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终...

3415
来自专栏恰童鞋骚年

数据结构基础温故-5.图(中):最小生成树算法

图的“多对多”特性使得图在结构设计和算法实现上较为困难,这时就需要根据具体应用将图转换为不同的树来简化问题的求解。

1412

扫码关注云+社区

领取腾讯云代金券