データ構造実験8図のエルゴード

一、実験の目的
図の2つの巡回方法を把握する:深さ優先検索図と広さ優先検索図.
二、実験内容
【図の深さ優先検索】ツリーの先の順序巡回と同様である.図の広さ優先検索は図のようなレベル巡回である.
まず隣接表を用いて図の格納構造を作成し、完全なプログラムを作成して図の深さ優先巡回と広さ優先検索を実現する.
三、ソースコード

/*********************************************/
/*            	 */
/*********************************************/

#include 
#include 
#include 
using namespace std;
#define M 20
int visited[M];					/*          */
typedef char DataType;  /*        */
typedef struct node{    /*    */
   int adjvex;                  /*   */
   struct node *next;
}EdgeNode;

typedef struct vnode{   /*     */
   DataType vertex;         /*    */
   EdgeNode *FirstEdge; /*       */
}VertexNode;

typedef struct{           /*     */
 VertexNode adjlist[M];  /*         */
 int n,e;                 /*        */
}LinkedGraph;
/*    ：       
      ：       g；         filename;      c，c=0       ，         
       ： 
*/
void creat(LinkedGraph *g,char *filename,int c)
    { int i,j,k;
      EdgeNode *s;
      FILE *fp;
      fp=fopen(filename,"r");
      if (fp)
      {
      fscanf(fp,"%d%d",&g->n,&g->e);              /*        */

      for(i=0;in;i++)
       {
            fscanf(fp,"%1s",&g->adjlist[i].vertex);    /*      */
            g->adjlist[i].FirstEdge=NULL;         /*      */
       }

      for(k=0;ke;k++)                     /*  e     */
        {
            fscanf(fp,"%d%d",&i,&j);                 /*     （i,j）*/
            s=(EdgeNode *)malloc(sizeof(EdgeNode));
            s->adjvex=j;                         /*      j*/
            s->next=g->adjlist[i].FirstEdge;
            g->adjlist[i].FirstEdge=s;           /*    *s    vi     */
            if (c==0)                            /*   */
            {
            s=(EdgeNode *)malloc(sizeof(EdgeNode));
            s->adjvex=i;                         /*      i*/
            s->next=g->adjlist[j].FirstEdge;
            g->adjlist[j].FirstEdge=s;           /*    *s    vj     */
			}
        }
    fclose(fp);
    }
    else
    g->n=0;
   }




/*         ，     */
/*********************************************/
void dfs(LinkedGraph g,int i)
{

    EdgeNode *p;
    printf("visit vertex: %c
",g.adjlist[i].vertex);
    visited[i]=1;
    p=g.adjlist[i].FirstEdge;
    while(p)
    {
        if(!visited[p->adjvex])
            dfs(g,p->adjvex);
        else p=p->next;
    }
}
/*********************************************/
/*    ：       
      ：     g
*/
void DfsTraverse(LinkedGraph g)
{  int i;
   for (i=0;iQ;
void bfs(LinkedGraph g, int i)
{ /*   i         g     */
    EdgeNode *p;
    visited[i]=1;
    printf("%d",i);
    p=g.adjlist[i].FirstEdge;
    while(p)
    {
        if(!visited[i]){
            printf("%d",i);
            Q.push(i);
        }
        p=p->next;
    }
    while(!Q.empty())
    {
        int u=Q.front();
        Q.pop();
        bfs(g,u);
    }
}
/*********************************************/
/*    ：       g
      ：   g
*/
int BfsTraverse(LinkedGraph g)
{  int i,count=0;
   for (i=0;i%d",p->adjvex);
            p=p->next;
        }
     printf("
");
   }
}
int main()
{ LinkedGraph g;
  creat(&g,"g11.txt",0);  	/*  g11.txt        */
  printf("
 The graph is:
");
  print(g);
  printf("
");
  DfsTraverse(g);
  printf("
");
  BfsTraverse(g);
  printf("
");
  return 0;
}