欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 财经 > 创投人物 > 2.11学习总结

2.11学习总结

2025/8/21 23:02:01 来源:https://blog.csdn.net/2402_88130280/article/details/145564705  浏览:    关键词:2.11学习总结

最短路径:

单源最短路径—迪杰斯特拉Dijskra算法:从一个起始点出发,到达一个终点
多源最短路径—弗洛伊德Floyd算法:求每一对顶点之间的最短路径

深搜广搜:

void BFS(int G[][N], int s) //G[i][j]=1表示i可以到达j,s表示搜索的起始点
{ visited[s] = 1;              Q[0]=s;int first=-1,last=0,v;while(first!=last){ v=Q[++first];for (int i=0;i<N;i++){if (G[v][i]==1){if(visited[i] == 0){Q[++last]=i;visited[i] = 1;        }}	}	} 
}

全排列:从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列。当m=n时所有的排列情况叫全排列。

数小):嵌套循环

譬如123的全排列(if内语句很重要)

for(a=1;a<=3;a++)for(b=1;b<=3;b++)for(c=1;c<=3;c++)if(a!=b&&a!=c&&b!=c)printf("%d%d%d",a,b,c);

数大):搜索dfs

图的存储

邻接矩阵

#define MAX 100//顶点数目的最大值
typedef struct {char Vex[MAX];//顶点表int Edge[MAX][MAX];//邻接矩阵,边表int vexnum, arcnum;//图的当前顶点数和边数
}MGraph;

带权图/网

#define MAX 100//顶点数目的最大值
#define INFINITY//宏定义量正无穷
typedef char VertexType;//顶点的数据类型
typedef int EdgeType;//带权图中边上权值的数据类型
typedef struct {char Vex[MAX];//顶点int Edge[MAX][MAX];//边的权int vexnum, arcnum;//图的当前顶点数和边数
}MGraph;

邻接表

洛谷b3643图的存储

#include <stdio.h>
#include <stdlib.h>
int main() {int n, m;scanf("%d %d", &n, &m);// 初始化邻接矩阵int adjMatrix[n + 1][n + 1];for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {adjMatrix[i][j] = 0;}}// 初始化邻接表int* adjList[n + 1];int degree[n + 1];for (int i = 1; i <= n; i++) {adjList[i] = (int*)malloc(n * sizeof(int));degree[i] = 0;}// 读取边并填充邻接矩阵和邻接表for (int i = 0; i < m; i++) {int u, v;scanf("%d %d", &u, &v);adjMatrix[u][v] = 1;adjMatrix[v][u] = 1;adjList[u][degree[u]++] = v;adjList[v][degree[v]++] = u;}// 输出邻接矩阵for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {printf("%d ", adjMatrix[i][j]);}printf("\n");}// 输出邻接表for (int i = 1; i <= n; i++) {printf("%d ", degree[i]);for (int j = 0; j < degree[i]; j++) {printf("%d ", adjList[i][j]);}printf("\n");}// 释放邻接表的内存for (int i = 1; i <= n; i++) {free(adjList[i]);}return 0;
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

热搜词