图片 14

邻接矩阵,图的找出算法有何

By admin in 编程 on 2019年10月8日

垄断开头复习算法。于是展开那么些种类,希望得以学一些,计算一点,写在此间。便于复习,也能够方便进一步深刻的知情。

数据结构之图

图的落成方式有二种:一种是邻接矩阵,一种是邻接链表。

 --- Richardo 09/14/2015

图(Graph)

 

明天看了无向图的率先有些。首要讲了那样多少个东西。图的API,然后经过那几个API,初叶记挂找寻。七个寻找的目标。1.找寻,某多少个结点是不是连接在一块儿。2.搜寻,某五个节点是不是连接在联合,假设是,他们的最短距离是稍稍。

包含
  一组顶点:常常用V (Vertex) 表示顶点集合
  一组边:日常用E (Edge) 表示边的成团
    边是终极对:(v, w) ∈E ,在那之中v, w ∈ V
    有向边<v, w> 表示从v指向w的边(单行线)
    不思量重边和自回路

图(Graph)是三个用线或边连接在一同的极限或结点的联谊。

对此第三个。目标很纯粹。小编只需求怀想,五个点是否连接在协同,而无需思量他们是怎么连的,即便是绕了一大圈连上的,只要连上了就行了。对于第四个,目标就特别切实了,不止要判定是还是不是连接,而且必得求明了,他们中间的最短路线是何许。

无向图:边是无向边(v, w)

G = (V,E)
 //V:顶点,结点或点。E:边,弧或连线。

首先个,鲜明用DFS
越发有益。每三个源点,都以一种意见。以差异顺序的源点出发实行DFS,所达到的另外的门径很恐怕是分歧的。因为Bag集合本来便是冬辰的。然则那没事,因为纵然路线分歧,也无法改造,七个点是或不是连接的实际情况。第三个,确定是用BFS。当用来判断多少个结点的最短距离时,只可以固定的从四个点出发。那是自然的哇。算七个点的最短距离,料定是从个中三个点出发去找最短距离。

有向图:边是有向边<v, w>

依据图的边是还是不是有来头,能够把图分为有向图和无向图。

接下来说了一旦推断,八个无向图是不是存在环,当然,不思量,self-loop 和
parallel edges.

紧接:就算从V到W存在一条(无向)路线,则称V和W是对接的

而根据图的边和顶峰的关联又足以分为完全图和非完全图。完全图指的是n个极端有n(n-1)/2条边的无向图。

那是前几天早晨看的源委的八个轮廓,框架,之后临时光,会把这几个框架填好。

连通图(Connected
Graph):若是对于图的任一八个顶点v、w∈V,v和w都以对接的,则称该图为过渡图。图中随便两顶点均连通。

无向图和有向图最常用的贯彻都是基于邻接的方法。即邻接矩阵毗邻链表

 --- 09/14/2015 12:03

对接分量(Connected Component):无向图中的极菲尼克Stone子图。

 

先来谈一下图,Graph。分为有向图和无向图。又足以分为,有权值图,无权值图。小编明日攻读的,是最轻易易行的模子。无向无权值图。下边直接付出Graph的API。

  不小顶点数:再加1个顶峰就不连通了
  十分的大边数:富含子图中负有终端相连的具有边

邻接矩阵:

public class Graph { private final int V; private int E; private Bag<Integer>[] adj; public Graph { this.V = V; this.E = 0; adj = (Bag<Integer>[]) new Bag[this.V]; //泛型需要强制转换 for (int i = 0; i < this.V; i++) // initialize all lists to empty adj[i] = new Bag<Integer>(); //此处是让Bag类清空的。我觉得new出来的不就是空的么。。不能理解 } } public int V() { return this.V;} public int E() { return this.E;} public void addEddge(int v, int w) { adj[v].add; adj[w].add; E++; // don't forget to plus E } public Iterable<Integer> adj { return adj[v]; } }

强连通:有向图中顶点V和W之间存在双向路径,则称V和W是强连通的。
强连通图:有向图中随机两顶点均强连通。
强连通分量:有向图的偌大强连通子图。

n个顶点的图G=(V,E),为n*n的矩阵A。A中的每种成分是0或1。由于无向图是未有动向的,由此矩阵中(n,m)和(m,n)的值都为1,所以无向图的邻接矩阵是对称的,在积累时方可开展削减。

待补充。。。。

路子:V到W的路线是一雨后鞭笋顶点{V, v1, v2, …,vn,
W}的聚合,个中任一对附近的终点间皆有图中的边。路径的尺寸是路径中的边数(假如带权,则是独具边的权重和)。

毗邻链表:

   如若V到W之间的有着终端都比不上,则称轻巧路线
回路:起源等于终点的不二诀要

图的交界链表是作为链表保存的。

  

 

一.邻接矩阵

 

图的邻接矩阵存款和储蓄情势正是用二个二维数组来代表。

 

交界矩阵G[N][N]——N个顶点从0到N-1编号

图的物色指的是从三个加以的巅峰初叶,能够达到的顶峰的晤面。图的寻觅算法首要有广度优先找寻和纵深优先寻找。

顶点i、j有边,则G[i][j] = 1 或边的权重

 

  图片 1图片 2

图的寻找指的是从四个加以的终极最早,访谈能够到达的终端。

邻接矩阵的长处

广度优先遍历(BFS)

  直观、简单、好理解
  方便检查肆意一对顶点间是不是存在边
  方便找任一顶点的装有“邻接点”(有边直接相接的顶点)
  方便总结任一顶点的“度”(从该点发出的边数为“出度”,指向该点的边数为“入度”)
  无向图:对应行(或列)非0成分的个数
  有向图:对应行非0成分的个数是“出度”;对应列非0成分的个数是“入度”

(1)从某些顶点V出发,访谈该终端的全部邻接点V1,V2..VN

邻接矩阵的毛病

(2)从邻接点V1,V2…VN出发,再拜会他们分别的具备邻接点

  浪费空间—— 存疏弃图(点多多而边相当少)有雅量失效成分
    对稠密图(特别是截然图)依旧很合算的
    浪费时间—— 总括荒废图中一同有微微条边

(3)重复上述手续,直到全数的极端都被访谈过

图片 3图片 4

.深度优先遍历(DFS)

  1 /* ͼµÄÁÚ½Ó¾ØÕó±íʾ·¨ */
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <cstdlib> 
  5 #include <queue>
  6 using namespace std;
  7 
  8 #define MaxVertexNum 100    /* ×î´ó¶¥µãÊýÉèΪ100 */
  9 #define INFINITY 65535        /* ÉèΪ˫×Ö½ÚÎÞ·ûºÅÕýÊýµÄ×î´óÖµ65535*/
 10 typedef int Vertex;         /* Óö¥µãϱê±íʾ¶¥µã,ΪÕûÐÍ */
 11 typedef int WeightType;        /* ±ßµÄȨֵÉèΪÕûÐÍ */
 12 typedef char DataType;        /* ¶¥µã´æ´¢µÄÊý¾ÝÀàÐÍÉèΪ×Ö·ûÐÍ */
 13   
 14 /* ±ßµÄ¶¨Òå */
 15 typedef struct ENode *PtrToENode;
 16 struct ENode{
 17     Vertex V1, V2;      /* ÓÐÏò±ß<V1, V2> */
 18     WeightType Weight;  /* ȨÖØ */
 19 };
 20 typedef PtrToENode Edge;
 21          
 22 /* ͼ½áµãµÄ¶¨Òå */
 23 typedef struct GNode *PtrToGNode;
 24 struct GNode{
 25     int Nv;  /* ¶¥µãÊý */
 26     int Ne;  /* ±ßÊý   */
 27     WeightType G[MaxVertexNum][MaxVertexNum]; /* ÁÚ½Ó¾ØÕó */
 28     DataType Data[MaxVertexNum];      /* ´æ¶¥µãµÄÊý¾Ý */
 29     /* ×¢Ò⣺ºÜ¶àÇé¿öÏ£¬¶¥µãÎÞÊý¾Ý£¬´ËʱData[]¿ÉÒÔ²»ÓóöÏÖ */
 30 };
 31 typedef PtrToGNode MGraph; /* ÒÔÁÚ½Ó¾ØÕó´æ´¢µÄͼÀàÐÍ */
 32 bool Visited[MaxVertexNum] = {false};
 33 
 34 MGraph CreateGraph( int VertexNum );
 35 void InsertEdge( MGraph Graph, Edge E );
 36 MGraph BuildGraph();
 37 bool IsEdge( MGraph Graph, Vertex V, Vertex W );
 38 void InitVisited();
 39 Vertex BFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) );
 40 Vertex DFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) );
 41 Vertex listDFS( MGraph Graph, void (*Visit)(Vertex) );
 42 void DFSListComponents( MGraph Graph, void (*Visit)(Vertex) );
 43 void BFSListComponents( MGraph Graph, void (*Visit)(Vertex) ); 
 44 
 45 MGraph CreateGraph( int VertexNum )
 46 { /* ³õʼ»¯Ò»¸öÓÐVertexNum¸ö¶¥µãµ«Ã»ÓбߵÄͼ */
 47     Vertex V, W;
 48     MGraph Graph;
 49       
 50     Graph = (MGraph)malloc(sizeof(struct GNode)); /* ½¨Á¢Í¼ */
 51     Graph->Nv = VertexNum;
 52     Graph->Ne = 0;
 53     /* ³õʼ»¯ÁÚ½Ó¾ØÕó */
 54     /* ×¢Ò⣺ÕâÀïĬÈ϶¥µã±àºÅ´Ó0¿ªÊ¼£¬µ½(Graph->Nv - 1) */
 55     for (V=0; V<Graph->Nv; V++)
 56         for (W=0; W<Graph->Nv; W++)  
 57             Graph->G[V][W] = INFINITY;
 58               
 59     return Graph; 
 60 }
 61          
 62 void InsertEdge( MGraph Graph, Edge E )
 63 {
 64      /* ²åÈë±ß <V1, V2> */
 65      Graph->G[E->V1][E->V2] = E->Weight;    
 66      /* ÈôÊÇÎÞÏòͼ£¬»¹Òª²åÈë±ß<V2, V1> */
 67      Graph->G[E->V2][E->V1] = E->Weight;
 68 }
 69   
 70 MGraph BuildGraph()
 71 {
 72     MGraph Graph;
 73     Edge E;
 74     Vertex V;
 75     int Nv, i;
 76       
 77     scanf("%d", &Nv);   /* ¶ÁÈ붥µã¸öÊý */
 78     Graph = CreateGraph(Nv); /* ³õʼ»¯ÓÐNv¸ö¶¥µãµ«Ã»ÓбߵÄͼ */ 
 79       
 80     scanf("%d", &(Graph->Ne));   /* ¶ÁÈë±ßÊý */
 81     if ( Graph->Ne != 0 ) { /* Èç¹ûÓÐ±ß */ 
 82         E = (Edge)malloc(sizeof(struct ENode)); /* ½¨Á¢±ß½áµã */ 
 83         /* ¶ÁÈë±ß£¬¸ñʽΪ"Æðµã ÖÕµã ȨÖØ"£¬²åÈëÁÚ½Ó¾ØÕó */
 84         for (i=0; i<Graph->Ne; i++) {
 85             scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); 
 86             /* ×¢Ò⣺Èç¹ûȨÖز»ÊÇÕûÐÍ£¬WeightµÄ¶ÁÈë¸ñʽҪ¸Ä */
 87             InsertEdge( Graph, E );
 88         }
 89     } 
 90   
 91     /* Èç¹û¶¥µãÓÐÊý¾ÝµÄ»°£¬¶ÁÈëÊý¾Ý */
 92     for (V=0; V<Graph->Nv; V++) 
 93         scanf(" %c", &(Graph->Data[V]));
 94   
 95     return Graph;
 96 }
 97 /* ÁÚ½Ó¾ØÕó´æ´¢µÄͼ - BFS */
 98   
 99 /* IsEdge(Graph, V, W)¼ì²é<V, W>ÊÇ·ñͼGraphÖеÄÒ»Ìõ±ß£¬¼´WÊÇ·ñVµÄÁڽӵ㡣  */
100 /* ´Ëº¯Êý¸ù¾ÝͼµÄ²»Í¬ÀàÐÍÒª×ö²»Í¬µÄʵÏÖ£¬¹Ø¼üÈ¡¾öÓÚ¶Ô²»´æÔڵıߵıíʾ·½·¨¡£*/
101 /* ÀýÈç¶ÔÓÐȨͼ, Èç¹û²»´æÔڵı߱»³õʼ»¯ÎªINFINITY, Ôòº¯ÊýʵÏÖÈçÏÂ:         */
102 bool IsEdge( MGraph Graph, Vertex V, Vertex W )
103 {
104     return Graph->G[V][W]<INFINITY ? true : false;
105 }
106 
107 //³õʼ»¯ Visited[] = false
108 void InitVisited()
109 {
110     for(int i = 0; i < MaxVertexNum; i++)
111         Visited[i] = false;
112 } 
113 
114 void Visit(Vertex v)
115 {
116     printf("%d ",v);
117 }
118 
119 /* Visited[]Ϊȫ¾Ö±äÁ¿£¬ÒѾ­³õʼ»¯Îªfalse */
120 Vertex BFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) )
121 {   /* ÒÔSΪ³ö·¢µã¶ÔÁÚ½Ó¾ØÕó´æ´¢µÄͼGraph½øÐÐBFSËÑË÷ */
122     queue<Vertex> Q;     
123     Vertex V, W;
124   
125     /* ·ÃÎʶ¥µãS£º´Ë´¦¿É¸ù¾Ý¾ßÌå·ÃÎÊÐèÒª¸Äд */
126     Visit( S );
127     Visited[S] = true; /* ±ê¼ÇSÒÑ·ÃÎÊ */
128     Q.push(S); /* SÈë¶ÓÁÐ */
129       
130     while ( !Q.empty() ) {
131         V = Q.front();
132         Q.pop();      /* µ¯³öV */
133         for( W=0; W < Graph->Nv; W++ ) /* ¶ÔͼÖеÄÿ¸ö¶¥µãW */
134             /* ÈôWÊÇVµÄÁڽӵ㲢ÇÒδ·ÃÎʹý */
135             if ( !Visited[W] && IsEdge(Graph, V, W) ) {
136                 /* ·ÃÎʶ¥µãW */
137                 Visit( W );
138                 Visited[W] = true; /* ±ê¼ÇWÒÑ·ÃÎÊ */
139                 Q.push(W); /* WÈë¶ÓÁÐ */
140             }
141     } /* while½áÊø*/
142     //ÒÑÓà BFSListComponents( MGraph Graph, void (*Visit)(Vertex) )½øÐиĽø 
143 //    printf("\n");
144 //    
145 //    //±éÀú Visited[]ÁгöËùÓÐBFSµÄ¶¥µã ÈôÖ»ÐèÒ»¸ö¶¥µã¿ªÊ¼µÄBFS¿ÉºöÂÔ 
146 //    Vertex i;
147 //    for(i = 0; i < Graph->Nv; i++) {
148 //        if(Visited[i] == false)//ÕÒ³öδ±»·ÃÎʹýµÄ½áµã¼Ç¼iÖµ 
149 //            break;
150 //    }
151 //    if(i == Graph->Nv)
152 //        return 0;
153 //    else
154 //        return BFS(Graph,i,Visit);
155 }
156 
157 /* ÒÔSΪ³ö·¢µã¶ÔÁÚ½Ó¾ØÕó´æ´¢µÄͼGraph½øÐÐDFSËÑË÷ */
158 Vertex DFS ( MGraph Graph, Vertex S, void (*Visit)(Vertex) )
159 {
160     Visited[S] = true;
161     Visit(S);
162     for(Vertex w = 0; w < Graph->Nv; w++) {
163         if( IsEdge(Graph, S, w) && Visited[w]==false) {
164             DFS(Graph,w,Visit);
165         }
166     }    
167 }
168 //ÁгöDFSµÄËùÓж¥µã ÒÑÓÃDFSListComponents( MGraph Graph, void (*Visit)(Vertex) )½øÐиĽø 
169 Vertex listDFS( MGraph Graph, void (*Visit)(Vertex) )
170 {
171     Vertex i;
172     for(i = 0; i < Graph->Nv; i++) {
173         if(Visited[i] == false)//ÕÒ³öδ±»·ÃÎʹýµÄ½áµã¼Ç¼iÖµ 
174             break;
175     }
176     if(i == Graph->Nv)
177         return 0;
178     DFS(Graph, i, Visit);
179     printf("\n");
180     
181     return listDFS(Graph,Visit);
182 }
183 void DFSListComponents( MGraph Graph, void (*Visit)(Vertex) )
184 { 
185     for(Vertex i = 0; i < Graph->Nv; i++) {
186         if(Visited[i] == false) {
187             DFS(Graph, i, Visit);
188             printf("\n");
189         }
190     }      
191 }
192 void BFSListComponents( MGraph Graph, void (*Visit)(Vertex) )
193 { 
194     for(Vertex i = 0; i < Graph->Nv; i++) {
195         if(Visited[i] == false) {
196             BFS(Graph, i, Visit);
197             printf("\n");
198         }
199     }      
200 }
201 
202 int main()
203 {
204     MGraph graph;
205     graph = BuildGraph();
206     InitVisited(); 
207     listDFS(graph,&Visit);
208     InitVisited(); 
209     DFSListComponents(graph,&Visit); 
210     InitVisited(); 
211 //    BFS(graph,0,&Visit);
212     BFSListComponents(graph,&Visit); 
213     return 0;
214 } 

(1)从有些顶点V出发,访谈顶点并标识为已会见

sj5_0 图的邻接矩阵

(2)访问V的邻接点,若无访谈过,访谈该终端并标识为已走访,然后再寻访该终端的邻接点,递归实践。

 

要是该终端已拜见过,退回上一个极限,再检查该终端的邻接点是或不是都被访谈过,若是有未有访谈过的存在延续向下访谈,假诺一切都访谈过继续后退到上一个终极,继续一样的步子。

二.邻接表

 

G[N]为指针数组,对应矩阵每行多个链表,只存非0成分。

 

图片 5

——整理自《C/C++工程师·面试宝典》

邻接表的亮点
  方便找任一顶点的有着“邻接点”
  节约疏弃图的空中
  必要N个头指针+ 2E个结点(每种结点最少2个域)
  方便总计任一顶点的“度”?
    对无向图:是的
    对有向图:只可以总计“出度”;须要协会“逆邻接表”(存指向自个儿的边)来方便计算“入度”

 

邻接表的劣点

  不平价检查自便一对顶点间是或不是存在边

图片 6图片 7

  1 /* 图的邻接表表示法 */ 
  2 //build用的 头插法 尾插法遍历 出来不同 但无影响 
  3 #include <iostream>
  4 #include <cstdio>
  5 #include <cstdlib> 
  6 #include <queue>
  7 using namespace std;
  8 
  9 #define MaxVertexNum 100    /* 最大顶点数设为100 */
 10 typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
 11 typedef int WeightType;        /* 边的权值设为整型 */
 12 typedef char DataType;        /* 顶点存储的数据类型设为字符型 */
 13   
 14 /* 边的定义 */
 15 typedef struct ENode *PtrToENode;
 16 struct ENode{
 17     Vertex V1, V2;      /* 有向边<V1, V2> */
 18     WeightType Weight;  /* 权重 */
 19 };
 20 typedef PtrToENode Edge;
 21   
 22 /* 邻接点的定义 */
 23 typedef struct AdjVNode *PtrToAdjVNode; 
 24 struct AdjVNode{
 25     Vertex AdjV;        /* 邻接点下标 */
 26     WeightType Weight;  /* 边权重 */
 27     PtrToAdjVNode Next;    /* 指向下一个邻接点的指针 */
 28 };
 29   
 30 /* 顶点表头结点的定义 */
 31 typedef struct Vnode{
 32     PtrToAdjVNode FirstEdge;/* 边表头指针 */
 33     DataType Data;            /* 存顶点的数据 */
 34     /* 注意:很多情况下,顶点无数据,此时Data可以不用出现 */
 35 } AdjList[MaxVertexNum];    /* AdjList是邻接表类型 */
 36   
 37 /* 图结点的定义 */
 38 typedef struct GNode *PtrToGNode;
 39 struct GNode{  
 40     int Nv;     /* 顶点数 */
 41     int Ne;     /* 边数   */
 42     AdjList G;  /* 邻接表 */
 43 };
 44 typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */
 45 bool Visited[MaxVertexNum] = {false}; 
 46 
 47 LGraph CreateGraph( int VertexNum );
 48 void InsertEdge( LGraph Graph, Edge E );
 49 LGraph BuildGraph();
 50 void Visit( Vertex V );
 51 void InitVisited();
 52 void DFS( LGraph Graph, Vertex V, void (*Visit)(Vertex) );
 53 Vertex listDFS( LGraph Graph, void (*Visit)(Vertex) );
 54 int BFS( LGraph Graph, Vertex V, void (*Visit)(Vertex) );
 55 void DFSListComponents( LGraph Graph, void (*Visit)(Vertex) );
 56 void BFSListComponents( LGraph Graph, void (*Visit)(Vertex) );
 57  
 58 LGraph CreateGraph( int VertexNum )
 59 { /* 初始化一个有VertexNum个顶点但没有边的图 */
 60     Vertex V;
 61     LGraph Graph;
 62       
 63     Graph = (LGraph)malloc( sizeof(struct GNode) ); /* 建立图 */
 64     Graph->Nv = VertexNum;
 65     Graph->Ne = 0;
 66     /* 初始化邻接表头指针 */
 67     /* 注意:这里默认顶点编号从0开始,到(Graph->Nv - 1) */
 68        for (V=0; V<Graph->Nv; V++)
 69         Graph->G[V].FirstEdge = NULL;
 70               
 71     return Graph; 
 72 }
 73          
 74 void InsertEdge( LGraph Graph, Edge E )
 75 {
 76     PtrToAdjVNode NewNode;
 77       
 78     /* 插入边 <V1, V2> */
 79     /* 为V2建立新的邻接点 */
 80     NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
 81     NewNode->AdjV = E->V2;
 82     NewNode->Weight = E->Weight;
 83     /* 将V2插入V1的表头 */
 84     NewNode->Next = Graph->G[E->V1].FirstEdge;
 85     Graph->G[E->V1].FirstEdge = NewNode;
 86           
 87     /* 若是无向图,还要插入边 <V2, V1> */
 88     /* 为V1建立新的邻接点 */
 89     NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
 90     NewNode->AdjV = E->V1;
 91     NewNode->Weight = E->Weight;
 92     /* 将V1插入V2的表头 */
 93     NewNode->Next = Graph->G[E->V2].FirstEdge;
 94     Graph->G[E->V2].FirstEdge = NewNode;
 95 }
 96   
 97 LGraph BuildGraph()
 98 {
 99     LGraph Graph;
100     Edge E;
101     Vertex V;
102     int Nv, i;
103       
104     scanf("%d", &Nv);   /* 读入顶点个数 */
105     Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */ 
106       
107     scanf("%d", &(Graph->Ne));   /* 读入边数 */
108     if ( Graph->Ne != 0 ) { /* 如果有边 */ 
109         E = (Edge)malloc( sizeof(struct ENode) ); /* 建立边结点 */ 
110         /* 读入边,格式为"起点 终点 权重",插入邻接矩阵 */
111         for (i=0; i<Graph->Ne; i++) {
112             scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); 
113             /* 注意:如果权重不是整型,Weight的读入格式要改 */
114             InsertEdge( Graph, E );
115         }
116     } 
117   
118     /* 如果顶点有数据的话,读入数据 */
119     for (V=0; V<Graph->Nv; V++) 
120         scanf(" %c", &(Graph->G[V].Data));
121   
122     return Graph;
123 }
124 
125 void Visit( Vertex V )
126 {
127     printf("%d ", V);
128 }
129 
130 //初始化 Visited[] = false
131 void InitVisited()
132 {
133     for(int i = 0; i < MaxVertexNum; i++)
134         Visited[i] = false;
135 }  
136 
137 /* Visited[]为全局变量,已经初始化为false */
138 void DFS( LGraph Graph, Vertex V, void (*Visit)(Vertex) )
139 {   /* 以V为出发点对邻接表存储的图Graph进行DFS搜索 */
140     PtrToAdjVNode W;
141       
142     Visit( V ); /* 访问第V个顶点 */
143     Visited[V] = true; /* 标记V已访问 */
144   
145     for( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */
146         if ( !Visited[W->AdjV] )    /* 若W->AdjV未被访问 */
147             DFS( Graph, W->AdjV, Visit );    /* 则递归访问之 */
148 }
149 //已用InitVisited();进行改进 
150 Vertex listDFS( LGraph Graph, void (*Visit)(Vertex) )
151 {
152     Vertex i;
153     for(i = 0; i < Graph->Nv; i++) {
154         if(Visited[i] == false)//找出未被访问过的结点记录i值 
155             break;
156     }
157     if(i == Graph->Nv)
158         return 0;
159     DFS(Graph, i, Visit);
160     printf("\n");
161     return listDFS(Graph,Visit);
162 } 
163 //图不连通时 列出各连通分量 
164 void DFSListComponents( LGraph Graph, void (*Visit)(Vertex) )
165 { 
166     for(Vertex i = 0; i < Graph->Nv; i++) {
167         if(Visited[i] == false) {
168             DFS(Graph, i, Visit);
169             printf("\n");
170         }
171     }      
172 }
173 int BFS( LGraph Graph, Vertex V, void (*Visit)(Vertex) )
174 {
175     queue<Vertex> Q;     
176     Vertex W;
177     
178     Visit( V ); /* 访问第V个顶点 */
179     Visited[V] = true; /* 标记V已访问 */
180     Q.push(V);
181     
182     while( !Q.empty() ) {
183         W = Q.front();
184         Q.pop();
185         for(PtrToAdjVNode tempV = Graph->G[W].FirstEdge; tempV; tempV=tempV->Next ) /* 对W的每个邻接点tempV->AdjV */
186             if( !Visited[tempV->AdjV]) {
187                 Visited[tempV->AdjV] = true;
188                 Visit(tempV->AdjV);
189                 Q.push(tempV->AdjV);
190             }
191     }
192     //已用 BFSListComponents进行改进 
193 //    printf("\n");
194 //    
195 //    //遍历 Visited[]列出所有BFS的顶点 若只需一个顶点开始的BFS可忽略 
196 //    Vertex i;
197 //    for(i = 0; i < Graph->Nv; i++) {
198 //        if(Visited[i] == false)//找出未被访问过的结点记录i值 
199 //            break;
200 //    }
201 //    if(i == Graph->Nv)
202 //        return 0;
203 //    else
204 //        return BFS(Graph,i,Visit);
205     return 0;
206 }
207 //图不连通时 列出各连通分量 
208 void BFSListComponents( LGraph Graph, void (*Visit)(Vertex) )
209 { 
210     for(Vertex i = 0; i < Graph->Nv; i++) {
211         if(Visited[i] == false) {
212             BFS(Graph, i, Visit);
213             printf("\n");
214         }
215     }      
216 }
217 
218 
219 int main()
220 {
221     LGraph graph;
222     graph = BuildGraph();
223     InitVisited();
224     listDFS(graph,&Visit);
225     InitVisited();
226     DFSListComponents(graph,&Visit);
227     InitVisited();
228 //    BFS(graph, 0, &Visit);
229     BFSListComponents(graph,&Visit);
230     return 0;
231 }

sj5_1 图的邻接表

 

三.BFS广度优先寻觅(Breadth First
Search, BFS)

图片 8

应用队列,将顶点V的各种邻接点进队。(类似于树的层先遍历)

若有N个顶点、E条边,时间复杂度是

  用邻接表存款和储蓄图,有O(N+E)
  用邻接矩阵存款和储蓄图,有O(N^2)

 

四.DFS深度优先寻觅索(Depth First
Search, DFS)

图片 9

用递归(类似于树的先序遍历)。

ListComponents 图不连通时,列出各接入分量。

若有N个顶点、E条边,时间复杂度是

  用邻接表存款和储蓄图,有O(N+E)
  用邻接矩阵存款和储蓄图,有O(N^2)

 

五.最短路线

  七个不等顶点之间的有所门路中,边的权值之和纤维的那一条路径

    第二个极端为源点(Source)

    最终二个终端为终端(Destination)

 

单源最短路线难点:从某固定源点出发,求其到具有其余顶点的最短路线

无权图(无论是不是有向):依据路线长度递增(非递减)的逐一寻觅到各样顶点的最短路

图片 10

好像于BFS,运用队列

dist[W] = S到W最短距离

dist[S] = 0;

path[W] = S到W路上经过的极端

日子复杂度T = O(V + E)

图片 11图片 12

 1 /* dist[]和path[]全部初始化为-1 */
 2 void Unweighted ( LGraph Graph, int dist[], int path[], Vertex S )
 3 {
 4     queue<Vertex> Q;
 5     Vertex V;
 6     PtrToAdjVNode W;
 7      
 8     dist[S] = 0; /* 初始化源点 */
 9     Q.push(S);
10  
11     while( !Q.empty() ){
12         V = Q.front();
13         Q.pop();
14         for ( W = Graph->G[V].FirstEdge; W; W = W->Next ) /* 对V的每个邻接点W->AdjV */
15             if ( dist[W->AdjV] == -1 ) { /* 若W->AdjV未被访问过 */
16                 dist[W->AdjV] = dist[V] + 1; /* W->AdjV到S的距离更新 */
17                 path[W->AdjV] = V; /* 将V记录在S到W->AdjV的路径上 */
18                 Q.push(W->AdjV);
19             }
20     } /* while结束*/
21 }

View Code

 

有权图(无论是还是不是有向):依据递增的逐条寻找到各样顶点的最短路

Dijkstra 算法

  令S={源点s + 已经规定了最短路线的极端vi}

  对任一未收音和录音的顶点v,定义dist[v]为s到v的最短路线长度,但该路线仅透过S中的顶点。即路线{s–>(vi∈S)–>v}的微小长度

  路线是依据递增(非递减)的各类生成的,则

     的确的最短路必得只通过S中的顶点(!!!)
因为是递增的逐一生成 假设顶点w不再路线集结上
不过是最短,应该已经收音和录音了(意会。。。)

     每便从未收音和录音的顶点中选一个dist最小的选定(贪心)

     扩大二个v步向S,也许影响别的二个w的dist值!(要是收音和录音v使得s到w的门径变短,则s到w的路子一定经过v,并且v到w有一条边)

      dist[w] = min{dist[w], dist[v] + <v,w>的权重}

图片 13 白话算法:

 每一趟找到dist最小的值,即首先次找到S和第三个顶点dist最小的极度,    
         相比较创新该终端未访谈过的邻接点的dist          
                        然后直接找dist最小的

 

  图片 14

  不可能有负值圈

 

图只更新dist[]中的值 不转移邻接矩阵的值!

图片 15图片 16

 1 /* 邻接矩阵存储 - 有权图的单源最短路算法 */
 2 Vertex FindMinDist( MGraph Graph, int dist[], int collected[] )
 3 { /* 返回未被收录顶点中dist最小者 */
 4     Vertex MinV, V;
 5     int MinDist = INFINITY;
 6  
 7     for (V=0; V<Graph->Nv; V++) {
 8         if ( collected[V]==false && dist[V] < MinDist) {
 9             /* 若V未被收录,且dist[V]更小 */
10             MinDist = dist[V]; /* 更新最小距离 */
11             MinV = V; /* 更新对应顶点 */
12         }
13     }
14     if (MinDist < INFINITY) /* 若找到最小dist */
15         return MinV; /* 返回对应的顶点下标 */
16     else return ERROR;  /* 若这样的顶点不存在,返回错误标记 */
17 }
18  
19 bool Dijkstra( MGraph Graph, int dist[], int path[], Vertex S )
20 {
21     int collected[MaxVertexNum];
22     Vertex V, W;
23  
24     /* 初始化:此处默认邻接矩阵中不存在的边用INFINITY表示 */
25     for ( V=0; V < Graph->Nv; V++ ) {
26         dist[V] = Graph->G[S][V];
27         path[V] = -1;
28         collected[V] = false;
29     }
30     /* 先将起点收入集合 */
31     dist[S] = 0;
32     collected[S] = true;
33  
34     while (1) {
35         /* V = 未被收录顶点中dist最小者 */
36         V = FindMinDist( Graph, dist, collected );
37         if ( V==ERROR ) /* 若这样的V不存在 */
38             break;      /* 算法结束 */
39         collected[V] = true;  /* 收录V */
40         for( W = 0; W < Graph->Nv; W++ ) /* 对图中的每个顶点W */
41             /* 若W是V的邻接点并且未被收录 */
42             if ( collected[W]==false && Graph->G[V][W]<INFINITY ) {
43                 if ( Graph->G[V][W]<0 ) /* 若有负边 */
44                     return false; /* 不能正确解决,返回错误标记 */
45                 /* 若收录V使得dist[W]变小 */
46                 if ( dist[V]+Graph->G[V][W] < dist[W] ) {
47                     dist[W] = dist[V] + Graph->G[V][W]; /* 更新dist[W] */
48                     path[W] = V; /* 更新S到W的路径 */
49                 }
50             }
51     } /* while结束*/
52     return true; /* 算法执行完毕,返回正确标记 */
53 }

View Code

有关找小小dist

  ①直接围观全数未收音和录音顶点-O(V)

    T=O(V^2+E)   —>对于稠密图效果好

  ②将dist存在最小堆中-O(logV)

    更新dist(W)的值-O(logV)

    T = O(VlogV+ElogV) = O(ElogV)    —>对于稠萧疏图效果好

 

多源最短路线难点:求自便两顶点间的最短路线

方式一:直接将单源最短路算法调用V遍

    T = O(V^3 + E*V)   —>对于萧条图效果好

主意二:Floyd算法  —>对于稠密图效果好

    T = O(V^3)

Floyd 算法

  Dk[i][j] = 路线{ i -> { l ≤ k } -> j }的微小长度

  D0, D1, …, D|V|-1[i][j]即给出了i到j的确实最短距离

  最先的D-1是邻接矩阵

  当Dk-1已经产生,递推到Dk时:

    或然k ∉最短路线{ i -> { l ≤ k } -> j },则Dk = Dk-1

    也许k ∈最短路线{ i -> { l ≤ k } -> j
},则该路线必定由两段最短路径组成:
Dk[i][j]=Dk-1[i][k]+Dk-1[k][j]

图片 17图片 18

 1 /* 邻接矩阵存储 - 多源最短路算法 */
 2  
 3 bool Floyd( MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum] )
 4 {
 5     Vertex i, j, k;
 6  
 7     /* 初始化 */
 8     for ( i=0; i<Graph->Nv; i++ )
 9         for( j=0; j<Graph->Nv; j++ ) {
10             D[i][j] = Graph->G[i][j];
11             path[i][j] = -1;
12         }
13  
14     for( k=0; k<Graph->Nv; k++ )
15         for( i=0; i<Graph->Nv; i++ )
16             for( j=0; j<Graph->Nv; j++ )
17                 if( D[i][k] + D[k][j] < D[i][j] ) {
18                     D[i][j] = D[i][k] + D[k][j];
19                     if ( i==j && D[i][j]<0 ) /* 若发现负值圈 */
20                         return false; /* 不能正确解决,返回错误标记 */
21                     path[i][j] = k;
22                 }
23     return true; /* 算法执行完毕,返回正确标记 */
24 }

View Code

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图
Copyright @ 2010-2019 澳门新葡亰官网app 版权所有