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

Chapter 13-2: Graphs-unweighted graphs

(2009-09-09 10:45:37)
标签:

杂谈

分类: DataStructures&Algorith笔记

(1)
最小生成树(MST)(Minimum Spanning Trees)
执行这种算法的结果就是产生了一个图,它用最少的边连接了所有的顶点。
(The result would be a graph with the minimum number of edges necessary to connect the vertices.)

 

对给定的一组顶点,可能有很多种最小生成树。最小生成树边E的数量总比顶点V的数量小1: E=V-1

Remember that we're not worried here about the length of the edges. We're not trying to find a minimum physical length, just the minimum number of edges. (This will change when we talk about weighted graphs in the next chapter.)

 

创建最小生成树的算法与搜索的算法几乎是相同的。它同样可以基于广度优先搜索或深度优先搜索。

 

It turns out that by executing the depth-first search and recording the edges you've traveled to make the search, you automatically create a minimum spanning tree. The only difference between the minimum spanning tree method mst(), which we'll see in a moment, and the depth-first search method dfs(), which we saw earlier, is that mst() must somehow record the edges traveled.
  在执行深度优先搜索过程中,记录走过的边,就可以创建一棵最小生成树,这可能会使人感到有些奇怪。下面要看到的最小生成树算法mst()和前面看到的深度优先搜索算法dfs()之间的唯一区别就是mst()方法必须记录走过的边。

  正如刚才看到的,这段代码与dfs()方法非常类似。然而,在else语句中,当前顶点与它下一个未访问邻接点被显示。这两个顶点决定了一条边,沿着这条边,算法将要访问下一个新的顶点。所有这样的边就组成了最小生成树。

  最小生成树比较容易从深度优先搜索得到,这是因为DFS访问所有顶点,但只访问一次。它绝不会再次访问同一个顶点。当它看到某条边将到达一个已访问的顶点,它就不会走这条边。它从来不遍历那些不可能的边。因此,DFS算法走过整个图的路径必定是最小生成树。

   public void mst()  // minimum spanning tree (depth first)
                                      // start at 0
      vertexList[0].wasVisited = true;   // mark it
      theStack.push(0);                  // push it

      while( !theStack.isEmpty() )       // until stack empty
                                      // get stack top
         int currentVertex = theStack.peek();
         // get next unvisited neighbor
         int v = getAdjUnvisitedVertex(currentVertex);
         if(v == -1)                     // if no more neighbors
            theStack.pop();              //    pop it away
         else                            // got a neighbor
            {
            vertexList[v].wasVisited = true;  // mark it
            theStack.push(v);                 // push it
                                         // display edge
            displayVertex(currentVertex);     // from currentV
            displayVertex(v);                 // to v
            System.out.print(" ");
            }
         // end while(stack not empty)

         // stack is empty, so we're done
         for(int j=0; j<nVerts; j++)          // reset flags
            vertexList[j].wasVisited = false;
      // end mst()
  

(2)
有向图的拓扑排序(Topological Sorting with Directed Graphs)

  Topological sorting is another operation that can be modeled with graphs. It's useful in situations in which items or events must be arranged in a specific order.
  拓扑排序是可以用图模拟的另一种操作。它可用于表示一种情况,即某些项目或事件必须按特定的顺序排列或发生。

  在程序中,有向图和无向图的区别是有向图的边在邻接矩阵中只有一项。

 

  1代表一条边。行标表示边从哪里开始,列标表示边到哪里结束。因此,行A列B的值为1表示从A到B的边。如果边的方向是相反的,即从B到A,那么行B列A的值就是1.

  对于前面讨论的无向图,邻接矩阵的上下三角是对称的,所以一半的信息是冗余的。而有向图的邻接矩阵中所有行列值都包含必要的信息。它的上下三角不是对称的。

  对于有向图,增加边的方法只需要一条语句,
   public void addEdge(int start, int end) //directed graph
      {
      adjMat[start][end] = 1;
      }
 而在无向图中要两条语句。
  
(3)
拓扑排序

  Topological sorting can model other situations besides course prerequisites. Job scheduling is an important example. If you're building a car, you want to arrange things so that brakes are installed before the wheels and the engine is assembled before it's bolted onto the chassis. Car manufacturers use graphs to model the thousands of operations in the manufacturing process, to ensure that everything is done in the proper order.

  除了课程优先关系以外,拓扑排序还可以对其他情况进行建模。工作进度是一个重要的例子。

  用图对工作进度建模叫做关键路径分析。尽管这里没有提到带权图,但是会用到它。

  Modeling job schedules with graphs is called critical path analysis. Although we don't show it here, a weighted graph (discussed in the next chapter) can be used, which allows the graph to include the time necessary to complete different tasks in a project. The graph can then tell you such things as the minimum time necessary to complete the project.

 

  拓扑排序算法的思想虽然不寻常但是很简单,有两个步骤是必需的:
步骤1:找到一个没有后继的顶点。
步骤2:从图中删除这个顶点,在列表的前面插入顶点的标记。

重复步骤1和步骤2,直到所有顶点都从图中删除。这时,列表显示的顶点顺序就是拓扑排序的结果。


  The algorithm works because if a vertex has no successors, it must be the last one in the topological ordering. As soon as it's removed, one of the remaining vertices must have no successors, so it will be the next-to-last one in the ordering, and so on.
  算法能够执行是因为,如果一个顶点没有后继,那么它肯定是拓扑序列中的最后一个。一旦删除它,剩下的顶点中必然有一个没有后继,所以它成为下一个拓扑序列中的最后一个,依此类推。


  The topological sorting algorithm works on unconnected graphs as well as connected graphs. This models the situation in which you have two unrelated goals, such as getting a degree in mathematics and at the same time obtaining a certificate in first aid.
  拓扑排序算法既可以用于连通图,也可以用于非连通图。这可以模拟另外一种有两个互不相关的目标的情况,例如同时得到数学学位和急救资格的证书。


(4)
环和树
  有一种图是拓扑排序算法不能处理的,那就是有环图。什么是环?它是一条路径,路径的起点和终点都是同一个顶点。

  A graph with no cycles is called a tree. The binary and multiway trees we saw earlier in this book are trees in this sense. However, the trees that arise in graphs are more general than binary and multiway trees, which have a fixed maximum number of child nodes. In a graph, a vertex in a tree can be connected to any number of other vertices, provided that no cycles are created.
 

  不包含环的图叫做树。本书前面讨论的二叉树和多叉树更具有一般意义,因为二叉树和多叉树定死了子节点的最大个数。在图中,树的顶点可以连接任意数量的顶点,只要不存在环即可。

要计算出无向图是否存在环也很简单。如果有N个顶点的图有超过N-1条边,那么它必定存在环。

 

  A topological sort is carried out on a directed graph with no cycles. Such a graph is called a directed, acyclic graph, often abbreviated DAG.
拓扑排序必须在无环的有向图中进行。这样的图叫做有向无环图,缩写为DAG。

 

下面是topp()方法的代码,这个方法执行了拓扑排序:

   public void topo()  // toplogical sort
      {
      int orig_nVerts = nVerts;  // remember how many verts

      while(nVerts > 0)  // while vertices remain,
         {
         // get a vertex with no successors, or -1
         int currentVertex = noSuccessors();
         if(currentVertex == -1)       // must be a cycle
            {
            System.out.println("ERROR: Graph has cycles");
            return;
            }
         // insert vertex label in sorted array (start at end)
         sortedArray[nVerts-1] = vertexList[currentVertex].label;

         deleteVertex(currentVertex);  // delete vertex
         // end while

      // vertices all gone; display sortedArray
      System.out.print("Topologically sorted order: ");
      for(int j=0; j<orig_nVerts; j++)
         System.out.print( sortedArray[j] );
      System.out.println("");
      // end topo

主要工作在while循环中进行。这个循环直到顶点数目为0时才退出。下面是步骤:
1.调用noSuccessors()找到任意一个没有后继的顶点。
2.如果找到一个这样的顶点,把顶点放入数组sortedArray[],并且从图中删除顶点。

 

If an appropriate vertex isn't found, the graph must have a cycle.
(如果没有这样的顶点,则图必然存在环。)

 

  The last vertex to be removed appears first on the list, so the vertex label is placed in sortedArray starting at the end and working toward the beginning, as nVerts (the number of vertices in the graph) gets smaller.
(最后一个被删除的顶点出现在列表的开头,所以,随着nVerts(图中顶点个数)逐渐变小,顶点从sortedArray数组的最后开始,依次向前排列。)


  If vertices remain in the graph but all of them have successors, the graph must have a cycle, and the algorithm displays a message and quits. Normally, however, the while loop exits, and the list from sortedArray is displayed, with the vertices in topologically sorted order.
(如果有顶点还在图中,但它们都有后继,那么图必然存在环,算法会显示一条消息并退出。如果没有环,则while循环退出,显示sortedArray数组中的数据,这时顶点时按照拓扑有序排列。)

 

  The noSuccessors() method uses the adjacency matrix to find a vertex with no successors. In the outer for loop, it goes down the rows, looking at each vertex. For each vertex, it scans across the columns in the inner for loop, looking for a 1. If it finds one, it knows that that vertex has a successor, because there's an edge from that vertex to another one. When it finds a 1, it bails out of the inner loop so that the next vertex can be investigated.
(noSuccessors()方法使用邻接矩阵找到没有后继的顶点。在外层for循环中,沿着每一行考察每个顶点。在每行中,用内层for循环扫描列,查找值为1的顶点。如果找到一个,就说明顶点有后继,因为从这个顶点到其他点有边存在。当找到一个1时,跳出内层循环,考察下一个顶点。)


  Only if an entire row is found with no 1s do we know we have a vertex with no successors; in this case, its row number is returned. If no such vertex is found, –1 is returned.
(只有整个一行都没有1存在,才说明有一个顶点没有后继,这时,就返回它的行号。如果没有这样的顶点,就返回-1.下面是noSuccessors()方法:)

   public int noSuccessors()  // returns vert with no successors
                           // (or -1 if no such verts)
      boolean isEdge;  // edge from row to column in adjMat

      for(int row=0; row<nVerts; row++)  // for each vertex,
         {
         isEdge = false;                 // check edges
         for(int col=0; col<nVerts; col++)
            {
            if( adjMat[row][col] > 0 )   // if edge to
                                      // another,
               isEdge = true;
               break;                    // this vertex
                                      //    has a successor
                                      //    try another
         if( !isEdge )                   // if no edges,
            return row;                  //    has no successors
         }
      return -1;                         // no such vertex
      // end noSuccessors()
  
  除了一些细节外,删除一个顶点很简单。顶点从vertexList[]数组删除,后面的顶点向前移动填补空位。同样的,顶点的行列从邻接矩阵中删除,下面的行和右面的列移动来填补空位。对于这个算法,用邻接表表示图效率更高,但要使用更多空间。

  Deleting a vertex is straightforward except for a few details. The vertex is removed from the vertexList[] array, and the vertices above it are moved down to fill up the vacant position. Likewise, the row and column for the vertex are removed from the adjacency matrix, and the rows and columns above and to the right are moved down and to the left to fill the vacancies. This is carried out by the deleteVertex(), moveRowUp(), and moveColLeft() methods, which you can examine in the complete listing for topo.java. It's actually more efficient to use the adjacency-list representation of the graph for this algorithm, but that would take us too far afield.

 

class Vertex
   {
   public char label;        // label (e.g. 'A')
// -------------------------------------------------------------
   public Vertex(char lab)   // constructor
      { label = lab; }
   // 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 char sortedArray[];
// -------------------------------------------------------------
   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;
      sortedArray = new char[MAX_VERTS];  // sorted vert labels
      // end constructor
// -------------------------------------------------------------
   public void addVertex(char lab)
      {
      vertexList[nVerts++] = new Vertex(lab);
      }
// -------------------------------------------------------------
   public void addEdge(int start, int end)
      {
      adjMat[start][end] = 1;
      }
// -------------------------------------------------------------
   public void displayVertex(int v)
      {
      System.out.print(vertexList[v].label);
      }
// -------------------------------------------------------------
   public void topo()  // toplogical sort
      {
      int orig_nVerts = nVerts;  // remember how many verts

      while(nVerts > 0)  // while vertices remain,
         {
         // get a vertex with no successors, or -1
         int currentVertex = noSuccessors();
         if(currentVertex == -1)       // must be a cycle
            {
            System.out.println("ERROR: Graph has cycles");
            return;
            }
         // insert vertex label in sorted array (start at end)
         sortedArray[nVerts-1] = vertexList[currentVertex].label;

         deleteVertex(currentVertex);  // delete vertex
         // end while

      // vertices all gone; display sortedArray
      System.out.print("Topologically sorted order: ");
      for(int j=0; j<orig_nVerts; j++)
         System.out.print( sortedArray[j] );
      System.out.println("");
      // end topo
// -------------------------------------------------------------
   public int noSuccessors()  // returns vert with no successors
                           // (or -1 if no such verts)
      boolean isEdge;  // edge from row to column in adjMat

      for(int row=0; row<nVerts; row++)  // for each vertex,
         {
         isEdge = false;                 // check edges
         for(int col=0; col<nVerts; col++)
            {
            if( adjMat[row][col] > 0 )   // if edge to
                                      // another,
               isEdge = true;
               break;                    // this vertex
                                      //    has a successor
                                      //    try another
         if( !isEdge )                   // if no edges,
            return row;                  //    has no successors
         }
      return -1;                         // no such vertex
      // end noSuccessors()
// -------------------------------------------------------------
   public void deleteVertex(int delVert)
      {
      if(delVert != nVerts-1)      // if not last vertex,
                                // delete from vertexList
         for(int j=delVert; j<nVerts-1; j++)
            vertexList[j] = vertexList[j+1];
                                   // delete row from adjMat
         for(int row=delVert; row<nVerts-1; row++)
            moveRowUp(row, nVerts);
                                   // delete col from adjMat
         for(int col=delVert; col<nVerts-1; col++)
            moveColLeft(col, nVerts-1);
         }
      nVerts--;                    // one less vertex
      // end deleteVertex
// -------------------------------------------------------------
   private void moveRowUp(int row, int length)
      {
      for(int col=0; col<length; col++)
         adjMat[row][col] = adjMat[row+1][col];
      }
// -------------------------------------------------------------
   private void moveColLeft(int col, int length)
      {
      for(int row=0; row<length; row++)
         adjMat[row][col] = adjMat[row][col+1];
      }
// -------------------------------------------------------------
   // end class Graph

 

(5)
有向图的连通性
前面已经看到在无向图中,如何利用深度优先搜索或广度优先搜索找到所有相互连通的点。当试图找到有向图中所有的连通点时,事情变得更加复杂了。因为不能从任意一个顶点开始,并期望找到所有其他的连通的顶点。

 

(6)
连通性表
Chapter <wbr>13-2: <wbr>Graphs-unweighted <wbr>graphs

  我们可以很容易地改变dfs.java程序,依次从每个顶点开始进行搜索。对于图13.15所示的图,输出如下所示:
AC
BACE
C
DEC
EC
  这是有向图的连通性表,第一个字母是起始点,接下来的字母显示能够到达的顶点(直接或者通过其他顶点)


(7)
Warshall算法
  在有些应用中,需要快速地找出是否一个顶点可以从其他顶点到达。
  可以通过检索连通性表,但是那要查看指定行的所有表项,需要O(N)的时间(这里N是指定顶点可到达的顶点数目平均值)。如果时间紧迫,可否有更快的方式?

  可以构造一个表,这个表将立即(即,O(1)的复杂度)告知一个顶点对另一个点是否是可达的。这样的表可以通过系统的修改图的邻接矩阵得到。由这种修正过的邻接矩阵表示的图,叫做原图的传递闭包。

  记住,在原来的邻接矩阵中,行号代表边从哪里开始,列号代表到哪里结束。(在连通表中的排列是类似的。)行C列D的交叉点为,表示从顶点C到顶点D有一条边。可以一步从一个顶点到另一个顶点。表13.6显示了图13.15中所示的图的邻接矩阵。

Chapter <wbr>13-2: <wbr>Graphs-unweighted <wbr>graphs

  可以使用Warshall算法把邻接矩阵变成图的传递闭包,算法用有限的几行做了很多工作。它基于一个简单的思想:
  如果能从顶点L到M,并且能从顶点M到N,那么可以从L到N。
  这里已经从两个一步路径得到一个两步路径。邻接矩阵显示了所有的一步路径,所以它可以很好地应用这个规则。

  你可能想知道这个算法是否可以找到比两步还长的路径。毕竟规则只讨论了从两个一步路径合并成一个两步路径。在它执行时,算法建立在用前面发现的多步路径来创建任意长度的基础上。将要描述的实现保证了这个结果,但是它的证明超出了本书的范围。

  下面是它的实现过程。这里使用表13.6作为例子,要检查邻接矩阵的每个单元,一次一行。

 

行A
  从行A开始。列A和列B为0,但列C为1,所以在这里停下来。
  现在,1说明从A到C有一条路径。如果这时知道从某个顶点X到A有一条路径,那么就知道有条路径从顶点X到C。以A为终点的边(如果存在)在哪里?它只可能在列A中出现:结果发现行B是1.这说明从B到A有一条路径。所以就知道有一条边从B到A,另一条(前面开始的那条)从A到C。那么这就暗示可以通过两步从B到C。
  为了记录这个结果,把行B和列C的交叉点置为1.
  行A余下的单元为空。

 

行B、C和D
  下面来看行B。在列A,也就是第一个单元,值就是1,表示有一条边从B到A。有没有边是以B为结尾的?那么看列B,发现它是空的,所以就知道,列B没有1存在,这样就没有发现更长的路径,因为没有以B为终点的边。

  行C没有1存在,所以直接到行D。这时发现有一条边从D到E。然而,列D是空的,所有没有其他边以D结尾。

 

行E
  在行E,有一条边从E到C。考察列E,E的第一个条目是从B到E的边,所以根据B到E和E到C,可以知道有一条路径从B到C。然而,它已经被发现了,所以相应的位置已经被置为1.
  列E还有一个1,在行D。这条从D到E的边加上从E到C的边说明有一条路径从D到C,所以把相应单元置1.

Warshall算法现在结束。由于向邻接矩阵增加了两个1,现在邻接矩阵可以显示某个顶点通过任意步可以从另一个顶点到达。

Chapter <wbr>13-2: <wbr>Graphs-unweighted <wbr>graphs

 

(8)
Warshall算法的实现
  实现Warshall算法的一个方法是用三层嵌套的循环。外层循环考察每一行:称它为变量y,它里面的一层循环考察行中的每个单元,它使用变量x。如果在单元(x,y)发现1,那么表明有一条边从y到x,这时执行最里层循环,它使用变量z。

  第三个循环检查列y的每个单元,看是否有边以y为终点。(注意y在第一个循环中作为行,在这个循环中作为列。)如果行Z列y值为1,说明有一条边从z到y。一条边从z到y,另一条从y到x,就可以说有一条路径从z到x,所以把(z,x)置为1.

0

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

    发评论

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

      

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

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

    新浪公司 版权所有