网站设计主流尺寸,wordpress 微博小工具,个人网站免费服务器,简洁企业网站源码目录
图的基本概念#xff1a;
图的存储结构
邻接矩阵#xff08;GraphByMatrix#xff09;#xff1a;
基本参数#xff1a;
初始化#xff1a;
获取顶点元素在其数组中的下标 #xff1a;
添加边和权重#xff1a;
获取顶点的度#xff1a;
打印图#xf…目录
图的基本概念
图的存储结构
邻接矩阵GraphByMatrix
基本参数
初始化
获取顶点元素在其数组中的下标
添加边和权重
获取顶点的度
打印图
邻接表GraphByNode
基本参数
注意
初始化
获取顶点元素在其数组中的下标
添加边和权重
获取顶点的度
打印图
结语 图的基本概念
图是由顶点集合及顶点间的关系组成的一种数据结构G (V E)。 其中 1顶点集合V {x|x属于某个数据对象集}是有穷非空集合。 2E {(x,y)|x,y属于V}或者E {|x,y属于V Path(x, y)}是顶点间关系的有穷集合也叫做边的集合。 3(x, y)表示x到y的一条双向通路即(x, y)是无方向的Path表示从x到y的一条单向通路即Path 是有方向的。 顶点和边
图中结点称为顶点第i个顶点记作vi。两个顶点vi和vj相关联称作顶点vi和顶点vj之间有一条边 图中的第k条边记作ekek (vivj)或。
有向图和无向图
在有向图中顶点对是有序的顶点对称为顶点x到顶点y的一条边(弧)和是两条不同的边比如下图G3和G4为有向图。在无向图中顶点对(x, y)是无序的顶点对(x,y) 称为顶点x和顶点y相关联的一条边这条边没有特定方向(x, y)和(yx)是同一条边比如下图G1和G2为 无向图。注意无向边(x, y)等于有向边和。
例如下图G1和G2位无向图G3和G4为有向图。 完全图
在有n个顶点的无向图中若有n * (n-1)/2条边即任意两个顶点之间有且仅有一条边则称此图为 无向完全图比如上图G1在n个顶点的有向图中若有n * (n-1)条边即任意两个顶点之间有且仅有方向 相反的边则称此图为有向完全图比如上图G4。
顶点的度
顶点v的度是指与它相关联的边的条数记作deg(v)。在有向图中顶点的度等于该顶点的入度与 出度之和其中顶点v的入度是以v为终点的有向边的条数记作indev(v);顶点v的出度是以v为起始点的有向 边的条数记作outdev(v)。因此dev(v) indev(v) outdev(v)。注意对于无向图顶点的度等于该顶 点的入度和出度即dev(v) indev(v) outdev(v)。
路径
在图G (V E)中若从顶点vi出发有一组边使其可到达顶点vj则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径。
路径长度
对于不带权的图一条路径的路径长度是指该路径上的边的条数对于带权的图一条路径的路 径长度是指该路径上各个边权值的总和。 简单路径与回路
若路径上各顶点v1v2v3…vm均不重复则称这样的路径为简单路径。若路 径上 第一个顶点v1和最后一个顶点vm重合则称这样的路径为回路或环。例如下图 子图
设图G {V, E}和图G1 {V1E1}若V1属于V且E1属于E则称G1是G的子图。如下图 连通图
在无向图中若从顶点v1到顶点v2有路径则称顶点v1与顶点v2是连通的。如果图中任意一 对顶点 都是连通的则称此图为连通图。
强连通图
在有向图中若在每一对顶点vi和vj之间都存在一条从vi到vj的路径也存在一条从vj到 vi的路 径则称此图是强连通图。
生成树
一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条 边。
图的存储结构
因为图中既有节点又有边(节点与节点之间的关系)因此在图的存储中只需要保存节点和边关系即可。故图的存储结构有两种。1.邻接矩阵 2.邻接表。其中最常用的是邻接矩阵。
邻接矩阵GraphByMatrix
因为节点与节点之间的关系就是连通与否即为0或者1因此邻接矩阵(二维数组)即是先用一个数组将定 点保存然后采用矩阵来表示节点与节点之间的关系。 注意
1. 无向图的邻接矩阵是对称的第i行(列)元素之和就是顶点i的度。有向图的邻接矩阵则不一定是对称的第i行(列)元素之后就是顶点i 的出(入)度。
2. 如果边带有权值并且两个节点之间是连通的上图中的边的关系就用权值代替如果两个顶点不通则使用无穷大代替。
如下图 3. 用邻接矩阵存储图的优点是能够快速知道两个顶点是否连通缺陷是如果顶点比较多边比较少时矩 阵中存储了大量的0成为系数矩阵比较浪费空间并且要求两个节点之间的路径不是很好求。
实现GraphByMatrix类arrayv用来存放顶点matrix来存放边isDirect用来判断图是否是有向图。根据上面给出的注意2要用fill将数组初始化为无穷大。
基本参数
public class GraphByMatrix {private char[] arrayV;//存放顶点·private int[][] matrix;//存放边private boolean isDirect;//是否是有向图public GraphByMatrix(int size,boolean isDirect){arrayV new char[size];matrix new int[size][size];for(int i 0;i size;i){Arrays.fill(matrix[i],Integer.MAX_VALUE);}this.isDirect isDirect;}
}
初始化
初始化arrayV顶点数组。
public void initArrayV(char[] array){for(int i 0;i array.length;i){arrayV[i] array[i];}}
获取顶点元素在其数组中的下标
public int getIndexOfV(char v){for(int i 0;i arrayV.length;i){if(v arrayV[i]){return i;}}return -1;}
添加边和权重
先查找出两个顶点在顶点数组中的位置特别注意无向图的话两边都要设置,因为有向图每条边都是单独的。
public void addEdge(char v1,char v2,int weight){int index1 getIndexOfV(v1);int index2 getIndexOfV(v2);matrix[index1][index2] weight;if(!isDirect){matrix[index2][index1] weight;}}
效果如下
这是一个无向图将边的关系抽象为二维数组其中2^31-1为未赋予权重。 获取顶点的度 1、现在顶点数组 arrayV 中找到顶点的下标。 2、无向图只需要计算出度就好了。 3、如果是有向图有向图的度 入度 出度。 4、此时的count中存储的就是顶点V的度。 第二个for循环是沿着y轴遍历。
public int getDevOfV(char v){int indexV getIndexOfV(v);int count 0;for(int i 0;i arrayV.length;i){if(matrix[indexV][i] ! Integer.MAX_VALUE){count;}}if(isDirect){for(int i 0;i arrayV.length;i){if(matrix[i][indexV] ! Integer.MAX_VALUE){count;}}}return count;}
测试如下
我们add了A的两条边故打印2. 打印图
为了使打印效果更好我们将2^31-1打印为无穷大。
public void printGraph(){for(int i 0;i arrayV.length;i){System.out.print(arrayV[i] );}System.out.println();for(int i 0;i matrix.length;i){for(int j 0;j matrix[i].length;j){if(matrix[i][j] Integer.MAX_VALUE) {System.out.print(∞ );}else {System.out.print(matrix[i][j] );}}System.out.println();}}
效果如下 邻接表GraphByNode
邻接表使用数组表示顶点的集合使用链表表示边的关系。
1. 无向图邻接表存储 注意无向图中同一条边在邻接表中出现了两次。如果想知道顶点vi的度只需要知道顶点vi边链表集 合中结点的数目即可。
2.有向图邻接表存储 注意有向图中每条边在邻接表中只出现一次与顶点vi对应的邻接表所含结点的个数就是该顶点的出度也称出度表要得到vi顶点的入度必须检测其他所有顶点对应的边链表看有多少边顶点的dst取值是i。
基本参数
需要设置一个静态内部类Node结点结点要能存储起始终点权重和下一结点的数据。运用数组加链表的存储方式。
public class GraphByNode {static class Node{public int src;//起始下标public int dest;//重点下标public int weight;//权重public Node next;public Node(int src,int dest,int weight){this.src src;this.dest dest;this.weight weight;}}private ArrayListNode edgeList;private char[] arrayV;//存放顶点private boolean isDirect;//是否是有向图public GraphByNode(int size,boolean isDirect){arrayV new char[size];edgeList new ArrayList(size);for(int i 0;i size;i){edgeList.add(null);}this.isDirect isDirect;}
}
注意
new ArrayList(size)里面直接加参数是不能初始化list大小的例如 我们可以看到size的大小为0这样在进行操作时就会报错。
解决方法如下 这样就成功解决了。
初始化
public void initArrayV(char[] array){for(int i 0;i array.length;i){arrayV[i] array[i];}}
获取顶点元素在其数组中的下标
public int getIndexOfV(char v){for(int i 0;i arrayV.length;i){if(arrayV[i] v){return i;}}return -1;}
添加边和权重
为了使代码更加整洁在addEdge里面再调用addEdgeChild方法。注意区分有向图和无向图的区别如果要添加的边已经再链表里了直接return退出添加失败而不是大多数的覆盖用头插法插入数据。
public void addEdge(char v1,char v2,int weight){int src getIndexOfV(v1);int dest getIndexOfV(v2);addEdgeChild(src,dest,weight);if(!isDirect){addEdgeChild(dest,src,weight);}}private void addEdgeChild(int src,int dest,int weight){Node cur edgeList.get(src);while(cur ! null){if(cur.dest dest){return;}cur cur.next;}//头插法Node node new Node(src,dest,weight);node.next edgeList.get(src);edgeList.set(src,node);}
效果如下 获取顶点的度 1、现在顶点数组 arrayV 中找到顶点的下标。 2、如果是无向图只需要遍历链表的节点个数。 3、如果是有向图必须检测其他所有顶点对应的边链表看有多少边顶点的dst取值是i //有向图也就一张表。 使用continue来跳过当前自己的顶点链表防止有重复。
public int getDevOfV(char v){int indexV getIndexOfV(v);int count 0;Node cur edgeList.get(indexV);while(cur ! null){count;cur cur.next;}if(isDirect){int dest indexV;for(int src 0;src arrayV.length;src){if(src dest){continue;}else{Node pCur edgeList.get(src);while(pCur ! null){if(pCur.dest dest){count;}pCur pCur.next;}}}}return count;}
效果如下 打印图 public void printGraph(){for(int i 0;i arrayV.length;i){System.out.print(arrayV[i] -);Node cur edgeList.get(i);while(cur ! null){System.out.print(cur.dest -);cur cur.next;}System.out.println(null);}}
效果如下 结语
其实写博客不仅仅是为了教大家同时这也有利于我巩固自己的知识点和一个学习的总结由于作者水平有限对文章有任何问题的还请指出接受大家的批评让我改进如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注这可以激励我写出更加优秀的文章。
