图(2)

一：图的遍历 1.概念： 从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次（图的遍历算法是求解图的 连通性问题 、 拓扑排序 和求 关键路径 等算法的基

一：图的遍历

      1.概念： 从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次（图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。）

       2.深度优先搜索(DFS)

            1).基本思想:

                           (1)在访问图中某一起始顶点 v 后，由 v 出发，访问它的任一邻接顶点 w1；
                           (2)再从 w1 出发，访问与 w1邻接但还未被访问过的顶点 w2；
                           (3)然后再从 w2 出发，进行类似的访问，… 
                           (4)如此进行下去，直至到达所有的邻接顶点都被访问过为止。
                           (5)接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。
                                     如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；
                                     如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。

            2)算法实现(明显是要用到(栈)递归):                           

Void DFSTraverse( Graph  G, Status (*Visit) (int v))
{         // 对图G做深度优先遍历
    for (v=0; v<g.vexnum visited false for v if dfs void g>//从第v个顶点出发递归地深度优先遍历图G
{
   visited[v]=TRUE ;  Visit(v);  //访问第v个顶点 
   for(w=FirstAdjVex(G,v)/*从图的第v个结点开始*/; w>=0; w=NextAdjVex(G,v,w)/*v结点开始的w结点的下一个结点*/)
       if (!visited[w])   DFS(G,w); 
      //对v的尚未访问的邻接顶点w递归调用DFS 
}
</g.vexnum>

           3)DFS时间复杂度分析：

                     (1)如果用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，因此遍历全部顶点所需的时间为O(n2)。
                     (2)如果用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n 个头结点的时间，因此遍历图的时间复杂度为O(n+e)。

3.广度优先搜索(BFS)

     1).基本思想：

               (1)从图中某个顶点V0出发，并在访问此顶点后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0                                     有 路径相通的顶点都被访问到；
                (2)若此时图中尚有顶点未被访问(非连通图)，则另选图中一个未曾被访问的顶点作起始点；
                (3)重复上述过程，直至图中所有顶点都被访问到为止。

     2).算法实现(明显是要用到队列)              

void BFSTraverse(Graph G, Status (*Visit)(int v)){
            //使用辅助队列Q和访问标志数组visited[v] 
  for (v=0; v<g.vexnum visited false initqueue for v="0;" if true visit enqueue while dequeue u>=0;w=NextAdjVex(G,u,w)）
          if ( ! visited[w]){  
           //w为u的尚未访问的邻接顶点
             visited[w] = TRUE; Visit(w);
             EnQueue(Q, w);
          }   //if
       }   //while
   }if
}  // BFSTraverse</g.vexnum>

      3).BFS时间复杂度分析：

               (1) 如果使用邻接表来表示图，则BFS循环的总时间代价为 d0 + d1 + … + dn-1 = 2e=O(e)，其中的 di 是顶点 i 的度
               (2)如果使用邻接矩阵，则BFS对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（ n 个元素），总的时间代价为O(n2)。

二.图的连通性问题：

     1. 相关术语：

                 (1)连通分量的顶点集：即从该连通分量的某一顶点出发进行搜索所得到的顶点访问序列；
                 (2)生成树：某连通分量的极小连通子图(深度优先搜索生成树和广度优先搜索生成树)；
                 (3)生成森林：非连通图的各个连通分量的极小连通子图构成的集合。

     2.最小生成树：

             1).Kruskal算法:

                      先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中去，并使森林中不产生回路，直至森林变成一棵树为止(详细代码见尾文)。

                      

                 2）Prim算法（还是看上图理解）：

                          假设原来所有节点集合为V,生成的最小生成树的结点集合为U,则首先把起始点V1加入到U中,然后看比较V1的所有相邻边，选择一条最小的V3结点加入到集合U中,

                      然后看剩下的v-U结点与U中结点的距离，同样选择最小的.........一直进行下去直到边数=n-1即可。

                    

                   算法设计思路:

                          增设一辅助数组Closedge[ n ]，每个数组分量都有两个域：

                          

                         要求：求最小的Colsedge[ i ].lowcost   

                        

           3.两种算法比较：

                      (1)普里姆算法的时间复杂度为 O(n2)，与网中的边数无关,适于稠密图；
                      (2)克鲁斯卡尔算法需对 e 条边按权值进行排序，其时间复杂度为 O(eloge)，e为网中的边数,适于稀疏图。                  

           4.完整最小生成树两种算法实现：          

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std; 

#define MAX_VERTEX_NUM 20

#define OK 1

#define ERROR 0

#define MAX 1000

typedef struct Arcell
{
	double adj;//顶点类型
}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
	char vexs[MAX_VERTEX_NUM]; //节点数组,
	AdjMatrix arcs; //邻接矩阵
	int vexnum,arcnum; //图的当前节点数和弧数
}MGraph;

typedef struct Pnode //用于普利姆算法
{

	char adjvex; //节点

	double lowcost; //权值

}Pnode,Closedge[MAX_VERTEX_NUM]; //记录顶点集U到V-U的代价最小的边的辅助数组定义

typedef struct Knode //用于克鲁斯卡尔算法中存储一条边及其对应的2个节点

{

	char ch1; //节点1

	char ch2; //节点2

	double value;//权值

}Knode,Dgevalue[MAX_VERTEX_NUM];

//-----------------------------------------------------------------------------------

int CreateUDG(MGraph & G,Dgevalue & dgevalue);

int LocateVex(MGraph G,char ch);

int Minimum(MGraph G,Closedge closedge);

void MiniSpanTree_PRIM(MGraph G,char u);

void Sortdge(Dgevalue & dgevalue,MGraph G);

//-----------------------------------------------------------------------------------

int CreateUDG(MGraph & G,Dgevalue & dgevalue) //构造无向加权图的邻接矩阵
{
	int i,j,k;
	cout>G.vexnum>>G.arcnum;

	cout>G.vexs[i];

	for(i=0;i<g.vexnum for g.arcs cout cin>> dgevalue[k].ch1 >> dgevalue[k].ch2 >> dgevalue[k].value;

		i = LocateVex(G,dgevalue[k].ch1);

		j = LocateVex(G,dgevalue[k].ch2);

		G.arcs[i][j].adj = dgevalue[k].value;

		G.arcs[j][i].adj = G.arcs[i][j].adj;

	}

	return OK;

}

int LocateVex(MGraph G,char ch) //确定节点ch在图G.vexs中的位置

{

	int a ;

	for(int i=0; i<g.vexnum i if ch a="i;" return void minispantree_prim g u int closedge k="LocateVex(G,u);" for j g.arcs cout g.vexs minimum double minispantree_krsl dgevalue p1 bj sortdge p2="bj[LocateVex(G,dgevalue[i].ch2)];" temp char ch1> dgevalue[j].value)

			{

				temp = dgevalue[i].value;

				dgevalue[i].value = dgevalue[j].value;

				dgevalue[j].value = temp;

				ch1 = dgevalue[i].ch1;

				dgevalue[i].ch1 = dgevalue[j].ch1;

				dgevalue[j].ch1 = ch1;

				ch2 = dgevalue[i].ch2;

				dgevalue[i].ch2 = dgevalue[j].ch2;

				dgevalue[j].ch2 = ch2;

			}

		}

	}

}

void main()

{

	int i,j;

	MGraph G;

	char u;

	Dgevalue dgevalue;

	CreateUDG(G,dgevalue);

	cout>u;

	cout运行结果：

<p>             <img  src="/static/imghw/default1.png" data-src="/inc/test.jsp?url=http%3A%2F%2Fimg.blog.csdn.net%2F20140219123300296%3Fwatermark%2F2%2Ftext%2FaHR0cDovL2Jsb2cuY3Nkbi5uZXQvd3VzdF9fd2FuZ2Zhbg%3D%3D%2Ffont%2F5a6L5L2T%2Ffontsize%2F400%2Ffill%2FI0JBQkFCMA%3D%3D%2Fdissolve%2F70%2Fgravity%2FSouthEast&refer=http%3A%2F%2Fblog.csdn.net%2Fwust__wangfan%2Farticle%2Fdetails%2F19479007" class="lazy" alt="图(2)" ></p>


</g.vexnum></g.vexnum></iostream></stdlib.h></stdio.h>