图的建立与深度优先搜索.txt

来自「其中一部分是自己写得,一部分是摘录的,希望站长能批准,我以后一定多多努力上传!」· 文本 代码 · 共 98 行

<graph.h>
typedef int arcinfo;
typedef int vexinfo;
#define MAX_V_N 20;
int visited[20];
typedef struct arcnode
{
 int adjvex;
 struct arcnode *nxtarc;
 arcinfo data;
}arcnode;
typedef struct vnode
{
 vexinfo data;
 arcnode *fstarc;
}vnode;
typedef struct
{
 vnode adjlist[20];/*?*/
 int vexnum,arcnum;
}ALG;
void cr_ALG(ALG *g)
{
 int i,head,tail;
 arcinfo info;
 arcnode *p;
 printf("enter the graphic's vertex number and arc number\n");
 scanf("%d%d",&(g->vexnum),&(g->arcnum));
 printf("%d",g->vexnum);
 printf("enter each vertex's data\n");
 for(i=0;i<(g->vexnum);++i)
 {
  scanf("%d",&((g->adjlist[i]).data));
  (g->adjlist[i]).fstarc=NULL;
 }
 printf("enter each arc's head,tail,and data\n");
 for(i=0;i<(g->arcnum);++i)
 {
  scanf("%d%d%d",&head,&tail,&info);
  p=(arcnode*)malloc(sizeof(arcnode));
  p->adjvex=tail;
  p->nxtarc=(g->adjlist[head]).fstarc;
  p->data=info;
  (g->adjlist[head]).fstarc=p;
 }
}
void tra_DFS(ALG *g)
{
 int i,j;
 for(i=0;i<g->vexnum;++i)
  visited[i]=0;
 for(j=0;j<g->vexnum;++j)
 {
 if(visited[j]==0)
  dfs(g,j);
 }
}
dfs(ALG *g, int i)
{
 int j;
 visited[i]=1;
 printf("%d",(g->adjlist[i]).data);
 printf("*");
 for(j=fstadjvex(g,i);j>=0;j=nxtadjvex(g,i,j))
 {
 if(visited[j]==0)
  dfs(g,j);
 }
}
int fstadjvex(ALG *g,int i)
{
 if(g->adjlist[i].fstarc==NULL)
   return(-1);
 else return ((g->adjlist[i]).fstarc)->adjvex;
}
int nxtadjvex(ALG *g,int i,int j)
{
 arcnode *temp;
 temp=(g->adjlist[i]).fstarc;
 while(temp->adjvex!=j)
 {
  temp=temp->nxtarc;
 }
 if(temp->nxtarc==NULL)
  return -1;
 else return temp->nxtarc->adjvex;
}

<graph.c>#include <stdio.h>
#include <graph.h>
void main()
{
 ALG *g;
 cr_ALG(g);
 tra_DFS(g);
 getchar();
}