6.1 图的逻辑结构
图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为: G=(V,E)
其中:G表示一个图,V是图G中顶点的集合,E是图G中顶点之间边的集合。
在线性表中,元素个数可以为零,称为空表;
在树中,结点个数可以为零,称为空树;
在图中,顶点个数不能为零,但可以没有边。
若顶点vi和vj之间的边没有方向,则称这条边为无向边,表示为(vi,vj)。
如果图的任意两个顶点之间的边都是无向边,则称该图为无向图。
若从顶点vi到vj的边有方向,则称这条边为有向边,表示为<vi,vj>。
如果图的任意两个顶点之间的边都是有向边,则称该图为有向图。
简单图:在图中,若不存在顶点到其自身的边,且同一条边不重复出现。
数据结构中讨论的都是简单图。
邻接、依附
无向图中,对于任意两个顶点vi和顶点vj,若存在边(vi,vj),则称顶点vi和顶点vj互为邻接点,同时称边(vi,vj)依附于顶点vi和顶点vj。
有向图中,对于任意两个顶点vi和顶点vj,若存在弧<vi,vj>,则称顶点vi邻接到顶点vj,顶点vj邻接自顶点vi,同时称弧<vi,vj>依附于顶点vi和顶点vj 。
在线性结构中,数据元素之间仅具有线性关系;
在树结构中,结点之间具有层次关系;
在图结构中,任意两个顶点之间都可能有关系。
无向完全图:在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图。
有向完全图:在有向图中,如果任意两个顶点之间都存在方向相反的两条弧,则称该图为有向完全图。
含有n个顶点的无向完全图有n×(n-1)/2条边。
含有n个顶点的有向完全图有**n×(n-1)**条边。
稀疏图:称边数很少的图为稀疏图;
稠密图:称边数很多的图为稠密图。
顶点的度:在无向图中,顶点v的度是指依附于该顶点的边数,通常记为TD (v)。
顶点的入度:在有向图中,顶点v的入度是指以该顶点为弧头的弧的数目,记为ID (v);
顶点的出度:在有向图中,顶点v的出度是指以该顶点为弧尾的弧的数目,记为OD (v)。
在具有n个顶点、e条边的无向图G中,各顶点的度之和与边数之和的关系?在具有n个顶点、e条边的有向图G中,各顶点的入度之和与各顶点的出度之和的关系?与边数之和的关系?
权:是指对边赋予的有意义的数值量。
网:边上带权的图,也称网图。
路径:在无向图G=(V, E)中,从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2, …, vim=vq),其中,(vij1,vij)∈E(1≤j≤m)。若G是有向图,则路径也是有方向的,顶点序列满足<vij-1,vij>∈E。回路(环):第一个顶点和最后一个顶点相同的路径。
简单路径:序列中顶点不重复出现的路径。
简单回路(简单环):除了第一个顶点和最后一个顶点外,其余顶点不重复出现的回路。
子图:若图G=(V,E),G’=(V’,E’),如果V’⊆V 且E’ ⊆ E ,则称图G’是G的子图。
连通图:在无向图中,如果从一个顶点vi到另一个顶点vj(i≠j)有路径,则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的,则称该图是连通图。
连通分量:非连通图的极大连通子图称为连通分量。强连通图:在有向图中,对图中任意一对顶点vji和vj (i≠j),若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径,则称该有向图是强连通图。
强连通分量:非强连通图的极大强连通子图。
生成树:n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。生成森林:在非连通图中,由每个连通分量都可以得到一棵生成树,这些连通分量的生成树就组成了一个非连通图的生成森林。
- 图的遍历操作
图的遍历是从图中某一顶点出发,对图中所有顶点访问一次且仅访问一次。
- 在图中,如何选取遍历的起始顶点?
解决方案:从编号小的顶点开始 。
在线性表中,数据元素在表中的编号就是元素在序列中的位置,因而其编号是唯一的;
在树中,将结点按层序编号,由于树具有层次性,因而其层序编号也是唯一的;
在图中,任何两个顶点之间都可能存在边,顶点是没有确定的先后次序的,所以,顶点的编号不唯一。
为了定义操作的方便,将图中的顶点按任意顺序排列起来,比如,按顶点的存储顺序。
- 从某个起点始可能到达不了所有其它顶点,怎么办?
解决方案:多次调用从某顶点出发遍历图的算法。
- 因图中可能存在回路,某些顶点可能会被重复访问,那么如何避免遍历不会因回路而陷入死循环?
解决方案:附设访问标志数组visited[n] 。
- 在图中,一个顶点可以和其它多个顶点相连,当这样的顶点访问过后,如何选取下一个要访问的顶点?
解决方案:深度优先遍历和广度优先遍历。
1.深度优先遍历 (DFS:Depth First Search)
⑴ 访问顶点v;
⑵ 从v的未被访问的邻接点中选取一个顶点w,从w出发进行深度优先遍历;
⑶ 重复上述两步,直至图中所有和v有路径相通的顶点都被访问到。
2.广度优先遍历 (BFS:Broad First Search ;FIFO: First In First Out)
⑴ 访问顶点v;
⑵ 依次访问v的各个未被访问的邻接点v1, v2, …, vk;
⑶ 分别从v1,v2,…,vk出发依次访问它们未被访问的邻接点,并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。
6.2 图的存储结构及实现
基本思想:
用一个一维数组存储图中顶点的信息
用一个二维数组(称为邻接矩阵)存储图中各顶点之间的邻接关系。
假设图G=(V,E)有n个顶点,则邻接矩阵是一个n×n的方阵,定义为:无向图的邻接矩阵
无向图的邻接矩阵的特点:
主对角线为 0 且一定是对称矩阵。
求顶点i的度:
邻接矩阵的第i行(或第i列)非零元素的个数。
判断顶点 i 和 j 之间是否存在边:
测试邻接矩阵中相应位置的元素arc[i][j]是否为1。
求顶点 i 的所有邻接点:
将数组中第 i 行元素扫描一遍,若arc[i][j]为1,则顶点 j 为顶点 i 的邻接点。
有向图的邻接矩阵
有向图的邻接矩阵一定不对称?
不一定,例如有向完全图。
求顶点 i 的出度:
邻接矩阵的第 i 行元素之和。
求顶点 i 的入度:
邻接矩阵的第 i 列元素之和。
判断从顶点 i 到顶点 j 是否存在边:
测试邻接矩阵中相应位置的元素arc[i][j]是否为1。
网图的邻接矩阵
网图邻接矩阵可定义为的:邻接矩阵存储无向图的类
const int MaxSize=10;
template <class T>
class Mgraph{
public:
MGraph(T a[ ], int n, int e );
~MGraph( )
void DFSTraverse(int v);
void BFSTraverse(int v);
……
private:
T vertex[MaxSize];
int arc[MaxSize][MaxSize];
int vertexNum, arcNum;
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 构造函数MGraph(T a[ ], int n, int e );
1、确定图的顶点个数和边的个数;
2、输入顶点信息存储在一维数组vertex中;
3、初始化邻接矩阵;
4、依次输入每条边存储在邻接矩阵arc中;
4.1 输入边依附的两个顶点的序号i, j;
4.2 将邻接矩阵的第i行第j列的元素值置为1;
4.3 将邻接矩阵的第j行第i列的元素值置为1;
template <class T>
MGraph::MGraph(T a[ ], int n, int e) {
vertexNum=n; arcNum=e;
for (i=0; i<vertexNum; i++)
vertex[i]=a[i];
for (i=0; i<vertexNum; i++) //初始化邻接矩阵
for (j=0; j<vertexNum; j++)
arc[i][j]=0;
for (k=0; k<arcNum; k++) {
cin>>i>>j; //边依附的两个顶点的序号
arc[i][j]=1; arc[j][i]=1; //置有边标志
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 深度优先遍历
⑴ 访问顶点v;
⑵ 从v的未被访问的邻接点中选取一个顶点w,从w出发进行深度优先遍历;
⑶ 重复上述两步,直至图中所有和v有路径相通的顶点都被访问到。
递归定义
int visited[MaxSize];
template <class T>
void MGraph::DFSTraverse(int v)
{
cout<<vertex[v]; visited [v]=1;
for (j=0; j<vertexNum; j++)
if (arc[v][j]==1 && visited[j]==0)
DFSTraverse( j );
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 广度优先遍历
⑴ 访问顶点v;
⑵ 依次访问v的各个未被访问的邻接点v1, v2, …, vk;
⑶ 分别从v1,v2,…,vk出发依次访问它们未被访问的邻接点,并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。
int visited[MaxSize];
template <class T>
void MGraph::BFSTraverse(int v){
front=rear=-1; //假设采用顺序队列且不会发生溢出
int Q[MaxSize]; cout<<vertex[v]; visited[v]=1; Q[++rear]=v;
while (front!=rear) {
v=Q[++front];
for (j=0; j<vertexNum; j++)
if (arc[v][j]==1 && visited[j]==0 ) {
cout<<vertex[j]; visited[j]=1; Q[++rear]=j;
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
邻接表
邻接表存储的基本思想:
对于图的每个顶点vi,将所有邻接于vi的顶点链成一个单链表,称为顶点vi的边表(对于有向图则称为出边表)
所有边表的头指针和存储顶点信息的一维数组构成了顶点表。
邻接表有两种结点结构:顶点表结点和边表结点。vertex:数据域,存放顶点信息。
firstedge:指针域,指向边表中第一个结点。
adjvex:邻接点域,边的终点在顶点表中的下标。
next:指针域,指向边表中的下一个结点。
定义邻接表的结点 :
struct ArcNode
{
int adjvex;
ArcNode *next;
};
template <class T>
struct VertexNode
{
T vertex;
ArcNode *firstedge;
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 无向图的邻接表
边表中的结点表示:
每个结点对应图中的一条边,
邻接表的空间复杂度为O(n+e)。
求顶点 i 的度:
顶点i的边表中结点的个数。
判断顶点 i 和顶点 j之间是否存在边:
测试顶点 i 的边表中是否存在终点为 j 的结点。
- 有向图的邻接表(出边表)
求顶点 i 的出度:
顶点 i 的出边表中结点的个数。
求顶点 i 的入度:
各顶点的出边表中以顶点 i 为终点的结点个数。
求顶点 i 的所有邻接点:
遍历顶点 i 的边表,该边表中的所有终点都是顶点 i 的邻接点。
- 邻接表存储有向图的类
const int MaxSize=10; //图的最大顶点数
template <class T>
class ALGraph
{
public:
ALGraph(T a[ ], int n, int e);
~ALGraph;
void DFSTraverse(int v);
void BFSTraverse(int v);
………
private:
VertexNode adjlist[MaxSize];
int vertexNum, arcNum;
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 构造函数
- 确定图的顶点个数和边的个数;
- 输入顶点信息,初始化该顶点的边表;
- 依次输入边的信息并存储在边表中;
3.1 输入边所依附的两个顶点的序号i和j;
3.2 生成邻接点序号为j的边表结点s;
3.3 将结点s插入到第i个边表的头部;
template <class T>
ALGraph::ALGraph(T a[ ], int n, int e)
{
vertexNum=n; arcNum=e;
for (i=0; i<vertexNum; i++)
{
adjlist[i].vertex=a[i];
adjlist[i].firstedge=NULL;
}
for (k=0; k<arcNum; k++)
{
cin>>i>>j;
s=new ArcNode;s->adjvex=j;
s->next=adjlist[i].firstedge;
adjlist[i].firstedge=s;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 深度优先遍历
template <class T>
void ALGraph::DFSTraverse(int v){
cout<<adjlist[v].vertex; visited[v]=1;
p=adjlist[v].firstedge;
while (p!=NULL) {
j=p->adjvex;
if (visited[j]==0) DFSTraverse(j);
p=p->next;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 广度优先遍历
template <class T>
void ALGraph::BFSTraverse(int v){
front=rear=-1;
cout<<adjlist[v].vertex; visited[v]=1; Q[++rear]=v;
while (front!=rear) {
v=Q[++front]; p=adjlist[v].firstedge;
while (p!=NULL) {
j= p->adjvex;
if (visited[j]==0) {
cout<<adjlist[j].vertex; visited[j]=1; Q[++rear]=j;
}
p=p->next;
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 十字链表:有向图的链式存储结构
- 邻接多重表 :无向图的存储结构
- 边集数组
利用两个一维数组
一个数组存储顶点信息,另外一个数组存储边及其权
其中,数组分量包含三个域:边所依附的两个顶点,权值
各边在数组中的次序可以任意。
应用举例——最小生成树
生成树的代价:设G=(V,E)是一个无向连通网,生成树上各边的权值之和称为该生成树的代价。
最小生成树:在图G所有生成树中,代价最小的生成树称为最小生成树。
普里姆(Prim)算法
基本思想:
设G=(V, E)是具有n个顶点的连通网,
T=(U, TE)是G的最小生成树,
T的初始状态为U={u0}(u0∈V),TE={ },
重复执行下述操作:
在所有u∈U,v∈V-U的边中找一条代价最小的边(u, v)并入集合TE,同时v并入U,直至U=V。
Prim算法——伪代码:
- 初始化两个辅助数组lowcost(=arc[0][i])和adjvex(=0)(0是始点);
- 输出顶点u0,将顶点u0加入集合U中;
- 重复执行下列操作n-1次
3.1 在lowcost中选取最短边(lowcost[k]),取对应的顶点序号k;
3.2 输出顶点k和对应的权值;
3.3 将顶点k加入集合U中(lowcost[k]=0);
3.4 调整数组lowcost和adjvex;
Void prime(MGraph G){
for(int i=1;i<G.vertexNu;i++){
lowcost[i]=G.arc[0][i]; adjvex[i]=0;
}
lowcost[0]=0;
for(i=1;i<G.vertexNum;i+++){
k=MinEdge(lowcost,G.vertexNum)
cout<<K<<adjvex[k]<<lowcost[k];
lowcost[k]=0;
for(j=1;j<G.vertexNum;j++)
if((G.arc[k][j]<lowcost[j]){
lowcost[j]=G.arc[k][j];
arcvex[j]=k;
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
克鲁斯卡尔(Kruskal)算法
1、设无向连通网为G=(V, E),令G的最小生成树为T=(U, TE),其初态为U=V,TE={ },
2、然后,按照边的权值由小到大的顺序,考察G的边集E中的各条边。
2.1.若被考察的边的两个顶点属于T的两个不同的连通分量,则将此边作为最小生成树的边加入到T中,同时把两个连通分量连接为一个连通分量;
2.2.若被考察边的两个顶点属于同一个连通分量,则舍去此边,以免造成回路,
3、如此下去,当T中的连通分量个数为1时,此连通分量便为G的一棵最小生成树。
Kruskal算法思想:
- 初始化:U=V; TE={ };
- 循环直到T中的连通分量个数为1
2.1 在E中寻找最短边(u,v);
2.2 如果顶点u、v位于T的两个不同连通分量,则
2.2.1 将边(u,v)并入TE;
2.2.2 将这两个连通分量合为一个;
2.3 在E中标记边(u,v),使得(u,v)不参加后续最短边的选取;
Kruskal算法实现中的三个关键问题:
- 图的存储结构:采用边集数组存储图。
- 如何判断一条边所依附的两个顶点在同一个连通分两中(并查集)
定义Parent[i]数组。数组分量的值表示顶点i的双亲节点(初值为-1;)
当一条边(u,v)的两个顶点的根结不同时,这两个结点属于不同的连通分量(利用parent 数组查找一棵树的根节点。当一个结点n的parent==-1,树的根节点即为n) - 如何将一条边所依附的两个顶点合并到同一个连通分量中
要进行联通分量的合并 ,其中一个顶点所在的树的根节点为vex1,另一个顶点所在的树的根节点为vex2,则:parent[vex2]=vex1;
Kruskal算法的时间复杂性分析:
边集数组排序,时间复杂性O(eloge)
在e条边中选边,时间复杂性为O(e)
因此时间复杂性为O(eloge)
6.5 最短路径
在非网图中,最短路径是指两顶点之间经历的边数最少的路径。
在网图中,最短路径是指两顶点之间经历的边上权值之和最短的路径。
单源点到其他顶点的最短路径
Dijkstra方法,O(n2)
任意一对顶点之间的最短路径
Floyd方法,O(n3)
- 单源点最短路径问题
问题描述:给定带权有向图G=(V, E)和源点v∈V,求从v到G中其余各顶点的最短路径。
迪杰斯特拉(Dijkstra)提出了一个按路径长度递增的次序产生最短路径的算法——Dijkstra算法。
路径长度递增的理解:
含有n个顶点的图
计算图中顶点v到其他顶点(n-1个)的最短路
总共要找多少条最短路?
n-1条
按路径长度递增指的是这n-1条路的计算原则即,
先找第一条最短路(v,vi),所有n-1条路中最短的路
再找第二条最短路(v,vj)
…
基本思想:
1、设置一个集合S存放已经找到最短路径的顶点,S的初始状态只包含源点v,
2、对vi∈V-S,假设从源点v到vi的有向边为最短路径(从v到其余顶点的最短路径的初值)。
3、以后每求得一条最短路径v, …, vk,就将vk加入集合S中,并将路径v, …, vk , vi与原来的假设相比较,取路径长度较小者为最短路径。
重复上述过程,直到集合V中全部顶点加入到集合S中。
路径长度最短的最短路径(即第一条最短路)的特点:
在这条路径上,必定只含一条边,并且这条边上的权值最小。
下一条路径长度次短的最短路径的特点:
它只可能有两种情况:
或者是直接从源点到该点(只含一条边);
或者是从源点经过顶点v1(第一条最短路径所依附的顶点),再到达该顶点(由两条边组成)。
再下一条路径长度次短的最短路径的特点:
它可能有四种情况:或者是直接从源点到该点(只含一条边); 或者从源点经过顶点v1,再到达该顶点(由两条边组成);或者是从源点经过顶点v2,再到达该顶点(两条条边);或者是从源点经过顶点v1、v2,再到达该顶点(多条边)。
其余最短路径的特点:
它或者是直接从源点到该点(只含一条边); 或者是从源点经过已求得最短路径的顶点(集合S中的顶点),再到达该顶点。
数据结构 :
图的存储结构:邻接矩阵存储结构
数组dist[n]:每个分量dist[i]表示当前所找到的从始点v到终点vi的最短路径的长度。初态为:若从v到vi有弧,则dist[i]为弧上权值;否则置dist[i]为∞。
数组path[n]:path[i]是一个字符串,表示当前所找到的从始点v到终点vi的最短路径。初态为:若从v到vi有弧,则path[i]为vvi;否则置path[i]空串。
数组s[n]:存放源点和已经找到最短路径的终点,其初态为只有一个源点v。
迪杰斯特拉算法的主要步骤如下:
(1) g为用邻接矩阵表示的带权图。
S←{v0} , dist[i]= g.arcs[v0][vi],path[i]=“v0vi”或“”;
将v0到其余顶点的路径长度初始化为权值;
(2) 选择vk,使得dist[vk]=min(dist[i] | vi∈V-S)
vk为目前求得的下一条从v0出发的最短路径的终点。
将vk加入到S中
(3) 修改从v0出发到集合V-S上任一顶点vi的最短路径的长度。如果
dist[k]+ g.arcs[k][i]<dist[i];则将dist[i]修改为dist[k]+ g.arcs[k][i];path[i]=path[k]+”vi”;
(4) 重复(2)、(3) n-1次,即可按最短路径长度的递增顺序,逐个求出v0到图中其它每个顶点的最短路径。
const int MAX=1000;
void Dijkstra(MGraph g, int v){
for ( i =0; i<g.vexnum ; i++){
dist[i]=g.arcs[v][i];
if ( dist[i]!= MAX)
path [i]=g.vertex[v]+g.vertex[i];
else
path[i]=“”;
}
S[0]=g.vertex[v];
num=1;
While (num<g.vextexNum){
k=0;
for(i=0;i<G.vertexNum;i++)
if((dist[i]<dist[k]) k=i
cout<<dist[k]<<path[k];
s[num++]=G.vertex[k];
for(i=0;i<G.vertexNum;i++)
if(dist[k]+g.arc[k][i]<dist[i] {
dist[i]=dist[k]+g.arc[k][i];
path[i]=path[k]+g.vertex[i];
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 每一对顶点之间的最短路径
问题描述:给定带权有向图G=(V, E),对任意顶点vi,vj∈V(i≠j),求顶点vi到顶点vj的最短路径。
解决办法1:每次以一个顶点为源点,调用Dijkstra算法n次。显然,时间复杂度为O(n3)。
解决办法2:弗洛伊德提出的求每一对顶点之间的最短路径算法——Floyd算法,其时间复杂度也是O(n3),但形式上要简单些。
Floyd算法的基本思想:
设图g用邻接矩阵法表示,
求图g中任意一对顶点vi、 vj间的最短路径。
(-1) 将vi到vj 的最短的路径长度初始化为(vi,vj), 然后进行如下n次比较和修正:
(0) 在vi、vj间加入顶点v0,比较(vi, v0, vj)和(vi, vj)的路径的长度,取其中较短的路径作为vi到vj的且中间顶点号不大于0的最短路径。
(1) 在vi、vj间加入顶点v1,得(vi, …,v1)和(v1, …,vj),其中:(vi, …, v1)是vi到v1 的且中间顶点号不大于0的最短路径,(v1, …, vj) 是v1到vj 的且中间顶点号不大于0的最短路径,这两条路径在上一步中已求出。
将(vi, …, v1, …, vj)与上一步已求出的且vi到vj 中间顶点号不大于0的最短路径比较,取其中较短的路径作为vi到vj 的且中间顶点号不大于1的最短路径。
(2)在vi、vj间加入顶点v2,得(vi, …, v2)和(v2, …, vj),其中:(vi, …, v2)是vi到v2 的且中间顶点号不大于1的最短路径,(v2, …, vj) 是v2到vj 的且中间顶点号不大于1的最短路径,这两条路径在上一步中已求出。
将(vi, …, v2, …, vj)与上一步已求出的且vi到vj 中间顶点号不大于1的最短路径比较, 取其中较短的路径作为vi到vj 的且中间顶点号不大于2的最短路径。
……
数据结构:
图的存储结构:带权的邻接矩阵存储结构
数组dist[n][n]:存放在迭代过程中求得的最短路径长度。迭代公式:数组path[n][n]:放从vi到vj的最短路径,初始为path[i][j]=“vivj”。
void Floyd(MGraph G)
{
for (i=0; i<G.vertexNum; i++)
for (j=0; j<G.vertexNum; j++)
{
dist[i][j]=G.arc[i][j];
if (dist[i][j]!=∞)
path[i][j]=G.vertex[i]+G.vertex[j];
else path[i][j]="";
}
for (k=0; k<G.vertexNum; k++)
for (i=0; i<G.vertexNum; i++)
for (j=0; j<G.vertexNum; j++)
if (dist[i][k]+dist[k][j]<dist[i][j]) {
dist[i][j]=dist[i][k]+dist[k][j];
path[i][j]=path[i][k]+path[k][j];
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18