发布时间 : 星期五 文章MATLAB程序大全 - 图文更新完毕开始阅读ee93ef4b03d276a20029bd64783e0912a3167c3b
☆★☆★☆
matlab代码如下，netplot函数在这里，不过当时函数中表示两节点没有路径用的是0，而现在需要改成inf：
clear all;close all;clc %初始化邻接压缩表 b=[1 2 6; 1 4 7 2 3 5; 2 4 8; 2 5 -4; 3 2 -2; 4 3 -3; 4 5 9; 5 1 2; 5 3 7];
m=max(max(b(:,1:2))); %压缩表中最大值就是邻接矩阵的宽与高 A=compresstable2matrix(b); %从邻接压缩表构造图的矩阵表示 netplot(A,1) %形象表示
S=inf(1,m); %源到其他节点的最短距离，开始为inf S(1)=0; %源点到自己的距离为0 pa=zeros(1,m); %寻找到的节点的前趋 pa(1)=1; %源点的前趋是自己
pre_pa=ones(1,m);
while sum(pre_pa==pa)~=m %终止条件，判断终止的方法很多，这个应该不是最佳实践 pre_pa=pa; for k=1:m
☆★☆★☆
if pre_pa(k)~=0 %对每一个已搜寻到的节点，从此节点寻找后继节点
i=k; for j=1:m
if A(i,j)~=inf
if S(j)>S(i)+A(i,j)
S(j)=S(i)+A(i,j); %边缘松弛，取两节点间最小权值作为实际权值
pa(j)=i; %寻找前趋 end end end end end end
%最终我们需要的就是这两个值
S %源点到其他每一点的距离 pa %其他每一节点的前趋
%算法到此结束，下面只是为了形象的表示而写的。 re=[]; for i=2:m
re=[re;pa(i) i A(pa(i),i)]; end
A=compresstable2matrix(re); %从邻接压缩表构造图的矩阵表示 figure;
netplot(A,1) %形象表示
compresstable2matrix.m
function A=compresstable2matrix(b) [n ~]=size(b);
m=max(max(b(:,1:2))); A=inf(m,m);
for i=1:n
A(b(i,1),b(i,2))=b(i,3); end end
☆★☆★☆
11.
如此经典的算法竟一直没有单独的实现过，真是遗憾啊。
广度优先搜索在过去实现的二值图像连通区域标记和prim最小生成树算法时已经无意识的用到了，深度优先搜索倒是没用过。
这次单独的将两个算法实现出来，因为算法本身和图像没什么关系，所以更纯粹些。
广度优先搜索是从某一节点开始，搜索与其线连接的所有节点，按照广度方向像外扩展，直到不重复遍历所有节点。
深度优先搜索是从某一节点开始，沿着其搜索到的第一个节点不断深入下去，当无法再深入的时候，回溯节点，然后再在回溯中的某一节点开始沿另一个方向深度搜索，直到不重复的遍历所有节点。
广度优先搜索用的是队列作为临时节点存放处；深度优先搜索可以递归实现（算法导论就是用递归实现的伪代码），不过我这里是用栈作为临时节点存放处。
感觉也没什么好介绍的了，抄算法导论上的介绍也没什么意思，所有的内容都是书上的，真正学东西还是要看书。 下面是运行结果： 原连通图：
广度优先搜索：
☆★☆★☆
深度优先搜索：
matlab代码如下，其中的画图函数netplot.m。 BFS.m
clear all;close all;clc %初始化邻接压缩表 b=[1 2;1 3;1 4;2 4; 2 5;3 6;4 6;4 7];
m=max(b(:)); %压缩表中最大值就是邻接矩阵的宽与高 A=compresstable2matrix(b); %从邻接压缩表构造图的矩阵表示 netplot(A,1) %形象表示
head=1; %队列头
tail=1; %队列尾，开始队列为空，tail==head queue(head)=1; %向头中加入图第一个节点 head=head+1; %队列扩展
flag=1; %标记某个节点是否访问过了 re=[]; %最终结果
while tail~=head %判断队列是否为空 i=queue(tail); %取队尾节点 for j=1:m
if A(i,j)==1 && isempty(find(flag==j,1)) %如果节点相连并且没有访问过
queue(head)=j; %新节点入列 head=head+1; %扩展队列
flag=[flag j]; %对新节点进行标记 re=[re;i j]; %将边存入结果 end end