- 实验目的与要求
- 实验步骤与内容
- 问题与说明
- 备注
- 程序清单
实验目的与要求
1.了解图的基本性质，实现图的构造流程
2.图的基本操作
3.BFS和DFS的思想和实现
4.图在实际中的应用
实验步骤与内容
图
一个图定义为一个偶对（V，E），记G=(V,E)
V是顶点（Vertex）的非空有限集，记为V（G）
E是无序集V和V的一个子集，记为E（G），其元素是图的弧（ARC）
将顶点集合为空的图称为空图
弧（Arc）表示为两个顶点v和w之间存在个关系用顶点偶对< V，W>表示。
1.有向图（Digraph）
E（G）中顶点偶对< v,w>的v和w有序有向；有向图中 < v ，w >∈ E（G）；v弧尾始点，w弧头终点。
2.无向图（Undigraph）
（v，w）表示边
3.完全无向图
顶点n个e条边，有n（n-1）/2 条边的称为完全无向图
对于无向图G=（V，E），若任意两个不同的节点之间都有一条无向边则称为完全无向图。
4.完全有向图
n个点n（n-1）条边
，若对于有向图G=（V，E），任意两个不同的节点间有一弧
5.稀疏图和稠密图
边或弧的数量e小于nlogn的称为稀疏图
6.权值（Weight）
权可以表示从一个顶点到另一个顶点的距离或耗费
7.子图和生成子图
设有图G=（V，E）
子图：图的任意一部分（包括本身）都是图G的一个子图
定义：若V(H)⊆V(G)，E(H)⊆E(G)，且H中边的重数不超过G中对应边的条数，则称H为G的子图，记为H⊆G。
当H⊆G，但H≠G时，H是G的真子图，记为H⊂G。
生成子图：若图G的一个子图包含G的所有顶点，称该子图为G的生成子图
8.顶点的邻接（Adjacent）
对于无向图G=（V，E），若边（V，W）∈E，则称顶点V和W，互为邻接点，即V和W相邻接，边（V，W）依附（incident）与顶点v和w。
9.顶点的度，入度，出度
对于有向图G=（V，E），任意vi∈V，图G中依附于vi的边的数目称为顶点vi的度，记为TD（vi）。
无向图中，所有顶点的度的和第图中边数的两倍，即ΣTD（vi）=2e。
有向图中G=（V，E），若vi∈V，以Vi为起点的有向边称出度Outdegree记为OD（vi）。入度Indegree记为ID（vi），顶点vi的出度与入度之和称为vi的度，记为TD（vi），即TD（vi）=OD（vi）+ID（vi）。
10.路径（Path），路径长度，回路
对于无向图G=（V，E）若从顶点Vi经边若干条能到Vj称Vi和Vi是连通的又称有路径连接；
对于有向图G=（V，E），从顶点Vi到Vj有有向路径，指从Vi经过若干条边能到Vj。
路径之间所有的顶点序列，路径上的边或弧的数目称为路径长度；简单路径：在一条路径中若没有重复相同的节点该路径称为简单路径。
回路：第一个顶点和最后一个顶点相同的路径称为回路。
简单回路：子啊一个回路中若除第一个和最后一个节点外，其余顶点不重复出现称为简单路径。
11.连通图，图的连通分量
若任意Vi，Vj∈V，Vi和Vj都是连通的的称图是连通图，否则是非连通图，。若G是非连通图，则极大的连通子图称为G的连通分量，“极大”的含义是指对子图而言再增加G中的其他节点，子图就不再连通。任何连通图的连通分量只有一个，即其本身，而非连通图有多个连通分量。
对于有向图G=（V，E）若Vi∈V，Vj∈V，都以Vi为起点Vj为终点，及Vj为起点，Vi为终点，称图G是强连通图，否则称为非强连通图：
（1）若G是非强连通图，则有极大子图强连通分量
（2）强连通图只有一个强连通分量，非强连通图有多个连通分量
12.生成树和生成森林
一个连通图（无向图）的生成树是一个极小连通子图，它含有全部n个点和n-1条边足以构成一棵树。
13.网
每个边或弧都附加一个权值的图，称为带权图；带权的连通图，包括强连通的有向图称为网。
图的抽象数据类型定义
ADT{
数据对象V：具有相同特性的数据元素的集合，称为顶点集
数据对象R：R={VR}
VR={<v,w>|<v,w>|v,w∈V∩p(v,w)}
<v,w>表示从v到w的hu
p(v,w)定义了弧的信息
}图的储存结构和基本操作
邻接矩阵
用一位数组vexs[n]存储顶点
用二维数组A[n][n]存储顶点之间的关系，该二位数组称邻接矩阵。在邻接矩阵里，以顶点在vexs数组中下标表示点，邻接矩阵中A[i][j]存放关系
无向图的数组表示
（1）无权图的邻接矩阵
是个n阶对称方阵，A[i][j]=1，若（vi，vj）∈E，A[i][j]=1，若（vi，vj）∉E
（2）带权图的邻接矩阵
无向带权图G=（V，E）的邻接矩阵，是 一个方阵对角线元素为无穷大，如果有权值则为W，如果没有弧则为正无穷。
（3）无向图邻接矩阵的特征
是方阵，Vi的度数为邻接矩阵第i行非0元素个数，边数是上或下三角矩阵
有向图的数组
（1）无权图的邻接矩阵
1表示连接0表示没有连接
（2）带权图的邻接矩阵
简单自己想象一下
（3）有向图邻接矩阵的特征
非0元个数是弧数，第i行非0元非个数是出度OD（vi）；第i列非0元个数是入度ID（vi）。
图的邻接矩阵的操作
#define INIFINITY MAX_VAL
#define MAX_VEX 30
typedef struct AdjType{
ArcvalType ArcVal; //权值
ArcInfoType ArcInfo;
}AdjType;
typedef struct ArcType{
VexType vex1,vex2;
ArcvalType ArcVal;
ArcInforType ArcInfor;
}ArcType;
typedef struct {
GraphKind Kind;
int vexnum,arcnum;
VexType vexs[MAX_VEX];
AdjType adj[MAX_VEX][MAX_VEX];
}MGraph;或
typedef struct ArcVal{
IType adj;
InforType *Infor;
}ArcCell,AddMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {
VertexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
Graphkind kind;
}MGraph;图的各种操作：
（1）图的创建
AdjGraph *Create_Graph(MGraph *G){
scanf("%d",&G->kind);
G->vexnum=0;
return G;
}(2)图的顶点定位
int Locatevex(MGraph *G,VexType *vp){
int k;
for(k=0;k<G->vexnum;k++){
if(G->vexs[k]=*vp)
return k;
return -1;
}(3)加点
int AddVertex(Mgraph *G,VexType *vp){
int k,j;
if(G->vexnum >= MAX_VEX){
return -1;
}
if(LocateVex(G,vp)!=-1){
return -1;
}
k=G->vexnum;
G->vexs[G->vexnum++]=*vp;
if(G->kinf==DG||G->kind==WDG){
for(j=0;j<G->vexnum;j++)
G->adj[j][k].Arcval=G->adj[k][j].Arcval=0;
else
for(j=0;j<G->vexnum;j++){
G->adj[j][k].Arcval=INFINTY;
G->adj[j][k].Arcval=INFINTY;
}
return k;
}(4)向图中加弧
int AddArc(Mgraph *G,ArcType *arc){
int k,j;
k=Locate(G,&arc->vex1);
j=Locate(G,&arc->vex2);
if(k==-1 || j==-1) return -1;
if(G->kind==DG||G->kind==WDG){
G->adj[k][j].ArcVal=arc->Val;
G->adj[k][j].Infor=arc->Infor;
}else{
G->adj[k][j].ArcVal=arc->Val;
G->adj[j][k].ArcVal=arc->Val;
G->adj[k][j].Infor=arc->Infor;
G->adj[j][k].Infor=arc->Infor;
}
return 1;
}邻接链表法
对图的每一个顶点简历一个单链表存储该顶点所有的邻接顶点及其信息，每个单链表都有一个表头结点。
第i个单链表表示依附于Vi的边（对有向图来说是以顶点Vi为头或尾的弧）。
节点结构与邻接链表示例
链表中的节点称为表节点，由三个域组成：
邻接点域（adjvex）指示与顶点Vi邻接的顶点在图中的位置（编号）
链域（nextarc）指向下一个与顶点Vi邻接的表节点
数据域（data）储存与表节点相关的各种信息如权值等
链表法的特点
表头向量中每个分量就是一个单链表的表头节点，分量个数就是图中的顶点个数。
在边或弧稀疏的情况下用链表表示比使用矩阵节省空间
在无向图，顶点Vi的度是第i个链表的节点数
有向图可以建立正邻接表和逆邻接表，正邻接表是以Vi出度建立的邻接表，逆邻接表是一Vi入度建立的邻接表
有向图中第i个链表中的节点数是顶点Vi的出（入）度；求整个出度或入度需要遍历整个邻接表。
节点及其定义
#define MAXVEX 40;
typedef int InforType ;
typeef enum[DG,AG,WDG,WAG]GraphKind;
typedef struct LinkNode{
int adjvex;
InfoType info;
struct LinkNode *nextarc;
}LinkNode;
typedef struct VexType{
VexType data;
int indegree;
LinkNode *firstarc;
}VexNode;
typedef struct ArcType{
VexType vex1,vex2;
InforType info;
}ArcType;
typedef struct {
GraphKind kind;
int vexnum;
VexNode AdjList[MAX_VES];
}ALGraph;图的创建
ALGraph *Create_Graph(ALGraph *G){
scanf("%d",&G->Kind);
G->vexnum;
return G;
}图的顶点定位
实际上是确定一个顶点在AdjList数组中的某个元素的data域内容
int Locate（ALGraph *G,VexType *vp){
int k;
for(k=0;k<G->vexnum;k++)
if(G->AdjList[k].data==*vp)
return k;
return -1;
}图的加顶点
在AdjList数组末尾增加一个节点
int AddVertex（ALGraph *G,VexType *vp){
int k,j;
if(G->vexnum >= MAX_VEX) return -1;
if(LocateVex(G,vp)!=-1) return -1;
G->AdjList[G->vexnum].data =*vp;
G->AdjList[G->vexnum].degree=0;
G->AdjList[G->vexnum].firstarc=NULL;
k=++G->vexnum;
return k;
}(4)向图中加弧
无向图改一个表，有向图改两个表
int AddArc(AlGraph *G,ARcType *arc){
int k,j;
LinkNode *p,*q;
k=LocateVex(G,&arc->vex1);
j=LocateVex(G,&arc->vex2);
if(k==-1||j==-1) return -1;
p=(LinkNode *)malloc(sizeof(LonkNode));
p->adjvex=arc->vex1;
p->info=arc->infor;
p->nextarc=NULL;
q=(LinkNode *)malloc(sizeof(LinkNode));
q->adjvex=arc->vex2;
q->info=arc->infor;
q->nextarc=NULL;
if(G->kind==AG||g->Kind==WAG){
q->nextarc=G->adjList[k].firstarc;
G->adjList[k].firstarc=q;
p->nextarc=G->adjList[j].firstarc;
G->adjList[j].firstarc=p;
} else {
q->nextarc = G->adjList[k].firstarc;
G->adjList[k].firstarc=q;
p->nextarc=G->adjList[j].firstarc;
G->adjList[j].firstarc=p;
//无向图
} else {
q->nextarc = G->adjList[k].firstarc;
G->adjList[k].firstarc=q;
//p->nextarc = G->adjList[j].firstarc;
//g->adjList[j].firstarc=p;
//有向图
}
return 1;
}十字链表（Orthogonal List）
是有向图的另一种链式储存，是将正邻接表和逆邻接表结合起来
每条弧的弧头节点和弧尾节点都存放在链表中，并将弧节点分别组织到以弧尾节点为头（顶点）和一弧头节点为头的链表中。
#define INIFITY MAX_VAL;
#define MAX_VEX 30;
typedef struct ArcNode{
int tailvex ,headvex;
InfoType info;
struct ArcNode,*hlink,*tlink;
}ArcNode;
typedef struct VexNode{
VexType data;
ArcNode *firstin,*firstout;
}VexNode;
tyedef struct {
int vexnum;
VexNode tlink[MAX_VEX];
}OLGraph;从firstout出发，沿着tlink构成正邻接表；从firstin出发，沿着hlink构成逆邻接表。
邻接多重表（Adjacency Multlist）
是无向图的另一种链式存储结构
邻接多重表和邻接表的区别：后者的同一条表要用两个表节点，而邻接多重表只要一个点
图的遍历
遍历的要求：每个顶点仅一次，复杂性可能多次访问，解决办法，打标记。
深度优先搜索（DFS）
使用正邻接表
算法思想
设初始状态，所有节点都未被访问则：
（1）从图中某个节点Vi出发，访问Vi然后找到Vi的一个邻接顶点Vi
（2）从Vi出发深度优先访问Vi相邻接且未被访问过的所有节点
（3）转到（1），直到与Vi相邻接的所有的节点都被遍历
（4）继续选取图中的未被访问的节点，Vj作为起始顶点转（1），直到图中所有节点都被遍历
算法实现
由算法思想知，这是一个递归过程，因此先设计一个从某个顶点为V0开始深度优先搜索的函数，便于调用
typedef emun{FALSE,TRUE} BOOLEAN;
BOOLEAN Visited[MAX_VEX];
void DFS(ALGraph *G,int v){
LinkNode *p;
Visited[v]=TRUE;
visit(v);
p->G->AdjList[v].firstarc;
while(p!=NULL){
if(!visited[p->adjvex])
DFS(G,p->adjvex);
p=p->nextarc;
}
}
void DFS_traverse_Graph(ALGraph *G){
int v;
for(v=0;v<G->vexnum;v++)
visited[v]=FALSE;
//p=G->AdjList[v].first;
for(v=0;v<G->vexnum;v++)
if(!visited[v])
DFS(G,V);
}
boolean visited[];
Status (*VisitFunc)(int v);
void DFSTraverse(Graph G,Status (*visit)(int v)){
VisitFunc = Visit;
for(v=0;v<G->vexnum;++v)
visited[v]=FALSE;
for(v=0;v<G->vexnum;++v)
if(!visited[v])
DFS(G,W);
}
void DFS(Graph G,int v){
visited[v]=TRUE,VisitFunc(V);
for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
if(!visited[w])
DFS(G,w);
}算法分析
顶点至多有一次DFS，有e条边，n个顶点的图DFS时间复杂度为O（n+e），实质是对每个顶点查找邻接顶点的过程。
广度优先搜索算法（BFS）
层次遍历过程
算法思想
设初始节点所有都未被访问
（1）从Vi出发访问Vi；
（2）访问Vi所有节点；
（3）以Vi1，Vi2。。。的次序转（1）；
（4）继续选择未访问节点作为起点，转（1），直到图中所有节点都被访问。
算法实现
加标记数组，要加一个队列保存相邻接的节点
typedef emun {FALSE,TRUE} BOOLEAN;
BOOLEAN Vistied[MAX_VEX];
typedef struct Queue{
int elem[MAX_VEX];
int front,rear;
}Queue;
void BFS_traverse_Graph(ALGraph *G){
int k,v,w;
LinkNode *p;
Queue *Q;
Q=(Queue *)malloc(siezof(Queue));
Q->front=Q->rear=0;
for(k=0;k<G->vexnum;k++)
visited[k]=FALSE;
for(k=0;k<G->vexnum;k++){
v=G->AdjList[k].data;
if(!visited[v]){
Q->elem[++Q->rear]=v;
while(Q->front!=Q->rear){
w=Q->elem[++Q->front];
visited[w]=TRUE;
visited(w);
p=G->AdjList[w].firstarc;
while(p!=NULL){
if(!visited[p->adjvex]){
visited[w]=TRUE;
visit(w);
Q->elem[++Q->rear]=p->adjvex;
}
p=p->nextarc;
}
}
}
}
}
void BFS_Traverse(Graph G,Status (*visit)(int v)){
visited;
for(v=0;v<G->vexnum;++v)
visited[v]=FALSE;
InitQueue(Q);
for(v=0;v<G->vexnum;++v)
if(!visited[v]){
visited[v]=TRUE;
visit(v);
EnQueue(Q,v);
while(!QueueEmpty(Q)){
DeQueue(Q,u);
for(w=FirstAdjvex(G,v);w>=0;w=NextAdNext(G,v,w)
if(!visited[w]){
visited[w]=TRUE;
visit(w);
EnQueue(Q,w);
}
}
}
}
次序不同，时间O（n+e）DFS 回溯的方法；BFS分层顺序不是递归算法
图的遍历算法的应用
无向图的连通分量
生成树
对于无向图，对其遍历时
若连通图仅需从任一顶点出发就访问图中的所有顶点
若非连通图：从图中多个顶点出发，每次从一个新点出发访问所有的节点集序列恰好是各个连通分量的顶点集。
图的生成树和生成森林算法
储存结构，孩子-兄弟表示法 递归算法
对DFS（BFS）稍作修改
typedef struct CSNode{
ELemType data;
struct CSNode *firstchild,*nextsibing;
}CSNode ;
CSNode *DFStree(ALGraph *G,int v){
CSNode *T,*ptr,*q;
LinkNode *p;
int w;
visited[v]=TRUE;
T=(CSNode *)malloc(sizeof(CSNode));
T->data=G->AdjList[v].data;
T->firstchild=T->nextsibling=NULL;
q=NULL;
p=G->AdjList[v].firstarc;
q=NULL:
p=G->AdjList[v].firstarc;
while(p!=NULL){
w=p->adjvex;
if(!visited[w]){
ptr=DFStree(G,w);
if(q=NULL) T->firstchild=ptr;
else q->nextsibling=ptr;
q=ptr;
}
p=p->nextarc;
}
return T;
}判断连通性
bool Connect(ALGraph *G){
int i;
bool flag= true;
for(i=0;i<G->n;i++)
visited[i]=0;
DFS(G,0);
for(i=0;i<G->n;i++)
if(visited[i]==0){
flag=false;
break;
}
return flag;
}最小生成树（Minimum Spanning Tree）MST
权值最小但是不构成回路，n-1条边
普利姆算法（Prim）
算法实现
邻接矩阵（二维数组）两个顶点间不存在权，标记为最大值。
设置一个一维数组closedge保存V-V中各顶点到V中顶点是有权后最小的边
typedef struct {
int adjvex;
int lowcost;
}closedge[MAX_EDGE];closedge[j].adjvex=k表明边（Vi，Vk）是V-V中顶点j到V中权值最小的边
算法步骤
（1）从closedge中选择一条权值最小的边（Vk，Vj）
设closedge[k].lowcost为0，Vk加入V中；
根据Vk更新的closedge每个元素：任意Vi∈V-V，若cost（i，k）≤ closedge[i].lowcost
加入Vk后，（Vi，Vk）或Vi到U中权值最小的边closedge[i].lowcost=cost(i,k);closedge[i].adjvex=k;
（2）重复（1）n-1次就得到了MST
在prime中，图采用邻接矩阵存储，所构成最小生成树用一维数组n-1
typedef struct MSTEdge{
int vex1,vex2;
WeightType weight;
}MSTEdge;
#define INIFITY MAX_VAL;
MSTEdge *Prim_MST(AdjGraph *G,int u){
MSTEdge TE[];
int j,k,v,min;
for(j=0;j<G->vexnum;j++){
closedge[j].adjvex=u;
closedge[j].lowcost=G->adj[j][u];
}
closedge[u].lowcost=0;
TE=(MSTEdge *)malloc(sizeof(MSTEdge));
for(j=0;j<G->vexnum-1;j++){
min=INFINITY;
for(v=0;v<G->vexnum;v++)
if(closedge[v].lowcost!=0 && closedge[v].lowcost<min){
min=closedge[v].lowcost;
k=v;
}
TE[j].vex1=closedge[k].adjvex;
TE[j].vex2=k;
TE[j].weight=closedge[k].lowcost;
closedge[k].lowcost=0;
for(v=0;v<G->vexnum;v++)
if(G->adj[v][k] < closedge[v].lowcost){
closedge[v].lowcost=G->adj[v][k];
closedge[v].adjvex=k'
}
}
return TE;
}时间复杂度为O（n^2)与边的数目无关，求closedge权值最小的边为n-1修改closedge
克鲁斯卡尔算法（Kruskal）
Kruskal算法实现的关键是判断能否构成边，定义数组vset[n]存放T中每个顶点所在的连通分量的编号
初值：Vset[i]=i;表示每个点都是一个独立的连通分量
当往T中加入边（vi，vj）时先检查vset[i]vest[j]的值，若vset[i]=vset[j],表明vi和vj在同一个连通分量里，会产生回路
加入新点，将两个分量合并将一个连通分量的编号换成另一个的
MSTEdge *Kurskal_MST(ELGraph *G){
MSTEdge TE[];
int j,k,v,s1,s2,vset[];
WeightType w;
Vset=(int *)malloc(G->vexnum*sizeof(int));
for(j=0;j<G0>vexnum;j++)
vset[j]=j;
sort(G->edgeList);
j=0;
k=0;
while(k<G->vexnum-1&&j<G->edgenum){
s1=Vset[G->edgelist[j].vex1);
s2=Vset[G->edgelist[j].vex2);
if(s1!=s2){
TE[k].vex1=G->edgelist[j].vex1;
TE[k].vex2=G->edgelist[j].vex2;
TE[k].weight=G->edgelist[j].weight;
k++;
for(v=0;v<G->vexnum;v++)
if(vset[v]==s2)
vset[v]=s1;
}
j++;
}
free(vset);
return TE;
}算法时间复杂度O（eloge+n^2)
问题与说明
备注
CLion开发环境，C语言实现
