13518219792
图的遍历
创新互联建站从2013年成立，先为岷县等服务建站，岷县等地企业，进行企业商务咨询服务。为岷县企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。
从图中某一顶点出发访遍图中其余顶点，且使每一顶点仅被访问一次。这一过程叫做图的遍历。
遍历图的基本方法有两种：深度优先搜索和广度优先搜索。这两种方法都适用于有向图和无向图。
和树的遍历类似，图的遍历也是从某个顶点出发，沿着，某条边搜索路径对图中所有顶点各作一次访问。若给定的图是连通图，则从图中任意顶点出发顺着边可以访问到该图中所有的顶点，然而，图的遍历比树的遍历复杂得多，这是因为图中的任一点都可能和其余顶点相邻接，故在访问了某个顶点之后，可能顺着某条回路又到了该顶点。为了避免重复访问同一个顶点，必须记住每个顶点是否被访问过。为此，可设置一个布尔向量visited[1..n],它的初值为false，一旦访问了顶点vi，便将visited[i]置为ture。
一、连通图的深度优先搜索
连通图深度优先搜索的基本思想如下：假定图中某个顶点v1为出发点，首先访问出发点v1，然后任选一个v1的访问过的邻接点v2，以v2为新的出发点继续进行深度优先搜索，直至图中所有顶点被访问过。
显然，图的深度优先搜索是一个递归过程，类似于树的前序遍历，它的特点是尽可能先对纵深方向进行搜索，故称之深度优先搜索。
现以图5-10中G为例说明深度优搜索过程。假定v1是出发点，首先访问v1。因v1有两个邻接点v2、v3均未被访问，选择v2作为新的出发点。访问v2之后，再找v2的未访问过的邻接点。同v2邻接的有v1、v4、v5，其中v1以被访问过，而v4、v5未被访问。选择v4作为新的出发点。重复上述搜索过程继续依次访问v8、v5。访问v5之后，由于与v5相邻的顶点均以被访问，搜索退回到v8。由于v8、v4、v2都没有未被访问的邻接点，所以搜索过程连续地从v8退回到v4，再退回到v2最后退回到v1这时选择v1的未被访问过的邻接点v3，继续往下搜索，依次访问v3、v6、v7，从而遍历了图中全部顶点。在这个过程中得到的顶点的访问序列：
(a)无向图G
(b)G的深度优先搜索过程
图5-10a 深度优先搜索过程示例
v1→v2→v4→v8→v5→v3→v6→v7
这样的序列就称之为图的深度优先搜索遍历序列。
连通图的深度优先搜索的非形式算法如下:
procedure dfs (g:graph;v1:integer);
//从v1出发深度优先遍历图g//
begin write(v1);
visited[v1]:=ture;
找出g中v1的第一邻接点w;
while w存在do
[ if w 未被访问 then dfs(g,w);
w:=g中v1的下一邻接点]
end;
上述非行式算法未涉及图的存储结构.图的遍历过程必然地包含对图中每个顶点查找其邻接点这一操作;而在图的不同存储结构上查找邻接点的方法是不同的.
若以邻接表为存储结构,查找邻接点操作实际上是顺序查找链表.邻接表上的深度优先算法如下:
procedure dfs(g:adj_list;v1:integer);
//从v1出发深度优先遍历图g.g以邻接表为存储结构//
begin write(v1);
visited[v1]:=ture;//标志v1已访问//
p=g[v1].link;//找v1的第一个邻接点//
while pnil do
[ if not (visited[p↑.adjvex]);//书错写成vertex//
then dfs(g,p↑.adjvex);
p:=p↑.next]//回溯----找v1的下一个邻接点//
end;
二、连通图的广度优先搜索
连通图广度优先搜索的基本思想是：从图中某个顶点v1出发，访问了v1之后依次访问v1的所有邻接点；然后分别从这些邻接点出发按深度优先搜索遍历图的其它顶点，直至所有顶点都被访问到。它类似于树的按层次遍历，其特点是尽可能优先对横向搜索，故称之为广度优先搜索。
下面以图5-10中G为例说明广度优先搜索的过程。首先从起点v1出发，访问v1。v1有两个未曾访问的邻接点v2和v3。先访问v2，再访问v3。然后再先后访问v2的未曾访问过的邻接点v4、v5及v3的未曾访问过的邻接点v6、v7。最后访问v4的未曾访问过的邻接点v8。至此图中所有顶点均以被访问到。得到的顶点访问序列为：
(a)无向图G
(b)G的广度优先搜索过程
图5-10b 广度优先搜索过程示例
v1→v2→v3→v4→v5→v6→v7→v8
相应的，这样的序列就称之为图的广度优先搜索遍历序列。
在广度优先搜索中，若对x的访问先于y，则对x邻接点的访问也先于队y的邻接点的访问。因此，可采用队列来暂存那些刚访问过，但可能还有为访问过的邻接点的顶点。
连通图的广度优先搜索算法如下：
procedure bfs(g:adj_list;v1:integer);//书错写成adjlist//
//以邻接表为存储结构的广度优先搜索。Q为队列，假定visited的各分量已只置 为false//
begin init_linkedque(Q);//设计一个空队Q//
visited[v1]:=ture;write(v1);
in_limkedque(Q,v1); //v1入队//
while not empty(Q) do
[ v:=out_linkedque(Q);
p:=adj_list[v].link;//书错写成adjlist//
while pnil do
[ if visited[p↑.adjvex]:=false;//书错写成vertex//
then
[visited[p↑.adjvex]:=ture;
with(p↑.adjvex);
in_linkedque(Q,p↑.adjvex);]
p:=p↑.next]]
end;
三、图的连通分量计算
如果要遍历一个非连通图，则需要多次调用dfs或bfs，每一次都要得到一个连通分量；调用dfs或bfs的次数就是连通分量的个数。因此很容易写出非连通图的遍历算法和计算一个图的连通分量得算法。下面给出的是以邻接表为存储结构，通过调用深度优先搜索算法实现的计算连通分量的算法。
procedue conn_component (var g:graph;
var visited:array[1..vnum);
begin for v:=1 to vnum do
visited[v]:flase;
count:=0;
for v:=1 to vnum do
if not(visited[v])then
[count:=count+1;
write('component',count,':');
dfs(g,v);writeln;]
end;
对于图5-5中非连通图G3，用上述算法可求出3个连通分量，各连通分量所含顶点如下：
component1: 1 2 3
component2: 4 5 6 7
component3: 8 9
注意，若从上述算法中删去有关连通分量计数器的操作，就得到一个非连通图德遍历算法。
详细资料和图片请参看参考资料，那里的比较详细
#includeiostream
using namespace std;
#define MAX_VERTEX_NUM 20
bool visited[MAX_VERTEX_NUM];
struct Graph //无向图
{
char vex[MAX_VERTEX_NUM];
int vexnum,arcnum;
int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//1表示相邻，0表示不相邻
};
struct QNode
{
int data;
QNode *next;
};
struct LinkQueue
{
QNode *front;
QNode *rear;
};
int (*VisitFunc)(Graph G,int v);
int LocateVex(Graph G,char v) //返回顶点所在位置
{
int i;
for(i=0;iG.vexnum;i++)
if(v==G.vex [i]) return i;
return 0;
}
int CreateGraph(Graph G) //创建无向图
{
cout"输入顶点数和边数："endl;
cinG.vexnum G.arcnum ;
int i;
cout"输入顶点字符"endl;
for(i=0;iG.vexnum ;i++)
{
cinG.vex[i];
}
int j;
for(i=0;iG.vexnum;i++)
for(j=0;jG.vexnum;j++)
G.arc[i][j]=0;
char v1,v2;
int k;
cout"输入相邻的两顶点"endl;
for(k=0;kG.arcnum;k++)
{
cinv1v2;
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arc[i][j]=1;
G.arc[j][i]=1;
}
return 0;
}
int Visit(Graph G,int v)//访问顶点
{
coutG.vex[v]" ";
return 1;
}
int FirstAdjVex(Graph G,int v) //v的第一个邻接点
{
int j;
for(j=v+1;jG.vexnum;j++)
{
if(G.arc[v][j]==1) return j;
}
return 0;
}
int NextAdjVex(Graph G,int v,int w)//v的下一个邻接点
{
int j;
for(j=w+1;jG.vexnum ;j++)
{
if(G.arc[v][j]==1) return j;
}
return 0;
}
void DFS(Graph G,int v)
{
visited[v]=true;
VisitFunc(G,v);
int w;
for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))
if(!visited[w]) DFS(G,w);
}
void DFSTraverse(Graph G,int(*Visit)(Graph G,int v))//深度优先搜索
{
VisitFunc=Visit;
int v;
for(v=0;vG.vexnum;v++)
visited[v]=false;
for(v=0;vG.vexnum;v++)
{
if(!visited[v]) DFS(G,v);
}
}
int InitQueue(LinkQueue Q) //初始化队列
{
Q.front =Q.rear=new QNode;
if(!Q.front)return 0;
return 1;
}
int EnQueue(LinkQueue Q,int v)//入队列
{
QNode *p=new QNode;
if(!p) return 0;
p-data =v;
p-next =NULL;
Q.rear-next =p;
Q.rear=p;
return 1;
}
int DeQueue(LinkQueue Q,int v)//出队列
{
if(Q.front ==Q.rear ) return 0;
QNode *p=Q.front -next ;
v=p-data ;
Q.front -next =p-next ;
if(Q.rear ==p)Q.rear =Q.front;
delete p;
return 1;
}
bool QueueEmpty(LinkQueue Q)//队列是否为空
{
if(Q.front ==Q.rear ) return true;
return false;
}
void BFSTraverse(Graph G,int (*Visit)(Graph G,int v))//广度优先搜索
{
int v;
int w,u;
for(v=0;vG.vexnum ;v++) visited[v]=false;
LinkQueue Q;
InitQueue(Q);
for(v=0;vG.vexnum;v++)
if(!visited[v]){
visited[v]=true;
Visit(G,v);
EnQueue(Q,v);
while(!QueueEmpty(Q)){
DeQueue(Q,u);
for(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))
{
if(!visited[w])
{
visited[w]=true;
Visit(G,w);
EnQueue(Q,w);
}
}
}
}
}
int main()
{
Graph G;
CreateGraph(G);
/*
for(int i=0;iG.vexnum ;i++)
{
for(int j=0;jG.vexnum ;j++)
coutG.arc [i][j]" ";
coutendl;
}
*/
cout"深度优先搜索\n";
DFSTraverse(G,Visit);
cout"\n广度优先搜索\n";
BFSTraverse(G,Visit);
return 0;
}
问题很简单：
1.首先，你的数据源是数组，那么要想对每一个值作操作，必须遍历，所以就有如下代码：
for(int i=0;iA.length;i++){
...
}
2.在循环当中，数组中的每一个正在遍历的元素，就是：A[i];
3.String是java的一个字符串处理类，他有一个非常好用的方法就是，
public boolean startsWith(String prefix)，测试此字符串是否以指定的前缀开始。 所以：A[i].startsWith("C")如果返回true，那么他就是以C开头的。
4.综上所述，实现很简单，完成代码如下：
public class Test{
public static void main(String[] args){
String[] A ={"CSDF","FDS","CFDSA","DFS","FET"};
for(int i=0;iA.length;i++){
if(A[i].startsWith("C")){
System.out.println(A[i]);
}
}
}
}
总结：
临时写的，代码没有经过测试，但敢保证其正确性的几率很大，祝你成功。
首先这是一个无向图，用邻接表存储的顶点是无向图中顶点的2倍， 边自然也是二倍。但是这里为什么判断的时候顶点数没有乘以二而边数乘以二了呢？仔细看DFS深度遍历代码，while中有一个判断该顶点是否已遍历的语句，如果遍历过，则不执行递归，这就是为什么顶点数没有乘以二的原因；再说边数为什么要乘以二，还是看while中的循环，注意这条语句Enum++是在if判断的前面，也就是说不管这个顶点是否已遍历过，边数总要加一，这就导致重复遍历了边，这就是边数要乘以二的原因了。纯自己思考的，如有错误还望指正！
