算法设计与分析：图与计算几何算法

亦凉 2023-06-23 09:52 19阅读 0赞

图和计算几何

1.  有n个点、m条无向边的图，每条边都有长度d和花费p,再给出一个七点s和一个重点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。
2.  给定三角形的3条边，a、b、c，判断该三角形的类型。
3.  直接利用狄克斯特拉算法求从顶点s到顶点t花费最小的最短路径。在狄克斯特拉算法中要做两点修改，一是增加记录路径最小花费的数字cost，cost\[j\]表示从顶点s到顶点j的最短路径的最小花费，当存在多条最短路径时需要比较路径花费求cost\[j\]；二是如果顶点t的最短路径已求出，就不需要考虑其他顶点，输出结果并推出狄克斯特拉算法。
4.  最长边对应最大角，对3条边e\[0,2\]按递增排序，求出result=e\[0\]+e\[1\]-e\[3\],根据result可以确定三角形的类型。
5.

1-1  
\#include<stdio.h>  
\#define MAXV 1010  
\#define INF 0xffffff //定义无穷  
int n,m;  
int Dist\[MAXV\]\[MAXV\],Cost\[MAXV\]\[MAXV\];  
int s,t;  
void Dijikstra(int s)//狄克特斯拉算法  
\{  
int dist\[MAXV\];  
int cost\[MAXV\];  
int S\[MAXV\];  
int mindist,mincost,u;  
int i,j;  
for(i=1;i<=n;i++)//dist、cost、S初始化，注意顶点编号从1开始  
\{  
dist\[i\]=Dist\[s\]\[i\];  
cost\[i\]=Cost\[s\]\[i\];  
S\[i\]=0;  
\}  
dist\[s\]=cost\[s\]=0;  
S\[s\]=1;  
for(i=0;i<m;i++)  
\{  
mindist=INF;  
for(j=1;j<=n;j++)//求V-S中的最小距离mindist  
if(S\[j\]0&&mindist>dist\[j\])  
mindist=dist\[j\];  
if(mindistINF) break;//找不到连通的顶点  
mincost=INF;u=-1;  
for(j=1;j<=n;j++)//求尚未考虑的、距离最小的顶点u  
\{  
if(S\[j\]0&&mindistdist\[j\]&&mincost>cost\[j\])  
\{  
//在dist为最小的顶点中找最小的cost的顶点u  
mincost=cost\[j\];  
u=j;  
\}  
\}  
S\[u\]=1;//将顶点u加入到S集合  
for(j=1;j<=n;j++)//考虑顶点u，求s到顶点j的对端路径长度和花费  
\{  
int d=mindist+Dist\[u\]\[j\];//d记录经过顶点u的路径花费  
int c=cost\[u\]+Cost\[u\]\[j\];//c记录经过顶点u的花费  
if(S\[j\]0&&d<dist\[j\])  
\{  
dist\[j\]=d;  
cost\[j\]=c;  
\}  
else if(S\[j\]0&&ddist\[j\]&&c<cost\[j\])  
cost\[j\]=c;//有多条长度相同的最短路径  
\}  
if(S\[t\]1)//已经求出s到t的最短路径  
\{  
printf("%d %d\\n",dist\[t\],cost\[t\]);  
return ;  
\}  
\}  
\}  
int main()  
\{  
int a,b,d,p;  
int i,j;  
while(scanf("%d%d",&n,&m)!=EOF)  
\{  
if(m0&&n0)  
break;  
for(i=1;i<=n;i++)  
\{  
for(j=1;j<=n;j++)  
\{  
Dist\[i\]\[j\]=INF;  
Cost\[i\]\[j\]=INF;  
\}  
\}  
for(i=0;i<m;i++)  
\{  
scanf("%d%d%d%d\\n",&a,&b,&d,&p);  
if(Dist\[a\]\[b\]>d)  
\{  
Dist\[a\]\[b\]=Dist\[b\]\[a\]=d;//无向图的边是对称的  
Cost\[a\]\[b\]=Cost\[b\]\[a\]=p;  
\}  
\}  
scanf("%d%d",&s,&t);  
Dijikstra(s);  
\}  
return 0;  
\}  
1-2.  
\#include<bits/stdc++.h>  
using namespace std;  
int main()  
\{  
double e\[3\];  
while(cin>>e\[0\]>>e\[1\]>>e\[2\])  
\{  
sort(e,e+3);  
double result=pow(e\[0\],2)+pow(e\[1\],2)-pow(e\[2\],2);  
if(result==0)  
cout<<“直角三角形”<<endl;  
else if(result>0)  
cout<<“锐角三角形”<<endl;  
else  
cout<<“锐角三角形”<<endl;  
\}  
return 0;  
\}  
3.  
\#include<stdio.h>

\#define MAXEDGE 100  
\#define MAXVERTEX 100  
typedef struct Edge  
\{  
int begin;//边的起点  
int end; //边的终点  
int wight;//边的权值  
\}Edge;

typedef struct Graph  
\{  
char vertex\[MAXVERTEX\];//顶点  
Edge edges\[MAXEDGE\];//边  
int numvertex,numedges;//顶点和边的个数  
\}MGraph;

void CreateGraph(MGraph\* G)  
\{  
printf(“请输入顶点和边的个数：\\n”);  
scanf("%d%d", &G->numvertex, &G->numedges);  
printf(“请输入顶点：\\n”);  
getchar();//利用该函数除去上一系我们在输入结束时按得回车符  
for (int i = 0; i < G->numvertex; i++)  
\{  
scanf("%c", &G->vertex\[i\]);  
\}  
printf(“按权值从小到大输入边（vi,vj）对应的起点和终点的下标，begin，end以及权值wight:\\n”);  
for (int k = 0; k < G->numedges; k++)  
\{  
Edge e;  
scanf("%d%d%d", &e.begin, &e.end, &e.wight);  
G->edges\[k\] = e;  
\}  
\}

int Find(int \*parent, int f)  
\{  
while (parent\[f\]>0)  
\{  
f = parent\[f\];  
\}  
return f;  
\}

//最小生成树，克鲁斯卡尔算法  
void Kruskal(MGraph \*G)  
\{

int parent[MAXVERTEX];//存放最小生成树的顶点
    for (int i = 0; i < G->numvertex; i++)
    {
    	parent[i] = 0;
    }
    int m, n;
    for (int i = 0; i < G->numedges; i++)
    {
    	n = Find(parent, G->edges[i].begin);
    	m = Find(parent, G->edges[i].end);
    	if (n != m)//m=n说明有环
    	{
    		parent[n] = m;
    		printf("(%d,%d) %d\t", G->edges[i].begin, G->edges[i].end, G->edges[i].wight);//打印边和权值
    	}
    }

int main()  
\{  
MGraph G;  
CreateGraph(&G);  
Kruskal(&G);

return 0;

\}  
![在这里插入图片描述][20191218130707794.png]  
![在这里插入图片描述][20191218130719900.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzM5NzM0_size_16_color_FFFFFF_t_70]

[20191218130707794.png]: https://img-blog.csdnimg.cn/20191218130707794.png
[20191218130719900.png]: https://img-blog.csdnimg.cn/20191218130719900.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzM5NzM0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191218130736188.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzM5NzM0,size_16,color_FFFFFF,t_70