一：图的遍历 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="/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" alt="图(2)" ></p>
</g.vexnum></g.vexnum></iostream></stdlib.h></stdio.h>登录后复制
