shengdubianli.cpp

1.首先选定图的类别（有向图、无向图）

#include <stdio.h>
#include <malloc.h>
#include<conio.h>
#define MAX 30
typedef struct node{
int vno;
struct node *next;
}EdgeNode;
typedef EdgeNode *LGraph[MAX];
typedef  int MGraph[MAX][MAX];
int visited[MAX];
int queue[MAX];
int creat_Graph(LGraph lg,MGraph mg)
{
int vn,en,k,i,j;
EdgeNode *p;
printf("\n邻接表表达式建图:\n") ;
while(1)
{
 vn=en=0;
 printf("输入图的顶点数[1-30]\n");
 fflush(stdin);
 scanf("%d",&vn);
 if(vn<1||vn>30)
 continue;
 printf("输入图的边数[0-%d]\n",vn*(vn-1)/2);
 scanf("%d",&en);
 if(en>=0&&en<=vn*(vn-1)/2)
 break;
 }
 for(k=0;k<vn;k++)
 lg[k]=NULL;
  for(k=0;k<vn;k++)
  for(i=0;i<vn;i++)
  mg[k][i]=0;
  for(k=0;k<en;){
  i=j=-1;
  printf("输入第[%d]对相连的两个顶点[1-%d]:",k+1,vn);
  scanf("%d%d",&i,&j );
  if(i<1||j<1||i>vn||j>vn){
  printf("输入错误,边范围为[1-%d]\n",vn);
  continue;
  }
  k++;
  i--;
  j--;
  p=(EdgeNode *)malloc(sizeof(EdgeNode) );
  p->vno=j;
  p->next=lg[i];
  lg[i]=p;
  p=(EdgeNode *)malloc(sizeof(EdgeNode) );
  p->vno=i;
  p->next=lg[j];
  lg[j]=p;
  mg[i][j]=mg[j][i]=1;
  }
  return vn;
  }
  void LDFS(LGraph g,int i)
  {
   EdgeNode *t;
   printf("%4d",i+1);
   visited[i]=1;
   t=g[i];
   while(t!=NULL){
   if(visited[t->vno]==0)
   LDFS(g,t->vno);
   t=t->next;
   }
   }

    void main()
    {
    LGraph lg;
    MGraph mg;
    int n,i;
    n=creat_Graph(lg,mg);
    for(i=0;i<n;i++)
    visited[i]=0;
    printf("\n邻接表表示的图的递归深度优先遍历\n");
    LDFS(lg,0);
   getch();
  
    }