注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

hurt0759的个人主页

人生常态--跋涉.人生暂态--歇息.

 
 
 

日志

 
 

数据结构--图  

2011-01-06 17:15:10|  分类: IT |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
数据结构——
2007东北大学网络学院计算机软件技术基础课程组*
图是对结点的前趋和后继个数不加限制的数据结构
较之线性表和树形结构,图是一种更为复杂的非线性数据结构
图中各数据元素之间的关系可以是任意的
描述的是"多对多"的关系
图 (Graph) 的概念
图的结构定义
图是由顶点集V和顶点间的关系集合E(边的集合)组成的一种数据结构,可以用二元组定义为:G=(V,E)
其中
V(G)是顶点的非空有限集
E(G)是边的有限集合,边是顶点的无序对或有序对
例如: G=(V,E)
V={1,2,3,4}
E={(1,2), (1,3),(1,4),(2,4),(3,4)}
1
2
3
4
图的基本术语
有向图
有向图G是由两个集合V(G)和E(G)组成的
其中
V(G)是顶点的非空有限集
E(G)是有向边(也称弧)的有限集合,弧是顶点的有序对,记为,v,w是顶点,v为弧尾,w为弧头
在图中,用箭头标明了边是有方向性的
例G1中
V(G1)={1,2,3,4,5,6}
E(G1)={, , , , , , }
2
4
5
1
3
6
G1
图的基本术语
无向图
无向图G是由两个集合V(G)和E(G)组成的
其中
V(G)是顶点的非空有限集
E(G)是边的有限集合,边是顶点的无序对,记为(v,w)或(w,v),并且(v,w)=(w,v)
在无向图中,一条边(x,y)与(y,x)表示的结果相同
例G2中
V(G2)={1,2,3,4,5,6,7}
E(G1)={(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)}
1
5
7
3
2
4
G2
6
图的基本术语
有向图和无向图表示区别
无向图中
一条边(x,y)与(y,x)表示的结果相同,用圆括号表示
有向图中
一条边与表示的结果不相同,用尖括号表示
表示从顶点x发向顶点y的边,x为始点,y为终点
有向边也称为弧,则表示为x为弧尾,y为弧头的一条弧,而表示y为弧尾,x为弧头的另一条弧
图的基本术语
有向完全图
n个顶点的有向图最大边数是n(n-1)
对于一般有向图,顶点数为n,弧数为e, 则 0≤e≤n(n-1)
例G3.
无向完全图
n个顶点的无向图最大边数是n(n-1)/2
对于一般无向图,顶点数为n,边数为e,则 0≤e ≤n(n-1)/2
例G4
无向完全图和有向完全图都称为完全图
当一个图接近完全图时,则称它为稠密图
当一个图中含有较少的边或弧时(e
2
1
3
G3
2
1
3
G4
图的基本术语
顶点(Vertex)
图中的数据元素(结点)称为顶点
邻接点
假若顶点v 和顶点w 之间存在一条边,则称顶点v 和w 互为邻接点
无向图中,若边(Vx,Vy) E,则Vx,Vy互为邻接点
有向图中,若弧 E,则Vy是Vx的邻接点,反之,不成立
图的基本术语
顶点的度
在图中,一个顶点依附的边或弧的数目,称为该顶点的度
无向图中
顶点的度为与每个顶点相连的边数
例G5中,ID(B) = 3, ID(A) = 2
有向图中
顶点的度(TD)=出度(OD)+入度(ID)
入度:以顶点为弧头的弧的数目
出度:以顶点为弧尾的弧的数目
例G6中
OD(B) = 1, ID(B) = 2, TD(B) = 3
A
C
D
F
E
B
G5
A
B
E
C
F
G6
图的基本术语

在图的边或弧中给出相关的数,称为权
权可以代表一个顶点到另一个顶点的距离,耗费等

带权的图
子图
如果图G(V,E)和图G'(V',E'),满足:V' V,E' E, 则称G'为G的子图
2
1
3
有向带权图
2
4
1
5
3
4
2
1
3
无向带权图
4
5
6
1
2
3
4
1
2
3
4
1
3
4
图的基本术语
路径
路径是顶点的序列V={Vi0,Vi1,……Vin},满足(Vij-1,Vij) E 或 E,(1
路径可能是不唯一的
例G2:路径{1324},
例G6:路径{AECFBC}
路径长度
沿路径边的数目或沿路径各边权值之和
例G2:路径{1324}的路径长度为3
1
5
7
3
2
4
G2
6
A
B
E
C
F
G6
图的基本术语
简单路径
序列中顶点不重复出现的路径
例G2:路径{1,2,5,7}
例G6:路径{AECF}
回路
序列中第一个顶点和最后一个顶点相同的路径
简单回路
除了第一个顶点和最后一个顶点外,其余顶点不重复出现的回路
例G2:路径{1,2,3,1}
例G6:路径{ABCFA}
1
5
7
3
2
4
G2
6
A
B
E
C
F
G6
图的基本术语
连通
在无向图中,从顶点V到顶点W有一条路径,则说顶点V和顶点W是连通的
连通图
若图中任意两个顶点之间都有路径相通,则称此无向图为连通图,否则称为非连通图
1
2
3
4
连通图
2
5
1
3
4
非连通图
图的基本术语
连通分量
若无向图为非连通图,则图中各个极大连通子图称作此图的连通分量
提示:
任何连通图的连通分量只有一个,即它本身
非连通图有多个连通分量
2
5
1
3
4
非连通图
2
5
1
3
4
连通图分量
图的基本术语
强连通图
有向图中,若任意两个顶点之间都存在一条有向路径,既每一对Vi,Vj V, Vi Vj,从Vi到Vj 和从Vj到 Vi都存在路径,则称此有向图为强连通图,否则称为非强连通图.
A
B
E
C
F
强连通图
A
B
E
C
F
非强连通图
图的基本术语
强连通分量
有向图中,极大的强连通子图为该图的强连通分量
提示
任何强连通图的强连通分量只有一个,即它本身
非强连通图有多个强连通分量
生成树
假设一个连通图有 n 个顶点和 e 条边,其中 n-1 条边和 n 个顶点构成一个极小连通子图,称该极小连通子图为此连通图的生成树
B
A
C
D
F
E
图的存贮结构
图结构中的结点间没有确定的关系(没根)
任意两点之间都可能存在联系,因此无法用顺序结构来存放图的顶点数据
可以借助数组表示顶点之间的关系
实际上图的存储结构常用下面两种方法表示
邻接矩阵表示法
邻接表表示法
图的存贮结构
图结构中的结点间没有确定的关系(没根)
任意两点之间都可能存在联系,因此无法用顺序结构来存放图的顶点数据
可以借助数组表示顶点之间的关系
实际上图的存储结构常用下面两种方法表示
邻接矩阵表示法
邻接表表示法
图的存贮结构——邻接矩阵表示法
图的逻辑结构分为两部分:V和E的集合
用一个一维数组存放图中所有顶点数据;
用一个二维数组存放顶点间关系(边或弧)的数据,称这个二维数组为邻接矩阵
若(i,j)∈E(G)或〈i,j〉∈E(G), 则矩阵中第i行 第j列元素值为1,否则为0 .
邻接矩阵
表示顶点间相联关系的矩阵
图的存贮结构——邻接矩阵表示法
图的邻接矩阵定义
定义:设G=(V,E)是有n 1个顶点的图,G的邻接矩阵A是具有以下性质的n阶方阵
1 若(i,j)∈E(G)或〈i,j〉∈E(G)
A[i][j]=
0 其它情形
b
d
a
c
a
b
c
d
d
c
b
a
a
e
c
b
d
d
c
b
a
e
a
b
c
d
e
图的存贮结构——邻接矩阵特点
无向图邻接矩阵的特点
矩阵是对称的
可压缩存储
有n个顶点的无向图需存储空间为n(n+1)/2
第i行或第i 列1的个数为顶点i 的度;
矩阵中1的个数的一半为图中边的数目;
很容易判断顶点i 和顶点j之间是否有边相连
只要观察矩阵中i行j列值是否为1
图的存贮结构——邻接矩阵特点
有向图邻接矩阵的特点
矩阵不一定是对称的;
有n个顶点的有向图需存储空间为n
第i 行中1的个数为顶点i 的出度;
第i 列中1的个数为顶点 i的入度;
矩阵中1的个数为图中弧的数目;
很容易判断顶点i 和顶点j 是否有弧相连
图的存贮结构
建立无向图的邻接矩阵
算法
算法的时间复杂度为O(n2)
#define MAX_V_NUM 10
typedef struct graph {
Elemtype elem [M] [M];
int n, e ;
} Graph;
void creat_v_graph (graph &g)
{ int i, j,k ;
for (k=1; k<=n; k++)
scanf("%d",&g.v[k]); / *输入顶点信息*/
for (i=1; i<=n; i++ )
for (j=1; j<=n; j++)
g.arcs[i][j]=0;
for (k=1; k<=e; k++) {
scanf("%d , %d",&i, &j); /* 输入一条边 (i, j)*/
g.arcs[i][j]=1;
g.arcs[j][i]=1;
}
}
图的存贮结构
建立有向图的邻接矩阵
算法
算法的时间复杂度为O(n2)
#define MAX_V_NUM 10
typedef struct graph {
Elemtype elem [M] [M];
int n, e ;
} Graph;
void creat_w_graph (graph &g)
{ int i, j,k ;
for (k=1; k<=n; k++)
scanf("%d",&g.v[k]); /* 输入顶点信息*/
for (i=1; i<=n; i++ )
for (j=1; j<=n; j++)
g.arcs[i][j]=0;
for (k=1; k<=e; k++) {
scanf("%d , %d",&i, &j); /*输入一条弧 */
g.arcs[i][j]=1;
}
}
图的存贮结构——邻接表表示
邻接表是图的一种链式存储结构
邻接表
将每个结点的边用一个单链表链接起来,若干个结点可以得到若干个单链表,每个单链表都有一个头结点,所有头结点组成一个一维数组,称这样的链表为邻接表
在邻接表中,每个顶点由三个域组成
adjvex data nextarc
顶点Vi的邻接点
与边或弧有关的权值
指向Vi的下一个
邻接点的指针
图的存贮结构——邻接表表示
实现
为图中每个顶点建立一个单链表(n个顶点建立n个单链表), 第i个单链表中的结点表示依附于顶点Vi的边(有向图中指以Vi为尾的弧)
每个单链表附设一个头结点的结构
Vexdata firstarc
指向Vi单链表的第一个结点
存放Vi信息
a
e
c
b
d
1
2
3
4
a
c
d
b
4
2
1
2
^
^
^
5
e
4
3
5
^
1
5
3
2
3
^
图的存贮结构——邻接表表示
b
d
a
c
1
2
3
4
a
c
d
b
3
2
4
1
^
^
^
^
B的
图的存贮结构——邻接表表示特点
无向图邻接表的特点
占用的存储单元数目为n+2e(e:边数)
第i 个链表中结点数目为顶点i的度
所有链表中结点数目的一半为图中的边数
有向图邻接表的特点
占用的存储单元数目为n+e
顶点i的出度为第i个单链表中的结点个数
若要计算入度,必须遍历整个邻接表
顶点i的入度为整个单链表中邻接点域值是i的结点个数
所有链表中结点数目为图中弧数
图的存贮结构——邻接表表示
逆邻接表
有向图的邻接表,不能求出顶点的入度.必须另外建立有向图的逆邻接表,以便求出每一个顶点的入度
有向图的逆邻接表与邻接表类似,只是它不是从出度考虑结点而是从入度考虑结点
1
2
3
4
a
c
d
b
4
1
^
1
^
^
3
^
b
d
a
c
图的存贮结构——邻接表表示
建立无向图邻接表
算法的时间复杂度为O(n+e)
#define N max_n /*max_n 表示图中最大顶点数*/
#define E max_e / *max_e图中最大边数* /
struct link { /*定义链表类型 */
elemtype data ;
link *next ;
} ;
struct node { /*定义邻接表的表头类型*/
elemtype v; /*顶点信息*/
link *next;
} Adjlist [N+1] ;
void create_v_graph (int n, int e )
{ int i,j,k ; link *s ;
for (i=1; i<=n; i++) { /*建立邻接表头结点 */
Adjlist[i].v=i ; Adjlist[i].next=NULL; }
for (k=1; kdata=j ;
s->next=Adjlist [i].next ;
Adjlist[i].next=s ;
s=new link;
s->data=i ;
s->next=Adjlist [j].next ; Adjlist[j].next=s ;
}
}
图的存贮结构——邻接表表示
建立有向图邻接表
#define N max_n /*max_n 表示图中最大顶点数*/
#define E max_e / *max_e图中最大边数* /
struct link { /*定义链表类型 */
elemtype data ;
link *next ;
} ;
struct node { /*定义邻接表的表头类型*/
elemtype v; /*顶点信息*/
link *next;
} Adjlist [N+1] ;
void create_w_graph (int n, int e )
{ int i,j,k ; link *s ;
for (i=1; i<=n;i++) { /*建立邻接表头结点*/
Adjlist[i].v=i ; Adjlist[i].next=NULL; }
for (k=1; k<=e;k++) {
scanf("%d , %d",&i , &j) ; /*输入一条边 */
s=new link; //申请一个动态存储单元
s–>data=j ; s->next=Adjlist[i].next ;
a[i].next=s ;
}
}
图的遍历
从图中指定顶点出发访问图中每一个顶点,且使每个顶点只被访问一次,该过程为图的遍历
出发点不同,任一顶点的邻接点就不相同,路径也就不同
根据搜索路径的方向不同,图的遍历有两种方法
深度优先搜索遍历
广度优先搜索遍历
图的遍历
图中元素是"多对多"的关系,图的遍历要比树结构复杂的多
若给定的图是连通图,则从图中任一顶点出发顺着边可以访问到该图中所有的顶点,但是,在图中有回路,从图中某一顶点出发访问图中其它顶点时,可能又会回到出发点,而图中可能还剩余有顶点没有访问到
设置一个全局型标志数组visited来标志某个顶点是否被访过
未访问的值为0
访问过的值为1
图的遍历——深度优先遍历(DFS)
深度优先搜索遍历类似于树的先序遍历
假定给定图G的初态是所有顶点均未被访问过,在G中任选一个顶点i作为遍历的初始点
方法
从图的某一顶点V0出发,访问此顶点;然后依次从V0的未被访问的邻接点出发,深度优先遍历图,直至图中所有和V0相通的顶点都被访问到
若此时图中尚有顶点未被访问,则另选图中一个未被访问的顶点作起点,重复上述过程,直至图中所有顶点都被访问为止
图的遍历——深度优先遍历
连通图的深度优先搜索遍历
过程
访问顶点i,并将其访问标记置为访问过,即visited[i]=1
搜索与顶点i有边相连的下一个顶点j,若j未被访问过,则访问它,并将j的访问标记置为访问过,visited[j]=1
从j开始重复此过程,若j已访问,再看与i有边相连的其它顶点
若与i有边相连的顶点都被访问过,则退回到前一个访问顶点并重复刚才过程,直到图中所有顶点都被访问完止
图的遍历——深度优先遍历
例:深度遍历:V1, V2,V4, V8 ,V5 ,V3 ,V6 ,V7
V1
V2
V4
V5
V3
V7
V6
V8
(V1,V2) (V2,V4) (V4,V8) (V8,V5)
(V1,V3)
(V3,V6)
(V3,V7)

V1
V2
V4
V8
V5
V3
V6
V7
访问顶点
起始顶点V1
V1的第1个邻接点V2
V2的第1个邻接点V1已访问, 取下一个邻接点V4
V4的第1个邻接点V2已访问, 取下一个邻接点V8
V8的第1个邻接点V4已访问, 取下一个邻接点V5
V5的两个邻接点均被访问, 回退到V8,
V8的邻接点均被访问, 回退到V4,
V4的邻接点均被访问 ,回退到V2,
V2的邻接点均被访问 ,回退到V1,
V1的另一个邻接点V3 未被访问
V3的第一个邻接点V1已被访问,V6未被访问
V6的邻接点被访问,回退到V3
V3的另一个邻接点V7 未被访问
V7的邻接点被访问,回退到V3
V3的邻接点被访问,回退到V1
回退到V1,返回到出发点,遍历结束
遍历过程
图的遍历——深度优先遍历
连通图的深度优先搜索遍历
从顶点v1出发的深度优先搜索遍历序列可能多种
例:
V1,V2,V4,V8,V5,V6,V3,V7
V1,V2,V5,V8,V4,V7,V3,V6
V1,V3,V6,V8,V7,V4,V2,V5
V1
V2
V4
V5
V3
V7
V6
V8
图的遍历——深度优先遍历算法描述
采用邻接表表示存储结构
V1,V3,V7,V6,V2,V5,V8,V4
V1
V2
V4
V5
V3
V7
V6
V8
1
2
3
4
v1
v3
v4
v2
2
7
8
3
^
^
^
5
v5
6
4
1
^
5
1
2
8
2
^
v6
v7
v8
6
7
8
7
3
6
3
5
4
^
^
^
图的遍历——深度优先遍历算法描述
采用邻接表表示存储结构
void DFS_ma ( int i )
{ // i是遍历起始点的在邻接表中的下标值,其下标从1开始
link *p;
printf("%d ", Adjlist[i].v);
visited[i]=1;
p = Adjlist[i].next;
while(p!=NULL) {
if (!visited[p->data])
DFS (p->data);
p=p->next;
}
}
图的遍历——深度优先遍历
顶点V1出发的程序执行过程
V1,V2,V5,V8,V4,V7,V3,V6
V1
V2
V4
V5
V3
V7
V6
V8
DFS(1)
DFS(2)
DFS(5)
DFS(8)
DFS(4)
DFS(7)
DFS(3)
DFS(6)
图的遍历——深度优先遍历
非连通图的深度优先搜索
从非连通的或非强连通图中某一个顶点出发,不能用深度优先搜索访问到图中所有顶点,而只能访问到一个连通子图(既连通分量)或只能访问到一个强连通子图(既强连通分量)
可以采用在每个连通分量或每个强连通分量中都选一个顶点,进行深度优先搜索遍历,最后将每个连通分量或每个强连通分量的遍历结果合起来,以得到整个非连通图的遍历结果
遍历算法实现时需要对所有顶点进行循环,反复调用连通图的深度优先搜索遍历算法
图的遍历——广度优先遍历(BFS)
广度优先遍历法类似于树的按层次遍历的过程
先访问第1个顶点所有邻接点后,再访问下一个顶点所有未被访问的邻接点
方法
从图的某一顶点V0出发,访问此顶点后,依次访问V0的各个未曾访问过的邻接点;然后分别从这些邻接点出发,广度优先遍历图,直至图中所有已被访问的顶点的邻接点都被访问到;若此时图中尚有顶点未被访问,则另选图中一个未被访问的顶点作起点,重复上述过程,直至图中所有顶点都被访问为止
图的遍历——广度优先遍历
过程
访问顶点i,并将其访问标志置为已被访问,visited[i]=1;
依次访问与顶点i有边相连的所有顶点W1,W2,…,Wn;
按顺序访问与W1,W2,…,Wn有边相连又未曾访问过的顶点
直到图中所有顶点都被访问完为止
图的遍历——广度优先遍历
例如图
V1,V2,V3,V4,V5,V6,V7,V8
V1
V2
V4
V5
V3
V7
V6
V8
(V1,V3), (V1,V2),(V1,V4)
(V2,V5),(V2,V4)
(V3,V6),(V3,V7)
(V4,V8)

V1
V3,V2
V4 , V5
V6 , V7
V8

访问顶点
起始顶点V1
访问V1的未被访问过的所有邻接点
访问V2的未被访问过的所有邻接点
访问V3的未被访问过的所有邻接点
访问V4的未被访问过的所有邻接点
访问V5的未被访问过的所有邻接点
所有顶点已被访问,结束
遍历过程
V1
V2
V4
V5
V3
V7
V6
V8
V1,V2,V3,V4,V6,V7,V8,V5
图的遍历——广度优先遍历
连通图的广度优先搜索遍历
无向图从顶点v1出发的广度优先搜索遍历序列可能多种
例:
V1,V2,V3,V4,V5,V6,V7,V8
V1,V3,V2,V7,V6,V5,V4,V8
V1,V2,V3,V5,V4,V7,V6,V8
V1
V2
V4
V5
V3
V7
V6
V8
图的遍历——广度优先遍历算法
描述
采用邻接表存储图结构,实现广度优先搜索遍历过程
void BFS_ma(int i)
{ int q[n+1] ; /*定义队列* /
int fro,rea; link *p ; /*P为搜索指针* /
fro=rea=0 ;
printf("%d",a[i].v) ;
visited[i]=1 ; rea++; q[rea]=i ; /*进队* /
while (fordata])
{ printf("%d",a[p->data].v);
visited[p->data]=1 ;
rea++;
q[r]=p->data ;
}
p=p->next;
}
}
}
图的遍历——广度优先遍历
连通图的广度优先搜索遍历
从非连通的或非强连通图中某一个顶点出发,不能用广度优先搜索遍历访问到图中所有顶点,而只能访问到一个连通子图(既连通分量)或只能访问到一个强连通子图(既强连通分量)
可以在每个连通分量或每个强连通分量中都选一个顶点,进行广度优先搜索遍历,最后将每个连通分量或每个强连通分量的遍历结果合起来,则得到整个非连通图或非强连通图的广度优先搜索遍历序列
遍历算法实现时需要对所有顶点进行循环,反复调用连通图的
图的应用——最小生成树
问题提出
假设要在 n 个城市之间建立通讯联络网,则连通 n 个城市只需要修建 n-1条线路,如何在最节省经费的前提下建立这个通讯网
该问题等价于构造网的一棵最小生成树,在 e 条带权的边中选取 n-1 条边(不构成回路),使"权值之和"为最小
图的应用——最小生成树(1)
问题分析
n个城市间,最多可设置n(n-1)/2条线路;n个城市间建立通信网,只需n-1条线路
问题转化为:在可能的线路中选择n-1条,能把 所有城市(顶点)均连起来,且总耗费 (各边权值之和)最小(即建立该通信网所需花费的总代价最小)
顶点——表示城市
权——城市间建立通信线路所需花费代价
图的应用——最小生成树(2)
方法
普里姆(Prim)算法
克鲁斯卡尔(Kruskal)算法
图的应用——最小生成树(3)
Prim算法的基本思想
取图中任意一个顶点 v 作为生成树的根,之后往生成树上添加新的顶点 w.在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边,并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小.之后继续往生成树上添加顶点,直至生成树上含有 n-1 个顶点为止
图的应用——最小生成树(4)
Prim算法的基本思想
一般情况下所添加的顶点应满足下列条件
顶点分属两个集合
已落在生成树上的顶点集 U
尚未落在生成树上的顶点集V-U
则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边
图的应用——最小生成树(5)
Prim算法实现过程
V1
V3
V5
V4
V7
V8
V6
V2
12
1
4
2
3
5
7
6
11
8
10
9
(1)U={V1}
V-U={V2,V3,V4,V5,V6,V7,V8}
(2)U={V1,V3}
V-U={V2,V4,V5,V6,V7,V8}
(3)U={V1,V3,V5}
V-U={V2,V4, V6,V7,V8}
(4)U={V1,V3,V5,V8}
V-U={V2,V4, V6,V7}
(5)U={V1,V3,V5,V8,V7}
V-U={V2,V4, V6}
(6)U={V1,V3,V5,V8,V7 , V6}
V-U={V2,V4}
(7)U={V1,V3,V5,V8,V7,V4}
V-U={V2}
(8)U={V1,V3,V5,V8,V7,V4 , V6 , V2}
V-U={}
所得生成树权值和
=1+2+3+5+6+8+10
=35
图的应用——最小生成树(6)
克鲁斯卡尔(Kruskal)算法的基本思想
出发点
为使生成树上边的权值之和达到最小,则应使生成树中每一条边的权值尽可能地小
先构造一个只含 n 个顶点的子图 SG,然后从权值最小的边开始,若它的添加不使SG 中产生回路,则在 SG 上加上这条边,如此重复,直至加上 n-1 条边为止
图的应用——最小生成树(7)
克鲁斯卡尔(Kruskal)算法的基本思想
出发点
为使生成树上边的权值之和达到最小,则应使生成树中每一条边的权值尽可能地小
先构造一个只含 n 个顶点的子图,然后从权值最小的边开始,若它的添加不使子图产生回路,则在子图上加上这条边,如此重复,直至加上 n-1 条边为止
图的应用——最小生成树(8)
克鲁斯卡尔(Kruskal)算法
设连通网N=(V,{E}),令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V,{ })
每个顶点自成一个连通分量
在E中选取代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T
否则,舍去此边,选取下一条代价最小的边
直至T中所有顶点都在同一连通分量上为止
图的应用——最小生成树(9)
Kruskal算法实现过程
V1
V3
V5
V4
V7
V8
V6
V2
12
1
4
2
3
5
7
6
11
8
10
9
  评论这张
 
阅读(4247)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017