什么是图的负权 – PingCode |
您所在的位置：网站首页 › 什么是负权回路 › 什么是图的负权 – PingCode |
什么是图的负权 – PingCode
|
图的负权（Negative Weight）是指图中存在一些边的权重为负数。一般情况下，人们认为图中边的权重是正数，实际上，在图论中，图中边的权重的范围是实数，因此，图中边的权重也可以为负数。通常，图的负权会对一些问题、算法产生影响。 
一、什么是图的负权
图的负权（Negative Weight）是指图中存在一些边的权重为负数。一般情况下，人们认为图中边的权重是正数，实际上，在图论中，图中边的权重的范围是实数，因此，图中边的权重也可以为负数。通常，图的负权会对一些问题、算法产生影响。 例如，假设我们需要在一个城市的街道网络上规划一条最短路径从A地到达B地，在该城市的街道网络示意图中，边上的数字表示该街道的长度。但是，由于工程施工的原因，有一条街道的长度为负数(-4)，如果我们使用Dijkstra算法来找到从A到B的最短路径，算法将会产生错误的结果，因为它不能处理带有负权的图。但是，如果我们使用Bellman-Ford算法，它可以正确地找到从A到B的最短路径，并考虑到AB路段的负权值。 二、什么是图图是一种比线性表和树更复杂的数据结构，在图中，结点之间的关系是任意的，任意两个数据元素之间都可能相关。图是一种多对多的数据结构。 1、基本概念图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。 注意：线性表中可以没有元素，称为空表。树中可以没有结点，叫做空树。但是在图中不允许没有顶点，可以没有边。 基本术语： 无向边：若顶点Vi和Vj之间的边没有方向，称这条边为无向边（Edge），用（Vi，Vj）来表示。 无向图（Undirected graphs）：图中任意两个顶点的边都是无向边。 有向边：若从顶点Vi到Vj的边有方向，称这条边为有向边，也称为弧（Arc），用来表示，其中Vi称为弧尾（Tail），Vj称为弧头（Head）。 有向图（Directed graphs）：图中任意两个顶点的边都是有向边。 简单图：不存在自环（顶点到其自身的边）和重边（完全相同的边）的图。 无向完全图：无向图中，任意两个顶点之间都存在边。 有向完全图：有向图中，任意两个顶点之间都存在方向相反的两条弧。 稀疏图：有很少条边或弧的图称为稀疏图，反之称为稠密图。 权（Weight）：表示从图中一个顶点到另一个顶点的距离或耗费。 网：带有权重的图。 度：与特定顶点相连接的边数。 出度、入度：有向图中的概念，出度表示以此顶点为起点的边的数目，入度表示以此顶点为终点的边的数目。 环：名列前茅个顶点和最后一个顶点相同的路径。 简单环：除去名列前茅个顶点和最后一个顶点后没有重复顶点的环。 连通图：任意两个顶点都相互连通的图。 极大连通子图：包含竟可能多的顶点（必须是连通的），即找不到另外一个顶点，使得此顶点能够连接到此极大连通子图的任意一个顶点。 连通分量：极大连通子图的数量。 强连通图：此为有向图的概念，表示任意两个顶点a，b，使得a能够连接到b，b也能连接到a 的图。 生成树：n个顶点，n-1条边，并且保证n个顶点相互连通（不存在环）。 最小生成树：此生成树的边的权重之和是所有生成树中最小的。 AOV网（Activity On Vertex Network）：在有向图中若以顶点表示活动，有向边表示活动之间的先后关系。 AOE网（Activity On Edge Network）：在带权有向图中若以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间。 2、图的存储结构由于图的结构比较复杂，任意两个顶点之间都可能存在关系，因此用简单的顺序存储来表示图是不可能，而若使用多重链表的方式（即一个数据域多个指针域的结点来表示），这将会出现严重的空间浪费或操作不便。这里总结一下常用的表示图的方法： 邻接矩阵 图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称邻接矩阵）存储图中的边或弧的信息。 代码： /** * 有向图的邻接矩阵实现 */ public class Digraph { private int vertexsNum; private int edgesNum; private int[][] arc; public Digraph(int[][] data, int vertexsNum) { this.vertexsNum = vertexsNum; this.edgesNum = data.length; arc = new int[vertexsNum][vertexsNum]; for (int i = 0; i < vertexsNum; i++) { for (int j = 0; j < vertexsNum; j++) { arc[i][j] = Integer.MAX_VALUE; } } for (int i = 0; i < data.length; i++) { int tail = data[i][0]; int head = data[i][1]; arc[tail][head] = 1; } } //用于测试，返回一个顶点的邻接点 public Iterable adj(int vertex) { Set set = new HashSet(); for (int i = 0; i < vertexsNum; i++) { if (arc[vertex][i] != Integer.MAX_VALUE) set.add(i); } return set; } public static void main(String[] args) { int[][] data = { {0,3}, {1,0}, {1,2}, {2,0}, {2,1}, }; Digraph wd = new Digraph(data,4); for(int i :wd.adj(1)) { System.out.println(i); } } }优缺点： 优点：结构简单，操作方便。 缺点：对于稀疏图，这种实现方式将浪费大量的空间。邻接表 邻接表是一种将数组与链表相结合的存储方法。其具体实现为：将图中顶点用一个一维数组存储，每个顶点Vi的所有邻接点用一个单链表来存储。这种方式和树结构中孩子表示法一样。 代码： /** * 有向图的邻接表实现 * */ public class AdjListDigraph { private class EdgeNode { int index; EdgeNode next; EdgeNode(int index, EdgeNode next){ this.index = index; this.next = next; } } private class VertexNode { int id; EdgeNode headNode; } private VertexNode[] vertexs; private int vertexsNum; private int edgesNum; public AdjListDigraph(int[][] data, int vertexsNum) { this.vertexsNum = vertexsNum; this.edgesNum = data.length; vertexs = new VertexNode[vertexsNum]; for (int i = 0; i < vertexs.length; i++) { vertexs[i] = new VertexNode(); vertexs[i].id = i; // } for (int i = 0; i < data.length; i++) { int index = data[i][1]; EdgeNode next = vertexs[data[i][0]].headNode; EdgeNode eNode = new EdgeNode(index,next); vertexs[data[i][0]].headNode = eNode; //头插法 } } //用于测试，返回一个顶点的邻接点 public Iterable adj(int index) { Set set = new HashSet(); EdgeNode current = vertexs[index].headNode; while(current != null) { VertexNode node = vertexs[current.index]; set.add(node.id); current = current.next; } return set; } public static void main(String[] args) { int[][] data = { {0,3}, {1,0}, {1,2}, {2,0}, {2,1}, }; AdjListDigraph ald = new AdjListDigraph(data,4); for(int i :ald.adj(1)) { System.out.println(i); } } }本算法的时间复杂度为 O(N + E)，其中N、E分别为顶点数和边数，邻接表实现比较适合表示稀疏图。 十字链表 十字链表（Orthogonal List)是将邻接表和逆邻接表相结合的存储方法，它解决了邻接表（或逆邻接表）的缺陷，即求入度（或出度）时必须遍历整个图。 代码： /** * 有向图的十字链表实现 * */ public class OrthogonalList { private class EdgeNode { int tailVex; int headVex; EdgeNode headNext; EdgeNode tailNext; public EdgeNode(int tailVex, int headVex, EdgeNode headNext, EdgeNode tailNext) { super(); this.tailVex = tailVex; this.headVex = headVex; this.headNext = headNext; this.tailNext = tailNext; } } private class VertexNode { int data; EdgeNode firstIn; EdgeNode firstOut; } private VertexNode[] vertexs; private int vertexsNum; private int edgesNum; public OrthogonalList(int[][] data, int vertexsNum) { this.vertexsNum = vertexsNum; this.edgesNum = data.length; vertexs = new VertexNode[vertexsNum]; for (int i = 0; i < vertexs.length; i++) { vertexs[i] = new VertexNode(); vertexs[i].data = i; // } //关键 for (int i = 0; i < data.length; i++) { int tail = data[i][0]; int head = data[i][1]; EdgeNode out = vertexs[tail].firstOut; EdgeNode in = vertexs[head].firstIn; EdgeNode eNode = new EdgeNode(tail,head,in,out); vertexs[tail].firstOut = eNode; vertexs[head].firstIn = eNode; } } //返回一个顶点的出度 public int outDegree(int index) { int result = 0; EdgeNode current = vertexs[index].firstOut; while(current != null) { current = current.tailNext; result++; } return result; } //返回一个顶点的入度 public int inDegree(int index) { int result = 0; EdgeNode current = vertexs[index].firstIn; while(current != null) { current = current.headNext; result++; } return result; } public static void main(String[] args) { int[][] data = { {0,3}, {1,0}, {1,2}, {2,0}, {2,1}, }; OrthogonalList orth = new OrthogonalList(data,4); System.out.println("顶点1的出度为" + orth.outDegree(1)); System.out.println("顶点1的入度为" + orth.inDegree(1)); } }十字链表创建图算法的时间复杂度和邻接表相同都为O(N + E)。在有图的应用中推荐使用。 延伸阅读1：图的遍历方法有哪些 深度优先遍历：深度优先遍历（Depth First Search，简称DFS），也成为深度优先搜索。 广度优先遍历：广度优先遍历（Breadth First Search，简称BFS），又称为广度优先搜索。 |
【本文地址】
今日新闻 |
推荐新闻 |