客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
http://www.cnblogs.com/abatei/archive/2008/06/06/1215114.html8.2 图的存储结构图的存储结构除了要存储图中各个顶点的本身的信息外，同时还要存储顶点与顶点之间的所有关系（边的信息），因此，图的结构比较复杂，很难以数据元素在存储区中的物理位置来表示元素之间的关系，但也正是由于其任意的特性，故物理表示方法很多。常用的图的存储结构有邻接矩阵、邻接表、十字链表和邻接多重表。 8.2.1 邻接矩阵表示法对于一个具有n个顶点的图，可以使用n*n的矩阵（二维数组）来表示它们间的邻接关系。图8.10和图8.11中，矩阵A(i，j)=1表示图中存在一条边(Vi，Vj)，而A(i，j)=0表示图中不存在边(Vi，Vj)。实际编程时，当图为不带权图时，可以在二维数组中存放bool值，A(i，j)=true表示存在边(Vi，Vj)，A(i，j)=false表示不存在边(Vi，Vj)；当图带权值时，则可以直接在二维数组中存放权值，A(i，j)=null表示不存在边(Vi，Vj)。
图8.10所示的是无向图的邻接矩阵表示法，可以观察到，矩阵延对角线对称，即A(i，j)= A(j，i)。无向图邻接矩阵的第i行或第i列非零元素的个数其实就是第i个顶点的度。这表示无向图邻接矩阵存在一定的数据冗余。 图8.11所示的是有向图邻接矩阵表示法，矩阵并不延对角线对称，A(i，j)=1表示顶点Vi邻接到顶点Vj；A(j，i)=1则表示顶点Vi邻接自顶点Vj。两者并不象无向图邻接矩阵那样表示相同的意思。有向图邻接矩阵的第i行非零元素的个数其实就是第i个顶点的出度，而第i列非零元素的个数是第i个顶点的入度，即第i个顶点的度是第i行和第i列非零元素个数之和。 由于存在n个顶点的图需要n2个数组元素进行存储，当图为稀疏图时，使用邻接矩阵存储方法将出现大量零元素，照成极大地空间浪费，这时应该使用邻接表表示法存储图中的数据。 8.2.2 邻接表表示法图的邻接矩阵存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。邻接表由表头结点和表结点两部分组成，其中图中每个顶点均对应一个存储在数组中的表头结点。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。如图8.12所示，表结点存放的是邻接顶点在数组中的索引。对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。 有向图的邻接表有出边表和入边表（又称逆邻接表）之分。出边表的表结点存放的是从表头结点出发的有向边所指的尾顶点；入边表的表结点存放的则是指向表头结点的某个头顶点。如图8.13所示，图(b)和(c)分别为有向图(a)的出边表和入边表。 以上所讨论的邻接表所表示的都是不带权的图，如果要表示带权图，可以在表结点中增加一个存放权的字段，其效果如图8.14所示。 【注意】：观察图8.14可以发现，当删除存储表头结点的数组中的某一元素，有可能使部分表头结点索引号的改变，从而导致大面积修改表结点的情况发生。可以在表结点中直接存放指向表头结点的指针以解决这个问题（在链表中存放类实例即是存放指针，但必须要保证表头结点是类而不是结构体）。在实际创建邻接表时，甚至可以使用链表代替数组存放表头结点或使用顺序表存代替链表存放表结点。对所学的数据结构知识应当根据实际情况及所使用语言的特点灵活应用，切不可生搬硬套。 【例8-1 AdjacencyList.cs】图的邻接表存储结构 using System;
using System.Collections.Generic; public class AdjacencyList<T> { List<Vertex<T>> items; //图的顶点集合 public AdjacencyList() : this(10) { } //构造方法 public AdjacencyList(int capacity) //指定容量的构造方法 { items = new List<Vertex<T>>(capacity); } public void AddVertex(T item) //添加一个顶点 { //不允许插入重复值 if (Contains(item)) { throw new ArgumentException("插入了重复顶点！"); } items.Add(new Vertex<T>(item)); } public void AddEdge(T from, T to) //添加无向边 { Vertex<T> fromVer = Find(from); //找到起始顶点 if (fromVer == null) { throw new ArgumentException("头顶点并不存在！"); } Vertex<T> toVer = Find(to); //找到结束顶点 if (toVer == null) { throw new ArgumentException("尾顶点并不存在！"); } //无向边的两个顶点都需记录边信息 AddDirectedEdge(fromVer, toVer); AddDirectedEdge(toVer, fromVer); } public bool Contains(T item) //查找图中是否包含某项 { foreach (Vertex<T> v in items) { if (v.data.Equals(item)) { return true; } } return false; } private Vertex<T> Find(T item) //查找指定项并返回 { foreach (Vertex<T> v in items) { if (v.data.Equals(item)) { return v; } } return null; } //添加有向边 private void AddDirectedEdge(Vertex<T> fromVer, Vertex<T> toVer) { if (fromVer.firstEdge == null) //无邻接点时 { fromVer.firstEdge = new Node(toVer); } else { Node tmp, node = fromVer.firstEdge; do { //检查是否添加了重复边 if (node.adjvex.data.Equals(toVer.data)) { throw new ArgumentException("添加了重复的边！"); } tmp = node; node = node.next; } while (node != null); tmp.next = new Node(toVer); //添加到链表未尾 } } public override string ToString() //仅用于测试 { //打印每个节点和它的邻接点 string s = string.Empty; foreach (Vertex<T> v in items) { s += v.data.ToString() + ":"; if (v.firstEdge != null) { Node tmp = v.firstEdge; while (tmp != null) { s += tmp.adjvex.data.ToString(); tmp = tmp.next; } } s += "\r\n"; } return s; } //嵌套类，表示链表中的表结点 public class Node { public Vertex<T> adjvex; //邻接点域 public Node next; //下一个邻接点指针域 public Node(Vertex<T> value) { adjvex = value; } } //嵌套类，表示存放于数组中的表头结点 public class Vertex<TValue> { public TValue data; //数据 public Node firstEdge; //邻接点链表头指针 public Boolean visited; //访问标志,遍历时使用 public Vertex(TValue value) //构造方法 { data = value; } } } AdjacencyList<T>类使用泛型实现了图的邻接表存储结构。它包含两个内部类，Vertex<Tvalue>类（109～118行代码）用于表示一个表头结点，Node类（99～107）则用于表示表结点，其中存放着邻接点信息，用来表示表头结点的某条边。多个Node用next指针相连形成一个单链表，表头指针为Vertex类的firstEdge成员，表头结点所代表的顶点的所有边的信息均包含在链表内，其结构如图8.12所示。所不同之处在于： l Vertex类中包含了一个visited成员，它的作用是在图遍历时标识当前节点是否被访问过，这一点在稍后会讲到。 l 邻接点指针域adjvex直接指向某个表头结点，而不是表头结点在数组中的索引。 AdjacencyList<T>类中使用了一个泛型List代替数组来保存表头结点信息（第5行代码），从而不再考虑数组存储空间不够的情况发生，简化了操作。 由于一条无向边的信息需要在边的两个顶点分别存储信息，即添加两个有向边，所以58～78行代码的私有方法AddDirectedEdge()方法用于添加一个有向边。新的邻接点信息即可以添加到链表的头部也可以添加到尾部，添加到链表头部可以简化操作，但考虑到要检查是否添加了重复边，需要遍历整个链表，所以最终把邻接点信息添加到链表尾部。 【例8-1 Demo8-1.cs】图的邻接表存储结构测试 using System;
class Demo8_1 { static void Main(string[] args) { AdjacencyList<char> a = new AdjacencyList<char>(); //添加顶点 a.AddVertex('A'); a.AddVertex('B'); a.AddVertex('C'); a.AddVertex('D'); //添加边 a.AddEdge('A', 'B'); a.AddEdge('A', 'C'); a.AddEdge('A', 'D'); a.AddEdge('B', 'D'); Console.WriteLine(a.ToString()); } }
运行结果：
|
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
六六分期app的软件客服如何联系？不知道吗？加qq群【895510560】即可！标题：六六分期
今天小编告诉大家如何处理win10系统火狐flash插件总是崩溃的问题，可能很多用户都不知
今天小编告诉大家如何对win10系统删除桌面回收站图标进行设置，可能很多用户都不知道
今天小编告诉大家如何对win10系统电脑设置节能降温的设置方法，想必大家都遇到过需要
我们在使用xp系统的过程中,经常需要对xp系统无线网络安装向导设置进行设置，可能很多
今天小编告诉大家如何处理win7系统玩cf老是与主机连接不稳定的问题，可能很多用户都不
电脑对日常生活的重要性小编就不多说了，可是一旦碰到win7系统设置cf烟雾头的问题，很
我们在日常使用电脑的时候，有的小伙伴们可能在打开应用的时候会遇见提示应用程序无法
今天小编告诉大家如何对win7系统打开vcf文件进行设置，可能很多用户都不知道怎么对win
今天小编告诉大家如何对win10系统s4开启USB调试模式进行设置，可能很多用户都不知道怎
请发表评论