Data Structure LXJ
第 8 章图西南科技大学 计算机学院信息教研室
Data Structure LXJ
图图 应用最广泛的数据结构。
不同于树的另一种非线性结构每个顶点可以与多个其他顶点相关联，各顶点之间的关系是任意的。
简单图 没有自身环，两点间至多一条边
V5
V1 V2
V3 V4
V1 V2
V3 V4
a）简单图 b） 多重图
V5
V1 V2
V3 V4
b） 带自身环的图
Data Structure LXJ
8.1 图的基本概念
图 (Graph)是由顶点集合及顶点间的关系集合组成的一种数据结构。即,G=(V,E)
1,顶点集 V={v1,v2,······,vn}
2,边集 E
无向图,E={ (vi,vj) | vi,vj∈ V}
有向图,E={<vi,vj>|vi,vj∈ V}有向边集
其中有向边 <vi,vj>,vi起点弧尾,vj终点弧头
V5
V1 V2
V3 V4
V1 V2
V3 V4
a）无向图 b） 有向图
Data Structure LXJ
基本概念度,TD(vi),一个顶点的度,以 vi为端点的边的数目
OD(vi),出度,以 vi为起点的边的数目
ID(vi),入度，以 vi为终点的边的数目
TD(vi)= OD(vi)+ ID(vi)
OD=ID,TD=2e,e =1/2*TD
TD OD ID 为整个图的总度,出度,入度数。
V5
V1 V2
V3 V4
V1 V2
V3 V4
Data Structure LXJ
基本概念权,图的边的附加信息，权可以表示实际问题中从一个问题到另一个问题距离、花费的代价、所需的时间带权图（网络）：
路径 vi······vj,以 vi为起点 vj为终点的顶点序列路径的长,路径上边的数目 (不带权的图 )
路径上各个边权值的总和。（带权的图）
简单路径,顶点都不重复的路径回路环,首尾相接的路径
vivj连通,有路径 vi······vj
连通图,任意两点都连通强连通,vi······vj,vj······vi
强连通图,任意两点都强连通。
V5
V1 V2
V3 V4
Data Structure LXJ
V5
V1
V3
V2
V4
V5
V1
V3
V2
V4
a）弱连通 b） 强连通基本概念
连通图
Data Structure LXJ
基本概念
完全图：任意两点间都有边相关联的图
1,无向完全图 共有边 (n*(n-1)) /2条
2,有向完全图 共有边 n(n-1) 条
Data Structure LXJ
基本概念子图：
G=(V,E),G’=(V’,E’)
如果 V’? V,E’? E,
就称 G’是 G的子图。
V5
V1
V3
V2
V4
V5
V1
V3
V2
a）图 b） 子图
Data Structure LXJ
基本概念
生成树
1,连通图的生成树：含有所有顶点的极小连通图子图,n个顶点的连通图的生成树有 n个定点，有 n-1条边
2,非连通图的生成森林：所有 k个连通分支的生成树组成生成森林，共有 条边
V5
V1
V3
V2
V4
V5
V1
V3
V2
V4
V6
V5
V1
V3 V2
V4
V1
V3 V2
V4
V5 V6
a）连通图和生成树 b） 非连通图和生成森林图
n-k
Data Structure LXJ
8.2 图的邻接矩阵存储结构
1.邻接矩阵用矩阵表示图的顶点之间的相邻关系。
A[i,j] =1 (vi,vj)?E
=0 (vi,vj)不存在
V5
V1 V2
V3 V4
V1 V2 V3 V4 V5
V1 0 1 1 0 0
V2 1 0 0 1 1
V3 1 0 0 0 1
V4 0 1 0 0 0
V5 0 1 1 0 0
A =
V = {V1 V2 V3 V4 V5}
Data Structure LXJ
无向图的邻接矩阵是对称矩阵
TD(vi)=ΣA[i,j] i行数字的和等于 vi的度
j=1
n
e=1/2 ΣΣA[i,j] 全部数字的和等于边数 *2 i=1
n
j=1
n
V5
V1 V2
V3 V4
V1 V2 V3 V4 V5
V1 0 1 1 0 0
V2 1 0 0 1 1
V3 1 0 0 0 1
V4 0 1 0 0 0
V5 0 1 1 0 0
Data Structure LXJ
有向图的邻接矩阵
A[i,j] =1 <vi,vj>?E
=0 <vi,vj>不存在
OD(vi)=ΣA[i,j] i行数字的和等于 vi的出度
j=1
n
|E|= ΣΣA[i,j] 全部数字的和等于边数i=1
n
j=1
n
V1 V2
V3 V4
V1 V2 V3 V4
V1 0 1 1 0
V2 1 0 0 0
V3 0 0 0 1
V4 1 0 0 0
Data Structure LXJ
网的邻接矩阵
A[i,j] =wi (vi,vj)∈ E 权为 wi
=∞ (vi,vj)不存在
V5
V1
V6
V2
V4
V3
5 4
8
9
5
73
1
5
6
V1 V2 V3 V4 V5 V6
V1 ∞ 5 ∞ 7 ∞ ∞
V2 ∞ ∞ 4 ∞ ∞ ∞
V3 8 ∞ ∞ ∞ ∞ 9
V4 ∞ ∞ 5 ∞ ∞ 6
V5 ∞ ∞ ∞ 5 ∞ ∞
V6 3 ∞ ∞ ∞ 1 ∞
Data Structure LXJ
8.2.2 邻接矩阵表示的图类－ AdjMWGraph
#include "queue.h“
#include "seqlist.h“
const int MaxVertics = 10;
template <class T>
class AdjMWGraph
{
SeqList<T> vertexList; //顶点集
int edge [MaxVertics][MaxVertics]; //边集
int graphsize;
int FindVertex(SeqList<T> &L,const T& vertex);
int GetVertexPos(const T& vertex);
…
Data Structure LXJ
AdjMWGraph class
…
AdjMWGraph(void);
int GraphEmpty(void) const;
int GraphFull(void) const;
int NumberOfVertices(void) const;
int GetWeight(const T& vertex1,const T&
vertex2);
SeqList<T>& GetNeighbors(const T& vertex);
int GetFirstNeighbor(const int v);
int GetNextNeighbor(const int v1,const int v2);
…
Data Structure LXJ
AdjMWGraph class
…
//graph modification methods
void InsertVertex(const T& vertex);
void InsertEdge(const T& vertex1,
const T& vertex2,int weight);
void DeleteVertex(const T& vertex);
void DeleteEdge(const T& vertex1,
const T& vertex2);
…
Data Structure LXJ
AdjMWGraph class
…
// utility methods
void ReadGraph(char *filename);
SeqList<T>& DFS( );
SeqList<T>& DFS(const int v,int *visited);
SeqList<T>& DepthFirstSearch(
const T& beginVertex);
SeqList<T>& BreadthFirstSearch(
const T& beginVertex);
int MinimumPath(const T& sVertex,
const T& eVertex);
};
Data Structure LXJ
8.2.3 图的遍历图的遍历
1,深度优先搜索 DFS（ Depth First Search）
2,广度优先搜索 BFS（ BrodFirstSearch）
V5
V1 V2
V3 V4
a） DFS序列,V1,V2,V4,V5,V3
b） BFS序列,V1,V2,V3,V4,V5
Data Structure LXJ
DFS
V5
V1 V2
V3 V4
V1 V2 V3 V4 V5
V1 0 1 1 0 0
V2 1 0 0 1 1
V3 1 0 0 0 1
V4 0 1 0 0 0
V5 0 1 1 0 0
V1 V2 V4 V5 V3遍历次序：
Data Structure LXJ
8.2.3 图的遍历
Int AdjMWGraph::GetFirstNeighbor(const int v)
{
…
for(int col = 0;col <= Vertices.ListSize();col++)
if(Edge[v][col] > 0&&Edge[v][col]<MaxWeight)
return col;
return –1;
}
V5
V1 V2
V3 V4
V1 V2 V3 V4 V5
V1 0 1 1 0 0
V2 1 0 0 1 1
V3 1 0 0 0 1
V4 0 1 0 0 0
V5 0 1 1 0 0
Data Structure LXJ
8.2.3 图的遍历
Int AdjMWGraph:,GetNextNeighbor (const int v1,connst int v2)
{
…
for(int col = v2+1;col <= Vertices.ListSize();col++)
if(Edge[v1][col] > 0&&Edge[v1][col]<MaxWeight)
return col;
return –1;
}
V5
V1 V2
V3 V4
V1 V2 V3 V4 V5
V1 0 1 1 0 0
V2 1 0 0 1 1
V3 1 0 0 0 1
V4 0 1 0 0 0
V5 0 1 1 0 0
Data Structure LXJ
邻接矩阵－递归 DFS
// 从 v顶点出发，深度优先遍历图
template<class T>
void AdjMWGraph,,DepthFirstSearch(int v,int visited[],
void visit(VerT item))
{
visit(GetValue(v)); // 访问 v结点
visited[v] = 1 ; // 说明 v已被访问过
int w = GetFirstNeighbor(v) ;// 取得 v的第一个邻接点
while(w ! = -1) // 若存在顶点 w
{
if(! visited[w]) // 若 w未被访问过，从 w递归访问
DepthFirstSearch(w,visited[],visit) ;
w = GetNextNeighbor (v,w) ;
// 令 w为 v关于 w的下一个邻接顶点
}
}
Data Structure LXJ
DFS
深度优先搜索：
1。访问初始定点 v,并标记顶点 v已经访问
2。查找顶点 v的第一个邻接顶点 w
3。若 w存在，则继续执行，否则算法结束
4。若 w尚未访问，则访问 w,并标记 w已访问且以顶点 w为当前顶点再次调用深度优先搜索。
5。若顶点 w已被访问，则查找顶点 v的（ v,w）邻接边的下一条邻接边（ v,w）,转到步骤 3。
V5
V1 V2
V3 V4
GetFirstNeighbor(v) ;
// 取得 v的第一个邻接点
GetNextNeighbor (v,w) ;
//找顶点 v的 <v,w>邻接边的下一条邻接边
Data Structure LXJ
BFS
V5
V1 V2
V3 V4
V1 V2 V3 V4 V5
V1 0 1 1 0 0
V2 1 0 0 1 1
V3 1 0 0 0 1
V4 0 1 0 0 0
V5 0 1 1 0 0
Data Structure LXJ
BFS
//从起始顶点 v开始深度优先遍历图
void AdjMWGraph<T>,,BroadFirstSearch(const
int v,int visited[],void visit(VerT item))
{
VerT u,w;
SeqQueue queue ;
Visit(GetValue(v));
visited[v] = 1 ;
queue.QInsert( v ) ; // 将起始顶点入队
…
Data Structure LXJ
邻接矩阵－ BFS
…
while( ! queue.QueueEmpty())// 队列非空时循环
{
u = queue.QDelete() ; // 弹出一个顶点 w
w = GetFirstNeighbor(u) ;//取得 w的第一个邻接顶点
while(w ! = -1) // 当 w没有邻接顶点时,k值为 -1
{
if( !visited[w])
{
Visit(GetValue(w));
visited[w] = 1 ; // 访问顶点 w
queue.QInsert(w) ;//若 k未被访问过，将 k入队
}
w = GetNextNeighbor(u,w) ;
}
}
}
Data Structure LXJ
DFS
广度优先搜索：
1。访问初始顶点 v,并标记顶点 v已经访问
2。顶点 v入队列
3。当队列非空时继续执行、否则算法结束；
4。出队列取得队头元素 u;
5。查找顶点 u的第一个邻接顶点 w
6。若 w存在，则继续执行，否则转到步骤 3
7。若 w尚未访问，则访问 w,并标记 w已访问且让顶点 w入队列
8。则查找顶点 u的（ u,w）邻接边的下一条邻接边
（ u,w）,转到步骤 6。
Data Structure LXJ
8.3 图的临接表存储结构
E
D
C
B
A0
1
2
3
4
1 ^2
1 ^2
0 3
0
^4
^4
^1
E
A B
C D
a）图 b） 图的邻接表
Data Structure LXJ
图的临接表存储结构结构描述
对图中 每个顶点 Vi建立一个单链表，每个链表结点为 两个域,
其中：
邻接点域（ adjvex） 记载与顶点 Vi邻接的顶点信息；
链域（ nextarc） 指向下一个与顶点 Vi邻接的邻接的链表 p结点
adjvex nextarc
每个链表附设一个头结点，头结点结构为,vexdata firstarc
其中,vexdata存放顶点信息（姓名、编号等） ；
fristarc指向链表的第一个结点。
Data Structure LXJ
A E
B D
C
1 A
2 E
3 C
4 B
5 D
1 2
3
4 52 4 ^
1 3 ^
2 3 ^
1 3 5 ^
2 4 5 ^
dest next cost
data adj
头结点表结点无向图链表中的结点 表示依附于顶点 Vi的边特点：设无向图中顶点数为 n，边数为 e，
则它的邻接表需要 n个头结点和 2e个表结点。
顶点 Vi的度 TD（ Vi） =链表 i中的表结点数。
Data Structure LXJ
A D
B C 1 A
2 D
3 B
4 C
1 2
3 4 4 ^
3 ^
1 ^
1 ^
有向图 1 A
2 D ^
3 B
4 C
2 3 ^
1 ^
4 ^ 邻接表逆邻接表与无向图的邻接表结构一样。
只是在 第 i条链表 上的结点是以 Vi为弧尾 的各个 弧头顶点特点：
1,n个顶点,e条弧的有向图，需 n个表头结点,e 个表结点
2,第 i条链表上的结点数，为 Vi的出度 （ 求顶点的出度易，求入度难）
Data Structure LXJ
插入顶点－ InsertVertex()
template <class T>
void Graph<T>::InsertVertex(const T& vertex)
{
Vertices[numVertices].data = vertex;
numVertices++;
}
E
D
C
B
A0
1
2
3
4
1 ^2
2 ^3
0 3
1
^4
^4
^2
Data Structure LXJ
插入边－ InsertEdge()
void AdjTWGraph::InsertEdge(const int v1,const int
v2,int weight)
{
if(v1 < 0|| v1 > numVertices || v2 < 0|| v2 >
numVertices)
{
cerr << "参数 v1或 v2越界出错 " << endl;
exit(1);
}
…
E
D
C
B
A0
1
2
3
4
1 ^2
2 ^3
0 3
1
^4
^4
^2
Data Structure LXJ
InsertEdge()
…
Edge* q = new Edge(v2,weight);
if(Vertices[v1].adj == NULL)
Vertices[v1].adj = q;
else
{
Edge* curr = Vertices[v1].adj,*pre = NULL;
while(curr != NULL && curr->dest < v2)
{
pre = curr;
curr = curr->next;
}
…
E
D
C
B
A0
1
2
3
4
1 ^2
2 ^3
0 3
1
^4
^4
^2
Data Structure LXJ
InsertEdge()
…
if(pre == NULL)
{
q->next = Vertices[v1].adj;
Vertices[v1].adj = q;
}
else
{
q->next = pre->next;
pre->next = q;
}
}
numOfEdges++;
} E
D
C
B
A0
1
2
3
4
1 ^2
2 ^3
0 3
1
^4
^4
^2
Data Structure LXJ
删除顶点－ DeleteVertex()
1,删除该顶点的所有入边
2,删除该顶点的所有出边
3,删除顶点
A B
C D
A B
C D
D
C
B
A0
1
2
3
1 ^2
^0
^3
^0
B
C D
D
C
B
0
1
2
3
^3
Data Structure LXJ
DeleteVertex()
void AdjTWGraph::Deletevertex(const int v)
{
Edge *pre,*curr;
for(int i = 0;i < numVertices;i++)
//在所有顶点为 i的单链表中寻找 dest域为 v的结点并删除，
//即删除顶点 v的入边
{
pre = NULL;
curr = Vertices[i].adj;
while(curr != NULL && curr->dest < v)
{
pre = curr;
curr = curr->next;
}
…
E
D
C
B
A0
1
2
3
4
1 ^2
2 ^3
0 3
1
^4
^4
^2
Data Structure LXJ
DeleteVertex()
…
if(pre == NULL&&curr->dest == v)
//该出边结点是单链表的第一个结点时
{
Vertices[i].adj = curr->next;
delete curr;
numOfEdges--;
}
else if(curr != NULL && curr->dest == v)
//该出边结点是单链表的其它结点时
{
pre->next = curr->next;
delete curr;
numOfEdges--;
}
} //for循环结束
… ED
C
B
A0
1
2
3
4
1 ^2
2 ^3
0 3
1
^4
^4
^2
Data Structure LXJ
DeleteVertex()
…
Edge *p = Vertices[v].adj,*q;
for(i = v;i < numVertices-1;i++)
Vertices[i] = Vertices[i+1]; //删除数组的顶点元素
numVertices--;
while(p != NULL) //删除顶点 v的所有出边
{
q = p->next;
//释放空间
delete p;
p = q;
numOfEdges--;
}
}
E
D
C
B
A0
1
2
3
4
1 ^2
2 ^3
0 3
1
^4
^4
^2
Data Structure LXJ
删除边－ DeleteEdge()
void AdjTWGraph::DelteEdge(int v1,int v2)
{
if(v1 < 0 || v1 > numVertices || v2 < 0 ||
V2 > numVertices)
{
cerr << "参数 v1,v2越界 " << end;
exit(1);
}
Edge* curr = Vertices[v1].adj,*pre = NULL;
while(curr != NULL && curr->dest < v2)
{
pre = curr;
curr = curr->next;
}
…
Data Structure LXJ
DeleteEdge()
…
if(pre == NULL && CURR->DEST == v2)
//要删除的是第一个结点
{
Vertice[v1].adj = curr-next；
delete curr;
numOfEdge--;
}
else if(pre != NULL && curr->dest <== v2)
//不是单链表的第一个结点
{
pre->next = curr->next;
delete curr;
numOfEdge--;
}
…
Data Structure LXJ
DeleteEdge()
…
else
{
cerr << "边不存在！ " << endl;
exit(1);
}
}
Data Structure LXJ
得到第一个邻接点－ GetFirstNeighbor()
int AdjTWGraph::GetFirstNeighbor(const int v)
{
if(v < 0 || v > numVertices)
{
cerr << "参数 v1越界出错 " << endl;
exit(1);
}
Edge* p = Vertices[v].adj;
if(p != NULL)
return p->dest;
else
return -1;
} E
D
C
B
A0
1
2
3
4
1 ^2
2 ^3
0 3
1
^4
^4
^2
Data Structure LXJ
得到下一个邻接点－ GetNextNeighbor()
int AdjTWGraph::GetNextNeighbor(const int v1,const int v2)
{
if(v1 < 0||v2 > numVertices||v2 < 0||v2 > numVertices)
{
cerr <<"参数 v1或 v2越界出错！ "<<endl;
}
Edge* p = Vertices[v1].adj;
while(p != NULL)
{
if(p->next != NULL&&p->dest == v2)
return p->next->dest;
else
p = p->next;
}
return -1;
} E
D
C
B
A0
1
2
3
4
1 ^2
2 ^3
0 3
1
^4
^4
^2
Data Structure LXJ
邻接表图的深度遍历－ DFS
void AdjTWGraph::DepthFirstSearch(const int v,
int visited[],void visit(T item))
{
visit(GetValue(v));
visited[v] = 1;
int w = GetFirstNeighbor(v);
while(w != -1)
{
if(!visited[w])
DepthFirstSearch(w,visited,visit);
w = GetNextNeighbor(v,w);
}
}
Data Structure LXJ
8.4 图的其它存储结结构
1,逆邻接表
2,十字链表
3,邻接多重表
Data Structure LXJ
8.4.1 逆邻接表
邻接表可以方便地找到顶点 v地出度，但不方便找入度，也不方便寻找以 v为头地弧，故引入逆邻接表
B
D
C E
A
a）图
^E4
D3
C2
^B1
A0
adjdata下标
4 3 2 ^1
^4
^2
E4
D3
C2
B1
^A0
adjdata下标
0 ^3
0 ^2
^0
^0
b）邻接表
c）逆邻接表只是在 第 i条链表 上的结点是以 Vi为弧尾 的各个 弧头顶点
Data Structure LXJ
8.4.2 十字链表
邻接表和逆邻接表中每条边的信息既要存储在邻接表中，又要存储在逆邻接表中，增加了插入删除算法的复杂性
十字链表用一个表就可以表达邻接表和逆邻接表所包含的信息
headVer tailVer weight tailNext headNext边结点：
data firstIn firstOut顶点结点：
Data Structure LXJ
十字链表
a）带权有向图
B
DC
E
A 40
30 30
2020
50
50
下标 data
0 A
1 B
2 C
3 D
4 E ^
0 1 40 0 2 30 ^ ^
1 3 30 ^ ^
2 1 50 ^ 2 4 20 ^
3 0 50 ^ 3 4 20 ^ ^
firstin firstout
b）十字链表存储结构
tailVer
headVer
weight tailNext
headNext
Data Structure LXJ
8.5 生成树
有 n个顶点的连通图的生成树是原图的极小连通图，
它包含原图中所有结点，且保持连通图的最少的边
1,在生成树中删除一条边，就使该生成树编程非连通而不再满足生成树定义；
2,在生成树中增加一条边，就会使生成树中有回路而不再满足生成树定义；
3,一个连通图可能存在多个生成树；
4,有 n个顶点无向图的生成树有且只有 n-1条边；
5,连通网（带权无向连通图）的所有生成树中必有一棵边的权值和最小的生成树，称最小代价生成树，简称最小生成树。
Data Structure LXJ
生成树具有 n个顶点的无向连通图 G
其任一生成 G’恰好含 n-1条边
生成树不一定唯一，如
4个顶点选择 3条边有如下 5种形状 (5× 4= 20种 ):
其中 16种为生成树,（保证了连通）
Data Structure LXJ
生成树
V1
V4
V2 V3
V5 V6
V1
V4
V2 V3
V5 V6
V1
V4
V2 V3
V5 V6
a）无向图 b）生成树 1 c）生成树 2
生成树不一定唯一
Data Structure LXJ
最小生成树
许多问题都是求无向连通图的最小生成树问题。如在 n个城市中铺设光缆，保证铺设费用最低
构造最小生成树必须满足以下三条
1,构造的最小生成树必须保证 n个顶点
2,构造的最小生成树有且只有 n-1条边（废话）
3,构造的最小生成树中不存在回路（废话）
构造最小生成树两种典型算法：
1,普里姆算法（ Prim）
2,克鲁斯卡尔算法（ Kruskal）
Data Structure LXJ
普里姆算法描述设 N=（ V,{E}）是一个连通网，
V=[1,2,…,n}是 N的顶点集合，
辅助集合 U，初值为 {Uo}，
用来存放当前所得到的最小生成树的顶点；
辅助集合 TE，初值为 {}，
用来存放当前所得到的最小生成树的边。
Data Structure LXJ
普里姆（ Prim）算法步骤
1,TE=Ф,U={u0}
2,当 U≠V,重复下列步骤：
(1)选取
（ u0,v0)=min{cost(u,v)|u∈U,v∈V -U}，
保证不形成回路
(2)TE=TE+（ u0,v0),边（ u0,v0)并入 TE
(3)U=U+{V0},顶点 V0 并入 U
特点,以连通为主选代价最小的邻接边
Data Structure LXJ
普里姆算法
60A B
C G
E F
D
50
40 70
65
45
42
52
50 30
（ a）
A B
C G
E F
D
（ b）
A B
C G
E F
D
50
40
42
50 30
（ g）
A B
C G
E F
D
50
（ c）
A B
C G
E F
D
50
40 50
（ e）
A B
C G
E F
D
50
40
（ d）
A B
C G
E F
D
50
40 50 30
（ f）
A B
C G
E F
D
50
40
45
42
50 30
（ h）
Data Structure LXJ
快速热身初始化,①
②
①
④
⑤
5
2
1
③
3 4
6
6
5 5
6
⑥
①
1
③
第 1步：
6
①
1
③
4
第 2步：
④
6
①
1
③
4 2
第 3步：
5② ④
6
①
1
③
4 2
第 4步：
23
⑤
② 5 ④
6
①
1
③
4
第 5步：
Data Structure LXJ
8.5.3 克鲁斯卡尔算法
设连通网 N={V,E,C},T为 N的最小支撑树。初始时,T={V,{∮ }}，即 T中没有边，只有 n个顶点，理所当然，这 n个顶点就是 n个连通分量。
1,在 E中选择权值最小的边，并将此边从 E中删除。
2,如果此边的两个顶点在 T的不同的连通分量中，则将此边加入到 T，从而导致 T中减少一个连通分量。
3,如果此边的两个顶点在 T的同一个连通分量中，则重复执行 (1) (2)，直至 T中仅剩一个连通分量时，终止操作。
Data Structure LXJ
克鲁斯卡尔算法
60A B
C G
E F
D
50
40 70
65
45
42
52
50 30
A B
C G
E F
D
30
A B
C G
E F
D
40 30
A B
C G
E F
D
40
42
30
A B
C G
E F
D
40
45
42
30
A B
C G
E F
D
50
40
45
42
30
A B
C G
E F
D
50
40
45
42
50 30
Data Structure LXJ
步骤 (v,u) E T
②
①
④
⑤
③
⑥
②
①
④
⑤
③
⑥
1 (1,3)
0 ②
①
④
⑤
5
2
③
3 4
6
6
5 5
6
⑥
②
①
④
⑤
5
③
3 4
6
6
5 5
6
⑥
2
1
快速热身
Data Structure LXJ
②
①
④
⑤
5
③
3 4
6
6
5 5
6
⑥
步骤 (v,u) E T
3 (2,5)
2 (4,6) ②
①
④
⑤
③
⑥
②
①
④
⑤
5
③
4
6
6
5 5
6
⑥
②
①
④
⑤
③
⑥
Data Structure LXJ
步骤 (v,u) E T
5 (1,4)
4 (3,6) ②
①
④
⑤
5
③
6
6
5 5
6
⑥
②
①
④
⑤
③
6
6
5 5
6
⑥
②
①
④
⑤
③
⑥
②
①
④
⑤
③
⑥
Data Structure LXJ
步骤 (v,u) E T
6 (2,3)
②
①
④
⑤
③
6
6
5
6
⑥
边数 =n-1=5
代价 =(1+2+3+4+5)=15
②
①
④
⑤
③
⑥
1
23 4
5
Data Structure LXJ
1.普里姆算法（ Prim）时间复杂度
O(n2),，只与图中顶点个数有关，适用于顶点不多而边稠密的图
2.克鲁斯卡尔算法（ Kruskal）时间复杂度 O(elog2e ),只与边数有关，适用于稀疏图
Data Structure LXJ
8.6 最短路径
算法步骤：
1,用 cost 初始化 dist；置 S={V0}；
2,选择 Vj,使得,dist[j]=Min{dist[i]|Vi∈ V-S} Vj 就是当前求得的从 V0出发的最短路径的终点，并将 Vj并入
S；
3,对 V-S上的所有顶点 Vk，修改：
dist[k]=Min{dist[j]+cost[j,k],dist[k]}
4,重复 2,3,n-1次。
在有向图中，寻找从某个源点到其余各个顶点或者每一对顶点之间的最短带权路径的运算，称为最短路径问题一、某个源点到其余各顶点的最短路径算法迪杰特拉（ Dijkstra） 算法：
Data Structure LXJ
8.6 最短路径
例子
① ② ③
④
⑤
0
5
10
50
30
100 60
10 20
cost 0 1 2 3 4 5
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞ ∞
10
5
∞
∞
∞
∞
∞
∞
∞
50
20
30
∞
∞
∞
∞
100
10
60
∞
0
1
2
3
4
5
终点 从 v0 到各终点的 dist 值和最短路径
v1
v2
v4
v3
v5
vj
60(v0,v4,v3,v5)
v5
∞
50(v0,v4,v3)
90(v0,v4,v5)
v3
∞ ∞
10(v0,v2)
30(v0,v4)
100(v0,v5)
v2
∞
∞ 60(v0,v2,v3)
v4
∞
30(v0,v4)
100(v0,v5)
Data Structure LXJ
8.6 最短路径二、每一对顶点之间的最短路径两种方法：
每次以一个顶点为源点，重复调用 Dijkstra算法 n次；
弗洛伊德算法 (Floyed)
1.弗洛伊德算法思想：以 A(0) [i,j]=cost[i,j] 递推出：
A(k)[i,j]=Min{A(k-1)[i,j],A(k-1)[i,k]+ A(k-1) [k,j]},1≤k≤n
其中,A[k][i,j] 表示从 vi到 vj 的中间顶点的序号不大于 k 的最短路径长度。最后得到的 A[n][i,j]就是从 vi 到 vj 的最短路径长度。
Data Structure LXJ
8.6 最短路径
2.例子
∞ 4 11
∞
∞∞
6 2
3
① ②
③
6
4
3 11
2
A B
C
1 2 3
A(0) A(1) A(2) A(3)A
4 11 6
∞
∞
6 2 5
3 7∞∞
1
2
3
1 2 3 1 2 3 1 2 3
∞
∞
∞3 7
4 6
2
第 8 章图西南科技大学 计算机学院信息教研室
Data Structure LXJ
图图 应用最广泛的数据结构。
不同于树的另一种非线性结构每个顶点可以与多个其他顶点相关联，各顶点之间的关系是任意的。
简单图 没有自身环，两点间至多一条边
V5
V1 V2
V3 V4
V1 V2
V3 V4
a）简单图 b） 多重图
V5
V1 V2
V3 V4
b） 带自身环的图
Data Structure LXJ
8.1 图的基本概念
图 (Graph)是由顶点集合及顶点间的关系集合组成的一种数据结构。即,G=(V,E)
1,顶点集 V={v1,v2,······,vn}
2,边集 E
无向图,E={ (vi,vj) | vi,vj∈ V}
有向图,E={<vi,vj>|vi,vj∈ V}有向边集
其中有向边 <vi,vj>,vi起点弧尾,vj终点弧头
V5
V1 V2
V3 V4
V1 V2
V3 V4
a）无向图 b） 有向图
Data Structure LXJ
基本概念度,TD(vi),一个顶点的度,以 vi为端点的边的数目
OD(vi),出度,以 vi为起点的边的数目
ID(vi),入度，以 vi为终点的边的数目
TD(vi)= OD(vi)+ ID(vi)
OD=ID,TD=2e,e =1/2*TD
TD OD ID 为整个图的总度,出度,入度数。
V5
V1 V2
V3 V4
V1 V2
V3 V4
Data Structure LXJ
基本概念权,图的边的附加信息，权可以表示实际问题中从一个问题到另一个问题距离、花费的代价、所需的时间带权图（网络）：
路径 vi······vj,以 vi为起点 vj为终点的顶点序列路径的长,路径上边的数目 (不带权的图 )
路径上各个边权值的总和。（带权的图）
简单路径,顶点都不重复的路径回路环,首尾相接的路径
vivj连通,有路径 vi······vj
连通图,任意两点都连通强连通,vi······vj,vj······vi
强连通图,任意两点都强连通。
V5
V1 V2
V3 V4
Data Structure LXJ
V5
V1
V3
V2
V4
V5
V1
V3
V2
V4
a）弱连通 b） 强连通基本概念
连通图
Data Structure LXJ
基本概念
完全图：任意两点间都有边相关联的图
1,无向完全图 共有边 (n*(n-1)) /2条
2,有向完全图 共有边 n(n-1) 条
Data Structure LXJ
基本概念子图：
G=(V,E),G’=(V’,E’)
如果 V’? V,E’? E,
就称 G’是 G的子图。
V5
V1
V3
V2
V4
V5
V1
V3
V2
a）图 b） 子图
Data Structure LXJ
基本概念
生成树
1,连通图的生成树：含有所有顶点的极小连通图子图,n个顶点的连通图的生成树有 n个定点，有 n-1条边
2,非连通图的生成森林：所有 k个连通分支的生成树组成生成森林，共有 条边
V5
V1
V3
V2
V4
V5
V1
V3
V2
V4
V6
V5
V1
V3 V2
V4
V1
V3 V2
V4
V5 V6
a）连通图和生成树 b） 非连通图和生成森林图
n-k
Data Structure LXJ
8.2 图的邻接矩阵存储结构
1.邻接矩阵用矩阵表示图的顶点之间的相邻关系。
A[i,j] =1 (vi,vj)?E
=0 (vi,vj)不存在
V5
V1 V2
V3 V4
V1 V2 V3 V4 V5
V1 0 1 1 0 0
V2 1 0 0 1 1
V3 1 0 0 0 1
V4 0 1 0 0 0
V5 0 1 1 0 0
A =
V = {V1 V2 V3 V4 V5}
Data Structure LXJ
无向图的邻接矩阵是对称矩阵
TD(vi)=ΣA[i,j] i行数字的和等于 vi的度
j=1
n
e=1/2 ΣΣA[i,j] 全部数字的和等于边数 *2 i=1
n
j=1
n
V5
V1 V2
V3 V4
V1 V2 V3 V4 V5
V1 0 1 1 0 0
V2 1 0 0 1 1
V3 1 0 0 0 1
V4 0 1 0 0 0
V5 0 1 1 0 0
Data Structure LXJ
有向图的邻接矩阵
A[i,j] =1 <vi,vj>?E
=0 <vi,vj>不存在
OD(vi)=ΣA[i,j] i行数字的和等于 vi的出度
j=1
n
|E|= ΣΣA[i,j] 全部数字的和等于边数i=1
n
j=1
n
V1 V2
V3 V4
V1 V2 V3 V4
V1 0 1 1 0
V2 1 0 0 0
V3 0 0 0 1
V4 1 0 0 0
Data Structure LXJ
网的邻接矩阵
A[i,j] =wi (vi,vj)∈ E 权为 wi
=∞ (vi,vj)不存在
V5
V1
V6
V2
V4
V3
5 4
8
9
5
73
1
5
6
V1 V2 V3 V4 V5 V6
V1 ∞ 5 ∞ 7 ∞ ∞
V2 ∞ ∞ 4 ∞ ∞ ∞
V3 8 ∞ ∞ ∞ ∞ 9
V4 ∞ ∞ 5 ∞ ∞ 6
V5 ∞ ∞ ∞ 5 ∞ ∞
V6 3 ∞ ∞ ∞ 1 ∞
Data Structure LXJ
8.2.2 邻接矩阵表示的图类－ AdjMWGraph
#include "queue.h“
#include "seqlist.h“
const int MaxVertics = 10;
template <class T>
class AdjMWGraph
{
SeqList<T> vertexList; //顶点集
int edge [MaxVertics][MaxVertics]; //边集
int graphsize;
int FindVertex(SeqList<T> &L,const T& vertex);
int GetVertexPos(const T& vertex);
…
Data Structure LXJ
AdjMWGraph class
…
AdjMWGraph(void);
int GraphEmpty(void) const;
int GraphFull(void) const;
int NumberOfVertices(void) const;
int GetWeight(const T& vertex1,const T&
vertex2);
SeqList<T>& GetNeighbors(const T& vertex);
int GetFirstNeighbor(const int v);
int GetNextNeighbor(const int v1,const int v2);
…
Data Structure LXJ
AdjMWGraph class
…
//graph modification methods
void InsertVertex(const T& vertex);
void InsertEdge(const T& vertex1,
const T& vertex2,int weight);
void DeleteVertex(const T& vertex);
void DeleteEdge(const T& vertex1,
const T& vertex2);
…
Data Structure LXJ
AdjMWGraph class
…
// utility methods
void ReadGraph(char *filename);
SeqList<T>& DFS( );
SeqList<T>& DFS(const int v,int *visited);
SeqList<T>& DepthFirstSearch(
const T& beginVertex);
SeqList<T>& BreadthFirstSearch(
const T& beginVertex);
int MinimumPath(const T& sVertex,
const T& eVertex);
};
Data Structure LXJ
8.2.3 图的遍历图的遍历
1,深度优先搜索 DFS（ Depth First Search）
2,广度优先搜索 BFS（ BrodFirstSearch）
V5
V1 V2
V3 V4
a） DFS序列,V1,V2,V4,V5,V3
b） BFS序列,V1,V2,V3,V4,V5
Data Structure LXJ
DFS
V5
V1 V2
V3 V4
V1 V2 V3 V4 V5
V1 0 1 1 0 0
V2 1 0 0 1 1
V3 1 0 0 0 1
V4 0 1 0 0 0
V5 0 1 1 0 0
V1 V2 V4 V5 V3遍历次序：
Data Structure LXJ
8.2.3 图的遍历
Int AdjMWGraph::GetFirstNeighbor(const int v)
{
…
for(int col = 0;col <= Vertices.ListSize();col++)
if(Edge[v][col] > 0&&Edge[v][col]<MaxWeight)
return col;
return –1;
}
V5
V1 V2
V3 V4
V1 V2 V3 V4 V5
V1 0 1 1 0 0
V2 1 0 0 1 1
V3 1 0 0 0 1
V4 0 1 0 0 0
V5 0 1 1 0 0
Data Structure LXJ
8.2.3 图的遍历
Int AdjMWGraph:,GetNextNeighbor (const int v1,connst int v2)
{
…
for(int col = v2+1;col <= Vertices.ListSize();col++)
if(Edge[v1][col] > 0&&Edge[v1][col]<MaxWeight)
return col;
return –1;
}
V5
V1 V2
V3 V4
V1 V2 V3 V4 V5
V1 0 1 1 0 0
V2 1 0 0 1 1
V3 1 0 0 0 1
V4 0 1 0 0 0
V5 0 1 1 0 0
Data Structure LXJ
邻接矩阵－递归 DFS
// 从 v顶点出发，深度优先遍历图
template<class T>
void AdjMWGraph,,DepthFirstSearch(int v,int visited[],
void visit(VerT item))
{
visit(GetValue(v)); // 访问 v结点
visited[v] = 1 ; // 说明 v已被访问过
int w = GetFirstNeighbor(v) ;// 取得 v的第一个邻接点
while(w ! = -1) // 若存在顶点 w
{
if(! visited[w]) // 若 w未被访问过，从 w递归访问
DepthFirstSearch(w,visited[],visit) ;
w = GetNextNeighbor (v,w) ;
// 令 w为 v关于 w的下一个邻接顶点
}
}
Data Structure LXJ
DFS
深度优先搜索：
1。访问初始定点 v,并标记顶点 v已经访问
2。查找顶点 v的第一个邻接顶点 w
3。若 w存在，则继续执行，否则算法结束
4。若 w尚未访问，则访问 w,并标记 w已访问且以顶点 w为当前顶点再次调用深度优先搜索。
5。若顶点 w已被访问，则查找顶点 v的（ v,w）邻接边的下一条邻接边（ v,w）,转到步骤 3。
V5
V1 V2
V3 V4
GetFirstNeighbor(v) ;
// 取得 v的第一个邻接点
GetNextNeighbor (v,w) ;
//找顶点 v的 <v,w>邻接边的下一条邻接边
Data Structure LXJ
BFS
V5
V1 V2
V3 V4
V1 V2 V3 V4 V5
V1 0 1 1 0 0
V2 1 0 0 1 1
V3 1 0 0 0 1
V4 0 1 0 0 0
V5 0 1 1 0 0
Data Structure LXJ
BFS
//从起始顶点 v开始深度优先遍历图
void AdjMWGraph<T>,,BroadFirstSearch(const
int v,int visited[],void visit(VerT item))
{
VerT u,w;
SeqQueue queue ;
Visit(GetValue(v));
visited[v] = 1 ;
queue.QInsert( v ) ; // 将起始顶点入队
…
Data Structure LXJ
邻接矩阵－ BFS
…
while( ! queue.QueueEmpty())// 队列非空时循环
{
u = queue.QDelete() ; // 弹出一个顶点 w
w = GetFirstNeighbor(u) ;//取得 w的第一个邻接顶点
while(w ! = -1) // 当 w没有邻接顶点时,k值为 -1
{
if( !visited[w])
{
Visit(GetValue(w));
visited[w] = 1 ; // 访问顶点 w
queue.QInsert(w) ;//若 k未被访问过，将 k入队
}
w = GetNextNeighbor(u,w) ;
}
}
}
Data Structure LXJ
DFS
广度优先搜索：
1。访问初始顶点 v,并标记顶点 v已经访问
2。顶点 v入队列
3。当队列非空时继续执行、否则算法结束；
4。出队列取得队头元素 u;
5。查找顶点 u的第一个邻接顶点 w
6。若 w存在，则继续执行，否则转到步骤 3
7。若 w尚未访问，则访问 w,并标记 w已访问且让顶点 w入队列
8。则查找顶点 u的（ u,w）邻接边的下一条邻接边
（ u,w）,转到步骤 6。
Data Structure LXJ
8.3 图的临接表存储结构
E
D
C
B
A0
1
2
3
4
1 ^2
1 ^2
0 3
0
^4
^4
^1
E
A B
C D
a）图 b） 图的邻接表
Data Structure LXJ
图的临接表存储结构结构描述
对图中 每个顶点 Vi建立一个单链表，每个链表结点为 两个域,
其中：
邻接点域（ adjvex） 记载与顶点 Vi邻接的顶点信息；
链域（ nextarc） 指向下一个与顶点 Vi邻接的邻接的链表 p结点
adjvex nextarc
每个链表附设一个头结点，头结点结构为,vexdata firstarc
其中,vexdata存放顶点信息（姓名、编号等） ；
fristarc指向链表的第一个结点。
Data Structure LXJ
A E
B D
C
1 A
2 E
3 C
4 B
5 D
1 2
3
4 52 4 ^
1 3 ^
2 3 ^
1 3 5 ^
2 4 5 ^
dest next cost
data adj
头结点表结点无向图链表中的结点 表示依附于顶点 Vi的边特点：设无向图中顶点数为 n，边数为 e，
则它的邻接表需要 n个头结点和 2e个表结点。
顶点 Vi的度 TD（ Vi） =链表 i中的表结点数。
Data Structure LXJ
A D
B C 1 A
2 D
3 B
4 C
1 2
3 4 4 ^
3 ^
1 ^
1 ^
有向图 1 A
2 D ^
3 B
4 C
2 3 ^
1 ^
4 ^ 邻接表逆邻接表与无向图的邻接表结构一样。
只是在 第 i条链表 上的结点是以 Vi为弧尾 的各个 弧头顶点特点：
1,n个顶点,e条弧的有向图，需 n个表头结点,e 个表结点
2,第 i条链表上的结点数，为 Vi的出度 （ 求顶点的出度易，求入度难）
Data Structure LXJ
插入顶点－ InsertVertex()
template <class T>
void Graph<T>::InsertVertex(const T& vertex)
{
Vertices[numVertices].data = vertex;
numVertices++;
}
E
D
C
B
A0
1
2
3
4
1 ^2
2 ^3
0 3
1
^4
^4
^2
Data Structure LXJ
插入边－ InsertEdge()
void AdjTWGraph::InsertEdge(const int v1,const int
v2,int weight)
{
if(v1 < 0|| v1 > numVertices || v2 < 0|| v2 >
numVertices)
{
cerr << "参数 v1或 v2越界出错 " << endl;
exit(1);
}
…
E
D
C
B
A0
1
2
3
4
1 ^2
2 ^3
0 3
1
^4
^4
^2
Data Structure LXJ
InsertEdge()
…
Edge* q = new Edge(v2,weight);
if(Vertices[v1].adj == NULL)
Vertices[v1].adj = q;
else
{
Edge* curr = Vertices[v1].adj,*pre = NULL;
while(curr != NULL && curr->dest < v2)
{
pre = curr;
curr = curr->next;
}
…
E
D
C
B
A0
1
2
3
4
1 ^2
2 ^3
0 3
1
^4
^4
^2
Data Structure LXJ
InsertEdge()
…
if(pre == NULL)
{
q->next = Vertices[v1].adj;
Vertices[v1].adj = q;
}
else
{
q->next = pre->next;
pre->next = q;
}
}
numOfEdges++;
} E
D
C
B
A0
1
2
3
4
1 ^2
2 ^3
0 3
1
^4
^4
^2
Data Structure LXJ
删除顶点－ DeleteVertex()
1,删除该顶点的所有入边
2,删除该顶点的所有出边
3,删除顶点
A B
C D
A B
C D
D
C
B
A0
1
2
3
1 ^2
^0
^3
^0
B
C D
D
C
B
0
1
2
3
^3
Data Structure LXJ
DeleteVertex()
void AdjTWGraph::Deletevertex(const int v)
{
Edge *pre,*curr;
for(int i = 0;i < numVertices;i++)
//在所有顶点为 i的单链表中寻找 dest域为 v的结点并删除，
//即删除顶点 v的入边
{
pre = NULL;
curr = Vertices[i].adj;
while(curr != NULL && curr->dest < v)
{
pre = curr;
curr = curr->next;
}
…
E
D
C
B
A0
1
2
3
4
1 ^2
2 ^3
0 3
1
^4
^4
^2
Data Structure LXJ
DeleteVertex()
…
if(pre == NULL&&curr->dest == v)
//该出边结点是单链表的第一个结点时
{
Vertices[i].adj = curr->next;
delete curr;
numOfEdges--;
}
else if(curr != NULL && curr->dest == v)
//该出边结点是单链表的其它结点时
{
pre->next = curr->next;
delete curr;
numOfEdges--;
}
} //for循环结束
… ED
C
B
A0
1
2
3
4
1 ^2
2 ^3
0 3
1
^4
^4
^2
Data Structure LXJ
DeleteVertex()
…
Edge *p = Vertices[v].adj,*q;
for(i = v;i < numVertices-1;i++)
Vertices[i] = Vertices[i+1]; //删除数组的顶点元素
numVertices--;
while(p != NULL) //删除顶点 v的所有出边
{
q = p->next;
//释放空间
delete p;
p = q;
numOfEdges--;
}
}
E
D
C
B
A0
1
2
3
4
1 ^2
2 ^3
0 3
1
^4
^4
^2
Data Structure LXJ
删除边－ DeleteEdge()
void AdjTWGraph::DelteEdge(int v1,int v2)
{
if(v1 < 0 || v1 > numVertices || v2 < 0 ||
V2 > numVertices)
{
cerr << "参数 v1,v2越界 " << end;
exit(1);
}
Edge* curr = Vertices[v1].adj,*pre = NULL;
while(curr != NULL && curr->dest < v2)
{
pre = curr;
curr = curr->next;
}
…
Data Structure LXJ
DeleteEdge()
…
if(pre == NULL && CURR->DEST == v2)
//要删除的是第一个结点
{
Vertice[v1].adj = curr-next；
delete curr;
numOfEdge--;
}
else if(pre != NULL && curr->dest <== v2)
//不是单链表的第一个结点
{
pre->next = curr->next;
delete curr;
numOfEdge--;
}
…
Data Structure LXJ
DeleteEdge()
…
else
{
cerr << "边不存在！ " << endl;
exit(1);
}
}
Data Structure LXJ
得到第一个邻接点－ GetFirstNeighbor()
int AdjTWGraph::GetFirstNeighbor(const int v)
{
if(v < 0 || v > numVertices)
{
cerr << "参数 v1越界出错 " << endl;
exit(1);
}
Edge* p = Vertices[v].adj;
if(p != NULL)
return p->dest;
else
return -1;
} E
D
C
B
A0
1
2
3
4
1 ^2
2 ^3
0 3
1
^4
^4
^2
Data Structure LXJ
得到下一个邻接点－ GetNextNeighbor()
int AdjTWGraph::GetNextNeighbor(const int v1,const int v2)
{
if(v1 < 0||v2 > numVertices||v2 < 0||v2 > numVertices)
{
cerr <<"参数 v1或 v2越界出错！ "<<endl;
}
Edge* p = Vertices[v1].adj;
while(p != NULL)
{
if(p->next != NULL&&p->dest == v2)
return p->next->dest;
else
p = p->next;
}
return -1;
} E
D
C
B
A0
1
2
3
4
1 ^2
2 ^3
0 3
1
^4
^4
^2
Data Structure LXJ
邻接表图的深度遍历－ DFS
void AdjTWGraph::DepthFirstSearch(const int v,
int visited[],void visit(T item))
{
visit(GetValue(v));
visited[v] = 1;
int w = GetFirstNeighbor(v);
while(w != -1)
{
if(!visited[w])
DepthFirstSearch(w,visited,visit);
w = GetNextNeighbor(v,w);
}
}
Data Structure LXJ
8.4 图的其它存储结结构
1,逆邻接表
2,十字链表
3,邻接多重表
Data Structure LXJ
8.4.1 逆邻接表
邻接表可以方便地找到顶点 v地出度，但不方便找入度，也不方便寻找以 v为头地弧，故引入逆邻接表
B
D
C E
A
a）图
^E4
D3
C2
^B1
A0
adjdata下标
4 3 2 ^1
^4
^2
E4
D3
C2
B1
^A0
adjdata下标
0 ^3
0 ^2
^0
^0
b）邻接表
c）逆邻接表只是在 第 i条链表 上的结点是以 Vi为弧尾 的各个 弧头顶点
Data Structure LXJ
8.4.2 十字链表
邻接表和逆邻接表中每条边的信息既要存储在邻接表中，又要存储在逆邻接表中，增加了插入删除算法的复杂性
十字链表用一个表就可以表达邻接表和逆邻接表所包含的信息
headVer tailVer weight tailNext headNext边结点：
data firstIn firstOut顶点结点：
Data Structure LXJ
十字链表
a）带权有向图
B
DC
E
A 40
30 30
2020
50
50
下标 data
0 A
1 B
2 C
3 D
4 E ^
0 1 40 0 2 30 ^ ^
1 3 30 ^ ^
2 1 50 ^ 2 4 20 ^
3 0 50 ^ 3 4 20 ^ ^
firstin firstout
b）十字链表存储结构
tailVer
headVer
weight tailNext
headNext
Data Structure LXJ
8.5 生成树
有 n个顶点的连通图的生成树是原图的极小连通图，
它包含原图中所有结点，且保持连通图的最少的边
1,在生成树中删除一条边，就使该生成树编程非连通而不再满足生成树定义；
2,在生成树中增加一条边，就会使生成树中有回路而不再满足生成树定义；
3,一个连通图可能存在多个生成树；
4,有 n个顶点无向图的生成树有且只有 n-1条边；
5,连通网（带权无向连通图）的所有生成树中必有一棵边的权值和最小的生成树，称最小代价生成树，简称最小生成树。
Data Structure LXJ
生成树具有 n个顶点的无向连通图 G
其任一生成 G’恰好含 n-1条边
生成树不一定唯一，如
4个顶点选择 3条边有如下 5种形状 (5× 4= 20种 ):
其中 16种为生成树,（保证了连通）
Data Structure LXJ
生成树
V1
V4
V2 V3
V5 V6
V1
V4
V2 V3
V5 V6
V1
V4
V2 V3
V5 V6
a）无向图 b）生成树 1 c）生成树 2
生成树不一定唯一
Data Structure LXJ
最小生成树
许多问题都是求无向连通图的最小生成树问题。如在 n个城市中铺设光缆，保证铺设费用最低
构造最小生成树必须满足以下三条
1,构造的最小生成树必须保证 n个顶点
2,构造的最小生成树有且只有 n-1条边（废话）
3,构造的最小生成树中不存在回路（废话）
构造最小生成树两种典型算法：
1,普里姆算法（ Prim）
2,克鲁斯卡尔算法（ Kruskal）
Data Structure LXJ
普里姆算法描述设 N=（ V,{E}）是一个连通网，
V=[1,2,…,n}是 N的顶点集合，
辅助集合 U，初值为 {Uo}，
用来存放当前所得到的最小生成树的顶点；
辅助集合 TE，初值为 {}，
用来存放当前所得到的最小生成树的边。
Data Structure LXJ
普里姆（ Prim）算法步骤
1,TE=Ф,U={u0}
2,当 U≠V,重复下列步骤：
(1)选取
（ u0,v0)=min{cost(u,v)|u∈U,v∈V -U}，
保证不形成回路
(2)TE=TE+（ u0,v0),边（ u0,v0)并入 TE
(3)U=U+{V0},顶点 V0 并入 U
特点,以连通为主选代价最小的邻接边
Data Structure LXJ
普里姆算法
60A B
C G
E F
D
50
40 70
65
45
42
52
50 30
（ a）
A B
C G
E F
D
（ b）
A B
C G
E F
D
50
40
42
50 30
（ g）
A B
C G
E F
D
50
（ c）
A B
C G
E F
D
50
40 50
（ e）
A B
C G
E F
D
50
40
（ d）
A B
C G
E F
D
50
40 50 30
（ f）
A B
C G
E F
D
50
40
45
42
50 30
（ h）
Data Structure LXJ
快速热身初始化,①
②
①
④
⑤
5
2
1
③
3 4
6
6
5 5
6
⑥
①
1
③
第 1步：
6
①
1
③
4
第 2步：
④
6
①
1
③
4 2
第 3步：
5② ④
6
①
1
③
4 2
第 4步：
23
⑤
② 5 ④
6
①
1
③
4
第 5步：
Data Structure LXJ
8.5.3 克鲁斯卡尔算法
设连通网 N={V,E,C},T为 N的最小支撑树。初始时,T={V,{∮ }}，即 T中没有边，只有 n个顶点，理所当然，这 n个顶点就是 n个连通分量。
1,在 E中选择权值最小的边，并将此边从 E中删除。
2,如果此边的两个顶点在 T的不同的连通分量中，则将此边加入到 T，从而导致 T中减少一个连通分量。
3,如果此边的两个顶点在 T的同一个连通分量中，则重复执行 (1) (2)，直至 T中仅剩一个连通分量时，终止操作。
Data Structure LXJ
克鲁斯卡尔算法
60A B
C G
E F
D
50
40 70
65
45
42
52
50 30
A B
C G
E F
D
30
A B
C G
E F
D
40 30
A B
C G
E F
D
40
42
30
A B
C G
E F
D
40
45
42
30
A B
C G
E F
D
50
40
45
42
30
A B
C G
E F
D
50
40
45
42
50 30
Data Structure LXJ
步骤 (v,u) E T
②
①
④
⑤
③
⑥
②
①
④
⑤
③
⑥
1 (1,3)
0 ②
①
④
⑤
5
2
③
3 4
6
6
5 5
6
⑥
②
①
④
⑤
5
③
3 4
6
6
5 5
6
⑥
2
1
快速热身
Data Structure LXJ
②
①
④
⑤
5
③
3 4
6
6
5 5
6
⑥
步骤 (v,u) E T
3 (2,5)
2 (4,6) ②
①
④
⑤
③
⑥
②
①
④
⑤
5
③
4
6
6
5 5
6
⑥
②
①
④
⑤
③
⑥
Data Structure LXJ
步骤 (v,u) E T
5 (1,4)
4 (3,6) ②
①
④
⑤
5
③
6
6
5 5
6
⑥
②
①
④
⑤
③
6
6
5 5
6
⑥
②
①
④
⑤
③
⑥
②
①
④
⑤
③
⑥
Data Structure LXJ
步骤 (v,u) E T
6 (2,3)
②
①
④
⑤
③
6
6
5
6
⑥
边数 =n-1=5
代价 =(1+2+3+4+5)=15
②
①
④
⑤
③
⑥
1
23 4
5
Data Structure LXJ
1.普里姆算法（ Prim）时间复杂度
O(n2),，只与图中顶点个数有关，适用于顶点不多而边稠密的图
2.克鲁斯卡尔算法（ Kruskal）时间复杂度 O(elog2e ),只与边数有关，适用于稀疏图
Data Structure LXJ
8.6 最短路径
算法步骤：
1,用 cost 初始化 dist；置 S={V0}；
2,选择 Vj,使得,dist[j]=Min{dist[i]|Vi∈ V-S} Vj 就是当前求得的从 V0出发的最短路径的终点，并将 Vj并入
S；
3,对 V-S上的所有顶点 Vk，修改：
dist[k]=Min{dist[j]+cost[j,k],dist[k]}
4,重复 2,3,n-1次。
在有向图中，寻找从某个源点到其余各个顶点或者每一对顶点之间的最短带权路径的运算，称为最短路径问题一、某个源点到其余各顶点的最短路径算法迪杰特拉（ Dijkstra） 算法：
Data Structure LXJ
8.6 最短路径
例子
① ② ③
④
⑤
0
5
10
50
30
100 60
10 20
cost 0 1 2 3 4 5
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞
∞ ∞
10
5
∞
∞
∞
∞
∞
∞
∞
50
20
30
∞
∞
∞
∞
100
10
60
∞
0
1
2
3
4
5
终点 从 v0 到各终点的 dist 值和最短路径
v1
v2
v4
v3
v5
vj
60(v0,v4,v3,v5)
v5
∞
50(v0,v4,v3)
90(v0,v4,v5)
v3
∞ ∞
10(v0,v2)
30(v0,v4)
100(v0,v5)
v2
∞
∞ 60(v0,v2,v3)
v4
∞
30(v0,v4)
100(v0,v5)
Data Structure LXJ
8.6 最短路径二、每一对顶点之间的最短路径两种方法：
每次以一个顶点为源点，重复调用 Dijkstra算法 n次；
弗洛伊德算法 (Floyed)
1.弗洛伊德算法思想：以 A(0) [i,j]=cost[i,j] 递推出：
A(k)[i,j]=Min{A(k-1)[i,j],A(k-1)[i,k]+ A(k-1) [k,j]},1≤k≤n
其中,A[k][i,j] 表示从 vi到 vj 的中间顶点的序号不大于 k 的最短路径长度。最后得到的 A[n][i,j]就是从 vi 到 vj 的最短路径长度。
Data Structure LXJ
8.6 最短路径
2.例子
∞ 4 11
∞
∞∞
6 2
3
① ②
③
6
4
3 11
2
A B
C
1 2 3
A(0) A(1) A(2) A(3)A
4 11 6
∞
∞
6 2 5
3 7∞∞
1
2
3
1 2 3 1 2 3 1 2 3
∞
∞
∞3 7
4 6
2
