judge1.txt

判断连通图

1连通图--对无向图，任意Vi<>Vj的两个顶点之间都存在路径   
  2强连通图--对有向图，任意Vi<>Vj的两个顶点之间都存在Vi→Vj，Vj→Vi的路径   
  3连通分量--无向图的极大连通子图   
  4强连通分量--有向图的极大连通子图   
  　　判断一个无向图是否为连通图或连通分量很容易，而判断一个   有向图是否为强连通图或强连通分量则比较困难，可采用下列方法，若一个有向图是强连通图或强连通分量，则一定能找到包含所有顶点在内的若干独立的有向回路。     
  5网路--边或弧带有权值的图，又称为带权图。   
  6生成树--图的无环连通子图   
  　　在一个图中究竟会有多少边或弧呢？我们先看看无向图：最少当然可能只有0条边，最多时即当任何两个顶点之间都有相联系的边时，边数将达到n*(n-1)/2。具有n*(n-1)/2条边的无向图我们称之为完全图。对于有向图，e的取值范围是0到n(n-1)，我们也把有n*(n-1)条弧的有向图称为有向完全图。对那些边或弧很少的图称之为稀疏图，反之称稠密图。有的时候，图的边或弧上还带有一个相关的数(称为权)，表示从一个顶点到另一个顶点的耗费，这种图就叫做网。     
  　　一般采用一些改进的方式来存储图，常用的有邻接表和十字链表等。下面我们以邻接表为例来说明一下:   
  　　邻接表(adjacency   list)是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边(或以vi为尾的弧)。很自然的，每个结点将由三个域组成，其中邻接点域(adjvex)指示与顶点vi邻接的点在图上的位置，链域(nextarc)指示下一条边或弧   的结点；数据域(info)存储和边或弧相关的信息，如权值等。     
  　　每个链表上附设一个表头结点。在每个表头结点中，除了设有链域之外，还有存储顶点vi的名或其它有关信息的数据域(vexdata)。这些表头结点通常以顺序结构的形式存储，以便能够随机访问任一顶点的链表。     
  　　下面的图将告诉你邻接表是如何构造出来的。   
  　　十字链表(ortholgonal   list)是有向图的另一种链式存储结构。可以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。在十字链表中，对应于有向图中每一条弧有一个结点，对应于每个顶点也有一个结点。这些结点根据顶点和弧的联系关系交织成网状   
          最后要注意两点:一个图的邻接矩阵表示是唯一的，而一个图的邻接表表示是不唯一的。   
  　　图的遍历算法:   
  　　因为图是一种非线性数据结构，因此我们有使其序列化的需要--即图的遍历。和树的遍历类似，图的遍历(traversing   graph)，就是从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。图的遍历算法是其后我们要学习的许多算法的基础。     
  　　按照搜索次序的不同，通常有两种遍历图的方法：深度优先搜索和广度优先搜索。它们对无向图和有向图都适用。   
  　　深度优先搜索(depth一first   search)遍历类似于树的先根遍历。     
  　　假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点v0出发，访问此顶点，然后依次从vo的未被访问的邻接点出发深度优先遍历图，直至图中所有和v0有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。     
  　　显然，这是一个递归的过程。为了在遍历过程中便于区分顶点是否已被访问，需附设访问标志数组visited[   1:n]，其初值为"false"，一旦某个顶点被访问，则其相应的分量置为   "true"。整个图的遍历算法如下所示。你也可以通过演示加深印象。   
  　　void   traver_dfs(Graph   g，bool   visited［］)   
  　　{   /*对图按深度优先进行遍历*/   
  　　for   (i=1;i<=vexnum;i++)   
  　　visited[i]＝false；//标志数组初始化   
  　　for   (i=1;i<=vexnum;i++)   
  　　if   (!visited[i])   
  　　dfs(g，i);   
  　　}   
  　　void   dfs(Graph   g   ,vtx   *   v0){   
  　　/*从v0出发深度优先遍历图g*/   
  　　visit(v0);   
  　　visited[v0]   =   true;   
  　　w=FIRSTADJ(g，v0);   //w为v0的邻接点   
  　　while   (w!=0)   {   //当邻接点存在时   
  　　if   (!visited[w])   
  　　dfs   (g，w);   
  　　w=   NEXTADJ(g，v0，w)//找下一邻接点   
  　　}   
  　　}//dfs   
  　　分析上述过程，在遍历图时，对图中每个顶点至多调用一次dfs过程，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需时间为O(n2)，其中n为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为O(e)，其中e为无向图中边的数或有向图中弧的数。由此，当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为O(n＋e)。     
  　　广度优先搜索(breadth一first   search)遍历类似于树的按层次遍历的过程。   假设从图中某顶点v0出发，在访问了v0之后依次访问v0的各个未曾访问过的邻接点，然后分别从这些邻接点出发广度优先搜索遍历图，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。换句话说，广度优先搜索遍历图的过程是以v0为起始点，由近至远，依次访问和v0有路径相通且路径长度为1，2，…的顶点。     
  　　和深度优先搜索类似，在遍历的过程中也需要一个访问标志数组。并且，为了顺次访问路径长度为2、3、…的顶点，需附设队列以存储已被访问的路径长度为1，2，…的顶点。广度优先遍历的算法如下所示。     
  　　分析上述过程，每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接点的过程、因此广度优先搜索遍历图的时间复杂度和深度优先搜索遍历相同，两者不同之处仅仅在于对顶点访问的顺序不同。     
  　　void   traver_bfs(Graph   g，bool   visited［］){   /*对图按广度优先进行遍历*/   
  　　for   (i=1;i<=vexnum;i++)   
  　　visited[i]＝false；//标志数组初始化   
  　　for   (i=1;i<=vexnum;i++)   
  　　if   (!visited[i］)   
  　　dfs(g，i);   
  　　}   
  　　void   bfs(Graph   g   ,vtx   *   v0){   
  　　/*从v0出发广度优先遍历图g*/   
  　　visit(v0);   
  　　visited[v0]=true;   
  　　INIQUEUE(Q);//初始化队列   
  　　ENQUEUE(Q,v0);   
  　　while   (!EMPTY(Q))   {   
  　　v=DLQUEUE(Q);   //队头元素出队   
  　　w=FIRSTADJ(g,v);//求v的邻接点   
  　　while   (w!=0){   
  　　if   (!visited[w])   {   
  　　visit(w);   
  　　visited[w]=true;   
  　　ENQUEUE(Q,w);   
  　　}   
  　　w=NEXTADJ(g,v,w);//求下一邻接点   
  　　}   
  　　}   
  　　}//bfs