草庐IT

图——邻接表法创建无向图算法。走起。。。。

懒喵喵々 2023-09-03 原文

一、算法步骤：

1、先输入无向图的的总顶点数和边数。
2、输入每个顶点的信息，并把所有顶点结点中的firstarc置为NULL。
3、输入与每条边相关联的两个顶点。
4、找到两个顶点的位置即在顶点结点中的序号。
5、生成两个新边节点、把两个边界点加到领个链表对应的头部。

二、部分步骤相关代码：

1、定义一个边结点的结构体：（包含adjvex、nextarc属性）

//定义一个边结点的结构体
typedef struct ArcNode{
	int adjvex;  //该边所指向的顶点的位置
    struct ArcNode *nextarc; //指向与该顶点相连的另一条边的指针 
}ArcNode;

2、定义一个顶点结点的结构体：（包含data、firstarc属性）

//定义一个顶点结点的结构体
typedef struct VNode{
	char data;    //顶点结点的数据 
	ArcNode *firstarc;//指向该顶点的第一条边 
}VNode,AdjList[MVNum];

3、定义一个无向图的结构体：（包含vertices、vexnum、arcnum）

typedef struct ALGraph{
	AdjList vertices;
	int vexnum,arcnum;//图的总顶点个数、总边数 
}ALGraph;

4、找与每条边关联的两个顶点的位置编号：
 

//找与每条边关联的两个顶点的位置编号
int LocateChar(ALGraph G,char v){
	for(int i=0;i<G.vexnum;i++)
	{
		if(G.vertices[i].data==v)
		   return i;
	}
}

5、初始化、构造无向图：

//初始化、构造无向图
int CreateUDG(ALGraph &G){
	cout<<"请输入无向图的总顶点数和总边数："<<endl;
	cin>>G.vexnum>>G.arcnum;
	//输入点的具体信息
	for(int i=0;i<G.vexnum;i++){
		cout<<"请输入第"<<(i+1)<<"个顶点的信息："<<endl;
		cin>>G.vertices[i].data;
		G.vertices[i].firstarc=NULL;
	} 
	//输入与边相连的两个顶点
	char v1,v2;
	for(int k=0;k<G.arcnum;k++){
		cout<<"请输入第"<<(k+1)<<"条边依附的顶点："<<endl;
		cin>>v1>>v2;
		int i = LocateChar(G,v1);
		int j = LocateChar(G,v2);
		
	    ArcNode	*p1=new ArcNode;//生成一个新的边结点
	    p1->adjvex=j;
		p1->nextarc=G.vertices[j].firstarc;//将边结点插入到 Vj顶点结点的头部 
		G.vertices[j].firstarc=p1; 
		
		ArcNode *p2=new ArcNode; //生成另外一个边结点 
		p2->adjvex=i;
		p2->nextarc=G.vertices[i].firstarc;//将边结点插入到Vi顶点节点的头部 
		G.vertices[i].firstarc=p2;
	}
	return OK;
}

6、主函数：

int main(){
	ALGraph G;
	CreateUDG(G);
	cout<<"您想要用邻接表创建的无向图如下："<<endl;//输出想要构造的无向图 
	for(int i=0;i<G.vexnum;i++){
		VNode temp = G.vertices[i];
	    ArcNode	*p = temp.firstarc;
		if(p==NULL){
			cout<<G.vertices[i].data<<endl; 
		}else{
		    cout<<G.vertices[i].data;
			while(p){ 
				cout<<"->";
				cout<<p->adjvex;
				p=p->nextarc; 
			}	
			cout<<endl;
		}
	}
	return 0; 
}

三：结果截图：

 注意：再找到某条边关联的两个顶点的位置后，需要创建两个新的边结点。创建新边结点的方式是ArcNode *p=new ArcNode;在这里*p代表的是这个新的边结点，而p代表的是指向这个边结点的指针。这里需要区别一下。

无向邻接ltxff算法链表图论c语言数据结构

有关图——邻接表法创建无向图算法。走起。。。。的更多相关文章

  1. ruby - 如何在 Ruby 中顺序创建 PI - 2

    出于纯粹的兴趣，我很好奇如何按顺序创建PI，而不是在过程结果之后生成数字，而是让数字在过程本身生成时显示。如果是这种情况，那么数字可以自行产生，我可以对以前看到的数字实现垃圾收集，从而创建一个无限系列。结果只是在Pi系列之后每秒生成一个数字。这是我通过互联网筛选的结果:这是流行的计算机友好算法，类机器算法:defarccot(x,unity)xpow=unity/xn=1sign=1sum=0loopdoterm=xpow/nbreakifterm==0sum+=sign*(xpow/n)xpow/=x*xn+=2sign=-signendsumenddefcalc_pi(digits

  2. python - 如何使用 Ruby 或 Python 创建一系列高音调和低音调的蜂鸣声？ - 2

    关闭。这个问题是opinion-based.它目前不接受答案。想要改进这个问题？更新问题，以便editingthispost可以用事实和引用来回答它.关闭4年前。Improvethisquestion我想在固定时间创建一系列低音和高音调的哔哔声。例如:在150毫秒时发出高音调的蜂鸣声在151毫秒时发出低音调的蜂鸣声200毫秒时发出低音调的蜂鸣声250毫秒的高音调蜂鸣声有没有办法在Ruby或Python中做到这一点？我真的不在乎输出编码是什么(.wav、.mp3、.ogg等等)，但我确实想创建一个输出文件。

  3. ruby - 使用 Vim Rails，您可以创建一个新的迁移文件并一次性打开它吗？ - 2

    使用带有Rails插件的vim，您可以创建一个迁移文件，然后一次性打开该文件吗？textmate也可以这样吗？ 最佳答案 你可以使用rails.vim然后做类似的事情::Rgeneratemigratonadd_foo_to_bar插件将打开迁移生成的文件，这正是您想要的。我不能代表textmate。 关于ruby-使用VimRails，您可以创建一个新的迁移文件并一次性打开它吗？，我们在StackOverflow上找到一个类似的问题： https://sta

  4. ruby-on-rails - 无法使用 Rails 3.2 创建插件？ - 2

    我对最新版本的Rails有疑问。我创建了一个新应用程序(railsnewMyProject)，但我没有脚本/生成，只有脚本/rails，当我输入ruby./script/railsgeneratepluginmy_plugin"Couldnotfindgeneratorplugin.".你知道如何生成插件模板吗？没有这个命令可以创建插件吗？PS:我正在使用Rails3.2.1和ruby​​1.8.7[universal-darwin11.0] 最佳答案 随着Rails3.2.0的发布，插件生成器已经被移除。查看变更日志here.现在

  5. ruby - 如何使用 RSpec::Core::RakeTask 创建 RSpec Rake 任务？ - 2

    如何使用RSpec::Core::RakeTask初始化RSpecRake任务？require'rspec/core/rake_task'RSpec::Core::RakeTask.newdo|t|#whatdoIputinhere?endInitialize函数记录在http://rubydoc.info/github/rspec/rspec-core/RSpec/Core/RakeTask#initialize-instance_method没有很好的记录；它只是说:-(RakeTask)initialize(*args,&task_block)AnewinstanceofRake

  6. ruby - 为什么 SecureRandom.uuid 创建一个唯一的字符串？ - 2

    关闭。这个问题需要detailsorclarity.它目前不接受答案。想改进这个问题吗？通过editingthispost添加细节并澄清问题.关闭8年前。Improvethisquestion为什么SecureRandom.uuid创建一个唯一的字符串？SecureRandom.uuid#=>"35cb4e30-54e1-49f9-b5ce-4134799eb2c0"SecureRandom.uuid方法创建的字符串从不重复？

  7. ruby - 有人可以帮助解释类创建的 post_initialize 回调吗 (Sandi Metz) - 2

    我正在阅读SandiMetz的POODR，并且遇到了一个我不太了解的编码原则。这是代码:classBicycleattr_reader:size,:chain,:tire_sizedefinitialize(args={})@size=args[:size]||1@chain=args[:chain]||2@tire_size=args[:tire_size]||3post_initialize(args)endendclassMountainBike此代码将为其各自的属性输出1,2,3,4,5。我不明白的是查找方法。当一辆山地自行车被实例化时，因为它没有自己的initialize方法

  8. ruby-on-rails - 如何在 Ruby on Rails 中实现无向图？ - 2

    我需要在RubyonRails中实现无向图G=(V,E)并考虑构建一个Vertex和一个Edge模型，其中Vertex有_多条边。由于边恰好连接两个顶点，您将如何在Rails中执行此操作？您是否知道任何有助于实现此类图表的gem或库(对重新发明轮子不感兴趣;-))？ 最佳答案 不知道有任何现有库在ActiveRecord之上提供图形逻辑。您可能必须实现自己的Vertex、EdgeActiveRecord支持的模型(请参阅Rails安装的rails/activerecord中的vertex.rb和edge.rb/test/fixtur

  9. ruby - 使用多个数组创建计数 - 2

    我正在尝试按0-9和a-z的顺序创建数字和字母列表。我有一组值value_array=['0','1','2','3','4','5','6','7','8','9','a','b'，'光盘'，'e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','','u','v','w','x','y','z']和一个组合列表的数组，按顺序，这些数字可以产生x个字符，比方说三个list_array=[]和一个当前字母和数字组合的数组(在将它插入列表数组之前我会把它变成一个字符串，]current_combo['0','0','0']

  10. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息，信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同，算法可以分为对称加密、非对称加密、对称加密和非

随机推荐