tsdbl.c

对于一个给定的任意边数和顶点值的有向图或无向图

#include <stdio.h>
#define MAX_VERTEX_NUM 50
typedef struct arcnode{int adjvex;
                       struct arcnode *nextarc;}arcnode;
typedef struct vexnode{int vexdata;
                       arcnode *firstarc;
                       int tag;}vexnode;
vexnode adjlist[MAX_VERTEX_NUM];
void creatadjlist()/*利用邻接表生成图函数*/
{arcnode *ptr,*p;
 int vexnum,arcnum,k,v1,v2,i;
 printf("\nplease input dingdianshu and bianshu:\n");/*请求输入图中顶点数和边数*/
 scanf("%d,%d",&vexnum,&arcnum);
 for(k=1;k<=vexnum;k++)
  {adjlist[k].vexdata=k;
   adjlist[k].firstarc=NULL;}
for(k=1;k<=arcnum;k++)
 {printf("\nplease input dingdiandui:\n");/*请求输入图中各顶点对*/
  scanf("%d,%d",&v1,&v2);
  ptr=(arcnode *)malloc(sizeof(arcnode));
  ptr->nextarc=adjlist[v1].firstarc;
  ptr->adjvex=v2;
  adjlist[v1].firstarc=ptr;}
 for(i=1;i<=vexnum;i++)/*依次输出邻接表中各顶点*/
  {p=adjlist[i].firstarc;
   printf("\n%5d:",adjlist[i].vexdata);
   for(;p!=NULL;p=p->nextarc)
     printf("%5d",p->adjvex);
   printf("\n");}}
void dfs(int v)/*图的深度优先遍历函数*/
{int w;arcnode *ptr[100];
 printf("%5d",v);
 adjlist[v].tag=1;
 ptr[v]=adjlist[v].firstarc;
 while(ptr[v]!=NULL)
  {w=ptr[v]->adjvex;
   if(adjlist[w].tag==0)
     dfs(w);
  ptr[v]=ptr[v]->nextarc;
  }}
main()/*主函数*/
{int v;
 creatadjlist();/*调用邻接表生成图函数*/
 printf("\nplease input the first data:");/*请求输入深度优先遍历的起始出发点*/
 scanf("%d",&v);
 dfs(v);/*调用图的深度优先遍历函数*/
 }