您的位置: 首页  >  IT文章  >  数据结构学习笔记05图 (邻接矩阵 邻接表-->BFS DFS、最短路径)

数据结构学习笔记05图 (邻接矩阵 邻接表-->BFS DFS、最短路径)

分类: IT文章 • 2024-02-05 16:00:00

数据结构之图

图(Graph)

包含
　　一组顶点：通常用V (Vertex) 表示顶点集合
　　一组边：通常用E (Edge) 表示边的集合
　　　　边是顶点对：(v, w) ∈E ，其中v, w ∈ V
　　　　有向边<v, w> 表示从v指向w的边（单行线）
　　　　不考虑重边和自回路

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

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

连通：如果从V到W存在一条（无向）路径，则称V和W是连通的

连通图(Connected Graph)：如果对于图的任一两个顶点v、w∈V，v和w都是连通的，则称该图为连通图。图中任意两顶点均连通。

连通分量(Connected Component):无向图中的极大连通子图。

　　极大顶点数：再加1个顶点就不连通了
　　极大边数：包含子图中所有顶点相连的所有边

强连通：有向图中顶点V和W之间存在双向路径，则称V和W是强连通的。
强连通图：有向图中任意两顶点均强连通。
强连通分量：有向图的极大强连通子图。

路径：V到W的路径是一系列顶点{V, v1, v2, …,vn, W}的集合，其中任一对相邻的顶点间都有图中的边。路径的长度是路径中的边数（如果带权，则是所有边的权重和）。

　　　如果V到W之间的所有顶点都不同，则称简单路径
回路：起点等于终点的路径

　　

一.邻接矩阵

图的邻接矩阵存储方式就是用一个二维数组来表示。

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

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

　　数据结构学习笔记05图 (邻接矩阵 邻接表-->BFS DFS、最短路径)数据结构学习笔记05图 (邻接矩阵 邻接表-->BFS DFS、最短路径)

邻接矩阵的优点

　　直观、简单、好理解
　　方便检查任意一对顶点间是否存在边
　　方便找任一顶点的所有“邻接点”（有边直接相连的顶点）
　　方便计算任一顶点的“度”（从该点发出的边数为“出度”，指向该点的边数为“入度”）
　　无向图：对应行（或列）非0元素的个数
　　有向图：对应行非0元素的个数是“出度”；对应列非0元素的个数是“入度”

邻接矩阵的缺点

　　浪费空间—— 存稀疏图（点很多而边很少）有大量无效元素
　　　　对稠密图（特别是完全图）还是很合算的
　　　　浪费时间—— 统计稀疏图中一共有多少条边

  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("
");
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("
");
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("
");
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("
");
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 }
sj5_0 图的邻接矩阵

二.邻接表

G[N]为指针数组，对应矩阵每行一个链表，只存非0元素。

数据结构学习笔记05图 (邻接矩阵 邻接表-->BFS DFS、最短路径)

邻接表的优点
　　方便找任一顶点的所有“邻接点”
　　节约稀疏图的空间
　　需要N个头指针+ 2E个结点（每个结点至少2个域）
　　方便计算任一顶点的“度”？
　　　　对无向图：是的
　　　　对有向图：只能计算“出度”；需要构造“逆邻接表”（存指向自己的边）来方便计算“入度”

邻接表的缺点

　　不方便检查任意一对顶点间是否存在边

  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("
");
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("
");
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("
");
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("
");
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)

数据结构学习笔记05图 (邻接矩阵 邻接表-->BFS DFS、最短路径)

运用队列，将顶点V的每个邻接点进队。(类似于树的层先遍历)

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

　　用邻接表存储图，有O(N+E)
　　用邻接矩阵存储图，有O(N^2)

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

数据结构学习笔记05图 (邻接矩阵 邻接表-->BFS DFS、最短路径)

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

ListComponents 图不连通时，列出各连通分量。

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

　　用邻接表存储图，有O(N+E)
　　用邻接矩阵存储图，有O(N^2)

五.最短路径

　　两个不同顶点之间的所有路径中，边的权值之和最小的那一条路径

　　　　第一个顶点为源点(Source)

　　　　最后一个顶点为终点(Destination)

单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径

无权图(无论是否有向)：按照路径长度递增（非递减）的顺序找出到各个顶点的最短路

数据结构学习笔记05图 (邻接矩阵 邻接表-->BFS DFS、最短路径)

类似于BFS，运用队列

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

dist[S] = 0;

path[W] = S到W路上经过的顶点

时间复杂度T = O(V + E)

 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>的权重}

数据结构学习笔记05图 (邻接矩阵 邻接表-->BFS DFS、最短路径)　白话算法：

　每次找到dist最小的值，即第一次找到S和第二个顶点dist最小的那个，　　　　          比较更新该顶点未访问过的邻接点的dist　　　　       　　　　　　　　　　              然后一直找dist最小的

　　数据结构学习笔记05图 (邻接矩阵 邻接表-->BFS DFS、最短路径)

　　不能有负值圈

图只更新dist[]中的值 不改变邻接矩阵的值！

 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]

 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

相关推荐