数学建模-Matlab学习笔记（十四）图论算法

本文最后更新于：December 3, 2021 pm

MATLAB（矩阵实验室）是第四代高层次的编程语言和交互式环境数值计算，可视化和编程。由美国MathWorks公司开发的一种编程语言。用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，主要包括MATLAB和Simulink两大部分。拥有众多的内置命令和数学函数，可以帮助您在数学计算，绘图和执行数值计算方法。

目录

一.可达矩阵算法

1
2
3
4
5
6
7
8
function p=dgraf(A)
	n=size(A,1);
	p=A;
		for i=2:n
			p=p+A^i;
		end
	p(p~=0)=1;
	p;

二.关联矩阵和临接矩阵互换算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
function w=incandadf(F,f)
	if f==0
		m=sum(sum(F))/2;
		n=size(F,1);
		w=zeros(n,m);
		k=1;
			for i=1:n
				for j=i:n
					if F(i,j)~=0
						w(i,k)=1;
						w(j,k)=1;
						k=k+1;
					end
				end
			end
	elseif f==1
		m=size(F,2);
		n=size(F,1);
		w=zeros(n,n);
		for i=1:m
			a=find(F(:,i)~=0);
			w(a(1),a(2))=1;
			w(a(2),a(1))=1;
		end
	else
			fprint('please input the right value of f');
	end
w;

三.有向图关联矩阵和临接矩阵互换算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
function w=mattransf(F,f)
	if f==0
		m=sum(sum(F));
		n=size(F,1);
		w=zeros(n,m);
		k=1;
		for i=1:n
			for j=i:n
				if F(i,j)~=0
					w(i,k)=1;
					w(j,k)=-1;
					k=k+1;
				end
			end
		end
	elseif f==1
		m=size(F,2);
		n=size(F,1);
		w=zeros(n,n);
		for i=1:m
			a=find(F(:,i)~=0);
			if F(a(1),i)==1
				w(a(1),a(2))=1;
			else
				w(a(2),a(1))=1;
			end
		end
	else
		fprint('please input the right value of f');
	end
	w;

四.最短路

4.1 Dijkstra（两点间距离）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function [l,z]=Dijkstra(w)
	n=size(w,1);
	for i=1:n
		l(i)=w(1,i);
		z(i)=0;
	end
	i=1;
	while i<=n
		for j=1:n
			if l(i)>l(j)+w(j,i)
				l(i)=l(j)+w(j,i);
				z(i)=j-1;
				if j<i
				i=j-1;
				end
			end
		end
		i=i+1;
	end

4.2 Floyd（任意两点间距离）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function [d,r]=floyd(a)
	n=size(a,1);
	d=a;
	for i=1:n
		for j=1:n
			r(i,j)=j;
		end
	end
	r;
	for k=1:n
		for i=1:n
			for j=1:n
				if d(i,k)+d(k,j)<d(i,j)
					d(i,j)=d(i,k)+d(k,j);
					r(i,j)=r(i,k);
				end
			end
		end
	end