数据结构期末复习（第七章 图）
数据结构期末复习（第七章 图）文章目录数据结构期末复习（第七章 图）Part 1、知识点总结1.图的基本概念1.1 图的定义1.2 图的基本术语1.3 完全图1.4 稠密图、稀疏图1.5 子图1.6 路径和路径长度1.7 回路或环1.8 连通、连通图和连通分量1.9 强连通图和强连通分量1.10 生成树、生成森林：1.11 权和网1.12 注意2 图的存储结构2.1 邻接矩阵表示法（数组表示）2.
·
数据结构期末复习（第七章 图）
文章目录
Part 1、知识点总结
1.图的基本概念
1.1 图的定义
- 图(Graph)是一种网状数据结构。 G由顶点集合V(G)和边集合E(G)构成，其形式化定义为：G=（V，E）。
- 说明：对于n个顶点的图，对每个顶点连续编号，即顶点的编号为0～n-1。通过编号唯一确定一个顶点。
- 在图G中，如果代表边的顶点对是无序的，则称G为无向图。用圆括号序偶表示无向边。
- 如果表示边的顶点对是有序的，则称G为有向图。用尖括号序偶表示有向边。
【例1】设有有向图G1，形式化定义是：
G1=(V1 ，E1)
V1={a,b,c,d}
E1={<a,b>,<a,c>, <c,d> ,<d,a>,<d,b>}
【例2】设有无向图G2，形式化定义是：
G2=(V2 ，E2)
V2={a,b,c,d}
E2={(a,b), (a,c), (b,c), (c,d)}
1.2 图的基本术语
-
端点和邻接点 无向图：若存在一条边(i，j) →顶点i和顶点j为端点，它们互为邻接点。 有向图：若存在一条边<i，j>
→顶点i为起始端点（简称为起点），顶点j为终止端点（简称终点），i邻接到j，j邻接于i。 -
顶点的度、入度和出度
无向图：以顶点i为端点的边数称为该顶点的度。
有向图：以顶点i为终点的入边的数目，称为该顶点的入度。以顶点i为始点的出边的数目，称为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。 -
若一个图中有n个顶点和e条边，每个顶点的度为di（0≤i≤n-1），则有：
1.3 完全图
- 无向图：每两个顶点之间都存在着一条边，称为无向完全图， 包含有n(n-1)/2条边。
- 有向图：每两个顶点之间都存在着方向相反的两条边，称为有向完全图，包含有n(n-1)条边。
1.4 稠密图、稀疏图
- 当一个图接近完全图时，则称为稠密图。
- 相反，当一个图含有较少的边数（即当e<nlogn）时，则称为稀疏图。
1.5 子图
设有两个图G=(V，E)和G’=(V’，E’)，若V’是V的子集，即V’∈V，且E’是E的子集，即E’ ∈E，则称G’是G的子图。
1.6 路径和路径长度
- 在一个图G=(V，E)中，从顶点i到顶点j的一条路径(i，i1，i2，…，im，j)。
所有的(ix，iy) ∈E(G)，或者<ix，iy> ∈E(G) - 路径长度是指一条路径上经过的边的数目。
- 若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径。
1.7 回路或环
若一条路径上的开始点与结束点为同一个顶点，则此路径被称为回路或环。
开始点与结束点相同的简单路径被称为简单回路或简单环。
1.8 连通、连通图和连通分量
- 无向图：若从顶点i到顶点j有路径，则称顶点i和j是连通的。
- 无向图G中的极大连通子图称为G的连通分量。
- 显然，任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。
- 若图中任意两个顶点都连通，则称为连通图，否则称为非连通图。
1.9 强连通图和强连通分量
- 有向图：若从顶点i到顶点j有路径，则称从顶点i到j是连通的。
- 若图G中的任意两个顶点i和j都连通，即从顶点i到j和从顶点j到i都存在路径，则称图G是强连通图。
- 有向图G中的极大强连通子图称为G的强连通分量。显然，强连通图只有一个强连通分量，即本身。非强连通图有多个强连通分量。
- 在一个非强连通中找强连通分量的方法。
- 在图中找有向环。
- 扩展该有向环：如果某个顶点到该环中任一顶点有路径，并且该环中任一顶点到这个顶点也有路径，则加入这个顶点。
1.10 生成树、生成森林：
一个连通图(无向图)的生成树是一个极小连通子图，它含有图中全部n个顶点和只有足以构成一棵树的n-1条边，称为图的生成树。
关于无向图的生成树的几个结论：
- 一棵有n个顶点的生成树有且仅有n-1条边；
- 如果一个图有n个顶点和小于n-1条边，则是非连通图；
- 如果多于n-1条边，则一定有环；
- 有n-1条边的图不一定是生成树。
有向图的生成森林是这样一个子图，由若干棵有向树组成，含有图中全部顶点，但是只有足够构成若干棵有向树的边。
有向树是只有一个顶点的入度为0 ，其余顶点的入度均为1的有向图。
1.11 权和网
图中每一条边都可以附带有一个对应的数值，这种与边相关的数值称为权。
权可以表示从一个顶点到另一个顶点的距离或花费的代价。
边上带有权的图称为带权图，也称作网。
1.12 注意
连通图、连通分量针对无向图，强连通图、强连通分量针对有向图
2 图的存储结构
- 存储每个顶点的信息
- 存储每条边的信息
图的常用的存储结构有：邻接矩阵、邻接链表、十字链表、邻接多重表和边表。
2.1 邻接矩阵表示法（数组表示）
设G=(V，E)是具有n（n＞0）个顶点的图，顶点的编号依次为0～n-1。
基本思想：
- 用一维数组vexs[n]存储顶点信息，
- 用二维数组A[n][n]存储顶点之间关系的信息。该二维数组称为邻接矩阵。
- 在邻接矩阵中，以顶点在vexs数组中的下标代表顶点，邻接矩阵中的元素A[i][j]存放的是顶点i到顶点j之间关系的信息。
G的邻接矩阵A是n阶方阵，其定义如下：
- 如果G是无权无向图，则：
- 如果G是带权无向图，则：
无向图邻接矩阵的特性:
- 邻接矩阵是对称方阵；
- 对于顶点vi，其度数是第i行的非0元素的个数；
- 无向图的边数是上(或下)三角形矩阵中非0元素个数。
- 如果G是无权有向图，则：
- 如果G是带权有向图，则:
有向图邻接矩阵的特性
对于顶点vi:- 第i行的非0元素的个数是其出度OD(vi)；
- 第i列的非0元素的个数是其入度ID(vi) ;
邻接矩阵中非0元素的个数就是图的弧的数目。
2.2 邻接矩阵操作
其存储结构形式定义如下：
#define INFINITY MAX_VAL /* 最大值∞ */
/* 根据图的权值类型，分别定义为最大整数或实数 */
#define MAX_VEX 30 /* 最大顶点数目 */
typedef enum {DG, AG, WDG,WAG} GraphKind ;
/* {有向图，无向图，带权有向图，带权无向图} */
其存储结构形式定义如下：
typedef struct ArcType
{
VexType vex1, vex2 ; /* 弧或边所依附的两个顶点 */
ArcValType ArcVal ; /* 弧或边的权值 */
ArcInfoType ArcInfo ; /* 弧或边的其它信息 */
}ArcType ; /* 弧或边的结构定义 */
其存储结构形式定义如下：
typedef struct
{
GraphKind kind ; /* 图的种类标志 */
int vexnum , arcnum ; /* 图的当前顶点数和弧数 */
VexType vexs[MAX_VEX] ; /* 顶点向量 */
AdjType adj[MAX_VEX][MAX_VEX];/*邻接矩阵*/
}MGraph ; /* 图的结构定义 */
以下不要求掌握！但是个人建议掌握。
(1) 图的创建(空图)
void Create_Graph(MGraph * G)
{
printf(“请输入图的种类标志：”) ;
scanf(“%d”, &G->kind) ;
G->vexnum=0 ; /* 初始化顶点个数 */
}
(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)
{ printf(“Vertex Overflow !\n”) ; return(-1) ; }
if (LocateVex(G , vp)!=-1)
{ printf(“Vertex has existed !\n”) ; return(-1) ; }
G->vexs[G->vexnum++]=vp ;
if (G->kind==DG||G->kind==AG) /*是不带权图 */
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=INFINITY ;
G->adj[k][j].ArcVal=INFINITY ;}
k=G->vexnum ;
return(k) ;
}
(4) 向图中增加一条弧
int AddArc(MGraph *G , ArcType *arc)
{ int k , j ;
k=LocateVex(G , arc->vex1) ;
j=LocateVex(G , arc->vex2) ;
if (k==-1||j==-1)
{ printf(“Arc’s Vertex do not existed !\n”) ;
return(-1) ;
}
if (G->kind==DG||G->kind==WDG)//有向图或带权有向图
{ G->adj[k][j].ArcVal=arc->ArcVal;
G->adj[k][j].ArcInfo=arc->ArcInfo ;
}
else /* 是无向图或带权的无向图,需对称赋值 */
{ G->adj[k][j].ArcVal=arc->ArcVal ;
G->adj[j][k].ArcVal=arc->ArcVal ;
G->adj[k][j].ArcInfo=arc->ArcInfo ;
G->adj[j][k].ArcInfo=arc->ArcInfo ;
}return(1) ;
}
以下开始需要掌握
2.3邻接链表存储
基本思想：只存储图中有关联的边的信息
- 对图的每个顶点均建立一个边表（单链表），存储该顶点所有邻接顶点及其相关信息。
- 每个顶点信息与其边链表的头指针构成一个表头结点表。
- 一个n个结点的图的邻接表表示由表头结点表和边表两部分构成。
- 表头结点
每个边表设一个表头结点(称为顶点结点)，由两个域组成：
链域(firstarc)指向链表中的第一个结点；
数据域(data) 存储顶点名或其他信息。
- 表头结点表：
由所有顶表头结点以顺序结构形式存储，以便可以随机访问任意顶点的邻接点单链表，下标指示顶点的序号。
- 边表
边表中的结点称为表结点，每个结点由三个域组成：
邻接点域(adjvex)指示与顶点Vi邻接的顶点在图中的位置(顶点编号)，
链域(nextarc)指向下一个与顶点Vi邻接的表结点
数据域(info)存储和边或弧相关的信息，如权值等。
- 用邻接链表存储图时，对无向图，其邻接链表是唯一的.
- 对有向图，其邻接链表有两种形式:
邻接表法的特点: - 表头结点表中每个分量就是一个单链表的头结点，分量个数就是图中的顶点数目；边表中结点数量是图中边的个数；
- 在边或弧稀疏的条件下，用邻接表表示比用邻接矩阵表示节省存储空间；
- 在邻接表上容易找出任一顶点的第一个邻接点和下一个邻接点；
- 在无向图，顶点Vi的度是第i个链表的结点数；
- 对有向图可以建立正邻接表或逆邻接表。
- 正邻接表是以顶点Vi为出度(即为弧的起点)而建立的邻接表；
- 逆邻接表是以顶点Vi为入度(即为弧的终点)而建立的邻接表；
- 在有向图中，第i个链表中的结点数是顶点Vi的出 (或入)度；求入 (或出)度，须遍历整个邻接表。
结点及其类型定义:
#define MAX_VEX 30 /* 最大顶点数 */
typedef int InfoType;
typedef enum {DG, AG, WDG,WAG} GraphKind ;
typedef struct LinkNode
{
int adjvex ; // 邻接点在头结点数组中的位置(下标)
InfoType info ; // 与边或弧相关的信息, 如权值
struct LinkNode *nextarc ; // 指向下一个表结点
}LinkNode ; /* 表结点类型定义 */
typedef struct VexNode
{
VexType data; // 顶点信息
int indegree ; //顶点的度, 有向图是入度或出度或没有
LinkNode *firstarc ; // 指向第一个表结点
}VexNode ; /* 顶点结点类型定义 */
typedef struct ArcType
{
VexType vex1, vex2 ; /* 弧或边所依附的两个顶点 */
InfoType info ; // 与边或弧相关的信息, 如权值
}ArcType ; /* 弧或边的结构定义 */
typedef struct
{
GraphKind kind ; /* 图的种类标志 */
int vexnum ;
VexNode AdjList[MAX_VEX] ;
}ALGraph ; /* 图的结构定义 */
以下不要求掌握！但是个人建议掌握。
(1) 图的创建
void Create_Graph(ALGraph * G)
{
printf(“请输入图的种类标志：”) ;
scanf(“%d”, &G->kind) ;
G->vexnum=0 ; /* 初始化顶点个数 */
}
(2) 图的顶点定位
int LocateVex(ALGraph *G , VexType vp)
{
int k ;
for (k=0 ; k<G->vexnum ; k++)
if (G->AdjList[k].data==vp) return(k) ;
return(-1) ; /* 图中无此顶点 */
}
(3) 向图中增加顶点
int AddVertex(ALGraph *G , VexType vp)
{
int k , j ;
if (G->vexnum>=MAX_VEX)
{ printf(“Vertex Overflow !\n”) ; return(-1) ; }
if (LocateVex(G , vp)!=-1)
{ printf(“Vertex has existed !\n”) ; 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)
{ printf(“Arc’s Vertex do not existed !\n”) ;
return(-1) ;
}
p=(LinkNode *)malloc(sizeof(LinkNode)) ;
p->adjvex=arc->vex1 ; p->info=arc->info ;
p->nextarc=NULL ; /* 边的起始表结点赋值 */
q=(LinkNode *)malloc(sizeof(LinkNode)) ;
q->adjvex=arc->vex2 ; q->info=arc->info ;
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 ; /* 建立正邻接链表用 */
//q->nextarc=G->adjlist[j].firstarc ;G->adjlist[j].firstarc=q ; /* 建立逆邻接链表用 */
}return(1);}
以下开始需要掌握
2.4 十字链表存储
十字链表是有向图的另外一种存储结构，它是正邻接表和逆邻接表的结合。
2.5 邻接多重表存储
邻接多重表是无向图的另外一种存储结构，与十字链表类似。
3.图的遍历
- 从给定图中任意指定的顶点（称为初始点）出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。
- 图的遍历得到的顶点序列称为图遍历序列。
- 图的任意顶点可能和其余的顶点相邻接，可能在访问了某个顶点后，沿某条路径搜索后又回到原顶点。
- 在遍历过程中记下已被访问过的顶点。
- 设置一个辅助向量Visitedn，其初值为0，一旦访问了顶点vi后，使Visited[i]为1或为访问的次序号。
- 图的遍历算法有深度优先搜索算法和广度优先搜索算法。采用的数据结构是(正)邻接链表。
3.1 深度优先搜索算法
深度优先搜索(Depth First Search–DFS)遍历类似树的先序遍历，是树的先序遍历的推广。
设初始状态时图中的所有顶点未被访问，则：
- 从图中某个顶点vi出发，访问vi；然后找到vi的一个邻接顶点vi1 ；
- 从vi1出发，深度优先搜索访问和vi1相邻接且未被访问的所有顶点；
- 转⑴ ，直到和vi相邻接的所有顶点都被访问为止
- 继续选取图中未被访问顶点vj作为起始顶点，转(1)，直到图中所有顶点都被访问为止。
无向图的深度优先搜索遍历示例(红色箭头)。某种DFS次序是：v0→ v2 → v1 → v3 → v4
int Visited[MAX_VEX] ; /* 访问标志，初始状态0 */
void DFS(AdjGraph *G，int v)
{ ArcNode *p; int w;
visited[v]=1; //置已访问标记
printf("%d "，v); //输出被访问顶点的编号
p=G->adjlist[v].firstarc; //p指向头结点为v的第一个边表结点 while (p!=NULL)
{ w=p->adjvex; //取p所指向边表结点元素的下标
if (visited[w]==0) //该结点未被访问过
DFS(G，w); //若w顶点未访问，递归访问它
p=p->nextarc; //p指向头结点为v的下一个边表结点
}
}
void DFS_traverse_Grapg(ALGraph *G)
{ int v ;
for (v=0 ; v<G->vexnum ; v++)
Visited[v]=0 ; /* 访问标志初始化 */
for (v=0 ; v<G->vexnum ; v++)
if (!Visited[v]) DFS(G , v);
}
该算法的时间复杂度为O(n+e)。
3.2 广度优先算法
广度优先搜索(Breadth First Search–BFS)遍历类似树的层次遍历的过程。
设初始状态时图中的所有顶点未被访问，则：
- 从图中某个顶点vi出发，访问vi；
- 访问vi的所有相邻接且未被访问的所有顶点vi1，vi2，…，vim；
- 以vi1，vi2， …，vim的次序，以vij(1≦j≦m)依此作为vi ，转⑴；
- 继续选取图中未被访问顶点vk作为起始顶点，转⑴，直到图中所有顶点都被访问为止。
- 为了标记图中顶点是否被访问过，同样需要一个访问标记数组，int Visited[MAX_VEX]；
- 其次，为了依此访问与vi相邻接的各个顶点，需要附加一个队列来保存访问vi的相邻接的顶点。
typedef struct Queue
{ int elem[MAX_VEX] ;
int front , rear ;
}Queue ; /* 定义一个队列保存将要访问顶点 */
void BFS (ALGraph *G,int v)
{ int k , w ;
LinkNode *p ; Queue *Q ;
Q=(Queue *)malloc(sizeof(Queue)) ;
Q->front=Q->rear=0 ; /* 建立空队列并初始化 */
for (k=0 ; k<G->vexnum ; k++)
{ v=G->AdjList[k].data ; /* 单链表的头顶点 */
if (!Visited[v]) /* v尚未访问 */
{ Q->elem[++Q->rear]=v ; /* v入队 */
while (Q->front!=Q->rear)
{ w=Q->elem[++Q->front] ; /* 队首出队 */
Visited[w]=1 ; /* 置访问标志 */
printf(“ %d ”, w) ; /* 访问队首元素 */
p=G->AdjList[w].firstarc ;
while (p!=NULL)
{ if (Visited[p->adjvex]==0) //若当前邻接点未被访问
Q->elem[++Q->rear]=p->adjvex ;
p=p->nextarc ; //找下一个邻接点
}
} /* end while */
} /* end if */
} /* end for */ printf("\n"); }
该算法的时间复杂度为O(n+e)。
void BFS_traverse_Grapg(ALGraph *G)
{ int v ;
for (v=0 ; v<G->vexnum ; v++)
Visited[v]=0 ; /* 访问标志初始化 */
for (v=0 ; v<G->vexnum ; v++)
if (!Visited[v]) BFS(G , v);
}
4. 图的连通性问题
4.1无向图的连通分量与生成树
- 对于无向图，对其进行遍历时：
- 若是连通图：仅需从图中任一顶点出发，就能访问图中的所有顶点；
- 若是非连通图：需从图中多个顶点出发。每次从一个新顶点出发所访问的顶点集序列恰好是各个连通分量的顶点集；
按图中给定的邻接表进行深度优先搜索遍历：
2次调用DFS所得到的顶点访问序列集是： { v1 ,v3 ,v2}和{ v4 ,v5 }
- 若G=(V,E)是无向连通图， 顶点集和边集分别是V(G) ，E(G) 。
若从G中任意点出发遍历时， E(G)被分成两个互不相交的集合：
T(G) ：遍历过程中所经过的边的集合；
B(G) ：遍历过程中未经过的边的集合；
显然，图G’=(V, T(G))是G的极小连通子图，且G’是一棵树。
G’称为图G的一棵生成树。
- 从任意点出发按DFS算法得到生成树G’称为深度优先生成树；
按BFS算法得到的G’称为广度优先生成树。
- 若G=(V,E)是无向非连通图，对图进行遍历时得到若干个：
连通分量的顶点集：V1(G) ,V2(G) ,…,Vn(G)
相应所经过的边集：T1(G) ,T2(G) , …,Tn(G)
则对应的顶点集和边集的二元组：
Gi=(Vi(G),Ti(G))(1≦i≦n)
是对应分量的生成树，所有这些生成树构成了原来非连通图的生成森林。
说明： - 当给定无向图要求画出其对应的生成树或生成森林时：
必须先给出相应的邻接表，然后才能根据邻接表画出其对应的生成树或生成森林。
4.2 最小生成树
- 如果连通图是一个带权图，则其生成树中的边也带权，生成树中所有边的权值之和称为生成树的代价。
- 最小生成树(Minimum Spanning Tree) ：带权连通图中代价最小的生成树称为最小生成树。
- 最小生成树的性质：
设N=(V,{E})是一连通网，U是顶点集V的一个非空子集。若（u,v）是一条具有最小权值的边，存在一颗包含边（u,v）的最小生成树。 - 构造最小生成树的基本原则是：
尽可能选取权值最小的边，但不能构成回路；
选择n-1条边构成最小生成树。
常用算法：Prim、Kruskal算法
4.3 prim算法
从连通网N=(V，E)中找最小生成树T=(U，TE)
- 算法思想
⑴ 若从顶点v0出发构造，U={v0}，TE={}；
⑵ 先找权值最小的边(u，v)，其中u∈U且v∈V-U，并且子图不构成环，则：
U= U∪{v}，TE=TE∪{(u，v)} ；
⑶ 重复⑵ ，直到U=V为止。则TE中必有n-1条边， T=(U，TE)就是最小生成树。
- 算法实现说明
设用邻接矩阵表示法，两个顶点之间不存在边的权值为机内允许的最大值。
为便于算法实现，设置一个一维数组closedge[n]，用来保存V- U中各顶点到U中顶点权值最小的边。数组元素的类型定义是：
struct {
int adjvex ; /* 边所依附于U中的顶点 */
int lowcost ; /* 该边的权值 */
}closedge[MAX_EDGE] ;
假设从顶点vs开始构造最小生成树。初始时令：
表示V-U中的各顶点到U中权值最小的边(k≠s) ，cost(k, s)表示边(vk, vs) 权值。
- 算法步骤
⑴ 从closedge中选择一条权值(不为0)最小的边(vk, vj) ，然后做：
① closedge[k].lowcost置0 ，表示vk已加入到U中；
② 根据新加入vk的更新closedge中每个元素：
vi∈V-U ，若cost(i, k)≦colsedge[i].lowcost，表明在U中新加入顶点vk后， (vi, vk)成为vi到U中权值最小的边，置：
⑵ 重复⑴n-1次就得到最小生成树。 - 算法实现
在Prime算法中，图采用邻接矩阵存储，所构造的最小生成树用一维数组存储其n-1条边，每条边的存储结构描述：
typedef struct MSTEdge
{ int vex1, vex2 ; /* 边所依附的图中两个顶点 */
WeightType weight ; /* 边的权值 */
}MSTEdge ;
#define INFINITY MAX_VAL /* 最大值 */
MSTEdge* Prim_MST(AdjGraph *G , int u){
/*从第u个顶点开始构造图G的最小生成树 */
MSTEdge *TE ; // 存放最小生成树n-1条边的数组指针
int j , k , v , min ;
for (j=0; j<G->vexnum; j++)
{ closedge[j].adjvex=u ;
closedge[j].lowcost=G->adj[j][u] ;
} /* 初始化数组closedge[n] */
closedge[u].lowcost=0 ; /* 初始时置U={u} */
TE=(MSTEdge *)malloc((G->vexnum-1)*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 ; /* 将顶点k并入U中 */
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 ;
} /* 修改数组closedge[n]的各个元素的值 */
}
return(TE) ;
} /* 求最小生成树的Prime算法 */
算法时间复杂度：设带权连通图有n个顶点，则算法的主要执行是二重循环：
n-1次加点；
每次加点以后修正权值，频度为n 。
因此，整个算法的时间复杂度是O(n2)，与边的数目无关。
4.4 克鲁斯卡尔(Kruskal)算法
- 算法思想（加边不构成回路）
设G=(V, E)是具有n个顶点的连通网，T=(U, TE)是其最小生成树。初值：U=V，TE={} 。
对G中的边按权值大小从小到大依次选取。
⑴ 选取权值最小的边(vi，vj)，若边(vi，vj)加入到TE后形成回路，则舍弃该边；否则，将该边并入到TE中，即TE=TE∪{(vi，vj)} 。
⑵ 重复⑴ ，直到TE中包含有n-1条边为止。
- 算法实现说明
Kruskal算法实现的关键是：当一条边加入到TE的集合后，如何判断是否构成回路?
简单的解决方法是：定义一个一维数组Vset[n] ，存放图T中每个顶点所在的连通分量的编号。
初值：Vset[i]=i，表示每个顶点各自组成一个连通分量，连通分量的编号简单地使用顶点在图中的位置(编号)。
当往T中增加一条边(vi，vj) 时，先检查Vset[i]和Vset[j]值：
若Vset[i]=Vset[j]：表明vi和vj处在同一个连通分量中，加入此边会形成回路；
若Vset[i]≠Vset[j]，则加入此边不会形成回路，将此边加入到生成树的边集中。
加入一条新边后，将两个不同的连通分量合并：将一个连通分量的编号换成另一个连通分量的编号。
MSTEdge * Kruskal_MST(ELGraph *G){
/* 用Kruskal算法构造图G的最小生成树 */
MSTEdge *TE ;
int j, k, v, s1, s2, *Vset;
WeightType w ;
Vset=(int *)malloc(G->vexnum*sizeof(int)) ;
for (j=0; j<G->vexnum; j++)
Vset[j]=j ; /* 初始化数组Vset[n] */
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] ;
/* 若边的两个顶点的连通分量编号不同, 边加入到TE中 */
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) ;
} /* 求最小生成树的Kruskal算法 */
5 有向无环图及其应用
- 有向无环图(Directed Acycling Graph)：是图中没有回路(环)的有向图。
- AOV-网：图中顶点表示活动，有向边表示活动之间的优先关系，这样的有向图称为顶点表示活动的网(Activity On Vertex Network ) 。
5.1 拓扑排序
- 定义
拓扑排序(Topological Sort) ：有向图G=（V，E）中顶点的线性序列。
必须满足：图中任意两个顶点vi,vj，有一条vi到vj的路径，则在拓扑排序中vi必须排在vj之前。 - 特性
先行关系具有可传递性
拓扑序列不唯一 - 拓扑排序算法思想
在AOV网中选择一个没有前驱的顶点且输出；
在AOV网中删除该顶点以及从该顶点出发的(以该顶点为尾的弧)所有有向弧(边) ；
重复①、②，直到图中全部顶点都已输出(图中无环)或图中不存在无前驱的顶点(图中必有环)。
- 算法实现说明
查找G中无前驱的顶点：查找入度为零的点
删除顶点以i为起点的弧：对链在顶点i后面的所有邻接顶点k入度减1。
为避免重复检测入度为0的顶点，设置一个入度为0的栈：若某一顶点的入度减为0，则将其入栈。每当输出某一顶点时，将其出栈。
(1) 统计各顶点入度的函数
void count_indegree(ALGraph *G)
{ int k ; LinkNode *p ;
for (k=0; k<G->vexnum; k++)
G->adjlist[k].indegree=0 ; /* 顶点入度初始化 */
for (k=0; k<G->vexnum; k++)
{ p=G->adjlist[k].firstarc ;
while (p!=NULL) /* 顶点入度统计 */
{ G->adjlist[p->adjvex].indegree++ ;
p=p->nextarc ;
}
}
}
(2) 拓扑排序算法
int Topologic_Sort(ALGraph *G, int topol[]){
/* 顶点的拓扑序列保存在一维数组topol中 */
int k, no, vex_no, top=0, count=0, boolean=1 ;
int stack[MAX_VEX] ; /* 用作堆栈 */
LinkNode *p ;
count_indegree(G) ; /* 统计各顶点的入度 */
for (k=0; k<G->vexnum; k++)
if (G->adjlist[k].indegree==0)
stack[++top]=G->adjlist[k].data ;
do
{ if (top==0) boolean=0 ;/* 栈空 */
else{ no=stack[top--] ; /* 栈顶元素出栈 */
topol[++count]=no ; /* 记录顶点序列 */
p=G->adjlist[no].firstarc ;
while (p!=NULL) /*删除以顶点P为尾的弧*/
{ vex_no=p->adjvex ;
G->adjlist[vex_no].indegree-- ;
if (G->adjlist[vex_no].indegree==0)
stack[++top]=vex_no ;
p=p->nextarc ;
} } }while(boolean==0) ;
if (count<G->vexnum) return(-1) ;
else return(1) ;
}
5.2 关键路径(Critical Path)
与AOV网相对应的是AOE(Activity On Edge) ，是边表示活动的有向无环图。
图中顶点表示事件(Event)，每个事件表示在其前的所有活动已经完成，其后的活动可以开始；
弧表示活动，弧上的权值表示相应活动所需的时间或费用。
-
与AOE有关的研究问题
关键路径（也称为工程完成最短时间）：从源点到汇点的最长路径长度(路径上各活动持续时间之和) 。
关键活动：关键路径上的活动。关键活动是影响整个工程的关键。
设v0是起点，从v0到vi的最长路径长度称为事件vi的最早发生时间，即是以vi为尾的所有活动的最早发生时间。
若活动ai是弧<j, k>，持续时间是dut<j, k>，设：
e(i)：表示活动ai的最早开始时间；
l(i)：在不影响进度的前提下，表示活动ai的最晚开始时间； 则l(i)-e(i)表示活动ai的时间余量，若l(i)-e(i)=0，表示活动ai是关键活动。
ve(i)：表示事件vi的最早发生时间，即从起点到顶点vi的最长路径长度；
vl(i)：表示事件vi的最晚发生时间。则有以下关系：
-
求AOE中关键路径和关键活动
⑴ 算法思想
① 利用拓扑排序求出AOE网的一个拓扑序列；
② 从拓扑排序的序列的第一个顶点(源点)开始，按拓扑顺序依次计算每个事件的最早发生时间ve(i) ；
③ 从拓扑排序的序列的最后一个顶点(汇点)开始，按逆拓扑顺序依次计算每个事件的最晚发生时间vl(i) ；
- 关键路径活动是：
a2，a5，a6，a9，a10， a12 - 根据关键路径的定义，知该AOE网的关键路径是：
(v0, v2, v4, v7 , v8) 和(v0, v2, v5 , v7 , v8)
⑵ 算法实现
void critical_path(ALGraph *G)
{ int j, k, m ; LinkNode *p ;
if (Topologic_Sort(G)==-1)
printf(“\nAOE网中存在回路，错误!!\n\n”) ;
else
{ for ( j=0; j<G->vexnum; j++)
ve[j]=0 ; /* 事件最早发生时间初始化 */
for (m=0 ; m<G->vexnum; m++)
{ j=topol[m] ;
p=G->adjlist[j].firstarc ;
for (; p!=NULL; p=p->nextarc )
{ k=p->adjvex ;
if (ve[j]+p->weight>ve[k]) ve[k]=ve[j]+p->weight ;
}
} /* 计算每个事件的最早发生时间ve值 */
for ( j=0; j<G->vexnum; j++)
vl[j]=ve[j] ; /* 事件最晚发生时间初始化 */
for (m=G->vexnum-1; m>=0; m--)
{ j=topol[m] ; p=G->adjlist[j].firstarc ;
for (; p!=NULL; p=p->nextarc )
{ k=p->adjvex ;
if (vl[k]-p->weight<vl[j]) vl[j]=vl[k]-p->weight ;}
} /* 计算每个事件的最晚发生时间vl值 */
for (m=0 ; m<G->vexnum; m++)
{ p=G->adjlist[m].firstarc ;
for (; p!=NULL; p=p->nextarc )
{ k=p->adjvex ;
if ( (ve[m]+p->weight)==vl[k])
printf(“<%d, %d>, m, j”) ;
}
} /* 输出所有的关键活动 */
} /* end of else */
}
6.最短路径
对于给定的有向图G=(V，E)及单个源点Vs，求Vs到G的其余各顶点的最短路径。
6.1 单源点最短路径
针对单源点的最短路径问题，Dijkstra提出了一种按路径长度递增次序产生最短路径的算法，即迪杰斯特拉(Dijkstra)算法。
- 算法思想说明
设给定源点为Vs，S为已求得最短路径的终点集，开始时令S={Vs} 。当求得第一条最短路径(Vs ,Vi)后，S为{Vs,Vi} 。根据以下结论可求下一条最短路径。
设下一条最短路径终点为Vj ，则Vj只有：
源点到终点有直接的弧<Vs，Vj>；
从Vs 出发到Vj 的这条最短路径所经过的所有中间顶点必定在S中。即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点Vj 。
若定义一个数组dist[n]，其每个dist[i]分量保存从Vs 出发中间只经过集合S中的顶点而到达Vi的所有路径中长度最小的路径长度值，则下一条最短路径的终点Vj必定是不在S中且值最小的顶点，即：
dist[i]=Min{ dist[k] | Vk∈V-S }
利用上述公式就可以依次找出下一条最短路径 - 算法步骤
① 用带权的邻接矩阵表示有向图，令S={Vs} ，将Vs到图中其余顶点Vi的路径长度，按以下原则置初值：
3.算法实现
用带权的邻接矩阵表示有向图：
设数组pre[n]保存从Vs到其它顶点的最短路径。若pre[i]=k，表示从Vs 到Vi的最短路径中，Vi的前一个顶点是Vk，即最短路径序列是(Vs , …, Vk , Vi) 。
设数组final[n]，标识一个顶点是否已加入S中。
6.2 每一对顶点间的最短路径
1、弗罗伊德(Floyd)算法思想
设顶点集S(初值为空)，用二维数组A[n][n]的每个元素A[i][j]保存从Vi只经过S中的顶点到达Vj的最短路径长度，其思想是：
① 初始时令S={ } ， A[n][n]的赋初值方式是：
② 将图中一个顶点Vk 加入到S中，修改A[i][j]的值，修改方法是：
A[i][j]=Min{A[i][j] , (A[i][k]+A[k][j]) }
原因： 从Vj只经过S中的顶点(Vk)到达Vj的路
径长度可能比原来不经过Vk的路径更短。
③ 重复②，直到G的所有顶点都加入到S中为止
2 算法实现
二维数组Path[n]n ，元素Path[i][j]保存从Vi到Vj的最短路径所经过的顶点
若Path[i][j]=k：从Vi到Vj 经过Vk ，最短路径序列是(Vi , …, Vk , …, Vj) ，则路径子序列：(Vi , …, Vk)和(Vk , …, Vj)一定是从Vi到Vk和从Vk到Vj 的最短路径。
从而可以根据Path[i][k]和Path[k][j]的值再找到该路径上所经过的其它顶点，…依此类推。
初始化为Path[i][j]=-1，表示从Vi 到Vj 不经过任何(S中的中间)顶点。
当某个顶点Vk加入到S中后使A[i][j]变小时，令Path[i][j]=k。## PPT课后题
自己康的一点题
- 在一个图中，所有顶点的度数之和等于所有边数的2倍。
- 在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的1倍。
- 一个有N个顶点的有向图最多有N(N-1)条边。
- 具有n个顶点的无向图至少有n-1条边才能确保是一个连通图。
- 一个有e条边的无向图，若使用邻接矩阵表示，则矩阵大小为n²，矩阵中非0元素个数为2e。
PPT课后题
⑴ 分析并回答下列问题：
① 图中顶点的度之和与边数之和的关系?
② 有向图中顶点的入度之和与出度之和的关系?
③ 具有n个顶点的无向图，至少应有多少条边才能确保是一个连通图? 若采用邻接矩阵表示，则该矩阵的大小是多少?
④ 具有n个顶点的有向图，至少应有多少条弧才能确保是强连通图的? 为什么?
⑵ 设一有向图G=(V,E)，其中V={a,b,c,d,e} ， E={<a,b>, <a,d>, <b,a>, <c,b>, <c,d>, <d,e>,<e,a>, <e,b>, <e,c>}
① 请画出该有向图，并求各顶点的入度和出度。
② 分别画出有向图的正邻接链表和逆邻接链表。
⑶ 对图7-27所示的带权无向图。
① 写出相应的邻接矩阵表示。
② 写出相应的边表表示。
③ 求出各顶点的度。
⑷ 已知有向图的逆邻接链表如图7-28所示。
① 画出该有向图。
② 写出相应的邻接矩阵表示。
③ 写出从顶点a开始的深度优先和广度优先遍历序列。
④ 画出从顶点a开始的深度优先和广度优先生成树。
⑸ 一个带权连通图的最小生成树是否唯一?在什么情况下可能不唯一?
⑹ 对于图7-27所示的带权无向图。
① 按照Prime算法给出从顶点2开始构造最小生成树的过程。
② 按照Kruskal算法给出最小生成树的过程。
⑺ 已知带权有向图如图7-29所示，请利用Dijkstra算法从顶点V4出发到其余顶点的最短路径及长度，给出相应的求解步骤。
⑻ 已知带权有向图如图7-30所示，请利用Floyd算法求出每对顶点之间的最短路径及路径长度。
⑼ 一个AOV网用邻接矩阵表示，如图7-31。用拓扑排序求该AOV网的一个拓扑序列，给出相应的步骤。
⑽ 拓扑排序的结果不是唯一的，请给出如图7-32所示的有向图的所有可能的拓扑序列。
⑾ 请在深度优先搜索算法的基础上设计一个对有向无环图进行拓扑排序的算法。
⑿ 设计一个算法利用图的遍历方法输出一个无向图G中从顶点Vi到Vj的长度为S的简单路径，设图采用邻接链表作为存储结构。
⒀ 假设一个工程的进度计划用AOE网表示，如图7-33所示。
① 求出每个事件的最早发生时间和最晚发生时间。
② 该工程完工至少需要多少时间?
③ 求出所有关键路径和关键活动。
Part 2、代码
//邻接表法
#include <stdio.h>
#include <stdlib.h>
#define max 100
typedef int Elemtype;
//边，弧
typedef struct ArcNode{
int adjvex; //边、弧指向哪个结点
struct ArcNode *next; //指向下一条弧的指针
// int info; //边的权值
}ArcNode;
//顶点
typedef struct VNode{
Elemtype data; //顶点信息
ArcNode *first; //第一条边/弧
}VNode;
//用邻接表存储的图
typedef struct{
VNode vertices[max];
int arcnum,vexnum; //边的个数和顶点的个数
int graphType;
}ALGraph;
int main()
{
ALGraph graph;
printf("请输入图边的个数和顶点的个数:\n");
scanf("%d %d",&graph.arcnum,&graph.vexnum);
int i = 0;
printf("请输入图的种类:\n");
scanf("%d",&graph.graphType);
//type = 0->无向；type = 1->有向
for(i = 0;i < graph.vexnum;i++)
{
//顶点信息
printf("请输入顶点[%d]的data：\n",i);
scanf("%d",&graph.vertices[i].data);
graph.vertices[i].first = NULL;
}
//建立边表
int j,nextbool;
ArcNode *s,*r;
for(i = 0;i < graph.vexnum;i++){
printf("请输入结点[%d]第一条边指向的结点下标:\n",i);
scanf("%d",&j);
s = (ArcNode*)malloc(sizeof(ArcNode));
// 边指向的结点下标
s->adjvex = j;
s->next = NULL;
graph.vertices[i].first = s;
while(1){
printf("有下一条边输入1，否则输入0；\n");
scanf("%d",&nextbool);
if(nextbool == 0) break;
r = (ArcNode*)malloc(sizeof(ArcNode));
printf("请输入这条边指向的结点下标:\n");
scanf("%d",&j);
r->adjvex = j;
r->next = NULL;
s->next = r;
s = r;
}
}
printf("创建成功！\n");
//打印
for(i = 0;i < graph.vexnum;i++)
{
s = graph.vertices[i].first;
printf("结点%d指向的结点下标",graph.vertices[i].data);
printf(" ");
while(s != NULL)
{
printf("%d ",s->adjvex);
s = s->next;
}
printf("\n");
}
return 0;
}
//邻接矩阵法
#include <stdio.h>
#define max 100
#define Elemtype char
typedef struct{
Elemtype vex[max]; //数据域
int edge[max][max]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和弧数
int mbool; //图的类型
}MGraph;
int main()
{
MGraph mgraph;
printf("输入顶点个数：\n");
scanf("%d",&mgraph.vexnum);
getchar();
printf("请输入edge矩阵：\n");
int i,j;
for(i = 0;i < mgraph.vexnum;i++)
for(j = 0;j < mgraph.vexnum;j++)
{
scanf("%d",&mgraph.edge[i][j]);
getchar();
}
//检验矩阵是否无误
// printf("矩阵为：\n");
// for(i = 0;i < mgraph.vexnum;i++)
// {
// for(j = 0;j < mgraph.vexnum;j++)
// {
// printf("%d ",mgraph.edge[i][j]);
// }
// printf("\n");
// }
printf("请输入元素值：\n");
for(i = 0;i < mgraph.vexnum;i++)
scanf("%c",&mgraph.vex[i]);
//检验元素值是否无误
// for(i = 0;i < mgraph.vexnum;i++)
// printf("%c",mgraph.vex[i]);
// printf("\n");
printf("请输入此图为有向图还是无向图：\n有向图输入0.无向图输入1：\n");
scanf("%d",&mgraph.mbool);
int count = 0,number[max] = {0};
if(mgraph.mbool == 1)
{
for(i = 0;i < mgraph.vexnum;i++)
{
count = 0;
for(j = 0;j < mgraph.vexnum;j++)
{
if(mgraph.edge[i][j] != 0)
count++;
else continue;
}
if(count != 0)
{
printf("第%d个顶点%c与%d个顶点连通;\n",i+1,mgraph.vex[i],count);
printf("度为%d\n",count);
printf("分别为:\n");
for(j = 0;j < mgraph.vexnum;j++)
{
if(mgraph.edge[i][j] !=0)
printf("第%d个顶点%c\n",j+1,mgraph.vex[j]);
}
printf("\n\n");
}
else
printf("第%d个顶点%c没有与任何顶点连通;\n\n",i+1,mgraph.vex[i]);
}
}
else if(mgraph.mbool == 0)
{
for(i = 0;i < mgraph.vexnum;i++)
{
count = 0;
for(j = 0;j < mgraph.vexnum;j++)
{
if(mgraph.edge[i][j] != 0)
count++;
else continue;
}
number[i] += count;
if(count != 0)
{
printf("第%d个顶点%c有%d个指向其它顶点边;\n",i+1,mgraph.vex[i],count);
printf("出度为%d\n",count);
printf("分别为:\n");
for(j = 0;j < mgraph.vexnum;j++)
{
if(mgraph.edge[i][j] !=0)
printf("第%d个顶点%c\n",j+1,mgraph.vex[j]);
}
printf("\n\n");
}
else
printf("第%d个顶点%c出度为0;\n\n",i+1,mgraph.vex[i]);
}
for(i = 0;i < mgraph.vexnum;i++)
{
count = 0;
for(j = 0;j < mgraph.vexnum;j++)
{
if(mgraph.edge[j][i] != 0)
count++;
else continue;
}
number[i] += count;
if(count != 0)
{
printf("第%d个顶点%c有%d个被其它顶点指向的边;\n",i+1,mgraph.vex[i],count);
printf("入度为%d\n",count);
printf("分别为:\n");
for(j = 0;j < mgraph.vexnum;j++)
{
if(mgraph.edge[j][i] !=0)
printf("第%d个顶点%c\n",j+1,mgraph.vex[j]);
}
printf("\n\n");
}
else
printf("第%d个顶点%c入度为0;\n\n",i+1,mgraph.vex[i]);
}
}
if(mgraph.mbool == 0)
for(i = 0;i < mgraph.vexnum;i++)
printf("第%d个元素%c的度为%d\n",i+1,mgraph.vex[i],number[i]);
return 0;
}
//十字链表 十字链表只能存储有向图
#include "stdio.h"
#include "stdlib.h"
#define max 100
//弧结点
typedef struct ArcBox {
int headvex, tailvex; //起点和终点在顺序表中的索引
struct ArcBox *hlink, *tlink; //起点或终点相同的弧
// int info; //权
}ArcBox;
//顶点结点
typedef struct VexNode {
ArcBox *firstin, *firstout; //出边和入边链表
int data; //数据
}VexNode;
//图
typedef struct {
VexNode xlist[max];
int vexnum, arcnum; //顶点个数和边的个数
}OLGraph;
//定义邻接矩阵
typedef struct {
int existbool;
ArcBox *node;
}Arr;
int main()
{
OLGraph graph;
printf("请输入图的顶点个数与边的个数：\n");
scanf("%d %d",&graph.vexnum,&graph.arcnum);
int i,j,k,flag;
printf("请输入顶点数据：\n");
//初始化顶点
for (i = 0;i < graph.vexnum;i++)
{
scanf("%d", &graph.xlist[i].data);
graph.xlist[i].firstin = NULL;
graph.xlist[i].firstout = NULL;
}
Arr a[max][max];
//利用邻接矩阵初始化十字链表
printf("请输入十字链表的邻接矩阵：\n");
//分配内存
//初始化矩阵
for (i = 0;i < graph.vexnum;i++)
{
for (j = 0;j < graph.vexnum;j++)
{
scanf("%d", &a[i][j].existbool);
if (a[i][j].existbool == 0)
continue;
a[i][j].node = (ArcBox*)malloc(sizeof(ArcBox));
a[i][j].node->headvex = j;
a[i][j].node->tailvex = i;
a[i][j].node->hlink = NULL;
a[i][j].node->tlink = NULL;
}
}
for (i = 0;i < graph.vexnum;i++)
{
flag = 0;
for (j = 0;j < graph.vexnum;j++)
{
if (a[i][j].existbool == 0)
continue;
for (k = j + 1;k < graph.vexnum;k++)
{
if (a[i][k].existbool == 1)
break;
}
if (k >= graph.vexnum)
a[i][j].node->tlink = NULL;
else
a[i][j].node->tlink = a[i][k].node;
if (flag == 0)
graph.xlist[i].firstout = a[i][j].node;
flag = 1;
}
}
for (i = 0;i < graph.vexnum;i++)
{
flag = 0;
for (j = 0;j < graph.vexnum;j++)
{
if (a[j][i].existbool == 0)
continue;
for (k = j + 1;k < graph.vexnum;k++)
{
if (a[k][i].existbool == 1)
break;
}
if (k >= graph.vexnum)
a[j][i].node->hlink = NULL;
else
a[j][i].node->hlink = a[k][i].node;
if (flag == 0)
graph.xlist[i].firstin = a[j][i].node;
flag = 1;
}
}
printf("十字链表初始化完成！\n");
printf("图中有%d个结点,%d条边\n",graph.vexnum,graph.arcnum);
int count;
ArcBox* s;
for (i = 0;i < graph.vexnum;i++)
{
printf("关于第[%d]个结点[%d]，指出的边信息如下：\n",i+1,graph.xlist[i].data);
count = 0;
s = graph.xlist[i].firstout;
while (s != NULL)
{
count++;
printf("第%d条：指向第[%d]个结点[%d]\n", count, s->headvex + 1, graph.xlist[s->headvex].data);
s = s->tlink;
}
count = 0;
printf("指入的边信息如下：\n");
s = graph.xlist[i].firstin;
while(s != NULL)
{
count++;
printf("第%d条：被第[%d]个结点[%d]指入\n",count,s->tailvex+1,graph.xlist[s->tailvex].data);
s = s->hlink;
}
}
return 0;
}
Part 3、总结
三万两千多字。。。真吓人啊。。。。。
这一章建议看看b站王道考研的网课
光看文字特别容易晕（我自己总结的时候就晕了…）
几个算法了解一下就行，要求不高，好像不要求代码实现。
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
3
0- 0
已为社区贡献2条内容
所有评论(0)