邻接矩阵存储方法实现图的存储与输出并输出图的深度优先搜索遍历序列

邻接矩阵存储方法实现图的存储与输出并输出图的深度优先搜索遍历序列

图的遍历是指从图中任一给定顶点出发，依次访问图中的其余顶点。如果给定的图是连通图，则从图中的任意一点出发，按照一个指定的顺序就可以访问到图中的所有顶点，且每个顶点只访问一次。这个过程称为图的遍历。
   图的遍历比树的遍历复杂的多。树是一种特殊类型的图，即无圈（无回路）连通图。树中的任意两个顶点间都有唯一的路径相通。在一个顶点被访问过之后，不可能又沿着另外一条路径访问到已被访问过的结点。而图中的顶点可能有边与其他任意顶点相连
。因此在访问了某个顶点之后，可能沿着另一条边访问已被访问过的顶点。例如图（a）中的g1，在访问了v1，v2和v3之后，有可能沿着边（v3，v1）访问到v1。为了避免一顶点被多次访问，可以设立一个集合visited，用来记录已被访问过的顶点。它的初值为空
集。一旦v1被访问过，即把v1加到集合visited中。图的遍厉通常有两种:图的深度优先
搜索和图的广度优先搜索。
1）图的深度优先搜索
   从图g=（v，e）的一个顶点v0出发，在访问了任意一个与v0相邻且未被访问过的顶点w1之后，再从w1出发，访问和w1相邻且未被访问过的顶点w2，然后再从w2出发进行如上所述访问，直到找到一个它相邻的结点，都被访问过的结点为止。然后退回到尚有相
邻结点未被访问过的顶点，再从该顶点出发，重复上述搜索过程，直到所有被访问过的顶点的邻接点都被访问过为止。图的这种遍历过程就称为图的深度优先搜索。例如从顶点v1出发对图3.3.5进行深度优先搜索，遍历的顺序为 v1,v2,v5,v10,v6,v7,v3,v12,v1
1,v8,v4,v9。（与邻接表中的邻接点排列顺序有关，即p->next.vertex=v2 or v3对遍历
顺序有影响 ）
 例25.(p194.c)图的深度优先搜索。从图g的顶点v0      
发进行深度优先搜索，打印出各个顶点的遍历顺序。  
 解：图的深度优先搜索法为：                    
（1）首先访问v0并把v0加到集合visited中；      
（2）找到与v0相邻的顶点w，若w未进入        
visited中，则以深度优先方法从w开始搜索。  
（3）重复过程（2）直到所有于v0相邻的顶点  
   都被访问过为止。                        

                                         
下面是对用邻接表表示的图g进行深度优先搜索的程序    
int rear=0;              
int visit[500];                                        
depth_first_search(g,v0)                      
graphptr g[ ];                    
int v0;  
{      
int w;                            
graphptr p;
visit [++rear]=v0;            
printf("%d\n",v0);                                              
p=g[v0];              
while (p!=null)                              
   {
   w=p->vertex ;
   if (!visited(w))
   depth_first_search(g,w);
   p=p->next;
   }
}
int  visited(w)
int  w ;
{
 int  i;
 for (i=1;i<=rear;i++)
  if (visit [ i ] == w) return(1);
return(0);              
}
2）图的广度优先搜索
  从图g的一个顶点v0出发，依次访问v0的邻接点k1,k2...kn。然后再顺序访问k1,k2...kn的所有尚未被访问过的邻接点。如此重复，直到图中的顶点都被访问过为止。图的这种搜索称为图的广度优先搜索。例如：从v1出发按广度优先搜索方法遍历图3.3.5,顶
点的访问顺序为v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12。
   图的广度优先搜索类似树的按层次遍历，需要有一个队列来存放还没
有来得及处理的顶点。图的广度优先搜索算法为：
 （1）首先把v0放入队列；
 （2）若队列为空则结束，否则取出队列的头v；
 （3）访问v并把所有与v相邻且未被访问的顶点插入队列；
 （4）重复（2）-（3）直到队列为空。
上述算法中所有已被访问过的顶点都放在队列中，因此只要检查某个顶点是否在队列中就可以判断出该顶点是否已被访问过。
   广度搜索法的程序如下：
broad_first_search(g,v0)  
graphptr g[ ];            
int v0;
{
int queue[500],front =1, tail=1,v;
graphptr p;
queue [tail]=v0;    
while (front <=tail)
 {
 v=queue[front++];
 printf("%d\n",v);  
 p=g[v];          
 while (p!=null)
    {
    v=p->vertex;  
    if (!visited(queue,tail,v))
    queue[++tail]=v;
     p=p-->next;
    }
 }
}
visited (q,tail,v)
int q[ ],tail,v;
{
int i;
for(i=1;i<=tail;i++)
return(0);
}

深度优先的非递归算法



nodetype stackmain,stacksec    
visit(p)
p->mark=true;
do
{
for(all v istheconnectnode of (g,p))//将当前点的邻接点中的所有结点压入副栈中
if(v.marked==false)
statcksec.push(v)
//将副栈中的点依次弹出，压入主栈中，这与非递归算法中使用队列的意图类似
while(!stacksec.isempty())
stackmain.push(statcksec.pop());
do//找出下一个未访问的结点或者没找到，直到栈为空
{
if(!stackmain.isempty())

{
p=stackmain.pop();

}
}while(p.marked==true&&!stackmain.isempty())
if(p.marked==false)//访问未访问结点.

{

      visit(p);

      p.marked=true;

}            

}while(!stackmain.isempty())