首页 > 其他分享 >20231114打卡

20231114打卡

时间：2023-11-14 22:33:05浏览次数：36  
标签：vexnum 20231114 int MAX ++ arc Graph 打卡

今天学习了数据结构
练习了最小生成树算法kruskal和最短路径dijkstra和floyd算法

#define MAX 10000000
#include<iostream>
using namespace std;

struct Graph
{
	int** arc;
	char* vex;
	int vexnum;
	int arcnum;
};

struct Edge {
	int start, end, weight;
};

Edge* createdge(Graph* g) {
	Edge* edge = new Edge[g->arcnum];
	int count = 0;
	for (int i = 0; i < g->vexnum - 1; ++i) {
		for (int j = i + 1; j < g->vexnum; ++j) {
			if (g->arc[i][j] > 0 && g->arc[i][j] < MAX) {
				edge[count].weight = g->arc[i][j];
				edge[count].start = i;
				edge[count].end = j;
				count++;
			}
		}
	}
	return edge;
}

void sort(Edge* edge,Graph* g) {
	Edge tmp;
	for (int i = 0; i < g->arcnum; i++) {
		for (int j = 0; j < g->arcnum - i - 1; ++j) {
			if (edge[j].weight > edge[j + 1].weight) {
				tmp = edge[j];
				edge[j] = edge[j + 1];
				edge[j + 1] = tmp;
			}
		}
	}
}

void kruskal(Graph* g) {
	int* connected = new int[g->vexnum];
	Edge* edge = createdge(g);
	sort(edge,g);
	for (int i = 0; i < g->vexnum; ++i) {
		connected[i] = i;
	}
	for (int i = 0; i < g->vexnum; ++i) {
		int v1 = edge[i].start;
		int v2 = edge[i].end;
		if (connected[v1] != connected[v2]) {
			cout << 'v' << g->vex[v1] << "->" << 'v' << g->vex[v2] << ' ' << edge[i].weight << endl;
			for (int j = 0; j < g->vexnum; ++j) {
				if (connected[j] == connected[v2]) {
					connected[j] = connected[v1];
				}
			}
		}
	}
}

Graph* creatGraph(int* nums,char* vex,int n){
	Graph* g = new Graph;
	g->arcnum = 0;
	g->arc = new int* [n];
	g->vex = new char[n];
	g->vexnum = n;
	for (int i = 0; i < n; ++i)
	{
		g->vex[i] = vex[i];
		g->arc[i] = new int[n];
		for (int j = 0; j < n; ++j) {
			g->arc[i][j] = nums[i * n + j];
			if (g->arc[i][j] > 0 && g->arc[i][j] < MAX)
			{
				g->arcnum++;
			}
		}
	}
	g->arcnum /= 2;
	return g;
}

void Dfs(Graph* g,int start,int* index)
{
	cout << g->vex[start]<<" ";
	index[start] = 1;
	for (int i = 0; i < g->vexnum; ++i) {
		for (int j = 0; j < g->vexnum; ++j) {
			if (g->arc[i][j] > 0 && g->arc[i][j] < MAX && !index[j]) {
				Dfs(g, j, index);
			}
		}
	}
}

int main() {
	char a[6] = { '1','2','3','4','5','6'};
	int index[6] = { 0 };
	int arc[6][6] = {
		0,6,1,5,MAX,MAX,
		6,0,5,MAX,3,MAX,
		1,5,0,5,6,4,
		5,MAX,5,0,6,2,
		MAX,3,6,MAX,0,6,
		MAX,MAX,4,2,6,0
	};
	Graph* g= creatGraph((int*)arc, a, 6);
	kruskal(g);
	return 0;
}

#define MAX 10000000
#include<iostream>
using namespace std;

struct Graph
{
	int** arc;
	char* vex;
	int vexnum;
	int arcnum;
};

Graph* creatGraph(int* nums, char* vex, int n) {
	Graph* g = new Graph;
	g->arcnum = 0;
	g->arc = new int* [n];
	g->vex = new char[n];
	g->vexnum = n;
	for (int i = 0; i < n; ++i)
	{
		g->vex[i] = vex[i];
		g->arc[i] = new int[n];
		for (int j = 0; j < n; ++j) {
			g->arc[i][j] = nums[i * n + j];
			if (g->arc[i][j] > 0 && g->arc[i][j] < MAX)
			{
				g->arcnum++;
			}
		}
	}
	g->arcnum /= 2;
	return g;
}

int getmin(int* s,int* d,int n) {
	int min = MAX;
	int index = -1;
	for (int i = 0; i < n; ++i) {
		if (d[i] < min && !s[i] && d[i]) {
			min = d[i];
			index = i;
		}
	}
	return index;
}

void Dijkstra(Graph* g, int start) {
	int* s = new int[g->vexnum];//存储是否加入u1集合
	int* p = new int[g->vexnum];//存储d数组集合的前驱节点
	int* d = new int[g->vexnum];//存储u1集合到u集合的距离
	for (int i = 0; i < g->vexnum; ++i) {
		d[i] = g->arc[start][i];
		p[i] = start;
		s[i] = 0;
	}
	s[start] = 1;
	for (int i = 0; i < g->vexnum; ++i) {
		int index = getmin(s,d, g->vexnum);
		if (index != -1) {
			s[index] = 1;
			for (int j = 0; j < g->vexnum; ++j) {
				if (d[index] + g->arc[index][j] < d[j]) {
					d[j] = d[index] + g->arc[index][j];
					p[j] = index;
				}
			}
		}
	}
	for (int i = 0; i < g->vexnum; ++i) {
		cout << s[i] << ' ' << p[i] << ' ' << d[i] << endl;//输出最终三个数组
	}
}

void Dfs(Graph* g, int start, int* index)
{
	cout << g->vex[start] << " ";
	index[start] = 1;
	for (int i = 0; i < g->vexnum; ++i) {
		for (int j = 0; j < g->vexnum; ++j) {
			if (g->arc[i][j] > 0 && g->arc[i][j] < MAX && !index[j]) {
				Dfs(g, j, index);
			}
		}
	}
}

int main() {
	char a[7] = { '1','2','3','4','5','6','7'};
	int index[7] = { 0 };
	int arc[7][7] = {
		0,12,MAX,MAX,MAX,16,14,
		12,0,10,MAX,MAX,7,MAX,
		MAX,10,0,3,5,6,MAX,
		MAX,MAX,3,0,4,MAX,MAX,
		MAX,MAX,5,4,0,2,8,
		16,7,6,MAX,2,0,9,
		14,MAX,MAX,MAX,8,9,0
	};
	Graph* g = creatGraph((int*)arc, a, 7);
	Dijkstra(g, 0);
	return 0;
}

#define MAX 10000000
#include<iostream>
using namespace std;

struct Graph
{
	int** arc;
	char* vex;
	int vexnum;
	int arcnum;
};

Graph* creatGraph(int* nums, char* vex, int n) {
	Graph* g = new Graph;
	g->arcnum = 0;
	g->arc = new int* [n];
	g->vex = new char[n];
	g->vexnum = n;
	for (int i = 0; i < n; ++i)
	{
		g->vex[i] = vex[i];
		g->arc[i] = new int[n];
		for (int j = 0; j < n; ++j) {
			g->arc[i][j] = nums[i * n + j];
			if (g->arc[i][j] > 0 && g->arc[i][j] < MAX)
			{
				g->arcnum++;
			}
		}
	}
	g->arcnum /= 2;
	return g;
}

void Floyd(Graph* g) {
	int** d = new int* [g->vexnum];//记录距离
	int** p = new int* [g->vexnum];//记录i到j的前驱
	for (int i = 0; i < g->vexnum; ++i) {
		d[i] = new int[g->vexnum];
		p[i] = new int[g->vexnum];
		for (int j = 0; j < g->vexnum; ++j) {
			d[i][j] = g->arc[i][j];
			p[i][j] = i;
			if (i == j || g->arc[i][j]==MAX)
			{
				p[i][j] = -1;
			}
		}
	}
	for (int i = 0; i < g->vexnum; ++i) {
		for (int j = 0; j < g->vexnum; ++j) {
			for (int k = 0; k < g->vexnum; ++k) {
				if (d[j][k] > d[j][i] + d[i][k]) {
					p[j][k] = p[i][k];
					d[j][k] = d[j][i] + d[i][k];
				}
			}
		}
	}
	for (int i = 0; i < g->vexnum; ++i) {
		for (int j = 0; j < g->vexnum; ++j) {
			cout << d[i][j] << ' ';
		}
		cout << endl;
	}
	cout << endl;
	for (int i = 0; i < g->vexnum; ++i) {
		for (int j = 0; j < g->vexnum; ++j) {
			cout << p[i][j] << ' ';
		}
		cout << endl;
	}
}

void Dfs(Graph* g, int start, int* index)
{
	cout << g->vex[start] << " ";
	index[start] = 1;
	for (int i = 0; i < g->vexnum; ++i) {
		for (int j = 0; j < g->vexnum; ++j) {
			if (g->arc[i][j] > 0 && g->arc[i][j] < MAX && !index[j]) {
				Dfs(g, j, index);
			}
		}
	}
}

int main() {
	char a[4] = { '1','2','3','4'};
	int index[4] = { 0 };
	int arc[4][4] = {
		0,1,MAX,3,
		1,0,2,2,
		MAX,2,0,8,
		3,2,8,0
	};
	Graph* g = creatGraph((int*)arc, a, 4);
	Floyd(g);
	return 0;
}

标签：vexnum,20231114,int,MAX,++,arc,Graph,打卡
From： https://www.cnblogs.com/wlxdaydayup/p/17832764.html

相关文章

  • 11.14打卡
    1.最小覆盖字串（76）给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。classSolution{publicStringminWindow(Strings,Stringt){intn=s.length();......
  • 大二打卡（11.13）
    今天做了什么：今天周一，没有工程实训，没有早八，开心，一觉睡到九点12，刚醒墩儿，手机一震，建民老师发布消息，下午分级测试，以为上周说的每周一套题，就单单是个练习，没想到还是考试，难顶，但是上午的时候还是没怎么放在心上，下午开始测试了，才发觉这玩意工作量这么大，没好好练，根本写不完，才三个小时，我估......
  • 多商家签到打卡奖励免单霸王餐小程序开发
    多商家签到打卡奖励免单霸王餐小程序开发用户注册和登录：提供用户注册和登录功能，以便用户能够参与签到打卡活动。商家入驻：商家可申请入驻平台，提交相关资料并等待平台审核，审核通过后即可发布活动和奖励。签到打卡活动：用户可通过小程序参与商家举办的签到打卡活动，定期签到打卡可获得积......
  • YCOJ734 [ 20231114 NOIP 模拟赛 T3 ] 二次函数
    题意给定\(n\)个形如\(f(x)=(x-m)^2+k\)的二次函数。\(1,m,k\)表示加入一个顶点位\((m,k)\)的二次函数。\(2,x,t\)表示删除所有\(f(x)\let\)的二次函数。求每次操作结束后还剩余几个二次函数。Sol注意到题中二次系数为\(1\)，这就意味着每一个函......
  • 20231114打卡
    早上，我在课堂上学习了拓扑排序和关键路径两个在工程实践中非常重要的概念。拓扑排序是一种拓扑排序算法，用于高效地解决有向无环图（DAG）中的依赖问题。关键路径则可以帮助我们确定项目计划中的关键节点和关键路径，是工程项目管理中非常常用的技术。通过课堂讲解和案例分析，我对这两个概......
  • 代码随想训练营第三十五天打卡（Python）｜ 860.柠檬水找零、406.根据身高重建队列、452. 用
    860.柠檬水找零classSolution:deflemonadeChange(self,bills:List[int])->bool:five,ten,twenty=0,0,0forbillinbills:ifbill==5:five+=1elifbill==10:iffive......
  • 202311141210——《一些修改表字段的sql语句》
    ALTERTABLEuserADDCOLUMNtelCHAR(11)AFTERwechat;#添加列ALTERtablecustomermodifycolumnpasswordvarchar(200);#修改列类型ALTERTABLEuserALTERCOLUMNstatusSETDEFAULT1;#设置默认值ALTERTABLEuserMODIFYcolumnemp_idTIMESTAMPDEFAULTNULL......
  • 20231114学习总结
    推荐参考书：[1]范淼,李超.Python机器学习及实践,清华大学出版社.[2]PeterHarrington.机器学习实战,人民邮电出版社。《机器学习B实验任务书1》一、上机安排时间地点第10周周一2023.11.06第6-7节九实4-3、4-4第11周周一2023.11.13第6-7节九实......
  • 20231113打卡
    今天上午电工基础实训，掌握基本的用电常识，提高我的用电安全意识，锻炼我的实操能力。下午java分级测试，我花了大量时间在后端构建上，前端分配的时间相对少了很多，主要是自己的技能水平不够熟练，勉强B级qwq......
  • 11月13每日打卡
    实验13：享元模式本次实验属于模仿型实验，通过本次实验学生将掌握以下内容：1、理解享元模式的动机，掌握该模式的结构；2、能够利用享元模式解决实际问题。 [实验任务一]：围棋设计一个围棋软件，在系统中只存在一个白棋对象和一个黑棋对象，但是它们可以在棋盘的不同位置显示多次。实......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99