6.3 应用实例：拯救007
voidSave007(GraphG)
{
for(eachVinG){
if(!visited[V] &&FirstJump(V)){//这个FirstJump(V)是007第一跳有没有可能从孤岛跳到V上有没有可能，有且没踩过就跳上去
answer=DFS(V);//or BFS(V)
if(answer==YES) break;0
}
}
if(answer==YES) output("Yes");
elseoutput("No");
}
DFS算法
voidDFS(VertexV)
{
visited[V] =true;//表示鳄鱼头踩过了
for(V的每个邻接点W)
if(!visited[W])
DFS(W);//递归
}
改良版本
voidDFS(VertexV)
{
visited[V] =true;//表示鳄鱼头踩过了
if(IOsSafe(V)) answer=YES;
else{
for(eachWinG )
if(!visited[W] &&Jump(V,W)){//可以从V jump跳到这个w上面，作用是算V到W之间的距离是不是小于007可以跳跃最大距离
answer=DFS(W);//递归
if(answer==YES) break;
}
}
returnanswer;
}
6.4 应用实例：六度空间(Six Degrees of Separation)
理论：
- 你和任何一个陌生人之间所间隔的人不会超过6个
- 给定社交网络图，请对每个节点计算符合"六度空间"理论的结点占结点总数的百分比
算法思路
1.对每个节点进行广度优先搜索
2.搜索过程中累计访问的节点数
3.需要记录"层"数,仅计算6层以内的节点数
voidSDS()
{
for(eachVinG){
count+=BFS(V);
Output= (count/N);
}
}
//结合最初的BFS
voidBFS(VertexV)
{
visited[V] =true;count=1;
Enqueue(V,Q);//压到队列里
while(!IsEmpty(Q)){
V=Dequeue(Q);//每次循环弹出一个节点
for(V的每个邻接点W)
if(!visited[W]){//没有访问过的去访问将其压入队列中
visited[W] =true;
Enqueue(W,Q);count++;
}
}returncount;
}
另外的解决方案
intBFS(VertexV)
{
vistex[V] =true;count=1;
level=0;last=V;
Enqueue(V,Q);
while(!IsEmpty(Q)){
V=Dequeue(Q);
for( V的每个邻接点W)
if(!visited[W]){
visited[W] =true;
Enqueue(W,Q);count++;
tail=W;
}
if(V==last ){
level++;last=tail;
}
}
returncount++;
}
小白专场：如何建立图：C语言实现
小白BG.1邻接矩阵表示的图结点的结构
typedefstructGNode*PtrToGNode;//PtrToGNode是指向GNode的一个指针
structGNode{
intNv;//顶点数
intNe;//边数
WeightTypeG[MaxVertexNum][MaxVertexNum];
DataTypeData[MaxVertexNum];//存顶点的数据
};
typedefPtrToGNodeMGraph;//以邻接矩阵存储的图类型。定义为指向节点的指针。因为要用到的时候一个指针远远比一整个图来的快捷
小白BG.2邻接矩阵表示的图——初始化
初始化一个有VertexNum个顶点但没有边的图
typedefintVertex;//用顶点下标表示顶点，为整型
MGraphCreateGraph(intVertexNum)//VertexNum这个顶点数真的是整数，
{
VertexV , W;//我们在说V跟W的时候不是在说整数，而是顶点
MGraphGraph;
Graph= (MGraph)malloc(sizeof(structGNode));
Graph->Nv=VertexNum;
Graph->Ne=0;
//注意：这里默认顶点编号从0开始，到(Graph->Nv - 1)
for(V=0;V<Graph->Nv;V++)
for((W=0;W<Graph->Nv;W++))
Graph->G[V][M] =0;//或者INFINITY，表示这两个顶点之间是没有边的
returnGraph
}
小白BG.3邻接矩阵表示的图——插入边
typedefstructENode*PtrToENode;
structENode{
VertexV1,V2;//有向边<V1,V2>，V1V2两个顶点一个出发点一个终点
WeightTypeWeight;//权重，有权图才需要。权重的类型是WeightType
};
typedefPtrToENodeEdge;
voidInsertEdge(MGraphGraph,EdgeE)
{
//插入边<V1,V2>，这是一条边
Graph->G[E->V1][E->V2] =E->Weight;
//无向图的话还需要一条边(一共两条)，<V2,V1>
Graph->G[E->V2][E->V1] =E->Weight;
}
小白BG.4邻接矩阵表示的图——建立图
完整的建立一个MGraph
输入格式
- Nv Ne
- V1 V2 Weight
- ......
MGraphBuildGraph()
{
MGraphGraph;
scanf("%d",&Nv);
Graph=CreateGraph(Nv);
//读入边数
scanf("%d",&(Graph->Ne));
if(Graph->Ne=0){//有边就还需要经过这里，没有边直接结束
E= (Edge)malloc(sizeof(structENode));//临时存一下边
for(i=0; i<Graph->Ne; i++){
scanf("%d %d %d",&E->V1,&E->V2,&E->Weight);
InsertEdge(Graph,E);
}
}
//如果顶点有数据的话，读入数据
for(V=0;V<Graph->Nv;V++)
scanf("%c",&(Graph->Data[V]));
returnGraph;
}
简易建法
intG[MAXN][MAXN],Nv,Ne;//声明为全局变量
voidBuildGraph()
{
inti,j,v1,v2,w;
scanf("%d",&Nv);
//CreateGraph
for(i=0;i<Nv;i++)
for(j=0;j<Nv;j++)
G[i][j] =0;//或INFINITY，把矩阵所有元素先初始化为0或者无穷大
scanf("%d",&Ne);
for(i=0;i<Ne; i++){
scanf("%d %d %d",&v1,&v2,&w);
//InsertEdge
G[v1][v2] =w;
G[v2][v1] =w;
}
}
小白BG.5邻接表表示的图结点的结构
邻接表：G[N]为指针数组，对应矩阵每一行一个链表，只存非0元素
typedefstructGNode*PtrToGNode;
structGNode {
intNv;//顶点数
intNe;//边数
AdjListG;//邻接表
};
typedefPtrToGNodeLGraph;
//以邻接表方式存储的图类型
//AdjList是自己定义的
typedefstructVnode{
PtrToAdjVNodeFirstEdge;
DataTypeData;//存顶点的数据
}AdjList[MaxVertexNum];//AdjList是邻接表类型
typedefstructAdjVNode*PtrToAdjVNode;
structAdjVNode{
VertexAdjV;//邻接点下标，定义为整型
WeightTypeWeight;//边权重
PtrToAdjVNodeNext;
};
小白BG.6邻接表表示的图——建立图
初始化一个有VertexNum个顶点但没有边的图
typedefintVertex;//用顶点下标表示顶点，为整型
LGraphCreateGraph(intVertexNum)
{
VertexV,W;
LGraphGraph;
Graph= (LGraph)malloc(sizeof(structGNode));
Graph->Nv=VertexNum;
Graph->Ne=0;
//没有边的意思是每个顶点跟着的那个链表都是空的
//注意：这里默认顶点编号从0开始，到(Graph->Nv - 1)
for(V=0;V<Graph->Nv;V++)
Graph->G[V].FirstEdge=NULL;
returnGraph;
}
向LGraph中插入边
voidInsertEdge(LGraphGraph,EdgeE)
{
PtrToAdjVNodeNewNode;
//-------------------插入边<V1,V2>------------------------------
//为V2建立新的邻接点
NewNode= (PtrToAdjVNode)malloc(sizeof(structAdjNode));
NewNode->AdjV=E->V2;
NewNode->Weight=E->Weight
//将V2插入到V1的表头
NewNode->Next=Graph->G[E->V1].FirstEdge;
Graph->G[E->V1].FirstEdge=NewNode;
//-------------------若是无向图，还需插入边<V2,V1>------------------
//为V1建立新的邻接点
NewNode= (PtrToAdjVNode)malloc(sizeof(structAdjNode));
NewNode->AdjV=E->V1;
NewNode->Weight=E->Weight
//将V2插入到V1的表头
NewNode->Next=Graph->G[E->V2].FirstEdge;
Graph->G[E->V2].FirstEdge=NewNode;
}
完整建立一个LGraph
LGraphBuildGraph()
{
LGraphGraph;
...............
}
