数据结构题。假定无向图G有6个结点和9条边，......(1) 画出G的邻接距阵和邻接表(2) 根据邻接表从顶点3

数据结构题。假定无向图G有6个结点和9条边，......(1) 画出G的邻接距阵和邻接表(2) 根据邻接表从顶点3

邻接矩阵
0 1 2 3 4 5
0 A A A A
1 A A
2 A A A A
3 A A
4 A A A A
5 A A
邻接表
0->1->2->4->5
1->0->2
2->1->3->4
3->2->4
4->0->2->3->5
5->0->4
深度优先算法
从图中某个顶点 V0 出发，访问此顶点，然后依次从 V0 的各个未被访问的邻接点出发深度优 先搜索遍历图，直至图中所有和 V0 有路径相通的顶点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
　　当以邻接表作存储结构时，深度优先搜索遍历图的时间复杂度为 O（n+e）。
执行结果：3，2，1，4，0，5
广度优先搜索
从图中的某个顶点 V0 出发，并在访问此顶点之后依次访问 V0 的所有未被访问过的邻接点，之 后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和 V0 有路径相通的顶点都 被访问到。若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上 述过程，直至图中所有顶点都被访问到为止。
执行结果：3，2，4，1，0，5

#include
#include
#include
#include
#define maxsize 64
#define TRUE 1
#define FALSE 0
#define  n  6
#define  e  9
typedef char datatype ;
typedef char vextype;typedef int adjtype;
 
typedef struct 
{
 vextype vexs[maxsize];
 adjtype arcs[maxsize][maxsize];}graph;
 
typedef struct 
{
 datatype data[maxsize];
 int front,rear;}sequeue;
 
typedef struct node 
{
 int adjvex;
 struct node *next;
}edgenode;
typedef struct
{
 vextype vertex;
 edgenode *link;}vexnode;
 
vexnode gl[maxsize];
graph  *ga;sequeue *Q;
 
graph *CREATGRAPH()
{
 int i,j,k;
 char ch;
 system("cls");
 scanf("%c",&ch);
 printf(" 请输入顶点信息(邻接矩阵):  ");
 for(i=1;i<=n;i++)
  scanf("%c",&ga->vexs[i]);
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
   ga->arcs[i][j]=0;
  printf(" 输入节点信息与权值： ");
  for(k=0;k  {
   scanf("%d%d",&i,&j);//读入一条变得两端顶点序号i,j及边上的权值
   ga->arcs[i][j]=1;
   ga->arcs[j][i]=1;
  }
  return ga;}
 
void PRINT()
{
 int i,j;
 system("cls");
 printf(" 对应的邻接矩阵是： ");
 for(i=1;i<=n;i++)
 {
  for(j=1;j<=n;j++)
   printf("%5d",ga->arcs[i][j]);
  printf(" ");
 }}
 
void CREATADJLIST()
{
 int i,j,k;
 edgenode *s;
 char ch;
 system("cls");
 printf("请输入顶点信息:  ");
 scanf("%c",&ch);
 for(i=1;i<=n;i++)
 { 
  gl[i].vertex=getchar();
  gl[i].link=NULL;
 }
 printf("输入边表节点信息： ");
 for(k=1;k<=e;k++)
 {
      scanf("%d %d",&i,&j);
      s=(edgenode *)malloc(sizeof(edgenode));
      s->adjvex=j;
      s->next=gl[i].link;
      gl[i].link=s;
      s=(edgenode *)malloc(sizeof(edgenode));
      s->adjvex=i;
      s->next=gl[j].link;
      gl[j].link=s;
    }}
 
void PRINTL()
{
 int i;
 edgenode *s;
 system("cls");
 printf(" 对应的邻接表是： ");
 for(i=1;i<=n;i++)
 {
   s=gl[i].link;   printf("%3c",gl[i].vertex);
 
   while(s!=NULL)
   {
  printf("%5d",s->adjvex);
  s=s->next;
   }
   printf(" ");
 }}
 
sequeue *SETNULL(sequeue *P)
{
 P->front=maxsize-1;
 P->rear=maxsize-1;
 return P;}
 
int EMPTY(sequeue *Q)
{
 if(Q->rear==Q->front)
  return TRUE;
 else
  return FALSE;}
 
sequeue *ENQUEUE(sequeue *Q,int k)
{
 if(Q->front==(Q->rear+1)%maxsize)
 {
  printf("队列已满! ");
  return NULL;
 }
 else
 {
  Q->rear=(Q->rear+1)%maxsize;
  Q->data[Q->rear]=k;
 }
 return Q;
}
int DEQUEUE(sequeue *Q)
{
 if(EMPTY(Q))
 {
  printf("队列为空，无法出队! ");
  return FALSE;
 }
 else
 {
  Q->front=(Q->front+1)%maxsize;
  return Q->data[Q->front];
 }
 return 1;
}
void BFS(int k)
{
  int i,j;
  int visited[maxsize]={0};
  printf(" 广度优先遍历后得到的序列是: ");
  Q=SETNULL(Q); 
  printf("%3c",ga->vexs[k]);
  visited[k]=TRUE;
  Q=ENQUEUE(Q,k);
  while(!EMPTY(Q))
  {
  i=DEQUEUE(Q);
  for(j=1;j<=n;j++)
  if((ga->arcs[i][j]==1)&&(!visited[j]))
    {
    printf("%3c",ga->vexs[j]);
     visited[j]=TRUE;
     Q=ENQUEUE(Q,j);
   }
 }
  printf(" 深度优先遍历后得到的序列是: ");
  }
 
void BFSL(int k)
{
   int i;
   int visited[maxsize]={0};
   edgenode *p;
   Q=SETNULL(Q); 
   printf(" 广度优先遍历后得到的序列是: ");
   printf("%3c",gl[k].vertex);
   visited[k]=TRUE;
   Q=ENQUEUE(Q,k);
   while(!EMPTY(Q))
   {
  i=DEQUEUE(Q);
  p=gl[i].link;
  while(p!=NULL)
  {
   if(!visited[p->adjvex])
   {
    printf("%3c",gl[p->adjvex].vertex);
              visited[p->adjvex]=TRUE;
              Q=ENQUEUE(Q,p->adjvex);
   }
   p=p->next; 
  }
 }
   printf(" 深度优先遍历后得到的序列是: ");}
 
void  DFS(int i)
{
   int j;
   static int visited[maxsize]={0};   
   printf("%3c",ga->vexs[i]);
   visited[i]=TRUE;
   for(j=1;j<=n;j++)
     if((ga->arcs[i][j]==1)&&(!visited[j]))
  DFS (j);
}
void DFSL(int k)
{
 int j;
 edgenode *p;
 static int visited[maxsize]={0}; 
 printf("%3c",gl[k].vertex);
 visited[k]=TRUE;
 p=gl[k].link; 
 while(p)
 {
  j=p->adjvex;
  if(!visited[j])
  DFSL(j);
  p=p->next;
 }
}
void main()
{
 int i,k;
 int ch;
 Q=malloc(sizeof(graph));
 ga=malloc(sizeof(graph));
 while(1)
 {
  printf(" ********************************************* ");
  printf(" 1.以邻接表遍历连通图 ");
  printf(" 2.以邻接矩阵遍历连通图 ");
  printf(" 3.退出程序 ");
  printf(" ********************************************* ");
  printf("输入你的选择: ");
  scanf("%d",&ch);
  switch(ch)
  {
  case 1: CREATADJLIST();
    PRINTL();
    printf("想从第几号结点开始: ");
    scanf("%d",&k);
    BFSL(k);
    DFSL(k);break;
  case 2: ga=CREATGRAPH();
    PRINT();
    printf("想从第几号结点开始: ");
    scanf("%d",&i);
    BFS(i);
    DFS(i);break;
  case 3:exit (0);
  }
 
}
}
 
 
 
 

PS:下标从1开始的，输入矩阵的对应元素时要按你的顺序输入  输入表的顺序是要逆序输入 否则两者答案不匹配 因为表的选择要有大小要求的 你可以试一下。
 
 

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息！