<![CDATA[阿巴睇的博客]]>

<![CDATA[阿巴睇的博客]]> http://cgbluesky.blog.163.com zh-CN Sun, 17 Aug 2008 00:16:50 +0800 Sun, 17 Aug 2008 00:16:50 +0800 http://blogs.law.harvard.edu/tech/rss 120 <![CDATA[阿巴睇的博客]]> http://cgbluesky.blog.163.com/style/common/user_default.gif http://cgbluesky.blog.163.com <![CDATA[C#与数据结构--图的遍历]]> http://cgbluesky.blog.163.com/blog/static/241235582008561245867

8.2 图的存储结构

图的存储结构除了要存储图中各个顶点的本身的信息外，同时还要存储顶点与顶点之间的所有关系（边的信息），因此，图的结构比较复杂，很难以数据元素在存储区中的物理位置来表示元素之间的关系，但也正是由于其任意的特性，故物理表示方法很多。常用的图的存储结构有邻接矩阵、邻接表、十字链表和邻接多重表。

8.2.1 邻接矩阵表示法

对于一个具有n个顶点的图，可以使用n*n的矩阵（二维数组）来表示它们间的邻接关系。图8.10和图8.11中，矩阵A(i，j)=1表示图中存在一条边(V_i，V_j)，而A(i，j)=0表示图中不存在边(V_i，V_j)。实际编程时，当图为不带权图时，可以在二维数组中存放bool值，A(i，j)=true表示存在边(V_i，V_j)，A(i，j)=false表示不存在边(V_i，V_j)；当图带权值时，则可以直接在二维数组中存放权值，A(i，j)=null表示不存在边(V_i，V_j)。

图8.10所示的是无向图的邻接矩阵表示法，可以观察到，矩阵延对角线对称，即A(i，j)= A(j，i)。无向图邻接矩阵的第i行或第i列非零元素的个数其实就是第i个顶点的度。这表示无向图邻接矩阵存在一定的数据冗余。

图8.11所示的是有向图邻接矩阵表示法，矩阵并不延对角线对称，A(i，j)=1表示顶点V_i邻接到顶点V_j；A(j，i)=1则表示顶点V_i邻接自顶点V_j。两者并不象无向图邻接矩阵那样表示相同的意思。有向图邻接矩阵的第i行非零元素的个数其实就是第i个顶点的出度，而第i列非零元素的个数是第i个顶点的入度，即第i个顶点的度是第i行和第i列非零元素个数之和。

由于存在n个顶点的图需要n²个数组元素进行存储，当图为稀疏图时，使用邻接矩阵存储方法将出现大量零元素，照成极大地空间浪费，这时应该使用邻接表表示法存储图中的数据。

8.2.2 邻接表表示法

图的邻接矩阵存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。邻接表由表头结点和表结点两部分组成，其中图中每个顶点均对应一个存储在数组中的表头结点。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。如图8.12所示，表结点存放的是邻接顶点在数组中的索引。对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。

有向图的邻接表有出边表和入边表（又称逆邻接表）之分。出边表的表结点存放的是从表头结点出发的有向边所指的尾顶点；入边表的表结点存放的则是指向表头结点的某个头顶点。如图8.13所示，图(b)和(c)分别为有向图(a)的出边表和入边表。

以上所讨论的邻接表所表示的都是不带权的图，如果要表示带权图，可以在表结点中增加一个存放权的字段，其效果如图8.14所示。

【注意】：观察图8.14可以发现，当删除存储表头结点的数组中的某一元素，有可能使部分表头结点索引号的改变，从而导致大面积修改表结点的情况发生。可以在表结点中直接存放指向表头结点的指针以解决这个问题（在链表中存放类实例即是存放指针，但必须要保证表头结点是类而不是结构体）。在实际创建邻接表时，甚至可以使用链表代替数组存放表头结点或使用顺序表存代替链表存放表结点。对所学的数据结构知识应当根据实际情况及所使用语言的特点灵活应用，切不可生搬硬套。

【例8-1 AdjacencyList.cs】图的邻接表存储结构

1 &65279;using System;

2 using System.Collections.Generic;

3 public class AdjacencyList<T>

4 {

5 List<Vertex<T>> items; //图的顶点集合

6 public AdjacencyList() : this(10) { } //构造方法

7 public AdjacencyList(int capacity) //指定容量的构造方法

8 {

9 items = new List<Vertex<T>>(capacity);

10 }

11 public void AddVertex(T item) //添加一个顶点

12 { //不允许插入重复值

13 if (Contains(item))

14 {

15 throw new ArgumentException("插入了重复顶点！");

16 }

17 items.Add(new Vertex<T>(item));

18 }

19 public void AddEdge(T from, T to) //添加无向边

20 {

21 Vertex<T> fromVer = Find(from); //找到起始顶点

22 if (fromVer == null)

23 {

24 throw new ArgumentException("头顶点并不存在！");

25 }

26 Vertex<T> toVer = Find(to); //找到结束顶点

27 if (toVer == null)

28 {

29 throw new ArgumentException("尾顶点并不存在！");

30 }

31 //无向边的两个顶点都需记录边信息

32 AddDirectedEdge(fromVer, toVer);

33 AddDirectedEdge(toVer, fromVer);

34 }

35 public bool Contains(T item) //查找图中是否包含某项

36 {

37 foreach (Vertex<T> v in items)

38 {

39 if (v.data.Equals(item))

40 {

41 return true;

42 }

43 }

44 return false;

45 }

46 private Vertex<T> Find(T item) //查找指定项并返回

47 {

48 foreach (Vertex<T> v in items)

49 {

50 if (v.data.Equals(item))

51 {

52 return v;

53 }

54 }

55 return null;

56 }

57 //添加有向边

58 private void AddDirectedEdge(Vertex<T> fromVer, Vertex<T> toVer)

59 {

60 if (fromVer.firstEdge == null) //无邻接点时

61 {

62 fromVer.firstEdge = new Node(toVer);

63 }

64 else

65 {

66 Node tmp, node = fromVer.firstEdge;

67 do

68 { //检查是否添加了重复边

69 if (node.adjvex.data.Equals(toVer.data))

70 {

71 throw new ArgumentException("添加了重复的边！");

72 }

73 tmp = node;

74 node = node.next;

75 } while (node != null);

76 tmp.next = new Node(toVer); //添加到链表未尾

77 }

78 }

79 public override string ToString() //仅用于测试

80 { //打印每个节点和它的邻接点

81 string s = string.Empty;

82 foreach (Vertex<T> v in items)

83 {

84 s += v.data.ToString() + ":";

85 if (v.firstEdge != null)

86 {

87 Node tmp = v.firstEdge;

88 while (tmp != null)

89 {

90 s += tmp.adjvex.data.ToString();

91 tmp = tmp.next;

92 }

93 }

94 s += "\r\n";

95 }

96 return s;

97 }

98 //嵌套类，表示链表中的表结点

99 public class Node

100 {

101 public Vertex<T> adjvex; //邻接点域

102 public Node next; //下一个邻接点指针域

103 public Node(Vertex<T> value)

104 {

105 adjvex = value;

106 }

107 }

108 //嵌套类，表示存放于数组中的表头结点

109 public class Vertex<TValue>

110 {

111 public TValue data; //数据

112 public Node firstEdge; //邻接点链表头指针

113 public Boolean visited; //访问标志,遍历时使用

114 public Vertex(TValue value) //构造方法

115 {

116 data = value;

117 }

118 }

119 }

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】图的邻接表存储结构测试

1 &65279;using System;

2 class Demo8_1

3 {

4 static void Main(string[] args)

5 {

6 AdjacencyList<char> a = new AdjacencyList<char>();

7 //添加顶点

8 a.AddVertex('A');

9 a.AddVertex('B');

10 a.AddVertex('C');

11 a.AddVertex('D');

12 //添加边

13 a.AddEdge('A', 'B');

14 a.AddEdge('A', 'C');

15 a.AddEdge('A', 'D');

16 a.AddEdge('B', 'D');

17 Console.WriteLine(a.ToString());

18 }

19 }

运行结果：

A：BCD

B：AD

C：A

D：AB

本例存储的表如图8.12所示，结果中，冒号前面的是表头结点，冒号后面的是链表中的表结点。

8.3 图的遍历

和树的遍历类似，在此，我们希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历(TraversingGraph)。如果只访问图的顶点而不关注边的信息，那么图的遍历十分简单，使用一个foreach语句遍历存放顶点信息的数组即可。但如果为了实现特定算法，就需要根据边的信息按照一定顺序进行遍历。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。

图的遍历要比树的遍历复杂得多，由于图的任一顶点都可能和其余顶点相邻接，故在访问了某顶点之后，可能顺着某条边又访问到了已访问过的顶点，因此，在图的遍历过程中，必须记下每个访问过的顶点，以免同一个顶点被访问多次。为此给顶点附设访问标志visited，其初值为false，一旦某个顶点被访问，则其visited标志置为true。

图的遍历方法有两种：一种是深度优先搜索遍历（Depth-First Search 简称DFS）；另一种是广度优先搜索遍历（Breadth_First Search 简称BFS）。

8.3.1 深度优先搜索遍历

图的深度优先搜索遍历类似于二叉树的深度优先搜索遍历。其基本思想如下：假定以图中某个顶点V_i为出发点，首先访问出发点，然后选择一个V_i的未访问过的邻接点V_j，以V_j为新的出发点继续进行深度优先搜索，直至图中所有顶点都被访问过。显然，这是一个递归的搜索过程。

现以图8.15为例说明深度优先搜索过程。假定V₁是出发点，首先访问V₁。因V₁有两个邻接点V₂、V₃均末被访问过，可以选择V₂作为新的出发点，访问V₂之后，再找V₂的末访问过的邻接点。同V₂邻接的有V₁、V₄和V₅，其中V₁已被访问过，而V₄、V₅尚未被访问过，可以选择V₄作为新的出发点。重复上述搜索过程，继续依次访问V₈、V₅ 。访问V₅之后，由于与V₅相邻的顶点均已被访问过，搜索退回到V₈，访问V₈的另一个邻接点V₆。接下来依次访问V₃和V₇，最后得到的的顶点的访问序列为：V₁ → V₂ → V₄ → V₈ → V₅ → V₆ → V₃ → V₇。

下面根据上一节创建的邻接表存储结构添加深度优先搜索遍历代码。

【例8-2 DFSTraverse.cs】深度优先搜索遍历

打开【例8-1 AdjacencyList.cs】，在AdjacencyList<T>类中添加以下代码后，将文件另存为DFSTraverse.cs。

35 public void DFSTraverse() //深度优先遍历

36 {

37 InitVisited(); //将visited标志全部置为false

38 DFS(items[0]); //从第一个顶点开始遍历

39 }

40 private void DFS(Vertex<T> v) //