招商网站大全,设计公司的网站详情,网站建设学习教程,外贸综合服务网站建设故事凌 今天基本知识点图可说是所有数据结构里面知识点最丰富的一个, 自己笨的知识点如下:阶(oRDER), 度: 出度(out-Degree), 入度(in-Degree)树(Tree), 森林(Forest), 环(Loop)有向图(Directed Graph), 无向图(Undirected Graph), 完全有向图, 完全无向图连通图(Connected Gra…故事凌 今天基本知识点图可说是所有数据结构里面知识点最丰富的一个, 自己笨的知识点如下:阶(oRDER), 度: 出度(out-Degree), 入度(in-Degree)树(Tree), 森林(Forest), 环(Loop)有向图(Directed Graph), 无向图(Undirected Graph), 完全有向图, 完全无向图连通图(Connected Graph), 连通分量(Connnected Component)存储和表达式: 邻接矩阵(Adjacency Matrix), 邻接链表(Adjacency List)围绕图的算法也是五花八门图的遍历: 深度优先, 广度优先环的检测: 有向图, 无向图拓扑排序最短路径算法: Dijkstra, Bellman-Ford, Floyd Warshall连通性相关算法: Kosaraju, Tarjan, 求解孤岛的数量, 判断是否为树图的着色, 旅行商问题等以上的知识点知识图轮里的冰山一角, 对于算法面试而言, 完全不需要对每个知识点都一一掌握, 而应该有的放矢的准备必会的知识点以下的知识点必须充分掌握并反复练习图的存储和表达式: 邻接矩阵(Adjacency Matrix), 邻接链表(Adjacency List)图的遍历: 深度优先, 广度优先二部图的检测(Bipartite), 数的检测, 环的检测, 有向图, 无向图拓扑排序联合-查找算法(Union-Find)最短路径Dijkstra, BellMan-Ford其中, 环的检测, 二部图的检测, 树的检测以及拓扑都是基于图的遍历, 尤其是深度优先方式的遍历, 而遍历可以在邻接矩阵或者邻接链表上进行, 所以掌握好图的遍历是重中之重, 因为它是所有其他图论算法的基础至于对端路径算法, 能区分它们的不同特点, 知道在什么情况下用哪种算法就很好了, 对于有充足时间准备的面试者, 能熟练掌握他们的写法当然是很好的我们来来看看数据结构中的图到底是什么1. 图的定义图是由一些点(vertex)和这些点之间的连线(edge)所组成的, 其中, 点通常称为顶点(vertex), 而点到点之间的连线通常称之为边或者弧(edge), 通常记为G (V,E)2. 图的分类图通常分为有向图和无向图, 而其表示方式分为邻接矩阵和邻接链表, 具体表示如下图.对于无向图其所有的边都不区分方向。G(V,E)。其中V{1,2,3,4,5}。V表示有”1,2,3,4,5”几个顶点组成的集合。E{(1,2),(1,5),(2,1),(2,5),(2,4),(2,3),(3,2),(3,4),(4,3),(4,2),(4,5),(5,1),(5,2),(5,4)}。E就是表示所有边组成的集合如(1,2)表示由顶点1到顶点2连接成的边。对于有向图其所有的边都是有方向的。G(V,E)。其中V{1,2,3,4,5}。V表示有”1,2,3,4,5”几个顶点组成的集合。E{1,2,2,55,4,4,23,5,3,6,6,6}。E就是表示所有边组成的集合如1,2表示由顶点1到顶点2连接成的边。注意有向图边和无向图边表示方法的不同有向图的边是矢量而无向图只是普通的括号。针对邻接矩阵和邻接链表两种不同的表示方式有如下优缺点邻接矩阵由于没有相连的边也占据空间相对于邻接链表存在空间浪费的问题但是在查找的时候邻接链表会比较耗时对于邻接矩阵来说它的查找复杂度就是O(1)。用邻接表表示图的代码#define MAX 100typedef struct ENode //邻接表中表对应的链表的顶点{ int ivex; //该边所指向的顶点的位置 int weight; //该边的权值 struct ENode *next_edge; //指向下一条边的指针}ENode,*PENode;typedef struct VNode //邻接表中表的顶点{ char data; //顶点的数据 struct VNode *first_edge; //指向第一条依附该顶点的边}VNode;typedef struct LGraph //邻接表{ int vexnum; //图的顶点数 int edgenum; //图的边数 VNode vexs[MAX];}LGraph;3. 度, 权, 连通图等概念对于无向图来说它的顶点的度就是指关联于该顶点的边的数目而对于有向图来说分为入度和出度所谓入度就是进入该顶点边的数目出度就是离开这个顶点边的数目有向图的度就是入度加出度。图还被分为有权图和无权图所谓有权图就是每条边都具有一定的权重通常就是边上的那个数字而无权图就是每条边没有权重也可以理解为权重为。如下图所示即为有权图(A,B)的权就是13。如果一个无向图中每个顶点到所有其他顶点都是可达的则称该图是连通的如果一个有向图中任意两个顶点互相可达则该有向图是强连通的。如图(b)中有3个连通分量{1,2,5},{3,6},{4}。若一个无向图只有一个连通分量则该无向图连通。而图(a)中有3个强连通分量{1,2,4,5}{3}{6}。{1,2,4,5}中所有顶点对互相可达。而顶点2与6不能相互可达所以不能构成一个强连通分量。4. 深度优先搜索(Depth First Search DFS)图的深度优先算法有点类似于树的前序遍历首先图中的顶点均未被访问确定某一顶点从该顶点出发依次访问未被访问的邻接点直到某个邻接点没有未被访问邻接点时则回溯父节点(此处我们将先被访问的节点当做后被访问节点的父节点例如对于节点A、B访问顺序是A -B则称A为B的父节点)找到父节点未被访问的子节点如此类推直到所有的顶点都被访问到。注意深度优先的存储方式一般是以栈的方式存储。无向图的深度优先搜索有向图的深度优先搜索深度优先搜索代码static void DFS(LGraph G, int i,int *visited){ Enode *node;E printf(“%c”,G.vexs[i].data); node G.vexs[i].first_edge; while(node ! NULL) { if(!visited[node-ivex]) DFS(G, node-ivex, visited); //递归调用DFS node node-next_edge; }}5. 广度优先搜索从图中的某个顶点出发访问它所有的未被访问邻接点然后分别从这些邻接点出发访问它的邻接点。说白了就是一层一层的访问“浅尝辄止”注意广度优先搜索的存储方式一般是以队列的方式存储。无向图的广度优先搜索有向图的广度优先搜索广度优先所有代码void BFS(LGraph G){ int head 0; int rear 0; int queue[MAX]; //辅助队列 int visited[MAX]; //顶点访问标记 eNode *node; for(int i 0; i ivex; if(!visited[k]) { visited[k] 1; printf(“%c”,G.vesx[k].data); queue[rear] k; } node node-next_edge; } } } printf(“”);}6.拓扑排序拓扑排序(Topological Order)是指讲一个有向无环图(Directed Acyclic Graph,DAG)进行排序而得到一个有序的线性序列。举个例子例如我们早上起床的穿衣顺序如下图所示。穿衣的顺序也是有个优先级的有些衣服就必须优先穿上例如领带依赖于衬衣所以领带最终排在衬衣之后对图a中的元素进行合理的排序就得到了图b的次序图。注意该次序图不是唯一的。int topological_sort(LGraph G){ int num G.vexnum; ENode *node; int head 0; //辅助队列的头 int rear 0; // 辅助队列的尾 int *ins (int *)malloc(num * sizeof(int)); //入度数组 char *tops (char *)malloc(num * sizeof(char)); //拓扑排序结果数组记录每个节点排序后的序号 int *queue (int *)malloc(num * sizeof(int)); //辅助队列 assert(ins ! NULL tops ! NULL queue ! NULL) memset(ins, 0, num * sizeof(int)); memset(tops, 0, num * sizeof(char)); memset(queue, 0, num * sizeof(int)); for(int i 0; i ivex]; node node-next_edge; } } for(int i 0; i ivex]--; //将节点node关联的节点的入度减1 if(ins[node-ivex] 0) //若节点的入度为0则将其添加到队列中 queue[rear] node-ivex; node node-next_edge; } } if(index ! G.vexnum) { printf(“Graph has a cycle!”); free(queue); free(ins); free(tops); return 1; //1表示失败该有向图是有环的 } printf(“ TopSort: ”); //打印拓扑排序结果 for(int i 0; i 7. 最小生成树所谓最小生成树就是将图中的顶点全部连接起来此时这个边的权重最小并且连接起来的是一个无环的树。很容易知道若此时的顶点是n则边的数量为n-1。所以在一个图中找最小生成树就是找最小权值的边让这些边连成一棵树。常用的算法有Prim算法和Kruskal算法。7. 1Prim算法该算法就是每次迭代选择权值最小的边对应的点加入到最小生成树中。具体实现如下所示。第一步选取顶点A此时U{A}V-U{B,C,D,E,F,G}。第二步选取与A点连接的权值最小的边此时就会选择到BU{A,B}V-U{C,D,E,F,G}。以上面的步骤类推得到如上图所示的结果此时U{A,B,C,D,E,F}V-U{G}。注意到C是此次加入的点而G没有加入此时G点的边应该如何选择最终得到如图所示的最小生成树此时U{A,B,C,D,E,F,G}V-U{}。#define INF (~(0x131)) //最大值(即0X7FFFFFFF)//返回ch在邻接表中的位置static int get_position(LGraph G, char ch){ for(int i 0; i 的权值若start到end不连通则返回无穷大 int getWeight(LGraph G, int start, int end) { ENode *node; if(start end) return 0; node G.vexs[start].first_edge; while(node ! NULL) { if(end node-ivex) return node-weight; node node-next_edge; } return INF; } void Prim(LGraph G,int start) //从图中的第start个元素开始生成最小树 { int index 0; //prim最小树的索引即prims数组的索引 char prims[MAX]; //prim最小树的结果数组 int wights[MAX]; //顶点间边的权重 //prim最小生成树中第一个数即图中的第start个数 prims[index] G.vexs[start].data; for(int i 0; i 7.2 Kruskal算法该算法的核心就是对权值进行排序然后从最小的权值开始不断增大权值如何该权值的所在边的两个顶点没有存在的路径连在一起则加入这条边否则则舍弃这条边知道所有的点都在这颗树中。如下所示的一个图我们从中找出最小生成树。对于左边所示的图对各个边的权值排序之后我们最先找到权值最小的边即AD。然后我们发现还有一个CE于是CE也会被标记起来。对于左边所示的图对各个边的权值排序之后我们最先找到权值最小的边即AD。然后我们发现还有一个CE于是CE也会被标记起来。typedef struct edata //边的结构体{ char start; //边的起点 char end; //边的终点 int weight; //边的权重}EData;EData *get_edges(LGraph G){ int index 0; ENode *node; EData *edges; edges (EData *)malloc(G.edgnum * sizeof(EData)); for(int i 0; i ivex i) { edges[index].start G.vexs[i].data; edges[index].end G.vexs[node-ivex].data; edges[index].weight node-weight; index; } node node-next_edge; } } return edges;}void Kruskal(LGraph G){ int index 0; //rets数组的索引 int vends[MAX] {0}; //用于保存“已有最小生成树”中每个顶点在该最小树中的终点 EData rets[MAX]; //结果数组保存kruskal最小生成树的边 EData *edges; //图对应的所有边 edges get_edges(G); //获取图中所有的边 Sorted_edges(edges, G.edgenum); //对边按照权值进行排序 for(int i 0; i 例题分析785. 判断二分图给定一个无向图graph当这个图为二分图时返回true。如果我们能将一个图的节点集合分割成两个独立的子集A和B并使图中的每一条边的两个节点一个来自A集合一个来自B集合我们就将这个图称为二分图。graph将会以邻接表方式给出graph[i]表示图中与节点i相连的所有节点。每个节点都是一个在0到graph.length-1之间的整数。这图中没有自环和平行边graph[i] 中不存在i并且graph[i]中没有重复的值。示例 1:输入: [[1,3], [0,2], [1,3], [0,2]]输出: true解释:无向图如下:0----1| || |3----2我们可以将节点分成两组: {0, 2} 和 {1, 3}。示例 2:输入: [[1,2,3], [0,2], [0,1,3], [0,2]]输出: false解释:无向图如下:0----1| || |3----2我们不能将节点分割成两个独立的子集。好了, 自己研究了半天, 题都没有研究明白,我决定放弃了, 要是哪个大佬知道, 快来教教我吧, 我们今天把树是个什么东西就好了!graph 的长度范围为 [1, 100]。graph[i] 中的元素的范围为 [0, graph.length - 1]。graph[i] 不会包含 i 或者有重复的值。图是无向的: 如果j 在 graph[i]里边, 那么 i 也会在 graph[j]里边。
