图的相关算法
Were equations, pictures or diagrams not properly rendered, please refresh the page. If the problem persists, you can contact me.
一、图的基本概念
1.图的定义（图不可以是空图，也就是说图的顶点集一定非空，但是边集可以为空）
- 有向图
- 弧是顶点的有序对，记为<v，w>
- v是弧尾，w是弧头
- 无向图
- 边是顶点的无序对，记为(v，w)
- (v，w) = (w，v)
- 简单图
- 不存在重复边
- 不存在顶点到自身的边
- 多重图
- 存在重复边
- 存在顶点到自身的边
- 完全图
- 无向图中，任意两个顶点之间都存在边
- 含n个顶点的无向完全图有n(n-1)/2条边
- 有向图中，任意两个顶点之间都存在方向相反的弧
- 含n个顶点的有向完全图有n(n-1)条边
- 子图
- 不是所有V和E的任何子集都可以构成G的子图（E的子集中的某些变关联的顶点不在这个V的子集中）
- 当V(G’) = V(G)时，子图G’称为G的生成子图
- 连通、连通图、连通分量（无向图中）
- 图G中任意两个顶点都是连通的，那么称G为连通图
- 无向图中的极大联通子图称为连通分量
- 如果一个图有n个顶点，但是边数小于n-1，此图必定是非连通图
- 强连通图、强连通分量（有向图中）
- 强连通：从顶点v到顶点w和从顶点w到顶点v之间都有路径
- 图G中任意两个顶点都是强连通的，那么称G为强连通图
- 有向图中的极大强联通子图称为强连通分量
- 生成树、生成森林
- 连通图的生成树：包含图中全部顶点的一个极小连通子图
- 非连通图的生成树：连通分量的生成树构成了非连通图的生成森林
- 顶点的度、入度、出度（题目考的很多）
- 无向图的全部顶点的度的和等于边数的两倍
- 顶点的入度与出度之和相等，而且等于边数
- 边的权和网
-
稠密图、稀疏图（记住公式： E < V ×log V 是稀疏图） - 路径、路径长度、回路
- 第一个顶点和最后一个顶点相同的路径称为环或者回路
- 如果一个图有n个顶点，并且有大于n-1条边，此图一定有环
- 简单路径、简单回路
- 距离
- 有向树：一个顶点的入度是0，其余顶点的入度都是1的有向图就是有向树
2.易错点
- 图的遍历要求每个结点只能被访问一次，而且如果图非连通，则从某一顶点出发无法访问到其他全部顶点
- 一个无向图G，如果题目要求它在任何情况下都是连通的，现在假设它有n个结点，我们可以这样理解，现在使用其中n-1个结点构成一个完全无向图，这样就使再加上一个结点，一个边后，必定是一个连通图，那么最少边数 = n(n-1)/2 + 1，计算完成，打完收工
- 一个非连通的无向图G，在直到它的边数求最小结点数时，可以这样理解，这个非连通图的边全部组成一个连通图，但是在这个连通图的基础上再加一个不连接的结点，自然就满足了非连通图的要求，也就可以求得此时的最少结点数
- 生成树、环、极大连通子图、极小连通子图需要分的很清楚
- 对于极大连通子图，我们可以把它分成3各部分来看
- 必须是子图
- 连通
- 极大
- 问题主要在于这个极大的理解。这个极大是指的边数极大，这个极大是在原图的边中的极大（也就是说，子图里面已经包括了原图中所有和子图中顶点有关的边）。之所以用极大而不用最大，是因为不一定只有一个连通分量。我想最大的困惑在于极大的判断。我们假设已经有了一个连通子图G，其顶点集为V，边集为E。如果E包含了在原图中和所有和V有关的边，那我们就认为它是极大连通子图。通常情况下，如果我们删除E中的某些边，该子图仍然是连通，当我们删除了所有能删除的边（再删除就会导致不连通），并且它仍然是连通的，我们就认为它是极小连通子图。对于极大和极小，个人理解为：在一个连通子图中，包含和顶点有关所有的边（the more the better），那就是极大连通子图；如果包含了必不可少的边（the less the better），那就是极小连通子图。
- 关于树的定义请在弄清楚后回来再看看，你是傻逼吗？
- 如何对无环有向图中的顶点号重新安排可使得该图的邻接矩阵中所有的1都集中到对角线上？
- 这个问题其实我一开始真的很迷
- 然后答案说需要把顶点号按照出度进行重新排序
- 于是我发现确实如此，但是为什么真的不明白
- 据说拓扑排序再依次编号更简单
二、图的存储和基本操作
1.邻接矩阵法
#include <stdio.h>
#include <stdlib.h>
#define MaxVertices 100 //定义最大容量
typedef struct AdjMatrix{
int Vertices[MaxVertices]; //用来保存顶点信息
int Edge[MaxVertices][MaxVertices]; //用来保存边的信息
int numV,numE; //图当前的顶点数与边数
}AdjMatrix;
void CreateGraph(AdjMatrix *G){
int n,e,vi,vj,w,i,j;
printf("请输入图的顶点数和边数（用空格分隔）：" );
scanf("%d%d",&n,&e);
G->numV = n;
G->numE = e;
for(i=0;i<n;i++) //开始初始化
{
for(j=0;j<n;j++){
if(i=j){
G->Edge[i][j] = 0;
}
else{
G->Edge[i][j] = 32767; //暂时这条边长度为无穷大
}
}
for(i=0;i<G->numV;i++) //将顶点存入数组中
{
printf("请输入第%d个顶点的信息(整型):",i+1);
scanf("%d",&G->Vertices[i]);
}
}
printf("\n");
for(i=0;i<G->numE;i++){
printf("请输入边的信息i,j,w(以空格分隔):");
scanf("%d%d%d",&vi,&vj,&w);
//若为不带权值的图，则w输入1
//若为带权值的图，则w输入对应权值
G->Edge[vi-1][vj-1]=w;//①
G->Edge[vj-1][vi-1]=w;//②
//无向图具有对称性的规律，通过①②实现
//有向图不具备此性质，所以只需要①
}
}
void DispGraph(AdjMatrix G){ //输出邻接矩阵的信息
int i,j;
printf("\n输出顶点的信息（整型）:\n");
for(i=0;i<G.numV;i++){
printf("%8d",G.Vertices[i]);
}
printf("\n输出邻接矩阵:\n");
printf("\t");
for(i=0;i<G.numV;i++){
printf("%8d",G.Vertices[i]);
}
for(i=0;i<G.numV;i++)
{
printf("\n%8d",i+1);
for(j=0;j<G.numV;j++){
if(G.Edge[i][j]==32767)
//两点之间无连接时权值为默认的32767，
//在无向图中一般用"0"表示，在有向图中一般用"∞",
//
这里为了方便统一输出 "∞"
printf("%8s", "∞");
else
printf("%8d",G.Edge[i][j]);
}
printf("\n");
}
}
int main()
{
AdjMatrix G;
CreateGraph(&G);
DispGraph(G);
}
- 在简单应用中可以直接使用二维数组作为图的邻接矩阵
- 无向图的邻接矩阵是对称矩阵，规模特别大的邻接矩阵可以采用压缩矩阵
- 邻接矩阵的空间复杂度为O(n^2)
- 邻接矩阵存储的局限性在于确定图中边数很麻烦
- 图G的邻接矩阵为A，A^n的元素A^n [i] [j] 等于顶点i到顶点j的长度为n的路径的数目
2.邻接表法
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 25
#define TRUE 1
#define FALSE 0
int visited[MaxSize];
typedef struct{
char data[MaxSize];
int front,rear;
}SqQueue;
typedef struct ArcNode{ //边结点
int adjvex; //该边所指向的顶点的位置
struct ArcNode *nextarc; //指向下一条边的指针
int info; //和边有关的信息
}ArcNode;
typedef struct VexNode{ //表头结点
int data;
ArcNode *firstarc; //指向第一条依附于该节点的边的指针
}VexNode,AdjList[MaxSize]; //AbjList表示一个表头结点表
typedef struct ALGraph{
AdjList vertices;
int vexNum,arcNum;
}ALGraph;
//循环队列
void InitQueue(SqQueue *Q){
Q->front = 0;
Q->rear = 0; //初始化队首，队尾指针
}
int isEmpty(SqQueue Q){
if(Q.rear == Q.front){
return TRUE;
}
else{
return FALSE;
}
}
int EnQueue(SqQueue *Q,char x){
if((Q->rear+1)%MaxSize == Q->front){
return FALSE;
}
else{
Q->data[Q->rear] = x;
Q->rear = (Q->rear+1)%MaxSize;
return TRUE;
}
}
int DeQueue(SqQueue *Q){
if(Q->rear == Q->front){
return FALSE; //队列是空的，不行
}
else{
Q->front = (Q->front+1)%MaxSize;
return TRUE;
}
}
int LocateVex(ALGraph G,char v){ //定位顶点的位置
int i;
for(i=0;i<G.vexNum;i++){
if(G.vertices[i].data == v){
return i;
}
}
}
void CreateUDG(ALGraph *G){
int i,j,k;
char vi,vj;
printf("scanf vexNum and arcNum\n");
scanf("%d", &G->vexNum); //输入顶点数与边数
scanf("%d", &G->arcNum);
getchar();
for(i=0;i<G->vexNum;i++){
printf("scanf vexs\n");
scanf("%c",&G->vertices[i].data); //输入顶点信息
getchar();
G->vertices[i].firstarc = NULL; //刚开始每个表头结点的第一条边指针都设置为NULL
}
for(k=0;k<G->arcNum;k++){ //输入各个边，构造邻接表
printf("scanf vi and vj\n");
scanf(" %c", &vi);
getchar();
scanf(" %c", &vj);
i = LocateVex(*G, vi);
printf("%d", i);
j = LocateVex(*G, vj);
printf("%d", j);
ArcNode *p1; //创建一个边结点p1
p1->adjvex = j;
p1->nextarc = G->vertices[i].firstarc;
G->vertices[i].firstarc = p1; //插入新的边结点
ArcNode *p2; //对称的边结点，这就是所有边出现两次的原因
p2->adjvex = i;
p2->nextarc = G->vertices[j].firstarc;
G->vertices[j].firstarc = p2;
}
}
int main(int argc, char const *argv[]) {
ALGraph G;
CreateUDG(&G);
BFS(G,'a');
return 0;
}
- 使用邻接矩阵可以减少稀疏图的空间浪费
- 有向图和无向图消耗的空间不一样，主要是边的差别，无向图边在邻接表中都出现两次
- 顶点的出度可以很快直到，但入度需要遍历整个邻接表
- 图的邻接表表示不唯一
3.十字链表：有向图的一种链式存储结构
#include <stdio.h>
#define MaxVertexNum 100
typedef struct ArcNode //弧结点
{
int tailvex, headvex; //该弧的头尾结点
struct ArcNode *hlink, *tlink; //分别指向弧头相同和弧尾相同的结点
}ArcNode;
typedef struct VNode //顶点结点
{
int data;
ArcNode *firstin,*firstout; //指向第一条入弧和出弧
}VNode;
typedef struct GLGraph{
VNode xlist[MaxVertexNum]; //邻接表
int vexnum, arcnum; //图的顶点数和弧数
}GLGraph;
4.邻接多重表：无向图的一种链式存储结构
#include <stdio.h>
#define MaxVertexNum 100
typedef struct ArcNode //弧结点
{
int mark; //访问标记
int ivex, jvex; //该弧的头尾结点
struct ArcNode *ilink, *jlink; //分别指向两个顶点的下一条边
}ArcNode;
typedef struct VNode //顶点结点
{
int data;
ArcNode ,*firstedge; //指向第一条依附该顶点的边
}VNode;
typedef struct AMLGraph{
VNode adjmulist[MaxVertexNum]; //邻接表
int vexnum, arcnum; //图的顶点数和弧数
}AMLGraph;
三、图的遍历
1.广度优先遍历
- 基本思想：类似于二叉树的层序遍历，首先访问起始顶点v，接着从v出发，访问v的各个未访问过的邻接顶点，以此类推，直到图中所有顶点都被访问过为止；
- 广度优先搜索是一种分层的查找过程，而且没有回退操作，因此它不是一个递归算法，因此它必须借助辅助队列，用来记忆正在访问顶点的下一层顶点；
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 25
#define TRUE 1
#define FALSE 0
int visited[MaxSize];
typedef struct{
char data[MaxSize];
int front,rear;
}SqQueue;
typedef struct AMGraph{
char vexs[MaxSize];
int arcs[MaxSize][MaxSize];
int vexNum,arcNum;
}AMGraph;
//循环队列
void InitQueue(SqQueue *Q){
Q->front = 0;
Q->rear = 0; //初始化队首，队尾指针
}
int isEmpty(SqQueue Q){
if(Q.rear == Q.front){
return TRUE;
}
else{
return FALSE;
}
}
int EnQueue(SqQueue *Q,char x){
if((Q->rear+1)%MaxSize == Q->front){
return FALSE;
}
else{
Q->data[Q->rear] = x;
Q->rear = (Q->rear+1)%MaxSize;
return TRUE;
}
}
int DeQueue(SqQueue *Q){
if(Q->rear == Q->front){
return FALSE; //队列是空的，不行
}
else{
Q->front = (Q->front+1)%MaxSize;
return TRUE;
}
}
int LocateVex(AMGraph G,char v){ //定位顶点的位置
int i;
for(i=0;i<G.vexNum;i++){
if(G.vexs[i] == v){
return i;
}
}
}
void CreateUDG(AMGraph *G){
int i,j,k;
char vi,vj;
printf("scanf vexNum and arcNum\n");
scanf("%d", &G->vexNum); //输入顶点数与边数
scanf("%d", &G->arcNum);
getchar();
for(i=0;i<G->vexNum;i++){
printf("scanf vexs\n");
scanf("%c",&G->vexs[i]); //输入顶点信息
getchar();
}
for(i=0;i<G->vexNum;i++){
for(j=0;j<G->vexNum;j++){
G->arcs[i][j] = 0;
}
}
for(k=0;k<G->arcNum;k++){
printf("scanf vi and vj\n");
scanf(" %c", &vi);
getchar();
scanf(" %c", &vj);
i = LocateVex(*G, vi);
printf("%d", i);
j = LocateVex(*G, vj);
printf("%d", j);
G->arcs[i][j] = G->arcs[j][i] = 1;
}
}
void BFS(AMGraph G, char v0) { //v0相当于初始节点
SqQueue Q;
InitQueue(&Q); //初始化一个辅助队列
int i,v;
char u,w;
v = LocateVex(G,v0); //获得初始结点的位置
printf("%c",v0);
visited[v] = 1; //标志现在的结点已经被访问
EnQueue(&Q,v0); //入队列
while (isEmpty(Q) == 0) {
u = Q.data[Q.front]; //队列头元素出来
v = LocateVex(G,u);
DeQueue(&Q);
for(i=0;i<G.vexNum;i++){
w = G.vexs[i];
if(G.arcs[v][i]==1 && visited[i]==0){ //顶点u和w间有边，且顶点w未被访问
printf("%c", w);
EnQueue(&Q,w);
visited[i] = 1;
}
}
}
}
int main(int argc, char const *argv[]) {
AMGraph G;
CreateUDG(&G);
BFS(G,'a');
return 0;
}
- 性能分析：无论是邻接表还是邻接矩阵，算法都需要借助一个辅助队列Q，因此在最坏情况下，空间复杂度为O(vexnum)；采用邻接表存储方式时，每个顶点都需要搜索一次，时间复杂度为O(vexnum)，在搜索任意一个顶点的邻接点时，每条边至少访问一次，时间复杂度是O(arcnum)，算法总时间复杂度是O(vexnum + arcnum)；采用邻接矩阵时，查找每个顶点邻接点的时间复杂度是O(vexnum)，所以总时间复杂度是O(vexnum^2)
- 求解单源最短路径问题（这是由广度优先算法总是按照距离由近到远来遍历图中每个顶点的性质决定的）：
void BFS_MIN_Distance(Graph G, int u){
//d[i]表示从u到i结点的最短路径
for(i=0;i<G.vexnum;++i){
d[i] = NoPath; //初始化路径长度
}
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]){
visited[w] = TRUE;
d[w] = d[u] + 1; //利用性质了
EnQueue(Q,w);
}
}
}
}
- 广度优先生成树：邻接矩阵生成树表示唯一；邻接表生成树不唯一
2.深度优先遍历
- 基本思想：类似于树的先序遍历，首先访问图中某一个起始结点v，然后从v出发，访问与v领接且未被访问的任一顶点w1，再访问与w1邻接且未被访问的任一顶点w2，重复上述过程，当不能继续向下访问时，依次退回到最近被访问的结点，若它还有邻接顶点未被访问，则从该点开始继续上述搜索过程，直到所有顶点都被访问过
- 采用递归思想，回退操作其实就是利用了递归中的调用栈
#include <stdio.h>
#include <stdlib.h>
#define MaxSize 25
#define TRUE 1
#define FALSE 0
int visited[MaxSize];
typedef struct AMGraph{
char vexs[MaxSize];
int arcs[MaxSize][MaxSize];
int vexNum,arcNum;
}AMGraph;
int LocateVex(AMGraph G,char v){ //定位顶点的位置
int i;
for(i=0;i<G.vexNum;i++){
if(G.vexs[i] == v){
return i;
}
}
}
void CreateUDG(AMGraph *G){
int i,j,k;
char vi,vj;
printf("scanf vexNum and arcNum\n");
scanf("%d", &G->vexNum); //输入顶点数与边数
scanf("%d", &G->arcNum);
getchar();
for(i=0;i<G->vexNum;i++){
printf("scanf vexs\n");
scanf("%c",&G->vexs[i]); //输入顶点信息
getchar();
}
for(i=0;i<G->vexNum;i++){
for(j=0;j<G->vexNum;j++){
G->arcs[i][j] = 0; //初始化
}
}
for(k=0;k<G->arcNum;k++){
printf("scanf vi and vj\n");
scanf(" %c", &vi);
getchar();
scanf(" %c", &vj);
i = LocateVex(*G, vi);
j = LocateVex(*G, vj);
G->arcs[i][j] = G->arcs[j][i] = 1;
}
}
void DFS(AMGraph G,char v0){
int i,v;
printf("%c ", v0);
v = LocateVex(G,v0);
visited[v] = 1;
for(i=0;i<G.vexNum;i++){
if(G.arcs[v][i]==1&&visited[i]==0){
DFS(G,G.vexs[i]);
}
}
}
int main(int argc, char const *argv[]) {
int i,j;
AMGraph G;
CreateUDG(&G);
for(i=0;i<G.vexNum;i++){
for(j=0;j<G.vexNum;j++){
printf("%d ", G.arcs[i][j]);
}
}
DFS(G,'a');
return 0;
}
- 性能分析：首先这个算法是一个递归算法，所以空间复杂度是O(vexnum)，在邻接矩阵表示时，查找每个顶点的邻接点所需的时间为O(vexnum)，所以总的时间复杂度为O(vexnum^2)，在邻接表表示时，查找所有顶点的邻接点时间复杂度为O(arcnum)，所以总的时间复杂度为O(vexnum + arcnum)
- 深度优先的生层树和生成森林
3.图的遍历可以判断图的连通性
四、图的应用（这一章极度重要的一部分）
1.最小生成树
-
性质
- 最小生成树不唯一，当图中各边权值互不相等时，最小生成树唯一
- 当无向连通图的边数比顶点数少1时，最小生成树就是它本身
- 最小生成树也是树，树的边数与顶点树关系它也满足
- 权值必定最小
-
Prim算法（基于贪心算法）
#include <stdio.h> #include <stdlib.h> #define MaxSize 25 typedef struct{ int from; int to; int weight; int flag; //用来判断这个结点有没有被加入最小生成树中 }ArrayNode; //辅助数组，用来更新结点最短路径 typedef struct AMGraph{ char vexs[MaxSize]; int arcs[MaxSize][MaxSize]; int vexNum,arcNum; }AMGraph; int LocateVex(AMGraph G,char v){ //定位顶点的位置 int i; for(i=0;i<G.vexNum;i++){ if(G.vexs[i] == v){ return i; } } } void CreateUDG(AMGraph *G){ int i,j,k; char vi,vj; int weight; printf("scanf vexNum and arcNum\n"); scanf("%d", &G->vexNum); //输入顶点数与边数 scanf("%d", &G->arcNum); getchar(); for(i=0;i<G->vexNum;i++){ printf("scanf vexs\n"); scanf("%c",&G->vexs[i]); //输入顶点信息 getchar(); } for(i=0;i<G->vexNum;i++){ for(j=0;j<G->vexNum;j++){ G->arcs[i][j] = 0; } } for(k=0;k<G->arcNum;k++){ printf("scanf vi and vj\n"); scanf(" %c", &vi); getchar(); scanf(" %c", &vj); i = LocateVex(*G, vi); j = LocateVex(*G, vj); printf("scanf weight between vi and vj\n"); scanf("%d", &weight); G->arcs[i][j] = G->arcs[j][i] = weight; } } void Init_Tree(AMGraph *Tree){ //初始化Prim的最小生成树 int i,j; printf("scanf vexNum and arcNum"); scanf("%d", &Tree->vexNum); //包含原连通无向图所有结点 scanf("%d", &Tree->arcNum); //比结点数刚好少一个的边数 for(i=0;i<Tree->vexNum;i++){ Tree->vexs[i] = '\0'; } for (i=0;i<Tree->vexNum;i++) { for (j=0;j<Tree->arcNum;j++) { Tree->arcs[i][j] = 0; } } } void Prim(AMGraph G,AMGraph T,char v0) { //Prim求最小生成树 int i,j,k; int index; //指向权值最小的边 ArrayNode edgeArray[MaxSize*2]; //辅助数组 int length=0; //数组长度，当然了，从0开始 int n = 1; //统计数组已经加入了多少个结点 //初始状态把第一个结点加入最小生成树中 T.vexs[0] = v0; printf("%-3c",T.vexs[0]); i = LocateVex(G,v0); while(1){ //寻找与顶点i相接且这条边的另一个顶点不在树中的边,存入edgeArray数组中 for(j=0;j<G.vexNum;j++){ if(G.arcs[i][j] > 0){//这个代表这两点之间有路径到达 //判断这条边的另一个结点是否已经在树中 for(k=0;k<T.vexNum;k++){ if(G.vexs[j] == T.vexs[k]){ break; } } if(k == T.vexNum){ //这个时候就说明这条边另一个结点不在树中 edgeArray[length].from = i; edgeArray[length].to = j; edgeArray[length].weight = G.arcs[i][j]; edgeArray[length].flag = 0; //现在只是辅助数组中存储，还没有被选中哦 length++; } } } //接下来就要从数组中选择最小权值的结点咯 //printf("print length: %d", length); index = -1; for(j=0;j<length;j++){ if(index == -1 && edgeArray[j].flag == 0){ index=j; } if(edgeArray[j].flag==0 && edgeArray[j].weight < edgeArray[index].weight){ //index保存了上一个目标结点 index=j; } } //printf("print index: %d", index); //printf("edgeArray[index].to: %d", edgeArray[index].to); //把选中的结点加入生成树中，把相关的边也加入 T.vexs[edgeArray[index].to] = G.vexs[edgeArray[index].to]; //printf("%-3c", G.vexs[edgeArray[index].to]); //printf("%-3c", T.vexs[edgeArray[index].to]); edgeArray[index].flag = 1; //这个选中的结点被使用了 T.arcs[edgeArray[index].from][edgeArray[index].to] = edgeArray[index].weight; T.arcs[edgeArray[index].to][edgeArray[index].from] = edgeArray[index].weight; //切分定理的舍弃部分，提高效率 for(k=0;k<length;k++){ if(edgeArray[k].to == edgeArray[index].to){ edgeArray[k].flag = 1; } } i = edgeArray[index].to; //printf("print i: %d", i); printf("%-3c",T.vexs[i]); n++; //个数增加 //当有G.vexNum个顶点时，最小生成树构造完成 if(n==G.vexNum) break; } for(i=0;i<T.vexNum;i++){ for(j=0;j<T.arcNum;j++){ printf("%d\n", T.arcs[i][j]); } } }- 从Vt = {u0}，E = {}开始
- 在所有u∈Vt，v∈V - Vt的边(u，v)∈E中找到一条代价最小的边(u0，v0)并入Et
- 将u0并入Vt，直到Vt = V
- 构造完成
- 时间复杂度是O(vexnum^2)，不依赖于边数，适合边稠密的图
-
Kruskal算法（基于贪心算法）
#include <stdio.h> #include <stdlib.h> #define MaxSize 25 typedef struct{ int from; int to; int weight; int flag; //用来判断这个结点有没有被加入最小生成树中 }ArrayNode; //辅助数组，用来更新结点最短路径 typedef struct AMGraph{ char vexs[MaxSize]; int arcs[MaxSize][MaxSize]; int vexNum,arcNum; }AMGraph; int LocateVex(AMGraph G,char v){ //定位顶点的位置 int i; for(i=0;i<G.vexNum;i++){ if(G.vexs[i] == v){ return i; } } } void CreateUDG(AMGraph *G){ int i,j,k; char vi,vj; int weight; printf("scanf vexNum and arcNum\n"); scanf("%d", &G->vexNum); //输入顶点数与边数 scanf("%d", &G->arcNum); getchar(); for(i=0;i<G->vexNum;i++){ printf("scanf vexs\n"); scanf("%c",&G->vexs[i]); //输入顶点信息 getchar(); } for(i=0;i<G->vexNum;i++){ for(j=0;j<G->vexNum;j++){ G->arcs[i][j] = 0; } } for(k=0;k<G->arcNum;k++){ printf("scanf vi and vj\n"); scanf(" %c", &vi); getchar(); scanf(" %c", &vj); i = LocateVex(*G, vi); j = LocateVex(*G, vj); printf("scanf weight between vi and vj\n"); scanf("%d", &weight); G->arcs[i][j] = G->arcs[j][i] = weight; } } void Init_Tree(AMGraph *Tree){ //初始化Prim的最小生成树 int i,j; printf("scanf vexNum and arcNum"); scanf("%d", &Tree->vexNum); //包含原连通无向图所有结点 scanf("%d", &Tree->arcNum); //比结点数刚好少一个的边数 for(i=0;i<Tree->vexNum;i++){ Tree->vexs[i] = '\0'; } for (i=0;i<Tree->vexNum;i++) { for (j=0;j<Tree->arcNum;j++) { Tree->arcs[i][j] = 0; } } } //之后的库鲁斯卡尔算法会用到，判断两个结点是否相连 int connected(AMGraph T,int from,int to){ int i,j,k; int vertex[MaxSize];//看做是队列 int front, rear; if(from == to){ return 1; } front = rear = 0; //把第一个顶点存入队列 vertex[rear++] = from; //遍历树 while(front <= rear){ i = vertex[front]; //现在是第一个结点 for(j=0;j<T.vexNum;j++) if(T.arcs[i][j]>0){ if(j==to) return 1; //返回1就是两个结点相连 //判断此顶点是否在队列中 for(k=0;k<rear;k++) //遍历现在在队列中的所有结点 if(vertex[k] == j) break; if(k==rear) //BFS的操作 vertex[rear++]=j; } front++; } return 0; } //库鲁斯卡尔算法 void Kruskal(AMGraph G,AMGraph T){ ArrayNode edgeArray[MaxSize]; //老样子，辅助数组 int length=0; int i,j,k,index,n; //与Prim算法基本一致 //先将所有顶点先加入到最小生成树中 for(i=0;i<T.vexNum;i++){ T.vexs[i] = G.vexs[i]; } //接下来把所有边有序（从小到大）的插入edgeArray数组中 for(i=0;i<G.vexNum;i++){ for(j=0;j<G.vexNum;j++){ if(i<j && G.arcs[i][j]>0){ //寻找插入的位置index for(k=0;k<length;k++){ if(edgeArray[k].weight > G.arcs[i][j]) break; } index=k; //移位 for(k=length;k>index;k--) edgeArray[k]=edgeArray[k-1]; //插入 length++; edgeArray[index].flag=0; edgeArray[index].from=i; edgeArray[index].to=j; edgeArray[index].weight=G.arcs[i][j]; } } } //从小到大取出n-1条边构造最小生成树 n = 0; printf("%d", n); while (n<G.vexNum-1) { /* code */ //从小到大开始选择 for(k=0;k<length;k++){ if(edgeArray[k].flag==0&&connected(T,edgeArray[k].from,edgeArray[k].to)==0){ printf("fail!!!!"); break; } printf("%d", n); //把这条边加入到树中 T.arcs[edgeArray[k].from][edgeArray[k].to] = edgeArray[k].weight; T.arcs[edgeArray[k].to][edgeArray[k].from] = edgeArray[k].weight; edgeArray[k].flag =1; printf("%d", edgeArray[k].weight); n++; } } } int main(int argc, char const *argv[]) { int i,j; AMGraph G; AMGraph T; CreateUDG(&G); Init_Tree(&T); // for (i=0;i<T.vexNum;i++) { // printf("%c ", T.vexs[i]); // } // // for(i=0;i<T.vexNum;i++){ // for(j=0;j<T.arcNum;j++){ // printf("%d ", T.arcs[i][j]); // } // } //Prim(G,T,'a'); Kruskal(G,T); return 0; }- 算法借助的性质是如果一条边连接了两棵不同树中的顶点，那么对这两棵树来说，它必定连通
- O(ElogE)，适合于边稀疏顶点多的图
2.最短路径（两点之间的最短路径也包含了路径上其他顶点间的最短路径）
- Dijkstra算法求解单源最短路径
- 设置一个集合S记录已经求得的最短路径的顶点，可以用S[]来实现，初始为0
- S[vi]表示将顶点vi放入S，初始时把v0（源点）远点放进S
- 设置两个辅助数组
- dist[]：记录从源点v0到其他各顶点当前的最短路径长度，dist[i]的初值为arcs[v0] [i]
- path[]：path[i]表示从源点到顶点i之间的最短路径的前驱结点，算法结束时，可以根据这个的值追溯得到源点v0到顶点vi的最短路径
- 说白就是没找一个点都是最短路径，那么最终自然是最短路径
- 时间复杂度都是O(V^2)
- 不允许图中带有负权值
- Floyd算法求各顶点之间最短路径
- 递推产生一个n阶方阵序列A^-1，A^0，A^1……A^(n-1)
- A^0[i] [j]表示从顶点vi到vj，中间顶点是v0的最短路径长度，A^k[i] [j]表示中间顶点的序号不大于k的最短路径
- 时间复杂度为O(V^3)
- 允许图中带有负权值
3.拓扑排序（当时弄的很迷糊）
- 在一个有向无环图中的顶点组成的序列满足这些条件，称为拓扑排序
- 每个顶点出现且只出现一次
- 如果顶点A在序列中排在顶点B的前面，那么不存在从B到A的路径
- 拓扑排序的算法
- 从DAG图中选择一个没有前驱的顶点并输出
- 从图中删除该顶点和以它为起点的有向边
- 重复上述步骤直到当前DAG图为空或当前图中不存在无前驱顶点为止（这种情况说明有环）
4.关键路径（类似于拓扑排序的应用？）
- 需要注意的是，顶点代表时间，边代表活动
- 时间Vk的最早发生时间Ve(k)，这个理解问题不大，从前往后的顺序计算
- 时间Vk的最迟发生时间Vl(k)，这个的理解意思是，在不推迟整个工期的情况下，为了能够保证下一个事件能够在最早发生时间按时发生，它之前的那个事件最迟必须发生的事件，从后往前的计算，减去所需时间嘛
- 活动ai的最早开始时间
- 活动ai的最迟开始时间，这个理解是，这个活动终点所表示的时间的最迟发生时间与该活动所需时间之差
- 一个活动ai的最迟开始时间和最早开始时间的差额代表时间余量
Comments
😅 Commenting is disabled on this post.