知名高端网站建设公司,wordpress熊掌号推送,云南疾控最新消息今天,app软件定制研发目录
注
图的定义
图的基本术语
图的类型定义
图的存储结构
邻接矩阵
1. 邻接矩阵表示法
2. 使用邻接矩阵表示法创建无向网
3. 邻接矩阵表示法的优缺点
邻接表
1. 邻接表表示法
2. 通过邻接表表示法创建无向图
3. 邻接表表示法的优缺点
十字链表#xff08;有向…目录
注
图的定义
图的基本术语
图的类型定义
图的存储结构
邻接矩阵
1. 邻接矩阵表示法
2. 使用邻接矩阵表示法创建无向网
3. 邻接矩阵表示法的优缺点
邻接表
1. 邻接表表示法
2. 通过邻接表表示法创建无向图
3. 邻接表表示法的优缺点
十字链表有向图
邻接多重表无向图
图的遍历
深度优先搜索DFS
广度优先搜索 注 本笔记参考《数据结构C语言版第2版》 图是一种比线性表和树更复杂是数据结构。在线性表中数据元素之间存在线性关系在树形结构中数据元素之间存在层次关系。但是到了图结构中结点之间的关系可以是任意的这意味着任意两个数据元素都可能相关。
图的定义
||| 图Graph记为G由两个集合V和E组成记为G(V, E)。其中
V顶点顶点的有穷非空集合V(G)表示图G的顶点集合E边V中顶点偶对的有穷集合偶对称的顶点连成了边E(G)表示图G的边集合可以为空。为空时图G只有顶点 。
有向图无向图使用的括号 ( )方向x, y 表示从顶点x到顶点y的一条有向边无特定方向边的区别x, y 和 y, x 是不同的两条边(x, y) 和 (y, x) 是同一条边对于有向图而言x, y 也可以被称为一条弧。其中x为弧尾y为弧头。 【例子】 图的基本术语
用n表示图中的顶点用e表示边的数目图有如下的基本术语
名称解释子图 设图G (V, E)图G (V, E) 若V ⊆ V且E ⊆ E则G是G的子图。 无向完全图和有向完全图 • 无向完全图①是无向图②具有n(n-1)/2条边。 • 有向完全图①是有向图②具有n(n-1)条弧。 稀疏图和稠密图 • 稀疏图边/弧很少的图譬如enlog₂n。 • 稠密图边/弧很多的图。 权和网 • 权每条边上具有的有某种含义的数值。 • 网带权的图被称为网。 邻接点两个结点由一条无向边或者有向边关联则称这两个结点为邻接点。度、入度和出度 • 顶点v的度和v关联的边的数目记为TD(v)。 • 对于有向图顶点的度分为入度和出度 入度以顶点为头的弧的数目记为ID(v) 出度以顶点为尾的弧的数目记为OD(v)。 有公式TD(v) ID(v) OD(v) 路径和路径长度 • 路径是由 顶点v 到 顶点v 的一个顶点序列若G是有向图则路径也是有向的。 • 路径长度是一条路径上的边/弧的数目。 回路或称 环 是第一个顶点和最后一个顶点相同的路径。 简单路径、 简单回路或称 简单环 • 简单路径序列中顶点不重复出现的路径。 • 简单回路/简单环除第一个顶点和最后一个顶点外其余顶点不重复的回路。 连通、连通图和连通分量 • 连通从 顶点v 到顶点v 有路径则称v和v是连通的。 • 连通图若图G中任意两个顶点连通则图G是连通图例上图的G₂。 • 连通分量即无向图中的极大连通子图。 强连通图和强连通分量 • 强连通图在有向图G中若对于每一对 v 和 v ∈ Vv ≠ v从 v 到v 和从 v 到 v 都有路径则图G是强连通图。 • 强连通分量有向图中的极大连通子图被称为有向图的强连通分量。
||| 连通图的生成树
是一个极小连通子图含有图中的所有顶点是边最少的连通子图只有足以构成一棵树的n - 1条边。
【例子】 若在上图的生成树中添上一条边则必定构成一个环。 一棵有n个顶点的生成树仅有n - 1条边。因此 若一个图有n个顶点和少于n - 1条的边则该图就是非连通图。若一个图有n个顶点和多于n - 1条的边则该图必定有环。注但是有n - 1条边的图不一定是生成树。 ||| 有向树和生成森林
有向树有一个顶点的入度为0其余顶点的入度均为1的有向图被称为有向树。生成森林一个有向图的生成森林由若干棵有向树组成含有图中所有顶点但是只有可以构成若干不相交的有向树的弧。
【例子】 图的类型定义 图的抽象数据类型的定义如下 图的存储结构 由于图的结构的复杂性无法通过数据元素在存储区中的物理位置来表示元素之间的关系所以图是没有顺序存储结构的。可以使用二维数组来表示元素之间的关系即邻接矩阵表示法。
邻接矩阵
1. 邻接矩阵表示法 邻接矩阵是表示顶点之间相邻关系的矩阵。设G(V, E)是具有n个顶点的图则G的邻接矩阵是具有如下性质的n阶方阵 【例子】 ------ 若G是网带权的图则可定义邻接矩阵为 【例子】 图的邻接矩阵存储表示如下
#define MVNum 50 //最大顶点数
#define MaxInt 32767 //定义权值的最大值足够大而不会溢出的数
typedef char VerTexType; //设置顶点的类型
typedef int ArcType; //设置边的权值类型
typedef struct
{VerTexType vexs[MVNum]; //顶点表ArcType arcs[MVNum][MVNum]; //邻接矩阵int vexnum, arcnum; //图当前的顶点数和边数
}AMGraph; 在C语言或者C中在头文件中规定了各种类型能够取得的最大值可以自行调用。 2. 使用邻接矩阵表示法创建无向网
【参考代码CreateUDN函数】
Status CreateUDN(AMGraph G)
{//------准备阶段------cin G.vexnum G.arcnum; //依次输入总顶点数、总边数for (int i 0; i G.vexnum; i) //依次输入点的信息cin G.vexs[i];for (int i 0; i G.vexnum; i) //初始化邻接矩阵将边的权值均设为最大值for (int j 0; j G.arcnum; j)G.arcs[i][j] MaxInt; //------构建邻接矩阵阶段------for (int k 0; k G.arcnum; k){VerTexType v1, v2;ArcType w;cin v1 v2 w; //v1、v2是一条边所依附的顶点w是该条边的权值int i LocateAMGVex(G, v1); //确定v1和v2在G中的位置即顶点数组的下标int j LocateAMGVex(G, v2);G.arcs[i][j] w; //将边v1, v2的权值置为wG.arcs[j][i] G.arcs[i][j]; //设置对称边}return true;
}
【参考代码LocateAMGVex函数】 对LocateVex函数的要求遍历顶点数组的下标并且返回所求顶点的位置。 int LocateAMGVex(AMGraph G, VerTexType v)
{for (int i 0; i G.vexnum; i){if (G.vexs[i] v)return i;}return -1;
}
【算法分析】 上述算法的时间复杂度O(n²) 。参考上述算法也可以通过稍加改动得到无向图、有向网、有向图的创建算法。 3. 邻接矩阵表示法的优缺点
1优点 ① 通过对A[i][j]的数值进行观察可以很快判断出两顶点之间是否有边。 ② 通过邻接矩阵可以轻易计算得到各个顶点的度出度、入度。
2缺点 ① 不便于增删顶点 ②不便于统计边的数目需要遍历邻接链表时间复杂度为O(n²) ③ 空间复杂度高是O(n²)对于稀疏图而言尤其浪费空间。 由于上述邻接法的缺点就需要有更适合稀疏图的数据结构。由此就引入了邻接表。
邻接表
1. 邻接表表示法 邻接表是图的一种链式存储结构。一般地邻接表有两部分组成
表头结点表由表头结点组成通过顺序结构进行存储方便访问表头结点用以存储顶点的相关信息。 边链表由表示图中关系的2n个边链表组成边链表由边结点组成。 由上述数据结构可知① 在无向图的邻接表中某顶点的度就是其对应链表中的结点数② 在有向图中某一链表中的结点数就是对应结点的出度。但是若要求得某一结点的入度就需要遍历整个邻接表。此时为了方便就需要一个有向图的逆邻链表如图 图的邻接表的存储结构头结点、边结点可参考下面
#define MVNum 50 //最大顶点数
#define OtherInfo int //相关信息的类型typedef struct ArcNode //边结点的存储结构
{int adjvex; //该条边指向的结点的位置struct ArcNode* nextarc; //指向与下一条边对应的结点OtherInfo info; //和边有关的信息例如权值
}ArcNode;
typedef struct VNode //顶点信息
{VerTexType data;ArcNode* firstarc; //指向与该顶点邻接的第一条边第一个顶点
}VNode, AdjList[MVNum];
typedef struct //邻接表
{AdjList vertices; //表本体int vexnum, arcnum; //图的当前顶点数和边数
}ALGraph; 2. 通过邻接表表示法创建无向图
【参考代码CreateUDG函数】
Status CreateUDG(ALGraph G)
{cin G.vexnum G.arcnum; //依此输入总顶点数、总边数for (int i 0; i G.vexnum; i) //输入各个顶点构造表头结点表{cin G.vertices[i].data; //输入顶点的值G.vertices[i].firstarc NULL; //表头结点的指针域置空}for (int k 0; k G.arcnum; k) //输入各边构造边链表{VerTexType v1, v2; //输入一条边依附的两个顶点cin v1 v2;int i LocateALGVex(G, v1); //确定顶点在G.vertices中的位置序号int j LocateALGVex(G, v2);ArcNode* p1 new ArcNode; //生成新的边结点p1-adjvex j; //邻接点的序号就是jp1-nextarc G.vertices[i].firstarc;G.vertices[i].firstarc p1; //将p1插入顶点i边表的表头ArcNode* p2 new ArcNode;p2-adjvex i;p2-nextarc G.vertices[j].firstarc;G.vertices[j].firstarc p2; //将p2插入顶点j边表的表头}return true;
}
【参考代码LocateALGVex函数】 类似于LocateAMGVex函数只是在搜索时稍加改动。 int LocateALGVex(ALGraph G, VerTexType v)
{for (int i 0; i G.vexnum; i){if (G.vertices[i].data v)return i;}return -1;
}
【算法分析】 上述算法的时间复杂度O(n e)。如若需要建立有向图的邻接表则更加简单。而若要创建有向网的邻接表则可在info域内输入边的权值。 注一个图的邻接矩阵是唯一的但是邻接表却是不唯一的。 3. 邻接表表示法的优缺点
1优点 ① 便于增删结点。 ② 便于统计边的数目通过扫描边表即可得到时间复杂度是O(n e)。 ③ 空间复杂度为O(n e)空间效率高适合稀疏图邻接矩阵表示法更适合稠密图。
2缺点 ① 不便于判断顶点之间是否存在边需要扫描对应边表最坏情况下时间复杂度为O(n)。 ② 不便于计算有向图中各个顶点的度特别是有向图为了求得入度需要遍历各顶点的边表。若采用逆邻接表则难求出度。 为了方便求出顶点的入度和出度接下来就要引入十字链表的概念。
十字链表有向图 十字链表是有向图的一种链式存储结构相当于结合了有向图的邻接表和逆邻接表。十字链表将结点分为了两种 —— 弧结点和边结点 在十字链表中弧头相同的弧在同一链表上弧尾相同的弧也在同一链表上。 【例如】 有向图的十字链表存储表示形式可参考下面
#define MAX_VERTEX_NUM 20
#define InfoType int
typedef struct ArcBox
{int tailvex, headvex; //该弧的尾和头顶点的位置struct ArcBox* hlink, * tlink; //分别为弧头相同和弧尾相同的弧的链域InfoType* info; //关于该弧的相关信息的指针
}ArcBox;
typedef struct VexNode
{VerTexType data;ArcBox* firstin, * firstout; //分别指向该顶点的第一条入弧和出弧
}VexNode;
typedef struct
{VexNode xlist[MAX_VERTEX_NUM]; //表头向量int vexnum, arcnum; //有向图的当前顶点数和弧数
}OLGraph; 如果要进行有向图的十字链表的创建可以模仿邻接表的创建算法 建立十字链表的时间复杂度也是O(n e)。但是十字链表在寻找弧和度上具有更大的优势。 邻接多重表无向图 邻接多重表是无向图的一种很有效的链式存储结构。由于在邻接表中一条弧依附的两个顶点分别被存储在不同的链表中在寻找一条弧对应的两个顶点时存在困难给某些图的操作带来了不便。所以就要通过邻接多重表解决这一问题。 类似于十字链表邻接多重表也由两种不同的结点构成 【例如】 邻接多重表的类型说明如下
//------无向图的邻接多重表存储表示------
#define MAX_VERTEX_NUM 20
typedef enum { unvisited, visited } VisitIf;
typedef struct EBox
{VisitIf mark; //是否访问的标记int ivex, jvex; //该条边依附的两个顶点的位置struct EBox* ilink, * jlink; //分别指向依附这两个顶点的下一条边InfoType* info;
}Ebox;
typedef struct VexBox
{VerTexType data;Ebox* firstedge; //指向依附于该顶点的第一条边
}VexBox;
typedef struct
{VexBox adjmulist[MAX_VERTEX_NUM];int vexnum, edgenum; //无向图的当前顶点数和边数
}AMLGraph; 邻接多重表的各种基本操作的实现和邻接表类似实现时可以参考邻接表。 图的遍历 类似于树的遍历图的遍历也需要从某一结点出发按照某种方式对图中所有结点进行仅一次的访问。但是图的遍历可能会涉及回路等的问题这意味着在沿某条路径进行访问时有可能回到最开始进行访问的结点。为此就需要对已访问的结点进行标记
一般地设辅助数组visited[n]辅助数组的初始值均为 0“false”将已经过的某一结点对应的visited[i]设为 1“true”。根据搜索路径方向的不同通常会有两种不同的遍历图的路径深度优先搜索和广度优先搜索。 深度优先搜索DFS 深度优先搜索可以看作是树的先序遍历的一种推广。其的过程用例子表示如下 由上图可得到一棵深度优先生成树如图 【参考代码DFS函数深度优先搜索访问连通图的递归算法实现】
//------深度优先搜索遍历连通图以无向图为例使用邻接表存储------
void DFS(ALGraph G, int v) //从第v个顶点开始访问
{cout G.vertices[v].data; //访问此处为输出第v个顶点visited[v] true; //在标志数组相应位置进行标记for (int w FirstAdjVex(G, v); w 0; w NextAdjVex(G, v, w)){if (!visited[w]) //对尚未访问的邻接顶点w进行访问DFS(G, w);}
} 除DFS函数之外还牵扯到两个函数FirstAdjVex() 和 NextAdjVex() 它们的作用分别是 ▪ FirstAdjVex函数检查v的所有邻接点w返回v的第一个邻接点 ▪ NextAdjVex函数返回v相对于w的下一个邻接点。 由于篇幅有限下面将仅展示通过邻接表实现的这两个函数。 【参考代码FirstAdjVex函数】
int FirstAdjVex(ALGraph G, int v)
{if (G.vertices[v].firstarc) //遍历边表return G.vertices[v].firstarc-adjvex;elsereturn -1; //邻接点不存在
}
【参考代码NextAdjVex函数】
int NextAdjVex(ALGraph G, int v, int w)
{ArcNode* p G.vertices[v].firstarc;while (p p-adjvex ! w) //寻找w指示顶点p p-nextarc;if (p p-nextarc)return p-nextarc-adjvex;elsereturn -1;
} 注意上述的情况没有涉及到非连通图的处理。也就是说当上述遍历执行完毕后非连通图中一定会有未被访问的顶点。此时需要在图中再次寻找新的起始点即仍未被访问的结点再次执行上述步骤直到图中所有顶点均被访问完毕。
【参考代码深度优先搜索遍历非连通图邻接表版本】
//------对非连通图G进行深度优先搜索------
void DFSTraverse(ALGraph G)
{for (int v 0; v G.vexnum; v) //初始化标志数组visited[v] false;for (int v 0; v G.vexnum; v) if (!visited[v]) //对尚未访问过的顶点进行函数调用DFS(G, v);
} 对于DFSTraverse函数每调用一次DFS_AL函数就代表着有一个连通分量。 【算法分析DFSTraverse函数以邻接表为例】 在遍历时一个顶点只访问一次之后就不会从该顶点出发进行搜索。故遍历图的实质就是对每个顶点查找其邻接点的过程。设图中顶点数为 n 边数为 e 则在邻接表中
查找邻接点的时间复杂度为O(e)深度优先搜索遍历图的时间复杂度为O(n e)。在邻接矩阵中查找邻接点的时间复杂度为O(n²)。 广度优先搜索 广度优先搜索类似于数的按层次遍历依旧以无向图G₄为例 同样的通过上述方法可以得到一棵广度优先生成树如图 【参考代码BFS函数广度优先搜索遍历连通图依旧以邻接表为例】 在这种类似于层次遍历的算法中先访问的顶点其邻接点也会被优先访问。因此需要引入队列保存以被访问过的结点。 另外该算法同样需要一个标志数组。 void BFS(ALGraph G, int v)
{cout G.vertices[v].data; //访问第v个顶点并且通过标志数组进行标记visited[v] true;SqQueue Q;InitQueue(Q); //初始化队列QEnQueue(Q, v); //v进队while (!QueueEmpty(Q)) //若队列非空{int u 0;DeQueue(Q, u); //弹出队头元素for (int w FirstAdjVex(G, u); w 0; w NextAdjVex(G, u, w)){//依此检查u的所有邻接点if (!visited[w]) //若w是u未被访问的邻接点{cout G.vertices[w].data;visited[w] true; //访问并置标记EnQueue(Q, w); //w进队}}}
} 若为非连通图则该算法也一定会有无法访问到的顶点。此时就需要另寻未被访问过的顶点重复上述广度优先搜索过程 这和深度优先算法很类似仅需将DFS函数替换为BFS函数即可。 【算法分析BFSTraverse函数】 因为每个顶点最多仅一次进入队列故该算法实质上就是通过边寻找邻接点的过程。类似于深度优先算法当使用邻接表存储时该算法的时间复杂度为O(n e)同样的若使用邻接矩阵存储则时间复杂度为O(n²)。
