Heap堆的完整c实现源码,图的遍历

笔者:JULY、二〇一二年八月十十二日

图的遍历 – 数据结构 

 

(1)算法观念

出处:

引言:
   
此文的编写指标很简短,就一个理由,个人以为:上一篇文章,二之再续、Dijkstra
算法 fibonacci堆的日渐c完结,写的远远不足好,特此再写Dijkstra
算法的贰个续集,谓之二之三续。
   
鉴于读者掌握斐波那契堆的难度,本文,以简要的细小堆为示范。同不经常间,本程序也会有参照网络朋友的贯彻。有任何难题,招待指正。

Dijkstra 算法+Heap堆完整算法思想
    在前一篇小说中,大家曾经了然到,Dijkstra 算法如下:

DIJKSTRA(G, w, s)
1  INITIALIZE-SINGLE-SOURCE(G, s)  //1、初步化结点专门的学业
2  S ← Ø
3  Q ← V[G]   //2、初叶化队列
4  while Q ≠ Ø
5      do u ← EXTRACT-MIN(Q)
//3、从细微队列中,收取最小结点(从前,先制造最小堆)
6         S ← S ∪{u}
7         for each vertex v ∈ Adj[u]
8             do RELAX(u, v, w)  //4、松弛操作。

    如此,大家不再赘言,直接就能够轻巧编写如下c/c++源码:

void dijkstra(ALGraph G,int s,int d[],int pi[],int Q[])
{
//Q[]是细微优先队列,Q[1..n]中存放的是图顶点标号,Q[0]中寄放堆的大小
 //优先队列中有key的概念,这里key能够从d[]中取得。比如说,Q[2]的大小(key)为
d[ Q[2] ]

 initSingleSource(G,s,d,pi);  //1、开始化结点专门的学问
 
 //2、起首化队列
 Q[0] = G.vexnum;
 for(int i=1;i<=Q[0];i++)

 {
  Q[i] = i-1;
 }
 Q[1] = s;
 Q[s+1] = 0;

 int u;
 int v;
 while(Q[0]!=0)

 {
  buildMinHeap(Q,d);     //3.1、塑造最小堆
  u = extractMin(Q,d);   //3.2、从细微队列中,收取最小结点
  ArcNode* arcNodePt = G.vertices[u].firstarc;
  while(arcNodePt!=NULL)
 {
   v = arcNodePt->adjvex;
   relax(u,v,G,d,pi);    //4、松弛操作。
   arcNodePt = arcNodePt->nextarc;
  }
 }

}

    ok,接下去,大家一步一步编写代码来达成此Dijkstra
算法,先提交第1、初叶化结点职业,和4、松弛操作俩个操作的源码:

void initSingleSource(ALGraph G,int s,int d[],int pi[])
{       //1、开首化结点职业
 for(int i=0;i<G.vexnum;i++)

 {
  d[i] = INFINITY;
  pi[i] = NIL;
 }
 d[s] = 0;
}

void relax(int u,int v,ALGraph G,int d[],int pi[])
{ //4、松弛操作。
        //u是新加盟会集S的终极的评释
 if(d[v]>d[u]+getEdgeWeight(G,u,v))

 {
  d[v] = d[u] + getEdgeWeight(G,u,v);
  pi[v] = u;
 }
}

   
ok,接下去,我们具体演讲第4个操作,3、从细微队列中,收取最小结点(以前,先创立最小堆)。

Heap最小堆的创立与抽取最小结点
    在自己的那篇作品二、堆排序算法里头,对最大堆的建构具备演说:
2.3.1、建堆(O(N))

BUILD-MAX-HEAP(A)
1  heap-size[A] ← length[A]
2  for i ← |_length[A]/2_| downto 1
3       do MAX-HEAPIFY(A, i)   
//建堆,怎么建列?原本就是不断的调用MAX-HEAPIFY(A, i)来构造建设最大堆。

   
建最小堆,也是贰回事,把上述代码改俩处就可以,一,MAX->MIN,二,MAX-HEAPIFY(A,
i)->MIN-HEAPIFY(A, i)。如此说来,是或不是很轻巧列,是的,自己就很简短。

    先是创设最小堆的行事:

void buildMinHeap(int Q[],int d[]) //建设构造最小堆
{
 for(int i=Q[0]/2;i>=1;i–)
 {
  minHeapify(Q,d,i); //调用minHeapify,以维持堆的特性。
 }
}

    然后,得编写minHeapify代码,来保持最小堆的性质:

void minHeapify(int Q[],int d[],int i)
{ //smallest,l,r,i都是优先队列成分的下标,范围是从1 ~ heap-size[Q]
 int l = 2*i;
 int r = 2*i+1;
 int smallest;
 if(l<=Q[0] && d[ Q[l] ] < d[ Q[i] ])

 {
  smallest = l;
 }
 else
 {
  smallest = i;
 }
 if(r<=Q[0] && d[ Q[r] ] < d[ Q[smallest] ])

 {
  smallest = r;
 }
 if(smallest!=i)
 {
  int temp = Q[i];
  Q[i] = Q[smallest];
  Q[smallest] = temp; 

  minHeapify(Q,d,smallest);
 }
}

您自个相比一下起家最小堆,与创立最大堆的代码,立马看见,一模一样,可是是改多少个字母而已:

MAX-HEAPIFY(A, i)   //创建最大堆的代码
 1 l ← LEFT(i)
 2 r ← RIGHT(i)
 3 if l ≤ heap-size[A] and A[l] > A[i]
 4    then largest ← l
 5    else largest ← i
 6 if r ≤ heap-size[A] and A[r] > A[largest]
 7    then largest ← r
 8 if largest ≠ i
 9    then exchange A[i] <-> A[largest]
10         MAX-HEAPIFY(A, largest)

    ok,最后,正是3、从非常的小队列中,收取最小结点的劳作了,如下:

int extractMin(int Q[],int d[])   //3、从细微队列中,抽出最小结点
{ //摘取优先队列中幽微元素的剧情,这里重返图中顶点的标号(0 ~
G.vexnum-1),
 //这么些标号是保留在Q[1..n]中的
 if(Q[0]<1)
 {
  cout<<“heap underflow!”<<endl;
  return -10000;
 }
 int min = Q[1];
 Q[1] = Q[Q[0]];
 Q[0] = Q[0] – 1;
 minHeapify(Q,d,1);
 return min;
}

ALGraph图的成立
    先定义多少个宏,

#define MAX_VERTEX_NUM 20 //图中最大的节点数目
#define INFINITY 10000
#define NIL -1

    再次创下设多少个数据结构:

typedef struct ArcNode  //弧节点,正是邻接链表的表节点

 int adjvex;    //该弧所指向尾节点的地点,其实保存的就是数组的下标
 ArcNode *nextarc;  //指向下一条弧的指针
 int weight;        //权重。
}ArcNode;

typedef struct VNode
{
 ArcNode* firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct
{
 AdjList vertices;
 int vexnum,arcnum;
}ALGraph;

    编写多少个职能函数:

void initALGraph(ALGraph* GPt,int vn)   //最初化结点
{
 GPt->arcnum = 0;
 GPt->vexnum = vn;
 for(int i=0;i<vn;i++)

 {
  GPt->vertices[i].firstarc = NULL;
 }
}

void insertArc(ALGraph* GPt,int vhead,int vtail,int w) //扩充结点操作
{
 ArcNode* arcNodePt = new ArcNode;
 arcNodePt->nextarc = NULL;
 arcNodePt->adjvex = vtail;
 arcNodePt->weight = w;
 
 ArcNode* tailPt = GPt->vertices[vhead].firstarc;
 if(tailPt==NULL)
 {
  GPt->vertices[vhead].firstarc = arcNodePt;
 }
 else
 {
  while(tailPt->nextarc!=NULL)
  {
   tailPt = tailPt->nextarc;
  }
  tailPt->nextarc = arcNodePt;
 }
 GPt->arcnum ++;
}

void displayGraph(ALGraph G)  //打字与印刷结点
{
 ArcNode* arcNodePt;
 for(int i=0;i<G.vexnum;i++)
 {
  arcNodePt = G.vertices[i].firstarc;
  cout<<“vertex”<<i<<“: “;
  while(arcNodePt!=NULL)
  {
  
cout<<arcNodePt->adjvex<<“(“<<“weight”<<arcNodePt->weight<<“)”<<”
“;
   arcNode

出处:
—————————————— 引言:
此文的写作目标很简单,就一个…

概述

 

图的遍历是指从图中的任一顶点出发,对图中的全部终端访谈三回且只访谈二遍。图的遍历操作和树的遍历操作功用相似。图的遍历是图的一种基本操作,图的别样算法如求解图的连通性难点,拓扑排序,求关键路线等都是起家在遍历算法的基础之上。

是因为图结构本人的扑朔迷离,所以图的遍历操作也较复杂,首要呈未来以下七个地点:

在图结构中,未有二个“自然”的首结点,图中自由多个终极都可看做第3个被访问的结点。

在非连通图中,从叁个终极出发,只好够访谈它所在的对接分量上的享有终端,因而,还需记挂什么挑选下叁个观点以访谈图中其余的联网分量。

在图结构中,如若有回路存在,那么二个终极被访问之后,有不小希望沿回路又赶回该顶点。


在图结构中,一个终极能够和其余多个极端相连,当那样的极端访谈过后,存在什么样选择下多个要访谈的终极的难题。

图的遍历经常有深度优先搜索和广度优先搜索三种办法,他们对无向图和有向图都适用。

 

     T=(U,TE)是存放MST的集合。
  ①T的初值是({r},¢)
    即最小生成树早先时独有三个红点r,未有红边。
  ②T经过n-1次如下步骤操作,最终收获一棵含n个顶峰,n-1条边的最小生成树
     ⒈选取紫边聚焦一条轻边并扩梁鹏T
  ⒉将轻边连接的蓝点改红点
  ⒊将轻边改红边
     ⒋修改紫边集

1.纵深优先找出

 

纵深优先搜索(Depth_Fisrst
Search)遍历类似于树的先根遍历,是树的先根遍历的加大。

 假诺初步状态是图中有所终端未曾被访谈,则深度优先找出可从图中某部顶点发v
出发,访谈此顶点,然后依次从v
的未被访谈的邻接点出发深度优先遍历图,直至图中存有和v
有路子相通的终端都被访谈到;若此时图中尚有顶点未被访问,则另选图中一个未曾被访谈的顶峰作发轫点,重复上述进程,直至图中全部终端都被访谈到甘休。

以如下图的无向图G5为例,进行图的纵深优先寻找:

图片 1

G5

寻找进度:

图片 2

 

假使从顶点v1 出发实行检索,在做客了顶点v1 现在,选用邻接点v2。因为v2
未曾采访,则从v2 出发举办搜寻。依次类推,接着从v4 、v8 、v5
出发进行检索。在做客了v5 之后,由于v5
的邻接点都已被访谈,则搜索回到v8。由于一样的说辞,搜索继续回到v4,v2
直至v1,此时出于v1 的另一个邻接点未被访问,则寻觅又从v1
到v3,再持续打开下去由此,得到的极端采访体系为:

图片 3

 

显而易见,那是一个递归的进度。为了在遍历进程中有益区分顶点是或不是已被访谈,需附设访谈标记数组visited[0:n-1],
,其初值为FALSE ,一旦有个别顶点被访谈,则其相应的轻重新载入参数为TRUE。
1)邻接矩阵的存款和储蓄格局贯彻:

 

[cpp] view
plain copy

 

 print?

  1. // stdafx.h : include file for standard system include files,  
  2. // or project specific include files that are used frequently, but  
  3. // are changed infrequently  
  4. //  
  5.   
  6. #pragma once  
  7.   
  8. #include “targetver.h”  
  9. #include <stdio.h>    
  10. #include “stdlib.h”  
  11. #include <iostream>  
  12. using namespace std;  
  13.   
  14. //宏定义      
  15. #define TRUE   1      
  16. #define FALSE   0     
  17. #define NULL 0  
  18. #define OK    1      
  19. #define ERROR   0    
  20. #define INFEASIBLE -1      
  21. #define OVERFLOW -2    
  22.   
  23. #define INFINITY   INT_MAX  
  24. #define MAX_VERTEX_NUM 30  
  25.   
  26.   
  27. typedef int Status   ;  
  28. typedef int ElemType ;  
  29. typedef int VrType  ;  
  30. typedef char VertexType  ;  
  31. /************************************************************************/  
  32. /* 数组表示:邻接矩阵数据结构 
  33. */  
  34. /************************************************************************/  
  35.   
  36. typedef struct ArcCell{  
  37.     VrType adj;                         //顶点关系项目,对无权图,0/1表示是不是相邻,有权图表示权值  
  38.     ArcCell  *info;                     //弧相关音讯的指针  
  39. }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];  
  40.   
  41. typedef struct{  
  42.     VertexType vexs[MAX_VERTEX_NUM];   //顶点向量  
  43.     AdjMatrix arcs;                    //邻接矩阵  
  44.     int vexnum,arcnum;                 //图的当下顶点数和弧数  
  45. }MGraph;  

 

 

[cpp] view
plain copy

 

 print?

  1. // Test.cpp : Defines the entry point for the console application.    
  2. //    
  3. #include “stdafx.h”   
  4.   
  5. bool visited[MAX_VERTEX_NUM];  //访问标志  
  6. Status (*VisitFunc) (int v);   //函数变量  
  7. /************************************************************************/  
  8. /*   
  9.     鲜明顶点v在图G的地方 
  10. */  
  11. /************************************************************************/  
  12. int LocateVex(MGraph G,VertexType v)  
  13. {  
  14.     for(int i = 0; i<G.vexnum; ++i) {  
  15.         if(G.vexs[i] == v) return i;//找到  
  16.     }  
  17.     return -1;//不存在  
  18. }  
  19.   
  20. /************************************************************************/  
  21. /*   
  22.    
  23. */  
  24. /************************************************************************/  
  25. int FirstAdjVex(MGraph G,int v)  
  26. {  
  27.     int i ;  
  28.     for(i = 0; i<G.vexnum; i++)  
  29.         if( G.arcs[v][i].adj ) return i;  
  30.     if(i == (G.vexnum  -1)) return -1;  
  31.     return -1;   
  32.   
  33. }  
  34.   
  35. int NextAdjVex(MGraph G,int v,int w)  
  36. {  
  37.     int i;  
  38.     for( i = w+1; i<G.vexnum; i++)//+1  
  39.         if(G.arcs[v][i].adj) return i;  
  40.     if(i == (G.vexnum  -1)) return -1;  
  41.     return -1;  
  42.   
  43. }  
  44. /************************************************************************/  
  45. /* 
  46.  邻接矩阵的无向图的创立: 
  47.  注释的代码能够动态生成图。 
  48. */  
  49. /************************************************************************/  
  50.   
  51. void CreatUDG(MGraph &G){  
  52.     cout<<“创造邻接矩阵的无向图:”<<endl;  
  53.     int i,j,k,w;  
  54.     //G5的存储:  
  55.     G.arcnum = 8;  
  56.     G.vexnum = 9;  
  57.     for(i=0;i<G.vexnum;++i)  
  58.         for(j=0;j<G.vexnum;++j) {  
  59.             G.arcs[i][j].adj=0;  
  60.             G.arcs[i][j].info=NULL;  
  61.         }  
  62.     G.vexs[0] = ‘1’;  
  63.     G.vexs[1] = ‘2’;  
  64.     G.vexs[2] = ‘3’;  
  65.     G.vexs[3] = ‘4’;  
  66.     G.vexs[4] = ‘5’;  
  67.     G.vexs[5] = ‘6’;  
  68.     G.vexs[6] = ‘7’;  
  69.     G.vexs[7] = ‘8’;  
  70.   
  71.     G.arcs[0][1].adj = 1;  
  72.     G.arcs[0][1].info = NULL;  
  73.     G.arcs[1][0].adj = 1;  
  74.     G.arcs[1][0].info = NULL;  
  75.   
  76.     G.arcs[1][3].adj = 1;  
  77.     G.arcs[1][3].info = NULL;  
  78.     G.arcs[3][1].adj = 1;  
  79.     G.arcs[3][1].info = NULL;  
  80.   
  81.     G.arcs[3][7].adj = 1;  
  82.     G.arcs[3][7].info = NULL;  
  83.     G.arcs[7][3].adj = 1;  
  84.     G.arcs[7][3].info = NULL;  
  85.   
  86.     G.arcs[7][4].adj = 1;  
  87.     G.arcs[7][4].info = NULL;  
  88.     G.arcs[4][7].adj = 1;  
  89.     G.arcs[4][7].info = NULL;  
  90.   
  91.     G.arcs[4][1].adj = 1;  
  92.     G.arcs[4][1].info = NULL;  
  93.     G.arcs[1][4].adj = 1;  
  94.     G.arcs[1][4].info = NULL;  
  95.   
  96.     G.arcs[0][2].adj = 1;  
  97.     G.arcs[0][2].info = NULL;  
  98.     G.arcs[2][0].adj = 1;  
  99.     G.arcs[2][0].info = NULL;  
  100.   
  101.     G.arcs[2][5].adj = 1;  
  102.     G.arcs[2][5].info = NULL;  
  103.     G.arcs[5][2].adj = 1;  
  104.     G.arcs[5][2].info = NULL;  
  105.   
  106.     G.arcs[5][6].adj = 1;  
  107.     G.arcs[5][6].info = NULL;  
  108.     G.arcs[6][5].adj = 1;  
  109.     G.arcs[6][5].info = NULL;  
  110.   
  111.     G.arcs[6][2].adj = 1;  
  112.     G.arcs[6][2].info = NULL;  
  113.     G.arcs[2][6].adj = 1;  
  114.     G.arcs[2][6].info = NULL;  
  115.     return ;  
  116.     /* 
  117.     char v1,v2; 
  118.     cout<<“请输入无向图顶点个数和边数:”<<endl; 
  119.     cin>>G.vexnum>>G.arcnum; 
  120.     cout<<“请输入”<<G.vexnum<<“个极点的值:”<<endl; 
  121.     for(i=0;i<G.vexnum;++i) cin>>G.vexs[i]; 
  122.     for(i=0;i<G.vexnum;++i) 
  123.         for(j=0;j<G.vexnum;++j) { 
  124.             G.arcs[i][j].adj=0; 
  125.             G.arcs[i][j].info=NULL; 
  126.         } 
  127.  
  128.         for( k=1;k<=G.arcnum;++k){ 
  129.             cout<<“请输入第”<<k<<“条边的七个顶点值和它们的权重:”<<endl; 
  130.             cin>>v1>>v2>>w; 
  131.             i = LocateVex(G,v1);   j=LocateVex(G,v2);  
  132.             G.arcs[i][j].adj=w; 
  133.             G.arcs[j][i]=G.arcs[i][j]; 
  134.         } 
  135.         */  
  136. }  
  137. /************************************************************************/  
  138. /* 有向图邻接矩阵的创设 
  139. */  
  140. /************************************************************************/  
  141. void CreatDG(MGraph &G){  
  142.     int i,j,k,w;  
  143.     char v1,v2;  
  144.     G.arcnum = 8;  
  145.     G.vexnum = 9;  
  146.     cout<<“请输入有向图顶点个数和边数:”;  
  147.     cin>> G.vexnum>> G.arcnum;  
  148.     cout<<“请输入”<<G.vexnum<<“个顶峰的值:”<<endl;  
  149.     for(i=0;i<G.vexnum;++i) cin>>G.vexs[i];  
  150.     for(i=0;i<G.vexnum;++i)  
  151.         for(j=0;j<G.vexnum;++j) {  
  152.             G.arcs[i][j].adj = 0;  
  153.             G.arcs[i][j].info = NULL;  
  154.         }  
  155.         for( k=1;k<=G.arcnum;++k){  
  156.             cout<<“请输入第”<<k<<“条边的七个顶点值和它们的权重:”<<endl;  
  157.             cin>>v1>>v2>>w;  
  158.             i= LocateVex(G,v1);   j = LocateVex(G,v2);   
  159.             G.arcs[i][j].adj = w;  
  160.         }  
  161. }  
  162.   
  163.   
  164. void visitVex(MGraph G, int v){  
  165.     cout<<G.vexs[v]<<” “;  
  166. }  
  167.   
  168. /************************************************************************/  
  169. /*  以V为出发点对图G 实行递归地DFS 寻找 
  170. */  
  171. /************************************************************************/  
  172. void DFS(MGraph G,int v){  
  173.     visited[v] = true;  
  174.     visitVex( G,  v); //访问第v 个顶点  
  175.     for(int w = FirstAdjVex(G,v); w>=0; w = NextAdjVex(G,v,w)){  
  176.         if(!visited[w]) DFS(G,w); //w未访谈过,递归DFS寻觅  
  177.   
  178.     }  
  179. }  
  180.   
  181. /************************************************************************/  
  182. /*      
  183. 无向图的吃水遍历        
  184. */  
  185. /************************************************************************/  
  186. void DFSTraverse(MGraph G){//  
  187.     int v;  
  188.     for( v = 0; v < G.vexnum; ++v) visited[v] = false;  
  189.     for( v = 0; v < G.vexnum; )   
  190.         if(!visited[v]) DFS( G, v); //v未访谈过,从vi起先DFS搜索  
  191.         ++v;//不要像书上写的那样,++v放到for语句,那样会招致多出贰次访谈  
  192.   
  193. }  
  194.   
  195.   
  196. void printMGraph(MGraph G){  
  197.     cout<<“邻接矩阵已经创办,邻接矩阵为:”<<endl;  
  198.     for(int i=0;i<G.vexnum;i++){  
  199.         for(int j=0;j<G.vexnum;j++)  
  200.             cout<<G.arcs[i][j].adj<<” “;  
  201.         cout<<endl;  
  202.     }  
  203. }  
  204.   
  205.   
  206. void main(){  
  207.       
  208.     MGraph G;  
  209.   
  210.     CreatUDG(G);  
  211.     printMGraph(G);  
  212.     cout<<“无向图邻接矩阵的深度遍历结果:”<<endl;  
  213.     DFSTraverse(G);  
  214. }  

2) 邻接表的代表达成情势

 

 

[cpp] view
plain copy

 

 print?

  1. // stdafx.h : include file for standard system include files,  
  2. // or project specific include files that are used frequently, but  
  3. // are changed infrequently  
  4. //  
  5.   
  6. #pragma once  
  7.   
  8. #include “targetver.h”  
  9. #include <stdio.h>    
  10. #include “stdlib.h”  
  11. #include <iostream>  
  12. using namespace std;  
  13.   
  14. //宏定义      
  15. #define TRUE   1      
  16. #define FALSE   0     
  17. #define NULL 0  
  18. #define OK    1      
  19. #define ERROR   0    
  20. #define INFEASIBLE -1      
  21. #define OVERFLOW -2    
  22.   
  23. #define INFINITY   INT_MAX  
  24. #define MAX_VERTEX_NUM 30  
  25.   
  26.   
  27. typedef int Status   ;  
  28. typedef int ElemType ;  
  29. typedef int VrType  ;  
  30. typedef char VertexType  ;  
  31.   
  32. /************************************************************************/  
  33. /*  邻接表示的图数据结构 
  34. */  
  35. /************************************************************************/  
  36. //定义边结点,即表节点  
  37. typedef struct ArcNode   
  38. {  
  39.     int adjvex;             //弧所指的终端地方  
  40.     ArcNode *nextarc;       //指向下一条弧的指针  
  41. }ArcNode;  
  42.   
  43. //定义顶点节点,即头节点  
  44. typedef struct VNode    
  45. {  
  46.     VertexType data;        //顶点消息  
  47.     ArcNode *firstarc;      //指向第一条依赖该顶点的弧的指针  
  48. }VNode,AdjList[MAX_VERTEX_NUM];  
  49.   
  50. //定义无向图     
  51. typedef struct                        
  52. {  
  53.     AdjList vertices;  
  54.     int vexnum,arcnum;   //图的当下顶点数和弧数  
  55. }ALGraph;  

[cpp] view
plain copy

 

 print?

  1. // Test.cpp : Defines the entry point for the console application.    
  2. //    
  3. #include “stdafx.h”   
  4.   
  5. bool visited[MAX_VERTEX_NUM];  //访谈标志  
  6. Status (*VisitFunc) (int v);   //函数变量  
  7.   
  8.   
  9. /************************************************************************/  
  10. /* 在无向图中增加以m,n为顶点的边 
  11. */  
  12. /************************************************************************/  
  13. void ArcAdd(ALGraph &G,int m,int n){  
  14.   
  15.     ArcNode *p,*h,*q;  
  16.     p = new ArcNode;  
  17.     p->adjvex = m;  
  18.     p->nextarc = NULL;  
  19.     h = q = G.vertices[n].firstarc;  
  20.     if(q == NULL)  
  21.         G.vertices[n].firstarc = p;  
  22.     else {   
  23.         if((p->adjvex)>(q->adjvex)){   
  24.             p->nextarc = q;  
  25.             G.vertices[n].firstarc = p;  
  26.         }  
  27.         else {   
  28.             while( G.vertices[n].firstarc != NULL && q->nextarc != NULL && (p->adjvex)<(q->adjvex)){ //使邻接表中边的数据按大到小排列。    
  29.                 h = q;  
  30.                 q = q->nextarc;  
  31.             }  
  32.             if(q->nextarc == NULL&&(p->adjvex)<(q->adjvex)){    
  33.                 q->nextarc = p;  
  34.             }  
  35.             else {    
  36.                 p->nextarc = q;  
  37.                 h->nextarc = p;  
  38.             }  
  39.         }  
  40.     }  
  41. }  
  42. /************************************************************************/  
  43. /* 
  44. 成立无向图 
  45. */  
  46. /************************************************************************/  
  47. void CreateDG(ALGraph &G){    
  48.     cout<<“请输入顶点个数和边数:”<<endl;  
  49.     cin>> G.vexnum>> G.arcnum;  
  50.     cout<<“请输入顶点值:”<<endl;  
  51.     for(int i= 1; i<= G.vexnum; i++) {  
  52.         char t;  
  53.         cin>>t;  
  54.         G.vertices[i].data = t;  
  55.         G.vertices[i].firstarc = NULL;  
  56.     }  
  57.     int m, n;  
  58.     for(int k = 1; k<=G.arcnum; k++){  
  59.         cout<<“请输入第”<<k<<“条边的三个极点:”<<endl;  
  60.         cin>>m>>n;  
  61.         if(m<= G.vexnum && n <= G.vexnum && m>0 && n>0){  
  62.             ArcAdd(G, m, n);  
  63.             ArcAdd(G, n, m);  
  64.         }  
  65.         else  cout<<“ERROR.”<<endl;   
  66.     }  
  67. }  
  68. /************************************************************************/  
  69. /* 打字与印刷邻接表的无向图       
  70. */  
  71. /************************************************************************/  
  72. void PrintGraph(ALGraph G)    
  73. {  
  74.     cout<<“无向图的创立完结,该图的邻接表表示为:”<<endl;  
  75.     ArcNode *p;  
  76.     for(int i=1; i<=G.vexnum; i++)  
  77.     {  
  78.         if(G.vertices[i].firstarc == NULL)  
  79.             cout<<i<<G.vertices[i].data<<“–>NULL”<<endl;  
  80.         else   
  81.         {  
  82.             p = G.vertices[i].firstarc;  
  83.             cout<<i<<G.vertices[i].data<<“–>”;  
  84.             while(p->nextarc!=NULL)  
  85.             {  
  86.                 cout<<p->adjvex<<“–>”;  
  87.                 p = p->nextarc;  
  88.             }  
  89.             cout<<p->adjvex<<“–>NULL”<<endl;  
  90.         }  
  91.     }  
  92. }  
  93.   
  94.   
  95. /************************************************************************/  
  96. /*     再次回到v的率先个邻接顶点。若顶点在G中从未邻接表顶点,则赶回“空”。    
  97. */  
  98. /************************************************************************/  
  99. int FirstAdjVex(ALGraph G,int v)  
  100. {   
  101.     if(G.vertices[v].firstarc)  
  102.         return G.vertices[v].firstarc->adjvex;  
  103.     else  
  104.         return NULL;  
  105. }  
  106. /************************************************************************/  
  107. /*    
  108.   再次回到v的(相对于w的)下一个接壤顶点。若w是v的末了一个邻接点,则赶回“回”。 
  109. */  
  110. /************************************************************************/  
  111. int NextAdjVex(ALGraph G,int v,int w)     
  112. {  
  113.     ArcNode *p;  
  114.     if(G.vertices[v].firstarc==NULL)  
  115.         return NULL;  
  116.     else {  
  117.         p = G.vertices[v].firstarc;  
  118.         while(p->adjvex!=w) p = p->nextarc;  
  119.   
  120.         if(p->nextarc == NULL) return NULL;  
  121.         else  return p->nextarc->adjvex;  
  122.     }  
  123. }  
  124.   
  125.   
  126.   
  127. void visitVex(ALGraph G, int v){  
  128.     cout<<G.vertices[v].data<<” “;  
  129. }  
  130.   
  131. /************************************************************************/  
  132. /*      
  133. 无向图的深度遍历        
  134. */  
  135. /************************************************************************/  
  136. //从第v个极端出发递归地深度优先遍历图G  
  137. void DFS(ALGraph G,int v)  
  138. {  
  139.     visited[v] = true;  
  140.     visitVex(G, v);  
  141.     for(int w = FirstAdjVex(G,v);w >= 1; w = NextAdjVex(G,v,w))  
  142.         if(!visited[w]) DFS(G,w);  
  143. }  
  144. //对图G作深度优先遍历  
  145. void DFSTraverse(ALGraph G)  
  146. {   
  147.     for(int v = 1; v <= G.vexnum; v++) visited[v]=false;  
  148.     for(int m = 1; m <= G.vexnum; m++)  
  149.         if(!visited[m]) DFS(G,m);  
  150. }  
  151.   
  152. void main(){  
  153.     ALGraph G;  
  154.     CreateDG(G);  
  155.     PrintGraph(G);  
  156.     DFSTraverse(G);  
  157. }  

 

深入分析上述算法,在遍历时,对图中各种终端至多调用一回DFS
函数,因为只要有个别顶点被标识成已被访谈,就不再从它出发进行寻找。因而,遍历图的历程实质上是对每一种终端查找其邻接点的长河。其开支的年华则在于所使用的存放结构。当用二维数组表示邻接矩阵图的积累结构时,查找每一种终端的邻接点所需时日为O(n2)
,当中n
为图中顶点数。而当以邻接表作图的仓库储存结构时,找邻接点所需时日为O(e),当中e
为无向图中边的数或有向图中弧的数。因而,当以邻接表作存款和储蓄结构时,深度优先找出遍历图的日子复杂度为O(n+e)

 

(2)相当的小紫边集的布局
     若当前产生的T中有k个顶点,|U|=k,|V-u|=n-k,故或许的紫边数目是k(n-k)。从这么大的紫边聚焦选用轻边是没用的。由此,必需构造十分的小的紫边集。
     对于每种蓝点v ∈V-U,从v到各红点的紫边中,独有最短的那一条才有望是轻边。因而,只须保留全部n-k个蓝点所关联的最短紫边作为轻边的候选集就能够。

2.广度优先找寻

广度优先寻找(Breadth_First Search) 遍历类似于树的按档案的次序遍历的长河。

 

假诺从图中某顶点v 出发,在拜谒了v 之后依次拜会v
的种种未曾访谈过和邻接点,然后分别从那么些邻接点出发依次拜谒它们的邻接点,并使“先被访问的顶峰的邻接点”先于“后被访问的顶峰的邻接点”被访谈,直至图中具有已被访问的极端的邻接点都被访谈到。若这时图中尚有顶点未被访问,则另选图中四个未曾被访问的终点作起首点,重复上述进程,直至图中装有终端都被访谈到甘休。换句话说,广度优先搜索遍历图的历程中以v
为发轫点,由近至远,依次拜望和v 有路子相通且路线长度为1,2,…的极限。

对图如下图所示无向图G5 进行广度优先寻觅遍历:

图片 4

 

广度寻觅进度:

图片 5

率先拜访v1 和v1 的邻接点v2 和v3,然后依次拜谒v2 的邻接点v4 和v5 及v3
的邻接点v6 和v7,最终访问v4
的邻接点v8。由于这个极端的邻接点均已被访谈,并且图中全体终端都被访谈,由些完毕了图的遍历。获得的极端访问体系为:

 

v1→v2 →v3 →v4→ v5→ v6→ v7 →v8

和深度优先寻觅类似,在遍历的历程中也急需贰个拜谒标识数组。而且,为了顺次访谈路线长度为2、3、…的极端,需附设队列以存款和储蓄已被访谈的门道长度为1、2、…
的终点。

实现:

 

[cpp] view
plain copy

 

 print?

  1. // stdafx.h : include file for standard system include files,  
  2. // or project specific include files that are used frequently, but  
  3. // are changed infrequently  
  4. //  
  5.   
  6. #pragma once  
  7.   
  8. #include <stdio.h>    
  9. #include “stdlib.h”  

[cpp] view
plain copy

 

 print?

  1. // func.h :  
  2. #pragma once  
  3.   
  4. #include <iostream>  
  5. using namespace std;  
  6.   
  7. //宏定义      
  8. #define TRUE   1      
  9. #define FALSE   0     
  10. #define NULL 0  
  11. #define OK    1      
  12. #define ERROR   0    
  13. #define INFEASIBLE -1      
  14. #define OVERFLOW -2    
  15.   
  16. #define INFINITY   INT_MAX  
  17. #define MAX_VERTEX_NUM 30  
  18.   
  19.   
  20. typedef int Status   ;  
  21. typedef int ElemType ;  
  22. typedef int VrType  ;  
  23. typedef char VertexType  ;  
  24.   
  25. /************************************************************************/  
  26. /*  邻接表示的图数据结构 
  27. */  
  28. /************************************************************************/  
  29. //定义边结点  
  30. typedef struct ArcNode   
  31. {  
  32.     int adjvex;             //弧所指的终极地方  
  33.     ArcNode *nextarc;       //指向下一条弧的指针  
  34. }ArcNode;  
  35.   
  36. //定义顶点结点  
  37. typedef struct VNode    
  38. {  
  39.     VertexType data;        //顶点信息  
  40.     ArcNode *firstarc;      //指向第一条依据该顶点的弧的指针  
  41. }VNode,AdjList[MAX_VERTEX_NUM];  
  42.   
  43. //定义无向图     
  44. typedef struct                        
  45. {  
  46.     AdjList vertices;  
  47.     int vexnum,arcnum;   //图的这几天顶点数和弧数  
  48. }ALGraph;  
  49.   
  50.   
  51. /************************************************************************/  
  52. /* 需要                                                                     */  
  53. /************************************************************************/  
  54. typedef struct node //定义结点  
  55. {  
  56.     char data;  
  57.     node *next;  
  58. }*Link;  
  59.   
  60. typedef struct //定义链表  
  61. {  
  62.     Link head,tail;  
  63.     int len;  
  64. }Queue;  
  65.   
  66. /************************************************************************/  
  67. /* 构造贰个牵头结点和尾结点的空的线性链表队列Q 
  68. */  
  69. /************************************************************************/  
  70. Status InitQueue(Queue &Q)  
  71. {  
  72.     Q.head = new node;  
  73.     Q.head->next = Q.tail = new node;  
  74.     Q.tail->next = NULL;  
  75.     Q.len = 0;  
  76.     return 0;  
  77. }  
  78.   
  79. /************************************************************************/  
  80. /*  
  81.  //在线性链表的队列L的尾声增添一个结点 
  82. */  
  83. /************************************************************************/  
  84.  void EnQueue(Queue &Q,int e)  
  85. {  
  86.     Link q = new node;  
  87.     Q.tail->next = q;  
  88.     Q.tail->data = e;  
  89.     Q.tail = q;  
  90.     Q.tail->next = NULL;  
  91.     Q.len++;  
  92. }  
  93. /************************************************************************/  
  94. /* 出列,并将出列的因素值用e再次回到 
  95. */  
  96. /************************************************************************/  
  97. void DeleteQueue(Queue &Q,int &e)  
  98. {  
  99.     if(Q.head->next == Q.tail) {  
  100.         cout<<“队列为空”<<endl;  
  101.         e = NULL;  
  102.     } else {  
  103.         Link p,q;  
  104.         p = Q.head->next;  
  105.         q = p->next;  
  106.         Q.head->next = q;  
  107.         e = p->data;  
  108.         delete p;  
  109.         Q.len–;  
  110.     }  
  111. }  

[cpp] view
plain copy

 

 print?

  1. // Test.cpp : Defines the entry point for the console application.    
  2. //    
  3. #include “stdafx.h”   
  4. #include “func.h”  
  5. bool visited[MAX_VERTEX_NUM];  //访问标志  
  6. Status (*VisitFunc) (int v);   //函数变量  
  7.   
  8. /************************************************************************/  
  9. /* 在无向图中增多以m,n为顶点的边 
  10. */  
  11. /************************************************************************/  
  12. void ArcAdd(ALGraph &G,int m,int n){  
  13.   
  14.     ArcNode *p,*h,*q;  
  15.     p = new ArcNode;  
  16.     p->adjvex = m;  
  17.     p->nextarc = NULL;  
  18.     h = q = G.vertices[n].firstarc;  
  19.     if(q == NULL)  
  20.         G.vertices[n].firstarc = p;  
  21.     else {   
  22.         if((p->adjvex)>(q->adjvex)){   
  23.             p->nextarc = q;  
  24.             G.vertices[n].firstarc = p;  
  25.         }  
  26.         else {   
  27.             while( G.vertices[n].firstarc != NULL && q->nextarc != NULL && (p->adjvex)<(q->adjvex)){   
  28.                 //使邻接表中边的数额按大到小排列。    
  29.                 h = q;  
  30.                 q = q->nextarc;  
  31.             }  
  32.             if(q->nextarc == NULL&&(p->adjvex)<(q->adjvex)){    
  33.                 q->nextarc = p;  
  34.             }  
  35.             else {    
  36.                 p->nextarc = q;  
  37.                 h->nextarc = p;  
  38.             }  
  39.         }  
  40.     }  
  41. }  
  42. /************************************************************************/  
  43. /* 
  44. 创设无向图 
  45. */  
  46. /************************************************************************/  
  47. void CreateDG(ALGraph &G){    
  48.     cout<<“请输入顶点个数和边数:”<<endl;  
  49.     cin>> G.vexnum>> G.arcnum;  
  50.     cout<<“请输入顶点值:”<<endl;  
  51.     for(int i= 1; i<= G.vexnum; i++) {  
  52.         char t;  
  53.         cin>>t;  
  54.         G.vertices[i].data = t;  
  55.         G.vertices[i].firstarc = NULL;  
  56.     }  
  57.     int m, n;  
  58.     for(int k = 1; k<=G.arcnum; k++){  
  59.         cout<<“请输入第”<<k<<“条边的五个顶峰:”<<endl;  
  60.         cin>>m>>n;  
  61.         if(m<= G.vexnum && n <= G.vexnum && m>0 && n>0){  
  62.             ArcAdd(G, m, n);  
  63.             ArcAdd(G, n, m);  
  64.         }  
  65.         else  cout<<“ERROR.”<<endl;   
  66.     }  
  67. }  
  68.   
  69. /************************************************************************/  
  70. /* 打字与印刷邻接表的无向图       
  71. */  
  72. /************************************************************************/  
  73. void PrintGraph(ALGraph G)    
  74. {  
  75.     cout<<“无向图的创导完成,该图的邻接表表示为:”<<endl;  
  76.     ArcNode *p;  
  77.     for(int i=1; i<=G.vexnum; i++)  
  78.     {  
  79.         if(G.vertices[i].firstarc == NULL)  
  80.             cout<<i<<G.vertices[i].data<<“–>NULL”<<endl;  
  81.         else   
  82.         {  
  83.             p = G.vertices[i].firstarc;  
  84.             cout<<i<<G.vertices[i].data<<“–>”;  
  85.             while(p->nextarc!=NULL)  
  86.             {  
  87.                 cout<<p->adjvex<<“–>”;  
  88.                 p = p->nextarc;  
  89.             }  
  90.             cout<<p->adjvex<<“–>NULL”<<endl;  
  91.         }  
  92.     }  
  93. }  
  94.   
  95. /************************************************************************/  
  96. /*     重返v的首先个邻接顶点。若顶点在G中绝非邻接表顶点,则赶回“空”。    
  97. */  
  98. /************************************************************************/  
  99. int FirstAdjVex(ALGraph G,int v)  
  100. {   
  101.     if(G.vertices[v].firstarc)  
  102.         return G.vertices[v].firstarc->adjvex;  
  103.     else  
  104.         return NULL;  
  105. }  
  106. /************************************************************************/  
  107. /*    
  108.   重返v的(相对于w的)下贰个接壤顶点。若w是v的末尾一个邻接点,则赶回“回”。 
  109. */  
  110. /************************************************************************/  
  111. int NextAdjVex(ALGraph G,int v,int w)     
  112. {  
  113.     ArcNode *p;  
  114.     if(G.vertices[v].firstarc==NULL)  
  115.         return NULL;  
  116.     else {  
  117.         p = G.vertices[v].firstarc;  
  118.         while(p->adjvex!=w) p = p->nextarc;  
  119.   
  120.         if(p->nextarc == NULL) return NULL;  
  121.         else  return p->nextarc->adjvex;  
  122.     }  
  123. }  
  124.   
  125. void visitVex(ALGraph G, int v){  
  126.     cout<<G.vertices[v].data<<” “;  
  127. }  
  128.   
  129. /************************************************************************/  
  130. /*      
  131. 广度优先遍历图G 
  132. */  
  133. /************************************************************************/  
  134.   
  135. void BFSTraverse(ALGraph G)  
  136. {  
  137.     Queue Q;  
  138.     int u;  
  139.     for(int m=1; m<= G.vexnum; m++) visited[m] = false;  
  140.     InitQueue(Q);//借助支持队列。  
  141.     for(int v=1;v<=G.vexnum;v++)  
  142.         if(!visited[v]) {  
  143.             visited[v]=true;  
  144.             visitVex(G,v);  
  145.             EnQueue(Q,v);  
  146.             while(Q.len!=0)  
  147.             {  
  148.                 DeleteQueue(Q,u);  
  149.                 for(int w=FirstAdjVex(G,u);w>=1;w=NextAdjVex(G,u,w))  
  150.                     if(!visited[w])  
  151.                     {  
  152.                         visited[w]=true;  
  153.                         visitVex(G,v);  
  154.                         EnQueue(Q,w);  
  155.                     }  
  156.             }  
  157.         }  
  158.         cout<<endl;  
  159. }  
  160.   
  161. void main(){  
  162.     ALGraph G;  
  163.     CreateDG(G);  
  164.     PrintGraph(G);  
  165.     cout<<“广度优先搜索的结果为:”<<endl;  
  166.     BFSTraverse(G);  
  167. }  

 

浅析上述算法,各种终端至多进一回队列。遍历图的经超过实际质是因此边或弧找邻接点的历程,由此广度优先寻找遍历图的时光复杂度和纵深优先搜索遍历一样,两个分化之处仅仅在于对极端访谈的顺序分歧。

(3)候选紫边会集的修改
     当把轻边(u,v)增加到T时,因为v由蓝变红,故对各样剩余的蓝点j,边(v,j)就由非紫边变为紫边,那条新紫边的长短大概低于蓝点j原本所波及的最短紫边的长度。因而,用长度更小的新紫边替代那多少个原本的最短紫边。

(4)Prim算法的C语言代码描述

/****** 基本变量定义*******************/

/****** Basic.h ***********************/

#include<string.h>

#include<ctype.h>

#include<malloc.h>//malloc()等

#include<limits.h>//INT_MAX等 

#include<stdio.h>//EOF(=^Z或F6),NULL 

#include<stdlib.h>//atoi() 

#include<io.h>//eof() 

#include<math.h>//floor(),ceil(),abs()

#include<process.h>//exit() 

//函数结果意况代码 

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

//#defineOVE奥迪Q5FLOW -2 因为在math.h中已定义OVE兰德WranglerFLOW的值为3,故去掉此行 

typedefint Status; //Status是函数的档期的顺序,其值是函数结果意况代码,如OK等 

typedefint Boolean; //Boolean是布尔类型,其值是TRUE或FALSE 

 

/****** 单链队列--队列的链式存款和储蓄结构****/

/****** LinkQueue.h***********************/

#define OK 1

#define ERROR 0

#defineOVERFLOW 2

typedefint Status;

typedefint QElemType;

 

typedefstruct QNode {

    QElemType data;

    struct QNode*next;

} QNode, *QueuePtr;

 

typedefstruct {

    QueuePtr front, rear; //队头、队尾指针

} LinkQueue;

 

/************************************************************************/

/* 链队列的基本操作(9个)                                                */

/************************************************************************/ 

 

//构造一个空队列Q

StatusInitQueue(LinkQueue *Q){ 

    (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode));

    if(!(*Q).front)

        exit(OVERFLOW);

    (*Q).front->next=NULL;

    return OK;

}

 

//销毁队列Q(无论空否均可) 

StatusDestroyQueue(LinkQueue *Q){

    while((*Q).front){

        (*Q).rear=(*Q).front->next;

        free((*Q).front);

        (*Q).front=(*Q).rear;

    }

    return OK;

}

 

//将Q清为空队列

StatusClearQueue(LinkQueue *Q){

    QueuePtr p,q;

    (*Q).rear=(*Q).front;

    p=(*Q).front->next;

    (*Q).front->next=NULL;

    while(p){

        q=p;

        p=p->next;

        free(q);

    }

    return OK;

}

 

//若Q为空队列,则赶回TRUE,否则再次来到FALSE

StatusQueueEmpty(LinkQueue Q){

    if(Q.front==Q.rear)

        returnTRUE;

    else

        returnFALSE;

}

 

//求队列的尺寸

int QueueLength(LinkQueue Q){ 

    int i=0;

    QueuePtr p;

    p=Q.front;

    while(Q.rear!=p){

        i++;

        p=p->next;

    }

    return i;

}

 

//若队列不空,则用e再次回到Q的队头成分,并赶回OK,不然重返EQashqaiRO普拉多

StatusGetHead_Q(LinkQueue Q,QElemType *e) { 

    QueuePtr p;

    if(Q.front==Q.rear)

        returnERROR;

    p=Q.front->next;

    *e=p->data;

    return OK;

}

 

//插入成分e为Q的新的队尾元素

StatusEnQueue(LinkQueue *Q,QElemType e)

    QueuePtr p=(QueuePtr)malloc(sizeof(QNode));

    if(!p) //存款和储蓄分配失利

        exit(OVERFLOW);

    p->data=e;

    p->next=NULL;

    (*Q).rear->next=p;

    (*Q).rear=p;

    return OK;

}

 

//若队列不空,删除Q的队头成分,用e重临其值,并赶回OK,不然重回E昂科雷ROPRADO

StatusDeQueue(LinkQueue *Q,QElemType *e)

    QueuePtr p;

    if((*Q).front==(*Q).rear)

        returnERROR;

    p=(*Q).front->next;

    *e=p->data;

    (*Q).front->next=p->next;

    if((*Q).rear==p)

        (*Q).rear=(*Q).front;

    free(p);

    return OK;

}

 

//从队头到队尾依次对队列Q中种种成分调用函数vi()。一旦vi败北,则操作失利。

StatusQueueTraverse(LinkQueue Q,void(*vi)(QElemType)){

    QueuePtr p;

    p=Q.front->next;

    while(p){

        vi(p->data);

        p=p->next;

    }

    printf(“\n”);

    return OK;

}

 

/****** 图的数组(邻接矩阵)存款和储蓄表示****/                                                          

/****** Mgraph.h*************************/

//#defineINT_MAX 99999 //库函数已经定义了

//#defineINFINITY INT_MAX //整型最大值代替∞

#define INFINITY 99999 //99999代替∞

#define MAX_VERTEX_NUM 20 //最大终端个数

 

typedefenum{DG,DN,UDG,UDN} GraphKind; //{有向图,有向网,无向图,无向网} 

typedefstruct {

    VRType adj; //顶点关系项目。对无权图,用1(是)或0(否)表示相邻否; 对带权图,c则为权值类型

    InfoType *info; //该弧相关消息的指针(可无)

} ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedefstruct {

    VertexType vexs[MAX_VERTEX_NUM]; //顶点向量

    AdjMatrix arcs; //邻接矩阵

    int vexnum, arcnum;//图的当下顶点数和弧数

    GraphKind kind; //图的种类标记

} MGraph;

 

/************************************************************************/

/*图的数组(邻接矩阵)存款和储蓄的基本操作(十多少个)                                  */

/************************************************************************/

 

//早先标准:图G存在,u和G中顶点有同一特征

//操作结果:若G中留存顶点u,则赶回该终端在图中地方;不然再次来到-1

int LocateVex(MGraph G, VertexType u) {

    int i;

    for (i=0;i<G.vexnum; ++i)

        if(strcmp(u, G.vexs[i])==0)

            returni;

    return -1;

}

 

//选拔数组(邻接矩阵)表示法,构造有向图G,构变成功再次回到1

StatusCreateDG(MGraph *G) {

    int i, j, k,l, IncInfo;

    chars[MAX_INFO], *info;

    VertexType va, vb;

    printf(“请输入有向图G的终端数、弧数、弧是或不是含另外新闻(是:1,否:0),以空格隔开分离:\n”);

    scanf(“%d%d%d”,&(*G).vexnum, &(*G).arcnum, &IncInfo);

    //构造顶点向量

    for (i=0;i<(*G).vexnum; ++i) {

        printf(“请输入第%d个极点的值(<%d个字符):\n”, i+1, MAX_NAME);

        scanf(“%s”,(*G).vexs[i]);

    }

    //先导化邻接矩阵

    for (i=0;i<(*G).vexnum; ++i)

        for(j=0; j<(*G).vexnum; ++j) {

            (*G).arcs[i][j].adj=0;//图

            (*G).arcs[i][j].info=NULL;

        }

        //输入结点之间的关联

        for(k=0; k<(*G).arcnum; ++k) {

            printf(“请输入第%d条弧的弧尾、弧头(以空格作为距离): \n”, k+1);

            scanf(“%s%s%*c”,va, vb); //%*c吃掉回车符

            i=LocateVex(*G, va);

            j=LocateVex(*G, vb);

            (*G).arcs[i][j].adj=1; //有向图

            if(IncInfo) {

                printf(“请输入该弧的连带音讯(<%d个字符): “, MAX_INFO);

                gets(s);

                l=strlen(s);

                if(l) {

                    info=(char*)malloc((l+1)*sizeof(char));

                    strcpy(info, s);

                    (*G).arcs[i][j].info=info; //有向

                }

            }

        }

        (*G).kind=DG;

        returnOK;

}

 

//选取数组(邻接矩阵)表示法,构造有向网G,构变成功重回1

StatusCreateDN(MGraph *G) {

    int i, j, k,w, IncInfo;

    chars[MAX_INFO], *info;

    VertexType va, vb;

    printf(“请输入有向网G的极限数、弧数、弧是还是不是含另外消息(是:1,否:0): “);

    scanf(“%d%d%d”,&(*G).vexnum, &(*G).arcnum, &IncInfo);

    //构造顶点向量

    for (i=0;i<(*G).vexnum; ++i) {

        printf(“请输入第%d个顶峰的值(<%d个字符):\n”, i+1, MAX_NAME);

        scanf(“%s”,(*G).vexs[i]);

    }

    //初阶化邻接矩阵

    for (i=0;i<(*G).vexnum; ++i)

        for(j=0; j<(*G).vexnum; ++j) {

            (*G).arcs[i][j].adj=INFINITY; //网

            (*G).arcs[i][j].info=NULL;

        }

        for(k=0; k<(*G).arcnum; ++k) {

            printf(“请输入第%d条弧的弧尾、弧头、权值(以空格作为距离): \n”, k+1);

            scanf(“%s%s%d%*c”,va, vb, &w); //%*c吃掉回车符

            i=LocateVex(*G, va);

            j=LocateVex(*G, vb);

            (*G).arcs[i][j].adj=w; //有向网

            if(IncInfo) {

                printf(“请输入该弧的连带音信(<%d个字符): “, MAX_INFO);

                gets(s);

                w=strlen(s);

                if(w) {

                    info=(char*)malloc((w+1)*sizeof(char));

                    strcpy(info, s);

                    (*G).arcs[i][j].info=info; //有向

                }

            }

        }

        (*G).kind=DN;

        returnOK;

}

 

//选择数组(邻接矩阵)表示法,构造无向图G,构变成功返回1

StatusCreateUDG(MGraph *G) { 

    int i, j, k,l, IncInfo;

    chars[MAX_INFO], *info;

    VertexType va, vb;

    printf(“请输入无向图G的极端数、边数、边是或不是含别的消息(是:1,否:0): “);

    scanf(“%d%d%d”,&(*G).vexnum, &(*G).arcnum, &IncInfo);

    //构造顶点向量

    for (i=0;i<(*G).vexnum; ++i) {

        printf(“请输入第%d个极点的值(<%d个字符):\n”, i+1, MAX_NAME);

        scanf(“%s”,(*G).vexs[i]);

    }

    //早先化邻接矩阵

    for (i=0;i<(*G).vexnum; ++i)

        for(j=0; j<(*G).vexnum; ++j) {

            (*G).arcs[i][j].adj=0; //图

            (*G).arcs[i][j].info=NULL;

        }

        //输入结点之间的调换

        for(k=0; k<(*G).arcnum; ++k) {

            printf(“请输入第%d条边的顶峰1、顶点2(以空格作为距离): \n”, k+1);

            scanf(“%s%s”,va, vb); //%*c吃掉回车符

            i=LocateVex(*G, va);

            j=LocateVex(*G, vb);

            (*G).arcs[i][j].adj=(*G).arcs[j][i].adj=1;//无向图

            if(IncInfo)

                printf(“请输入该边的相干音信(<%d个字符): “, MAX_INFO);

            gets(s);

            l=strlen(s);

            if(l) {

                info=(char*)malloc((l+1)*sizeof(char));

                strcpy(info, s);

                (*G).arcs[i][j].info=(*G).arcs[j][i].info=info;//无向

            }

        }

        (*G).kind=UDG;

        returnOK;

}

 

//选用数组(邻接矩阵)表示法,构造无向网G,构产生功重返1。算法7.2 

StatusCreateUDN(MGraph *G) { 

    int i, j, k,w, IncInfo;

    chars[MAX_INFO], *info;

    VertexType va, vb;

    printf(“请输入无向网G的巅峰数,边数,边是不是含别的音信(是:1,否:0): “);

    scanf(“%d%d%d”,&(*G).vexnum, &(*G).arcnum, &IncInfo);

    //构造顶点向量 

    for (i=0;i<(*G).vexnum; ++i) {

        printf(“请输入第%d个极端的值(<%d个字符):\n”, i+1, MAX_NAME);

        scanf(“%s”,(*G).vexs[i]);

    }

    //最初化邻接矩阵

    for (i=0;i<(*G).vexnum; ++i)

        for(j=0; j<(*G).vexnum; ++j) {

            (*G).arcs[i][j].adj=INFINITY; //网 

            (*G).arcs[i][j].info=NULL;

        }

        //输入结点之间的联络

        for(k=0; k<(*G).arcnum; ++k) {

            printf(“请输入第%d条边的终端1、顶点2、权值(以空格作为距离): \n”, k+1);

            scanf(“%s%s%d%*c”,va, vb, &w); //%*c吃掉回车符

            i=LocateVex(*G, va);

            j=LocateVex(*G, vb);

            (*G).arcs[i][j].adj=(*G).arcs[j][i].adj=w;//无向

            if(IncInfo) {

                printf(“请输入该边的相关音讯(<%d个字符): “, MAX_INFO);

                gets(s);

                w=strlen(s);

                if(w) {

                    info=(char*)malloc((w+1)*sizeof(char));

                    strcpy(info, s);

                    (*G).arcs[i][j].info=(*G).arcs[j][i].info=info;//无向

                }

            }

        }

        (*G).kind=UDN;

        returnOK;

}

 

//选拔数组(邻接矩阵)表示法,构造图G。算法7.1

//参数1:MGraph *G。

//重回值:创制作而成功重回1,战败再次来到0。

StatusCreateGraph(MGraph *G) {     

    printf(“请输入图G的类型:\n0:有向图\n1:有向网\n2:无向图\n3:无向网\n”);

    scanf(“%d”,&(*G).kind);

    switch((*G).kind) {

    case DG:

        returnCreateDG(G); //构造有向图

    case DN:

        returnCreateDN(G); //构造有向网

    case UDG:

        returnCreateUDG(G); //构造无向图

    case UDN:

        returnCreateUDN(G); //构造无向网

    default:

        returnERROR;

    }

}

 

//开首标准: 图G存在。

//操作结果: 销毁图G 

void DestroyGraph(MGraph *G) {

    int i, j;

    if((*G).kind<2) //有向 

        for(i=0; i<(*G).vexnum; i++) //释放弧的相关音讯(假如有些话)

        {

            for(j=0; j<(*G).vexnum; j++)

                if((*G).arcs[i][j].adj==1&&(*G).kind==0||(*G).arcs[i][j].adj!=INFINITY&&(*G).kind==1)//有向图的弧||有向网的弧

                    if((*G).arcs[i][j].info) //有相关音信

                    {

                        free((*G).arcs[i][j].info);

                        (*G).arcs[i][j].info=NULL;

                    }

        }

    else

        //无向 

        for(i=0; i<(*G).vexnum; i++)

            //释放边的相关音讯(假如部分话)

            for(j=i+1; j<(*G).vexnum; j++)

                if((*G).arcs[i][j].adj==1&&(*G).kind==2||(*G).arcs[i][j].adj!=INFINITY&&(*G).kind==3)//无向图的边||无向网的边 

                    //有有关音讯

                    if((*G).arcs[i][j].info)  {

                        free((*G).arcs[i][j].info);

                        (*G).arcs[i][j].info=(*G).arcs[j][i].info=NULL;

                    }

                    (*G).vexnum=0;

                    (*G).arcnum=0;

}

 

//最早典型: 图G存在,v是G中有个别顶点的序号。

//操作结果: 再次回到v的值 

VertexType*GetVex(MGraph G, int v) { 

    if(v>=G.vexnum||v<0)

        exit(ERROR);

    return&G.vexs[v];

}

 

//早先规范: 图G存在,v是G中某些顶点。

//操作结果: 对v赋新值value

Status PutVex(MGraph*G, VertexType v, VertexType value) {

    int k;

    k=LocateVex(*G, v); //k为顶点v在图G中的序号

    if (k<0)

        returnERROR;

    strcpy((*G).vexs[k], value);

    return OK;

}

 

//初叶标准: 图G存在,v是G中有个别顶点 

//操作结果: 重临v的首先个邻接顶点的序号。若顶点在G中绝非邻接顶点,则赶回-1

int FirstAdjVex(MGraph G, VertexType v) { 

    int i, j=0,k;

    k=LocateVex(G, v); //k为顶点v在图G中的序号 

    if(G.kind==DN||G.kind==UDN) //网 

        j=INFINITY;

    for (i=0;i<G.vexnum; i++)

        if(G.arcs[k][i].adj!=j)

            returni;

    return -1;

}

 

//起头标准: 图G存在,v是G中有些顶点,w是v的交界顶点

//操作结果: 再次来到v的(相对于w的)下三个交界顶点的序号,若w是v的最终贰个接壤顶点,则赶回-1 

int NextAdjVex(MGraph G, VertexType v, VertexType w){ 

    int i, j=0,k1, k2;

    k1=LocateVex(G, v); //k1为顶点v在图G中的序号 

    k2=LocateVex(G, w); //k2为极端w在图G中的序号 

    if(G.kind==DN||G.kind==UDN) //网

        j=INFINITY;

    for (i=k2+1;i<G.vexnum; i++)

        if(G.arcs[k1][i].adj!=j)

            returni;

    return -1;

}

 

//初叶标准: 图G存在,v和图G中顶点有一样特征 

//操作结果: 在图G中增加新顶点v(不扩大与极端相关的弧,留待InsertArc()去做) 

void InsertVex(MGraph *G, VertexType v) { 

    int i;

    strcpy((*G).vexs[(*G).vexnum], v); //构造新顶点向量

    for (i=0;i<=(*G).vexnum; i++) {

        if((*G).kind%2) //网

        {

            (*G).arcs[(*G).vexnum][i].adj=INFINITY;//早先化该行邻接矩阵的值(无边或弧) 

            (*G).arcs[i][(*G).vexnum].adj=INFINITY;//开始化该列邻接矩阵的值(无边或弧)

        } else//图

        {

            (*G).arcs[(*G).vexnum][i].adj=0;//初始化该行邻接矩阵的值(无边或弧) 

            (*G).arcs[i][(*G).vexnum].adj=0; //开头化该列邻接矩阵的值(无边或弧) 

        }

        (*G).arcs[(*G).vexnum][i].info=NULL; //初阶化相关音讯指针

        (*G).arcs[i][(*G).vexnum].info=NULL;

    }

    (*G).vexnum+=1; //图G的顶点数加1

}

 

//开首标准: 图G存在,v是G中有些顶点。

//操作结果: 删除G中顶点v及其相关的弧 

StatusDeleteVex(MGraph *G, VertexType v) { int i, j, k;

VRType m=0;

k=LocateVex(*G, v); //k为待删除顶点v的序号

if (k<0) //v不是图G的顶点

    returnERROR;

if ((*G).kind==DN||(*G).kind==UDN) //网

    m=INFINITY;

for (j=0; j<(*G).vexnum; j++)

    //有入弧或边

    if((*G).arcs[j][k].adj!=m)  {

        if((*G).arcs[j][k].info) //有相关音讯 

            free((*G).arcs[j][k].info); //释放相关音讯 

        (*G).arcnum–; //修改弧数

    }

    if((*G).kind==DG||(*G).kind==DN) //有向

        for(j=0; j<(*G).vexnum; j++)

            //有出弧

            if((*G).arcs[k][j].adj!=m)  {

                if((*G).arcs[k][j].info) //有相关新闻

                    free((*G).arcs[k][j].info); // 释放相关音讯

                (*G).arcnum–; //修改弧数 

            }

            for(j=k+1; j<(*G).vexnum; j++)

                //序号k前边的巅峰向量依次前移

                strcpy((*G).vexs[j-1],(*G).vexs[j]);

            for(i=0; i<(*G).vexnum; i++)

                for(j=k+1; j<(*G).vexnum; j++)

                    (*G).arcs[i][j-1]=(*G).arcs[i][j];// 移动待删除顶点之后的矩阵成分 

            for(i=0; i<(*G).vexnum; i++)

                for(j=k+1; j<(*G).vexnum; j++)

                    (*G).arcs[j-1][i]=(*G).arcs[j][i];// 移动待删除顶点之下的矩阵元素 

            (*G).vexnum–; //更新图的顶点数

            returnOK;

}

 

//起首规范: 图G存在,v和W是G中七个极点

//操作结果: 在G中扩大弧<v,w>,若G是无向的,则还扩充对称弧<w,v> 

StatusInsertArc(MGraph *G, VertexType v, VertexType w) { 

    int i, l,v1, w1;

    char *info,s[MAX_INFO];

    v1=LocateVex(*G, v); //尾

    w1=LocateVex(*G, w); //头

    if(v1<0||w1<0)

        returnERROR;

    (*G).arcnum++; //弧或边数加1

    if((*G).kind%2) //网 

    {

        printf(“请输入此弧或边的权值: “);

        scanf(“%d”,&(*G).arcs[v1][w1].adj);

    } else

        //图

        (*G).arcs[v1][w1].adj=1;

    printf(“是不是有该弧或边的连锁音信(0:无 1:有): “);

    scanf(“%d%*c”,&i);

    if (i) {

        printf(“请输入该弧或边的连带音讯(<%d个字符):”, MAX_INFO);

        gets(s);

        l=strlen(s);

        if (l) {

            info=(char*)malloc((l+1)*sizeof(char));

            strcpy(info, s);

            (*G).arcs[v1][w1].info=info;

        }

    }

    //无向

    if((*G).kind>1) {

        (*G).arcs[w1][v1].adj=(*G).arcs[v1][w1].adj;

        (*G).arcs[w1][v1].info=(*G).arcs[v1][w1].info;//指向同一个有关音讯

    }

    return OK;

}

 

//开端标准: 图G存在,v和w是G中八个顶峰

//操作结果: 在G中去除弧<v,w>,若G是无向的,则还删除对称弧<w,v> 

StatusDeleteArc(MGraph *G, VertexType v, VertexType w) { 

    int v1, w1;

    v1=LocateVex(*G, v); //尾

    w1=LocateVex(*G, w); //头 

    if(v1<0||w1<0) //v1、w1的值违规

        returnERROR;

    if((*G).kind%2==0) //图 

        (*G).arcs[v1][w1].adj=0;

    else

        //网

        (*G).arcs[v1][w1].adj=INFINITY;

    //有其它新闻

    if((*G).arcs[v1][w1].info) {

        free((*G).arcs[v1][w1].info);

        (*G).arcs[v1][w1].info=NULL;

    }

    //无向,删除对称弧<w,v> 

    if((*G).kind>=2){

        (*G).arcs[w1][v1].adj=(*G).arcs[v1][w1].adj;

        (*G).arcs[w1][v1].info=NULL;

    }

    (*G).arcnum–;

    return OK;

}

 

Booleanvisited[MAX_VERTEX_NUM]; //访谈标记数组(全局变量)

Status(*VisitFunc)(VertexType);//函数变量

 

//从第v个顶峰出发递归地深度优先遍历图G。算法7.5 

void DFS(MGraph G, intv) {

    VertexType w1, v1;

    int w;

    visited[v]=TRUE; //设置访谈标识为TRUE(已拜谒) 

    VisitFunc(G.vexs[v]); //访问第v个顶点

    w=FirstAdjVex(G, v1);

    strcpy(v1, *GetVex(G, v));

    strcpy(w1, *GetVex(G, w));

    for (;w>=0; w=NextAdjVex(G, v1, w1)) {

        strcpy(w1, *GetVex(G, w));

        if(!visited[w])

            DFS(G, w);

    }//对v的尚未访谈的序号为w的分界顶点递归调用DFS 

}

 

//开端规范: 图G存在,Visit是终端的行使函数。算法7.4 

//操作结果: 从第4个顶点起,深度优先遍历图G,并对每种终端调用函数Visit, 贰遍且仅一遍。一旦Visit()失利,则操作战败 

void DFSTraverse(MGraph G, Status(*Visit)(VertexType)) { 

    printf(“\n************************************************************************\n”);

    printf(“*纵深优先遍历                                                         *\n”);

    printf(“************************************************************************\n”);

 

    int v;

    VisitFunc=Visit; //使用全局变量VisitFunc,使DFS不必设函数指针参数

    for (v=0;v<G.vexnum; v++)

        visited[v]=FALSE; //访问标识数组开头化(未被访谈)

    for (v=0;v<G.vexnum; v++) {

        if(!visited[v]) {

            DFS(G, v); //对尚未访谈的极限调用DFS 

        }

    }

    printf(“\n”);

}

 

typedef VRType QElemType; //队列类型 

#include”LinkQueue.h”//BFSTraverse()用

 

// 早先规范: 图G存在,Visit是终端的选拔函数。算法7.6 

//操作结果: 从第四个顶点起,按广度优先非递归遍历图G,并对各类终端调用函数,Visit一回且仅叁次。

//一旦Visit()战败,则操作战败。

//使用接济队列Q和做客标记数组visited 

void BFSTraverse(MGraph G,Status(*Visit)(VertexType)) { 

    printf(“\n************************************************************************\n”);

    printf(“*广度优先遍历                                                         *\n”);

    printf(“************************************************************************\n”);

 

    int v, u, w;

    VertexType w1, u1;

    LinkQueue Q;

    for (v=0;v<G.vexnum; v++)

        visited[v]=FALSE; //置初值

    InitQueue(&Q); //置空的援救队列Q

    for (v=0;v<G.vexnum; v++)

        //v尚未访问

        if(!visited[v]){

            visited[v]=TRUE; //设置访谈标识为TRUE(已拜会)

            Visit(G.vexs[v]);

            EnQueue(&Q, v); //v入队列

            //队列不空

            while(!QueueEmpty(Q)) {

                DeQueue(&Q, &u); //队头成分出队并置为u

                strcpy(u1, *GetVex(G, u));

                for(w=FirstAdjVex(G, u1); w>=0; w=NextAdjVex(G, u1, strcpy(w1,

                    *GetVex(G, w))))

                    //w为u的从未有过访问的分界顶点的序号 

                    if(!visited[w]) {

                        visited[w]=TRUE;

                        Visit(G.vexs[w]);

                        EnQueue(&Q, w);

                    }

            }

        }

        printf(“\n”);

}

 

//输出邻接矩阵G 

void Display(MGraph G) {

    int i, j;

    char s[7],s1[3];

    switch(G.kind) {

    case DG:

        strcpy(s, “有向图\0”);

        strcpy(s1, “弧\0”);

        break;

    case DN:

        strcpy(s, “有向网\0”);

        strcpy(s1, “弧\0”);

        break;

    case UDG:

        strcpy(s, “无向图\0”);

        strcpy(s1, “边\0”);

        break;

    case UDN:

        strcpy(s, “无向网\0”);

        strcpy(s1, “边\0”);

    }

 

    printf(“\n************************************************************************\n”);

    printf(“*出口%s的交界矩阵                                                 *\n”,s);

    printf(“************************************************************************\n”);

 

 

    printf(“%d个顶点%d条%s的%s\n”, G.vexnum, G.arcnum, s1, s);

    for (i=0;i<G.vexnum; ++i)

        //输出G.vexs 

        printf(“G.vexs[%d]=%s\n”,i, G.vexs[i]);

    printf(“G.arcs.adj:\n”);// 输出G.arcs.adj 

    for (i=0;i<G.vexnum; i++) {

        for(j=0; j<G.vexnum; j++)

            printf(“%6d”,G.arcs[i][j].adj);

        printf(“\n”);

    }

    printf(“G.arcs.info:\n”);//输出G.arcs.info 

    printf(“顶点1(弧尾) 顶点2(弧头) 该%s信息:\n”, s1);

    if(G.kind<2) //有向 

        for(i=0; i<G.vexnum; i++)

            for(j=0; j<G.vexnum; j++) {

                if(G.arcs[i][j].info)

                    printf(“%5s %11s    %s\n”, G.vexs[i], G.vexs[j],

                    G.arcs[i][j].info);

            }

            //无向

    else {

        for(i=0; i<G.vexnum; i++)

            for(j=i+1; j<G.vexnum; j++)

                if(G.arcs[i][j].info)

                    printf(“%5s %11s    %s\n”, G.vexs[i], G.vexs[j],

                    G.arcs[i][j].info);

    }

 

}

 

/****** 完成算法普里姆(Prim)的次序 ****/  

/******Main.cpp ***********************/

#include”Basic.h”

typedefint VRType;

typedefchar InfoType;

#define MAX_NAME 3 //顶点字符串的最大尺寸+1 

#define MAX_INFO 20 //相关音信字符串的最大尺寸+1 

typedefcharVertexType[MAX_NAME];

#include”MGraph.h”

 

//记录从巅峰集U到V-U的代价最小的边的增加帮衬数组定义

typedefstruct{ 

    VertexType adjvex;

    VRType lowcost;

}minside[MAX_VERTEX_NUM];

 

//求closedge.lowcost的一点都不大正值 

int minimum(minside closeedge,MGraph G){ 

    inti=0,j,k,min;

    while(!closeedge[i].lowcost)

        i++;

    min=closeedge[i].lowcost; //第三个不为0的值 

    k=i;

    for(j=i+1;j<G.vexnum;j++)

        if(closeedge[j].lowcost>0)

            if(min>closeedge[j].lowcost){

                min=closeedge[j].lowcost;

                k=j;

            }

            returnk;

}

 

//用普里姆算法从第u个极端出发构造网G的最小生成树T,输出T的各条边 算法7.9 

void MiniSpanTree_PRIM(MGraph G,VertexType u){ 

    printf(“\n************************************************************************\n”);

    printf(“*最小生成树的Prim算法                                                 *\n”);

    printf(“************************************************************************\n”);

 

    int i,j,k;

    minside closedge;

    k=LocateVex(G,u);

    for(j=0;j<G.vexnum;++j){//协理数组初叶化 

        if(j!=k){

            strcpy(closedge[j].adjvex,u);

            closedge[j].lowcost=G.arcs[k][j].adj;

        }

    }

    closedge[k].lowcost=0; //初始,U={u} 

    printf(“最小代价生成树的各条边为:\n”);

    for(i=1;i<G.vexnum;++i){//选取别的G.vexnum-1个顶点 

        k=minimum(closedge,G); //求出T的下贰个结点:第K顶点 

        printf(“(%s-%s)\n”,closedge[k].adjvex,G.vexs[k]);//输出生成树的边 

        closedge[k].lowcost=0; //第K顶点并入U集 

        for(j=0;j<G.vexnum;++j)

            if(G.arcs[k][j].adj<closedge[j].lowcost){//新顶点并入U集后再也选取最小边 

                strcpy(closedge[j].adjvex,G.vexs[k]);

                closedge[j].lowcost=G.arcs[k][j].adj;

            }

    }

}

 

int main(){

    MGraph G;

    CreateUDN(&G);

    MiniSpanTree_PRIM(G,”V1″);

    

    system(“pause”);

    return 0;

}

 

/****** 测验数据 **********************/  

/****** 测量检验数据.txt *******************/

输入:

6 10 0

V1

V2

V3

V4

V5

V6

V1 V2 6

V1 V3 1

V1 V4 5

V2 V3 5

V2 V5 3

V3 V4 5

V3 V5 6

V4 V6 2

V5 V6 6

V3 V6 4

 

输出:

微小代价生成树的各条边为:

(V1-V3)

(V3-V6)

(V6-V4)

(V3-V2)

(V2-V5)