Ch5 图（p177）
# 5.2 图的存储及基本操作（p184）
# 5.2.1 邻接矩阵法（p184）
结点类型定义
#define MaxVertexNum 100 //顶点数目的最大值
typedef char VertexType; //顶点的数据类型
typedef int EdgeType; //带权图中边上权值的数据类型
typedef struct {
VertexType Vex[MaxVertexNum]; //顶点表
EdgeType Edge[MaxVertexNum][MaxVertexNum]; //邻接矩阵，边表
int vexnum, arcnum; //图的当前顶点数和弧数
} MGraph;
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 5.2.2 邻接表法（p186）
图的邻接表存储结构定义
#define MaxVertexNum 100 //图中顶点数目的最大值
typedef struct ArcNode { //边表结点
int adjvex; //该弧所指向的顶点的位置
struct ArcNode *next; //指向下一条弧的指针
//InfoType info; //网的边权值
} ArcNode;
typedef struct VNode { //顶点表结点
VertexType data; //顶点信息
ArcNode *first; //指向第一条依附该结点的弧的指针
} VNode, AdjList[MaxVertexNum];
typedef struct { //图的邻接表存储结构定义
AdjList vertices; //邻接表
int vexnum, arcnum; //图的顶点数和弧数
} ALGraph; //ALGraph是以邻接表存储的图类型
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 5.2.3 十字链表（p187）
十字链表存储结构定义
#define MaxVertexNum 100 //图中顶点数目的最大值
typedef struct ArcNode{ //边表结点
int tailvex, headvex; //该弧的头尾结点
struct ArcNode2 *hlink, *tlink; //分别指向弧头相同和弧尾相同的结点
//InfoType info; //相关信息指针
} ArcNode;
typedef struct VNode{ //顶点表结点
VertexType data; //顶点信息
ArcNode *firstin, *firstout; //指向第一条入弧和出弧
} VNode;
typedef struct {
VNode xlist[MaxVertexNum]; //邻接表
int vexnum, arcnum; //图的顶点数和弧数
} GLGraph; //GLGraph是以十字邻接存储的图类型
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 5.2.4 邻接多重表（p188）
图的邻接多重表存储结构定义
#define MaxVertexNum 100 //图中顶点数目的最大值
typedef struct ArcNode { //边表结点
bool mark; //访问标记
int ivex, jvex; //分别指向该弧的两个结点
struct ArcNode3 *ilink, *jlink; //分别指向两个顶点的下一条边
//InfoType info; //相关信息指针
} ArcNode;
typedef struct VNode { //顶点表结点
VertexType data; //顶点信息
ArcNode *firstedge; //指向第一条依附该顶点的边
}VNode;
typedef struct {
VNode adjmulist[MaxVertexNum]; //邻接表
int vexnum, arcnum; //图的顶点数和弧数
} AMLGraph; //AMLGraph是以邻接多重表存储的图类型
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 5.3 图的遍历（p195）
# 5.3.1 广度优先搜索（BFS)（p195）
1.广度优先搜索算法的伪代码
bool visited[MAX_VERTEX_NUM]; //访问标记数组
void BFSTraverse(Graph G){
//对图G进行广度优先遍历，设访问函数为visit()
for(i=0;i<G.vexnum,++i)
visited[i]=false; //访问标记数组初始化
InitQueue(Q); //初始化辅助队列Q
for (int i = 0; i < G.vexnum; ++i)//从0号顶点开始遍历
if(!visited[i]) //对每个连通分量调用一次BFS
BFS(G,i); //Vi未访问过，从Vi开始BFS
}
void BFS(Graph G,int v){
//从顶点v出发，广度优先遍历图G，算法借助一个辅助队列Q
visit(v); //访问初始顶点v
visited[v]=true; //对v做已访问标记
EnQueue(Q,v); //顶点v入队列
while(!IsEmpty(Q)){
DeQueue(Q,v); //顶点v出队列
for (w=FirstNeighbor(G,v); w>=0;w=NextNeighbor(G,v,w))
{ //检测v所有邻接点
if(!visited[w]){ //w为v的尚未访问的邻接顶点
visit(w); //访问顶点w
visited[w]=true; //对w做已访问标记
EnQueue(Q,w); //顶点w入队列
}//if
}
}//while
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
2.BFS算法求解单源最短路径问题
void BFS_MIN_Distance(Graph G,int u){
//d[i]表示从u到i结点的最短路径
for (int i = 0; i < G.vexnum; ++i)
d[i]=∞； //初始化路径长度
visited[u]=true;d[u]=0;
EnQueue(Q,u);
while(!IsEmpty(Q)){ //BFS算法主过程
DeQueue(Q,u); //队头元素u出队
for (w=FirstNeighbor(G,u); w>=0;w=NextNeighbor(G,u,w))
{
if(!visited[w]){ //w为u的尚未访问的邻接顶点
visited[w]=true; //设已访问标记
d[w]=d[u]+1; //路径长度加1
EnQueue(Q,w); //顶点w入队
}//if
}
}//while
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 5.3.2 深度优先搜索（p197）
bool visited[MAX_VERTEX_NUM]; //访问标记数组
void DFSTraverse(Graph G){
//对图G进行深度优先遍历，访问函数为visit()
for(v=0;v<G.vexnum,++v)
visited[v]=false; //初始化已访问标记数据
for (v = 0; v < G.vexnum; ++v) //本代码中是从v=0开始遍历
if(!visited[v])
DFS(G,v);
}
void DFS(Graph G,int v){
//从顶点v出发，采用递归思想，深度优先遍历图G
visit(v); //访问顶点v
visited[v]=true; //设已访问标记
for (w=FirstNeighbor(G,v); w>=0;w=NextNeighbor(G,v,w))
{
if(!visited[w]){ //w为u的尚未访问的邻接顶点
DFS(G,w);
}//if
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 5.4 图的应用（p206）
# 5.4.1 最小生成树（p207）
GENERIC_MST(G){
T=NULL;
while T 未形成一颗生成树；
do 找到一条最小代价边(u,v)并且加入T后不会产生回路；
T=T∪(u,v);
}
1
2
3
4
5
6
2
3
4
5
6
- Prim算法
void Prim(G,T){
T=∅; //初始化空树
U={w}; //添加任一顶点w
while((V-U)!=∅){ //若树中不含全部顶点
设(u,v)是使u∈U与v∈(V-U)，且权值最小的边；
T=T∪{(u,v)}; //边归入树
U=U∪{v}; //顶点归入树
}
}
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
2.Kruskal算法
void Kruskal(V,T){
T=V; //初始化树T，仅含顶点
numS=n; //连通分量数
while(numS>1){ //如果连通分量数大于1
从E中取出权值最小的边(v,u);
if(v和u属于T中不同的连通分量){
T=T∪{(v,u)}; //将此边加入生成数中
numS--; //连通分量数减1
}
}
}
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
# 5.4.3 拓扑排序（p212）
拓扑排序算法的实现如下
bool TopologicalSort(Graph G){
//如果G存在拓扑序列，返回true；否则返回false，这时G中存在环
InitStack(S); //初始化栈，存储入度为0的顶点
for (int i = 0; i < G.vexnum; ++i)
{
if(indegree[i]==0)
Push(S,i); //将所有入度为0的顶点进栈
}
int count=0; //计数，记录当前已经输出的顶点数
while(!IsEmpty(S)){ //栈不空，则存在入度为0的顶点
Pop(S,i); //栈顶元素出栈
print[count++]=i; //输出顶点i
for(p=G.vertices[i].firstarc;p=p->nextarc){
//将所有i指向的顶点的入度减1，并且将入度减为0的顶点压入栈S
v=p->adjvex;
if(!(--indegree[v]))
Push(S,v); //入度为0，则入栈
}//for
}//while
if(count < G.vexnum)
return false; //排序失败，有向图中有回路
else
return true; //拓扑排序成功
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
归纳总结 1.用邻接矩阵作存储结构
int NextNeighbor(MGraph& G,int x,int y){
if(x!=-1&&y!=-1){
for (int col=y+1;col < G.vexnum;col++)
{
if(G.Edge[x][col] > 0&&G.Edge[x][col] < maxWeight)
return col; //maxWeight代表∞
}
}
return -1;
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
2.用邻接表作存储结构
int NextNeighbor(ALGraph& G,int x,int y){
if(x!=-1){ //顶点x存在
ArcNode *p=G.vertices[x].first; //对应边链表第一个边结点
while(p!=NULL&&p->data!=y) //寻找邻接顶点Y
p=p->next;
if(p!=NULL&&p->next!=NULL)
return p->next->data; //返回下一个邻接顶点
}
return -1;
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
编辑 (opens new window)
上次更新: 2021/02/16, 02:45:37