加载中…
个人资料
whutgy
whutgy
  • 博客等级:
  • 博客积分:0
  • 博客访问:2,546
  • 关注人气:0
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

Chapter 13-1: Graphs-unweighted graphs

(2009-09-09 09:12:00)
标签:

杂谈

分类: DataStructures&Algorith笔记

(1)
  图是一种与树有些相像的数据结构。实际上,从数学意义上说,树是图的一种。然而,在计算机程序设计中,图的应用方式与树不同。

  The data structures examined previously in this book have an architecture dictated by the algorithms used on them. For example, a binary tree is shaped the way it is because that shape makes it easy to search for data and insert new data. The edges in a tree represent quick ways to get from node to node.

  Graphs, on the other hand, often have a shape dictated by a physical problem. For example, nodes in a graph may represent cities, while edges may represent airline flight routes between the cities. Another more abstract example is a graph representing the individual tasks necessary to complete a project. In the graph, nodes may represent tasks, while directed edges (with an arrow at one end) indicate which task must be completed before another. In both cases, the shape of the graph arises from the specific real-world situation.

Before going further, we must mention that, when discussing graphs, nodes are called vertices (the singular is vertex)(顶点). This is probably because the nomenclature for graphs is older than that for trees, having arisen in mathematics centuries ago. Trees are more closely associated with computer science.

 

邻接(Adjacency)
如果两个顶点被同一条边连接,就称这两个顶点是邻接的。
(Two vertices are said to be adjacent to one another if they are connected by a single edge.)

 

Paths
  A path is a sequence of edges. Figure 13.1 shows a path from vertex B to vertex J that passes through vertices A and E. We can call this path BAEJ. There can be more than one path between two vertices; another path from B to J is BCDJ.

 

Connected Graphs
  A graph is said to be connected if there is at least one path from every vertex to every other vertex.

 

  在非常抽象的图的问题中,只是简单地把顶点编号,从0到N-1(这里N是顶点数)。不需要任何变量类型存储顶点,因为它们的用处来自于它们之间的相互关系。

  然而在大多数情况下,顶点表示某个真实世界的对象,这个对象必须用数据项来描述。例如,如果在一个飞机航线模拟程序中,顶点代表城市,那么它需要存储城市名字、海拔高度、地理位置和其他相关信息。因此,通常用一个顶点类的对象来表示一个顶点。


  Our example programs store only a letter (like A), used as a label for identifying the vertex, and a flag for use in search algorithms, as we'll see later. Here's how the Vertex class looks:
 class Vertex
 {
  public char label; // label (e.g. 'A')
  public boolean wasVisited;
  public Vertex(char lab) // constructor
  {
   label = lab;
   wasVisited = false;
  }
 } // end class Vertex

 
  A graph, however, doesn't usually have the same kind of fixed organization as a tree. In a binary tree, each node has a maximum of two children, but in a graph each vertex may be connected to an arbitrary number of other vertices.
  To model this sort of free-form organization, a different approach to representing edges is preferable to that used for trees. Two methods are commonly used for graphs:the adjacency matrix and the adjacency list.
  图不像树,拥有几种固定的结构。二叉树中,每个节点最多有两个子节点,但图的每个顶点可以与任意多个顶点连接。为了模拟这种自由形式的组织结构,需要用一种不同的方法表示边,比树的表示方法更合适些。一般用两个方法表示图:即邻接矩阵和邻接表。

 

(2)
邻接矩阵(The Adjacency Matrix)
  邻接矩阵是一个二维数组,数据项表示两点间是否存在边。如果图有N个顶点,邻接矩阵就是N*N的数组。


  主对角线上的实体不代表任何真实世界的信息,所以为了方便,也可以把主对角线的值设为1.

  注意,这个矩形的上三角是下三角的镜像;两个三角包含了同样的信息。这个冗余信息看似低效,但在大多数计算机语言中,创造一个三角形数组比较困难,所以只好求其次接受这个冗余。这也要求当增加一条边时,必须更新邻接矩阵的两部分,而不是一部分。


(3)
邻接表(The Adjacency List)
  表示边的另一种方法是邻接表。邻接表中的表指的是第5章“链表”中讨论的那种链表。实际上,邻接表是一个链表数组(或者是链表的链表)。每个单独的链表表示了有哪些顶点与当前顶点领接。

 

(4)
向图中添加顶点和边
  为了向图中添加顶点,必须用new保留字生成一个新的顶点对象,然后插入到顶点数组vertexList中。

怎样添加边取决于用邻接矩阵还是用邻接表表示图。假定使用邻接矩阵并考虑在顶点1和顶点3之间加一条边。这些数字对应vertexList数组的下标,顶点存储在数组的对应位置。首次创建邻接矩阵adjMat时,初值为0.添加边的代码如下:
adjMat[1][3]=1;
adjMat[3][1]=1;
如果使用邻接表,就把1加到3的链表中,然后把3加到1的链表中。


  邻接矩阵(或者邻接表)提供了关于当前顶点的位置信息。特别是,当前顶点通过边与哪些顶点相连。为了回答关于顶点序列的更一般问题,就必须求助于其他的算法。

 

(5)
搜索
  在图中实现的最基本的操作之一就是搜索从一个指定顶点可以到达哪些顶点。
  还有另外一种情形可能需要找到所有当前顶点可到达的顶点。

  假设已经创建了这么一个图。现在需要一种算法来提供系统的方法,从某个特定的顶点开始,沿着边移动到其他顶点。移动完毕后,要保证访问了和起始点相连的每一个顶点。


  There are two common approaches to searching a graph: depth-first search (DFS) and breadth-first search (BFS). Both will eventually reach all connected vertices. The difference is that the depth-first search is implemented with a stack, whereas the breadthfirst search is implemented with a queue. These mechanisms result, as we'll see, in the graph being searched in different ways.
  有两种常用的方法可以用来搜索图:即深度优先搜索(DFS)和广度优先搜索(BFS)。它们最终都会到达所有连通的顶点。深度优先搜索通过栈来实现,而广度优先搜索通过队列实现。

 

(6)
深度优先搜索
  在搜索到尽头的时候,深度优先搜索用栈记住下一步的走向。
  为了实现深度优先搜索,找一个起始点——本例为顶点A。需要做三件事:首先访问该顶点,然后把该点放入栈中,以便记住它,最后标记该节点,这样就不会再访问它。

  下面可以访问任何与顶点A相连的顶点,只要还没有访问过它。假设顶点按字母顺序访问,所以下面访问顶点B。然后标记它,并放入栈中。

规则1. 如果可能,访问一个邻接的未访问顶点,标记它,并把它放入栈中。

规则2. 当不能执行规则1时,如果栈不空,就从栈中弹出一个顶点。

规则3. 如果不能执行规则1和规则2,就完成了整个搜索过程。

 

  深度优先搜索与迷宫问题类似。迷宫在英国很流行,可以由一方给另一方设置障碍,由另一方想办法通过。迷宫由狭窄的过道(认为是边)和过道的交汇点(顶点)组成。

 

  Suppose that someone is lost in the maze. She knows there's an exit and plans to traverse the maze systematically to find it. Fortunately, she has a ball of string and a marker pen. She starts at some intersection and goes down a randomly chosen passage, unreeling the string. At the next intersection, she goes down another randomly chosen passage, and so on, until finally she reaches a dead end.
  假设有个人在迷宫中迷路。她知道有一个出口,并且计划系统地搜索迷宫找到出口。幸运的是,她有一团线和一支笔。她从某个交汇点开始,任意选择一个通路,从线团上退下一些线。在下一个交汇点,她继续随机选择一条通路,再退下一些线,直到最后她到达死胡同。

 

  At the dead end she retraces her path, reeling in the string, until she reaches the previous intersection. Here she marks the path she's been down so she won't take it again, and tries another path. When she's marked all the paths leading from that intersection, she returns to the previous intersection and repeats the process.
  到达死胡同时,她按原路返回,在把线绕上,直到到达前一个交汇点。她标记了以前走过的路径,所以不会重复走那些通路,而选择未选择的通路。当她标记了这个交汇点的所有通路,就会再回到上一个交汇点,并且重复这个过程。

 

  The string represents the stack: It "remembers" the path taken to reach a certain point.
  线代表栈:它“记住”了走向某个特定点的路径。


  深度优先搜索的关键在于能够找到与某一顶点邻接且没有访问过的顶点。如何做呢?邻接矩阵是关键。找到指定顶点所在的行,从第一列开始向后寻找值为1的列:列号是邻接顶点的号码。检查这个顶点是否未访问过,如果是这样,那么这就是要访问的下一个顶点。如果该行没有顶点既等于1(领接)且又是未访问过的,那么与指定点相邻的顶点就全部访问过了。这个过程在getAdjUnvisitedVertex()方法中实现:

   // returns an unvisited vertex adj to v
   public int getAdjUnvisitedVertex(int v)
      {
      for(int j=0; j<nVerts; j++)
         if(adjMat[v][j]==1 && vertexList[j].wasVisited==false)
            return j;
      return -1;
      // end getAdjUnvisitedVertex()
  
  现在开始考察Graph类中的dfs()方法,这个方法实际执行了深度优先搜索。下面会看到这段代码如何包含了前面提出的三条规则。它循环执行,知道栈为空。每次循环中,它做四件事:
1. 用peek()方法检查栈顶的顶点.
2. 试图找到这个顶点还未访问的邻接点.
3. 如果没有找到,出栈。
4. 如果找到这样的顶点,访问这个顶点,并把它放入栈。

 

下面是dfs()方法及完整的代码:

  在dfs()方法的最后,重置了所有wasVisited标记位,这样就可以在稍后继续使用dfs()方法。栈此时已为空,所以不需要重置。

////////////////////////////////////////////////////////////////
class Vertex
   {
   public char label;        // label (e.g. 'A')
   public boolean wasVisited;
// ------------------------------------------------------------
   public Vertex(char lab)   // constructor
      {
      label = lab;
      wasVisited = false;
      }
// ------------------------------------------------------------
   // end class Vertex
////////////////////////////////////////////////////////////////
class Graph
   {
   private final int MAX_VERTS = 20;
   private Vertex vertexList[]; // list of vertices
   private int adjMat[][];      // adjacency matrix
   private int nVerts;          // current number of vertices
   private StackX theStack;
// ------------------------------------------------------------
   public Graph()               // constructor
      {
      vertexList = new Vertex[MAX_VERTS];
                                          // adjacency matrix
      adjMat = new int[MAX_VERTS][MAX_VERTS];
      nVerts = 0;
      for(int y=0; y<MAX_VERTS; y++)      // set adjacency
         for(int x=0; x<MAX_VERTS; x++)   //    matrix to 0
            adjMat[x][y] = 0;
      theStack = new StackX();
      // end constructor
// ------------------------------------------------------------
   public void addVertex(char lab)
      {
      vertexList[nVerts++] = new Vertex(lab);
      }
// ------------------------------------------------------------
   public void addEdge(int start, int end)
      {
      adjMat[start][end] = 1;
      adjMat[end][start] = 1;
      }
// ------------------------------------------------------------
   public void displayVertex(int v)
      {
      System.out.print(vertexList[v].label);
      }
// ------------------------------------------------------------
   public void dfs()  // depth-first search
                                     // begin at vertex 0
      vertexList[0].wasVisited = true;  // mark it
      displayVertex(0);                 // display it
      theStack.push(0);                 // push it

      while( !theStack.isEmpty() )      // until stack empty,
         {
         // get an unvisited vertex adjacent to stack top
         int v = getAdjUnvisitedVertex( theStack.peek() ); //peek()只是返回,不是弹出栈顶元素
         if(v == -1)                    // if no such vertex,
            theStack.pop();
         else                           // if it exists,
            {
            vertexList[v].wasVisited = true;  // mark it
            displayVertex(v);                 // display it,标记只标记一次,显示也只一次
            theStack.push(v);                 // push it
            }
         // end while

      // stack is empty, so we're done
      for(int j=0; j<nVerts; j++)          // reset flags
         vertexList[j].wasVisited = false;
      // end dfs
// ------------------------------------------------------------
   // returns an unvisited vertex adj to v
   public int getAdjUnvisitedVertex(int v)
      {
      for(int j=0; j<nVerts; j++)
         if(adjMat[v][j]==1 && vertexList[j].wasVisited==false)
            return j;
      return -1;
      // end getAdjUnvisitedVertex()
// ------------------------------------------------------------
   // end class Graph
  
(7)
广度优先搜索
  正如深度优先搜索中看到的,算法表现得好像要尽快地远离起始点似的。相反,在广度优先搜索中,算法好像要尽可能地靠近起始点。它首先访问起始顶点的所有邻接点,然后再访问较远的区域。这种搜索不能用栈,而要用队列来实现。

  A是起始点,所以访问它,并标记为当前顶点。然后应用下面几条规则:
规则1. 访问下一个未来访问的节点(如果存在),这个顶点必须是当前顶点的邻接点,标记它,并把它插入到队列中。

规则2. 如果因为已经没有未访问顶点而不能执行规则1,那么从队列头取一个顶点(如果存在),并使其成为当前顶点。

规则3. 如果因为队列为空而不能执行规则2,则搜索结束。

 

  At each moment, the queue contains the vertices that have been visited but whose neighbors have not yet been fully explored. (Contrast this with the depth-first search, where the contents of the stack is the route you took from the starting point to the current vertex.)
  在每一时刻,队列所包含的顶点时那些本身已经被访问,而它的邻居还有未访问的顶点。(对比深度优先搜索,栈的内容是起始点到当前顶点经过的所有顶点。)

  Graph类的bfs()方法和dfs()方法类似,只是用队列代替了栈,嵌套的循环代替了单层循环。外层循环等待队列为空,而内层循环依次寻找当前顶点的未访问邻接点。

  广度优先搜索有一个有趣的属性:它首先找到与起始点相距一条边的所有顶点,然后是与起始点相距两条边的顶点,依次类推。如果要寻找起始顶点到指定顶点的最短距离,那么这个属性非常有用。首先执行BFS,当找到指定顶点时,就可以说这条路径是到这个顶点的最短路径。如果有更短的路径,BFS算法就应该已经找到过它了。

class Queue
   {
   private final int SIZE = 20;
   private int[] queArray;
   private int front;
   private int rear;
// -------------------------------------------------------------
   public Queue()            // constructor
      {
      queArray = new int[SIZE];
      front = 0;
      rear = -1;
      }
// -------------------------------------------------------------
   public void insert(int j) // put item at rear of queue
      {
      if(rear == SIZE-1)
         rear = -1;
      queArray[++rear] = j;
      }
// -------------------------------------------------------------
   public int remove()       // take item from front of queue
      {
      int temp = queArray[front++];
      if(front == SIZE)
         front = 0;
      return temp;
      }
// -------------------------------------------------------------
   public boolean isEmpty()  // true if queue is empty
      {
      return ( rear+1==front || (front+SIZE-1==rear) );
      }
// -------------------------------------------------------------
   // end class Queue
////////////////////////////////////////////////////////////////
class Vertex
   {
   public char label;        // label (e.g. 'A')
   public boolean wasVisited;
// -------------------------------------------------------------
   public Vertex(char lab)   // constructor
      {
      label = lab;
      wasVisited = false;
      }
// -------------------------------------------------------------
   // end class Vertex
////////////////////////////////////////////////////////////////
class Graph
   {
   private final int MAX_VERTS = 20;
   private Vertex vertexList[]; // list of vertices
   private int adjMat[][];      // adjacency matrix
   private int nVerts;          // current number of vertices
   private Queue theQueue;
// ------------------------------------------------------------
   public Graph()               // constructor
      {
      vertexList = new Vertex[MAX_VERTS];
                                          // adjacency matrix
      adjMat = new int[MAX_VERTS][MAX_VERTS];
      nVerts = 0;
      for(int j=0; j<MAX_VERTS; j++)      // set adjacency
         for(int k=0; k<MAX_VERTS; k++)   //    matrix to 0
            adjMat[j][k] = 0;
      theQueue = new Queue();
      // end constructor
// -------------------------------------------------------------
   public void addVertex(char lab)
      {
      vertexList[nVerts++] = new Vertex(lab);
      }
// -------------------------------------------------------------
   public void addEdge(int start, int end)
      {
      adjMat[start][end] = 1;
      adjMat[end][start] = 1;
      }
// -------------------------------------------------------------
   public void displayVertex(int v)
      {
      System.out.print(vertexList[v].label);
      }
// -------------------------------------------------------------
   public void bfs()                   // breadth-first search
                                    // begin at vertex 0
      vertexList[0].wasVisited = true; // mark it
      displayVertex(0);                // display it
      theQueue.insert(0);              // insert at tail
      int v2;

      while( !theQueue.isEmpty() )     // until queue empty,
         {
         int v1 = theQueue.remove();   // remove vertex at head
         // until it has no unvisited neighbors
         while( (v2=getAdjUnvisitedVertex(v1)) != -1 )
                                            // get one,
            vertexList[v2].wasVisited = true;  // mark it
            displayVertex(v2);                 // display it
            theQueue.insert(v2);               // insert it
             // end while
         // end while(queue not empty)

      // queue is empty, so we're done
      for(int j=0; j<nVerts; j++)             // reset flags
         vertexList[j].wasVisited = false;
      // end bfs()
// -------------------------------------------------------------
   // returns an unvisited vertex adj to v
   public int getAdjUnvisitedVertex(int v)
      {
      for(int j=0; j<nVerts; j++)
         if(adjMat[v][j]==1 && vertexList[j].wasVisited==false)
            return j;
      return -1;
      // end getAdjUnvisitedVertex()
// -------------------------------------------------------------
   // end class Graph
////////////////////////////////////////////////////////////////

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有