配套资源下载
第七章 图【数据结构与算法】
7.1 应用实例
城市交通问题
7.2图的基本概念
图的定义:图是由顶点集V和弧集R构成的数据结构,Graph=（V,R）
其中：
V={v|v∈ DataObject}
R={VR}
VR={<v,w>|P(v,w)且(v,w∈V)}
<v,w>表示从顶点v到顶点w的一条弧,称为“弧尾”,w为“弧头”
谓词P(v,w)定义了弧<u,w>的意义或信息,表示从到w的一条单向通道。
苦<v,w>∈VR,必有<w,v>∈VR,则以(v,w)代替这两个有序对,称v和w之间存在一条边。
有向图:由顶点集和弧集构成的图称为“有向图”。
无向图:由顶点集和边集构成的图称为“无向图"。
有向网或无向网:有向图或无向图中的弧或边带权后的图分别称为“有向网"或“无向网”
子图:设图G=(V|{VR})和图G’=(V’|{VR’}),且V’⊆V,VR’⊆VR,则称G’为G的子图。
完全图:图中有n个顶点、n(n-1)/2条边的无向图称为“完全图”。
有向完全图;图中有n个顶点、n(n-1)条弧的有向图称为“有向完全图”
稀疏图:假设图中有n个顶点e条边(或弧),若边(或弧)的个数e<nlogn,则称为“稀疏图”, 否则称为“稠密图”
邻接点:若无向图中顶点v和w之间存在一条边(n,w),则称顶点v和w互为邻接点,称边 (r,w)依附于顶点n和w或边(v,w)与顶点v和w相关联。
顶点的度;在无向图中与顶点v关联的边的数目定义为v的度,记为TD(v)。
握手定理:可以看出,在无向图中,其总度数等于总边数的两倍。
对于有向图,若顶点v和w之间存在一条弧<u,w>,则称顶点v邻接到顶点w,顶点v邻接自 顶点v,称弧<v,w>与顶点u和w相关联。
以v为尾的弧的数目定义为v的出度,记为OD(v)。
以为头的弧的数目定义为v的入度,记为ID(v)。
顶点的度(TD)=出度(OD)+入度(ID)。
可以看出,在有向图中,其总人度、总出度和总强数相等
路径:设用G=(V|{VR}中的{u=vi,0,vi,1,…,vi,m=w}顶点序列中，有（vi,j-1,vi,j）∈VR（1<=j<=m）,则称从顶点u到顶点w之间存在一条路径。路径上边的数目称为“路径长度”，有向图的路径也是有向的。
简单路径:顶点不重复的欧种称为“简单路径“
回路:首尾顶点相同的路径称为“回路“
简单回路:除了首尾顶点,中间任何一个顶点不重复的问路称为“简单回路”
连通图:在无向图中,若顶点Vi到Vj有路径存在,则称Vi和Vj是连通的。若无向图中任意两个顶点之间都有路径相通,即是连通的,则称此图为连通图,否则,称其为非连通图
无向图中各个极大连通子图称为该图的“连通分量”
强连通图:在有向图中,若任意两个顶点之间都存在一条有向路径,则称此有向图为“强连通图”;否则,称其为“非强连通图”。
有向图中各个极大强连通子图称为该图的强连通分量
生成树:包含连通图中全部项点的极小连通子图称为该图的“生成树”,即假设一个连通图有n个顶点和e条边,其中n个顶点和n-1条边构成一个极小连通子图,该极小连通子图为此连通图的生成树。对非连通图,由各个连通分量的生成树构成的集合称为该非连通图的“生成森林”
7.3图的存储结构
7.3.1邻接矩阵
图的邻接矩阵是表示顶点之间的相邻关系的矩阵，是顺序存储结构。
设图G是一个具有n个顶点的图,它的顶点集合V={v0,v1,v2，…,vn-1}则顶点之间的关系可用如下形式的矩阵A来描述,即矩阵A中每个元素A[i][j]满足
{ 1 若<v~i~,v~j~>或（v~i~,v~j~）∈VR A[i][j] = { { 0 反之
对于带权图(网),邻接矩阵A中每个元素A[i][j]满足
{ weight 若<v~i~,v~j~>或（v~i~,v~j~）∈VR A[i][j] = { { ∞ 反之
邻接矩阵的数据类型描述为:
#include<stdio.h> #include<stdlib.h> #define MAXVEX 20 //最大顶点个数 #define INFINITY 32768 //表示极大值 typedef int Vextype; typedef struct{ int arcs[MAXVEX][MAXVEX]; //边（或弧）信息 Vextype vex[MAXVEX]; //顶点信息，顶点类型根据实际情况自行定义 int vexnum; //顶点数目 int arcnum; //边(或弧)数目 }AdjMatrix;//邻接矩阵
创建
相关代码请看配套资源
1-邻接矩阵.c
只针对无向网
void main(){ AdjMatrix* G=(AdjMatrix*)malloc(sizeof(AdjMatrix)); Create(G); Printf(G); }
运行结果如下
相关代码请看配套资源
2-邻接矩阵plus.c
适用于各种类型的图
void main(){ printf("创建\n"); AdjMatrix* G=(AdjMatrix*)malloc(sizeof(AdjMatrix)); printf("输入图的类型 "); printf("无向图(1) "); printf("有向图(2) "); printf("无向网(3) "); printf("有向网(4) ："); scanf("%d",&G->t); Create(G); printf("打印\n"); Printf(G); }
运行结果如下
7.3.2 邻接表
邻接表由边表和顶点表组成。
边表就是对图中的每一个顶点建立一条单链表，表中存放与该顶点邻接的所有顶点，相当于邻接矩阵的所有非零元素。
顶点表用于存放图中每一个顶点的信息以及指向改顶点边表的头指针。
顶点结构
vexdata head
图的边结构
adjvex next
网的边结构
adjvex weight next
邻接矩阵的数据类型描述为:
#include<stdio.h> #include<stdlib.h> #define MAXVEX 20 typedef struct ArcNode{ int adjvex; int weight; struct ArcNode *next; }ArcNode;
相关代码请看配套资源
3-邻接表.c
只针对无向网
void main(){ AdjList* G=(AdjList*)malloc(sizeof(AdjList)); Create(G); Printf(G); }
运行结果如下
相关代码请看配套资源
邻接表plus.c
适用于各种类型的图
void main(){ AdjList* G=(AdjList*)malloc(sizeof(AdjList)); printf("输入图的类型 "); printf("无向图(1) "); printf("有向图(2) "); printf("无向网(3) "); printf("有向网(4) ："); scanf("%d",&G->t); Create(G); Printf(G); }
运行结果如下
7.3.3 十字链表
略
7.3.4多重链表
略
7.4图的遍历
- BFS
- DFS
7.4.1深度优先搜索遍历
图的深度优先搜索遍历类似于树的先序遍历,尽可能先对纵深方向进行搜索。其基本思想为从图中某个顶点V出发,访问此顶点,然后依次从V的各个未被访问的邻接点出发深度优先搜索遍历图,直至图中所有和V,有路径相通的顶点都被访问到。若图是连通图,则遍历过程结束，否则，图中还有顶点未被访问,则另选图中一个未被访问的顶点作
为新的出发点。重复上述过程,直至图中所有顶点都被访问到。
相关代码请看配套资源
5-DFSAdjMatrix.c
#include<stdio.h> #include "1-邻接矩阵plus.c" //去掉main() void main(){ printf("创建\n"); AdjMatrix* G=(AdjMatrix*)malloc(sizeof(AdjMatrix)); printf("输入图的类型 "); printf("无向图(1) "); printf("有向图(2) "); printf("无向网(3) "); printf("有向网(4) ："); scanf("%d",&G->t); Create(G); int v0=1; printf("从v0=%d开始DFS:\n",v0); DFSAdjMatrix(*G,v0); printf("\n"); printf("DFS:\n"); TraverseG(*G); printf("\n"); // visited[MAXVEX]={0}; // int r=HasAPath(*G,1,2); // printf("%d",r); printf("打印\n"); Printf(G); }
运行结果如下
相关代码请看配套资源
6-DFSAdjList.c
#include<stdio.h> #include "4-邻接表plus.c" //去掉main() void main(){ AdjList* G=(AdjList*)malloc(sizeof(AdjList)); printf("输入图的类型 "); printf("无向图(1) "); printf("有向图(2) "); printf("无向网(3) "); printf("有向网(4) ："); scanf("%d",&G->t); Create(G); printf("DFS:\n"); // int v0=1; // DFSAdjMatrix(*G,v0); TraverseG(*G); printf("\n"); printf("打印\n"); Printf(G); }
运行结果如下
