dsf.c

无向图的深度优先搜索算法/c语言实现 其中图采用邻接矩阵存储

#include <stdio.h> 
#include <malloc.h> 
  
#define INFINITY 0
#define MAX_VEX 20 /*最大顶点个数 */
  
int visited[20];  /*访问标志数组 */
  
/*图的领结矩阵存储结构*/
typedef struct{ 
  char *vexs; /*顶点向量*/
  int arcs[MAX_VEX][MAX_VEX]; /*邻接矩阵*/
  int vexnum,arcnum; /*图的当前顶点数和弧数*/
}Graph; 
  
  
/*图G中查找元素C的位置*/
int Locate(Graph G,char c){ 
   int i;
  for(i=0;i<G.vexnum;i++)
  if(G.vexs[i]==c) return i; 
  return -1; 
} 
  
/*创建无向网*/
Graph CreateUDN(Graph G){
  int i,j,s1,s2; 
  char a,b,temp; 
  printf("请输入顶点数和弧数:"); 
  scanf("%d %d",&G.vexnum,&G.arcnum); 
  temp=getchar(); /*接收回车*/
  G.vexs=(char *)malloc(G.vexnum*sizeof(char)); /*分配顶点数目 */
  
  printf("输入%d个顶点.\n",G.vexnum); 
  for(i=0;i<G.vexnum;i++){ /*初始话顶点*/
    printf("输入顶点%d:",i); 
    scanf("%c",&G.vexs[i]); 
    temp=getchar(); /*接收回车*/
  } 
  printf("\n");
  for(i=0;i<G.vexnum;i++)
     printf("%c ",G.vexs[i]);
  printf("\n");   
  for(i=0;i<G.vexnum;i++) /*初始邻接矩阵*/
    for(j=0;j<G.vexnum;j++) 
      G.arcs[i][j]=INFINITY; 
  
  printf("输入%d条弧.\n",G.arcnum); 
  for(i=0;i<G.arcnum;i++){ /*初始化弧*/
    printf("输入弧%d:",i); 
    scanf("%c %c",&a,&b); /*输入一条边依附的顶点和权值 */
    temp=getchar(); /*接收回车 */
    s1=Locate(G,a); 
    s2=Locate(G,b); 
    G.arcs[s1][s2]=G.arcs[s2][s1]=1; 
  } 
  return G;
} 
  
/*图G中顶点K的第一个邻接矩阵*/
int FirstVex(Graph G,int k){ 
	int i;
  if(k>=0 && k<G.vexnum){ /*k合理 */
    for(i=0;i<G.vexnum;i++) 
      if(G.arcs[k][i]!=INFINITY) return i; 
  } 
  return -1; 
} 
  
/*图G中顶点i的j个邻接顶点的下一个邻接顶点 */
int NextVex(Graph G,int i,int j){ 
    int k;
  if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum){ /*i,j合理 */
    for(k=j+1;k<G.vexnum;k++) 
      if(G.arcs[i][k]!=INFINITY) return k; 
  } 
  return -1; 
} 
 void DSF(Graph G,int v){
 	  int w;
 	  visited[v]=1;
 	  printf("%c ",G.vexs[v]);
 	  for(w=FirstVex(G,v);w>=0;w=NextVex(G,v,w)){
 	  	 if(!visited[w]) 
 	  	    DSF(G,w);
 	  	}
 	}
 void DSFT(Graph G){
 	int i; 
 	//printf("%d",G.vexnum);
 	for(i=0;i<G.vexnum;i++)
 	  visited[i]=0;
 	// printf("HJJK"); 
 	for(i=0;i<G.vexnum;i++)
 	  if(!visited[i])
 	    DSF(G,i);	  
 }
/*主函数*/
void main(){ 
  //int i; 
  Graph G; 
  G=CreateUDN(G); 
  //visited=(bool *)malloc(G.vexnum*sizeof(bool));  
  printf("\n深度优先遍历: "); 
 // for(i=0;i<G.vexnum;i++) 
 // visited[i]=0; 
  fflush(stdin);
  DSFT(G); 
  printf("\n程序结束.\n"); 
}