网站的切图是谁来做,学会网站 建设,欧美风网站,海安企业网站建设图论在提高组中几乎占据半壁江山#xff0c;而今天要讲的就是如何存储一个图一.邻接矩阵原理要建立一个图#xff0c;根本的要素就是边和点而想要让计算机存储边和点就需要用到一些数据结构邻接矩阵是最简单的他使用了一个二维数组#xff0c;来表示一个图假设数组名为map那…图论在提高组中几乎占据半壁江山而今天要讲的就是如何存储一个图一.邻接矩阵原理要建立一个图根本的要素就是边和点而想要让计算机存储边和点就需要用到一些数据结构邻接矩阵是最简单的他使用了一个二维数组来表示一个图假设数组名为map那么map[i][j]的值就代表i到j的权值栗子例子一个普通的图注意一个无向边等于两个有向边比如1到2权值为1那么就相当于1-2一条有向边加上2-1一条有向边一共两条回归到这个图上在这里用邻接矩阵的写法就是map[1][2] 3map[2][1] 3map[2][3] 6map[3][2] 6map[1][3] 5map[3][1] 5map[5][3] 2map[3][5] 2map[1][5] 4map[5][1] 410条有向边邻接矩阵原理就是这么简单代码int n,m,vis[100001],mapa[1001][1001],ans1000000001;
n点 m边 vis点的状态 mapa邻接矩阵二维数组 ans遍历最短距离int main()
{cinnm;int i,j,a,b,c;memset(mapa,0x3f,sizeof(mapa));for(j0;jm;j){cinabc;mapa[b][a]c;//保证单向 mapa[a][b]c;}vis[1]1;dfs(1,0);coutansendl;return 0;
}
主函数部分
v[i]1表示这个点已经走过void dfs(int x,int dis)
{int i;if(disans)//小剪枝 return;if(xn){ansmin(ans,dis);return;}for(i1;in;i) //不一定向前走可能绕一下更近 if(mapa[x][i]!0x3f3f3f3fvis[i]0) {vis[i]1;dfs(i,dismapa[x][i]);vis[i]0;}
}dfs主体函数基础例题暑假小马想到小张家里去玩他们住在不同的城市这是小马第一次去小张家小马提前在百度地图上面查找行车路线输入出发城市和目的城市百度地图计算出最短路径请实现百度地图计算最短路径的方法。备注总共有n个n100城市小马家所在城市编号为1小张家所在城市编号为n公路为双向车道。输入第一行两个整数分别表示城市数量n和公路数量m。后面m行表示公路情况每一行三个整数a,b,c分别表示从城市a到城市b两个城市之间的公路路程c公里。输出最短路程公里数样例输入1
5 8
1 2 2
1 5 10
2 3 3
2 5 7
3 1 4
3 4 4
4 5 5
5 3 3
样例输出1
7纯属的模板其实这题严格来说是最短路径问题但用来练习邻接矩阵绝对是不二之选特点及优劣优实在好理解 简单易懂劣除了好理解全是劣势 时间复杂度、空间复杂度等等二.邻接表邻接表确实有些复杂但性能还是不错的1.原理以点为单位记录每个点连接的边数据结构vector动态数组动态数组好处就是不需要预估大小但是会占一些空间普通小图首先与1连接的边共有两条链表中大概就是这样如果没太看懂没关系蒟蒻用铅笔画了一下整个过程就是把n个点看成n个容器每个容器往里面扔元素一个元素含义就是一条边如1容器中扔了个2代表1、2之间有边每个往里面扔的元素需要有两个参数第一边的目标点也就是例子中的2第二边权值2.代码int main()
{node t;cinnm;int i,j,a,b,c;//memset(mapa,0x3f,sizeof(mapa));//初始化for(j0;jm;j){cinabc;t.vb;t.wc;e[a].push_back(t);t.va;t.wc;e[b].push_back(t);}vis[1]1;dfs(1,0);coutansendl;return 0;
}
e代表容器因为是vector一个变量就可以扔无数个元素所以想要每个点都有只需要一维即可
其他变量名称同邻接矩阵void dfs(int x,int dis)
{int i;if(disans)//小剪枝 return;if(xn){ansmin(ans,dis);return;}node tt; for(int i0;ie[x].size();i){tte[x][i];if(vis[tt.v]0){vis[tt.v]1;dfs(tt.v,distt.w);vis[tt.v]0;}}
}
就是邻接矩阵的处理上改了一些但优化了很多很多struct node
{int v;int w;
};vectornode e[105];
自定义部分vector动态数组案例依旧是邻接矩阵的18163.特点及优劣优解决了时间的问题以及空间的问题劣动态数组还是有些差三。链式前向星前两个你都不会也没事儿这个一定要会1.原理以边为单位记录每一条边的目标点以及权值和下一条边的编号1目标点还是那个例子1和2之间边权值为3目标点就为22权值不解释了2下一条边的编号链式前向星核心思路来了链式前向星顾名思义有链表的成分所在每条边都有自己的编号通过编号层层遍历 还得有一个数组表示以i点为起始点的边的编号还是画一下基本思路就是这么个思路代码也算是比较抽象一些但懂了之后也很简单2.代码int main()
{cinnm;int i,j,a,b,c;for(j0;jm;j){cinabc;addedge(a,b,c);加边操作一条无向边等于两条有向边addedge(b,a,c);}vis[1]1;dfs(1,0);coutansendl;return 0;
}void addedge(int u,int v,int w)
{cnt;边的数量e[cnt].tov;目标点初始化e[cnt].ww;权值e[cnt].nxth[u];下一条边的编号h[u]cnt;以u为起点的边的编号更新
}struct edge
{int to;int w;int nxt;
}e[300];
int cnt;
int h[105];
int n,m,vis[100001],mapa[1001][1001],ans1000000001;void dfs(int x,int dis)
{int i;if(disans)//小剪枝 return;if(xn){ansmin(ans,dis);return;}for(int ih[x];i0;ie[i].nxt)链式前向星遍历方法h[x]代表以x为起始点的最新的边只要i还是正数i作为编号就变成第k条边的下一条边的编号{int toe[i].to;int we[i].w;if(vis[to]0){vis[to]1;dfs(to,disw);vis[to]0;}}}特点及优劣优时间空间双重解决劣需要提前知道边的数量来定义数组否则就得用邻接表以上就是本蒟蒻对邻接矩阵邻接表链式前向星的理解了总结邻接矩阵基本没用有边的数量就用链式前向星否则就邻接表看了这么多点个赞再走才是好习惯doge
