访问广度：(定义 详解)

广度优先搜索(广度优先搜索 常用算法——广度优先搜索 算法过程)

访问广度：

定义

广告受众通过任何路径访问目标网站页面时达到的频道分类的广度，也可以说从一个访问目标到达别的目标的途径的多少。是网站或者电视广告的的一种术语。

详解

一般而言，一个在线网站流量分析系统，主要会研究访客数、访客的来源、访客地域、停留时长、访客深度。

访客深度被广泛的应用，也可以解释为二跳（率）、三跳......。一般而言主要指访客的忠诚度，是广告效果的主要判断依据之一。

访问广度是相对于访客深度而言，上海传漾科技率先提出和应用的评估指标。为广告主从多个维度高效评估广告效果的评估指标之一。通过对访客在网站的停留时长、访客广度、访客深度三个核心指标，辅以显示/点击监测，持续效果清洗/分析，为广告主全面评判广告提供高效直观的评估体系。

广度优先搜索

广度优先搜索

广度优先搜索算法（Breadth-First-Search），又译作宽度优先搜索，或横向优先搜索，简称BFS，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。

常用算法——广度优先搜索

在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索， 本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生 的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。英语中用Breadth-First-Search表示，所以我们 也把广度优先搜索法简称为BFS。

1、广度优先搜索的基本思想

从图中某一顶点Vo出发，首先访问Vo相邻的所有未被访问过的顶点V1、V2、……Vt；再依次访问与V1、V2、……Vt相邻的且未被访问过的所有顶点。如此继续，直到访问完图中所有的顶点。

如果用广度优先法对下图中结点进行搜索，从结点V1出发，先搜索处理 它的子结点V2和V3，即深度为2的结点；然后搜索深度为3的子结点V4、V5、V6、V7；最后搜索深度为4的 结点V8和V9。整个搜索的次序与结点产生的次序完全一致。

深度

__V1__ 1

/ \\

V2 V3 2

/ \\ / \\

V4 V5 V6 V7 3

/ \\

V8 V9 4

2.广度优先搜索基本算法：

1）从某个顶点出发开始访问，被访问的顶点作相应的标记，并输出访问顶点号；

2）从被访问的顶点出发，依次搜索与该顶点有边的关联的所有未被访问的邻接点，并作相应的标记。

3）再依次根据2）中所有被访问的邻接点，访问与这些邻接点相关的所有未被访问的邻接点，直到所有顶点被访问为止。

算法过程

procedure guangdu(i);

begin

write(i);

v[i]:=true;

insert(q,i);{q是队列，i进队}

repeat

k:=delete(q)；{出队}

for j:=1 to n do

if (a[k,j]=1) and (not v[j]) then

begin

write(j);

v[j]:=true;

insert(q,j);

end;

until 队列q为空;

【实际应用】：实际应用的算法流程图通常如下：

【问题描述】如下图，找出C1到C6的一条最短路径并求出其路程总长度(采用广度优先搜索的顶点访问序列为C1,C2,C3,C4,C5,C6)。

【Pascal程序】

program tu3bfs;

type fg=set of 1..6;

const link:array[1..5,1..6] of integer=((0,4,8,0,0,0),

(4,0,3,4,6,0),(8,3,0,2,2,0),(0,4,2,0,4,9),(0,6,2,4,0,4));

var pnt,city:array[1..10] of 0..6;

flag:fg;

r,k,head,tail:integer;

procedure print;

var n, i,cost,y:integer;

s:array[1..7] of 1..6;

begin

y:=tail;n:=0; cost:=0;

while y>0 do begin inc(n);s[n]:=y;y:=pnt[y] end;

writeln('minpath=',n-1);

write('1');

for i:=n-1 downto 1 do

begin

write('->',s[i]);

cost:=cost+link[s[i+1],s[i]];

end;

writeln;

writeln('cost=',cost);

end;

begin

flag:=[1];

pnt[1]:=0; city[1]:=1;

head:=0;tail:=1;

repeat

head:=head+1;

k:=city[head];

for r:=2 to 6 do

if not(r in flag) and (link[k,r]>0) then

begin

inc(tail);city[tail]:=r;

pnt[tail]:=head;

flag:=flag+[r];

if r=6 then begin print;halt end;

end;

until head>=tail;

readln;

end.