shu.txt

作为小镇网络建设

#include<stdio.h>

typedef struct maxtine
{
   int ju[100][100];
}


#include <stdio.h>
#include <string.h>

#define N 500

void main()
{
	int m,k,i,j,c[N],t[N][N],l;
	scanf("%d",&m);
		for (i=0;i<m;i++)
			for (j=0;j<m;j++) scanf("%d",&t[i][j]);
		k=0;
		l=0;
		for(j=0;j<m;j++) if (j!=0) c[j]=t[k][j];
		c[k]=0;
		for (i=1;i<m;i++)
		{
			k=0;
			while(c[k]==0) k++;
			for (j=1;j<m;j++) if (c[j]>0 && c[j]<c[k]) k=j;
			l+=c[k];
			c[k]=0;
			for(j=0;j<m;j++) if (t[k][j]<c[j]) c[j]=t[k][j];
		}
		printf ("%d\n",l);
	getchar();
	getchar();
}

main()
{ 
   int n,k,i,j;
   
   scanf("%n",&n);
   
   for(i=0;i<n;i++)
      for(j=0;j<n;j++)
         scanf("%n",&ju[i][j]);
      

}





#include   <stdio.h> 
#include   <stdlib.h> 
#define   maxlen   10 
#define   large   999 
#define   null   0 
typedef   struct 
{   int   a[maxlen],b[maxlen],w[maxlen]; 
    char   vexs[maxlen]; 
    int   vexnum,arcnum; 
    int   arcs[maxlen][maxlen]; 
}graph; 
graph   g; 

void   print_graph(graph   g) 
{   
int   i,j; 
printf( "邻接矩阵:\n "); 
printf( "vertex\t "); 
for(i=0;i <g.vexnum;i++) 
printf( "%4c ",g.vexs[i]); 
printf( "\n "); 
        for(i=0;i <g.vexnum;i++) 
{ 
printf( "%4c\t ",g.vexs[i]); 
for(j=0;j <g.vexnum;j++) 
printf( "%4d ",g.arcs[i][j]); 
printf( "\n "); 
} 
} 
graph   cre_grah(graph   g) 
{ 
int   i,j,k,c=999; 
for(i=0;i <g.vexnum;i++) 
for(j=0;j <g.vexnum;j++) 
g.arcs[i][j]=c; 
for(k=0;k <g.arcnum;k++) 
{ 
g.arcs[g.a[k]][g.b[k]]=g.w[k]; 
g.arcs[g.b[k]][g.a[k]]=g.w[k]; 
} 
print_graph(g); 
return   g; 
} 

void   prim(graph   g) 
{   int   i,j,k,min; 
    int   lowcost[maxlen]; 
    int   closet[maxlen]; 
    printf( "最小生成树的边为：\n "); 
    for(i=1;i <g.vexnum;i++) 
    { 
    lowcost[i]=g.arcs[0][i]; 
    closet[i]=1; 
    } 
    closet[1]=0; 
    j=1; 
    for(i=1;i <g.vexnum;i++) 
    { 
    min=lowcost[j]; 
    k=i; 
    for(j=1;j <g.vexnum;j++) 
    if(lowcost[j] <min&&closet[j]!=0) 
    {   min=lowcost[j]; 
    k=j;} 
    printf( "(%c,%c), ",g.vexs[closet[k]],g.vexs[k]); 
    closet[k]=0; 
    for(j=1;j <g.vexnum;j++) 
    if(g.arcs[k][j] <lowcost[j]&&closet[j]!=0) 
    {   lowcost[j]=g.arcs[k][j]; 
    closet   [j]=k; 
    } 
    } 
} 
void   main() 
{int   i,j,k; 
  system( "cls "); 
  printf( "请输入城市的个数，城市间道路的条数： "); 
  scanf( "%d,%d ",&i,&j); 
  g.vexnum=i; 
  g.arcnum=j; 
  for(i=0;i <g.vexnum;i++) 
  { 
  getchar(); 
  printf( "\n   第%d个顶点的信息： ",i+1); 
  g.vexs[i]=getchar(); 
  } 
  for(k=0;k <g.arcnum;k++) 
  { 
  printf( "\t   请输入第%d条边的起点： ",k); 
  scanf( "%d ",&g.a[k]); 
  
  printf( "\n   请输入第%d条边的终点： ",k); 
  scanf( "%d ",&g.b[k]); 
  
          printf( "\n   请输入第%d条边的权值： ",k); 
          scanf( "%d ",&g.w[k]); 
} 
  cre_grah(g); 
  prim(g); 
}



#include <stdio.h> 
#include <stdlib.h> 
#include <malloc.h> 
#define   M   20 
#define   MAX   20 
#define   MAXE   100 

/*Graph   kruskal*/ 
typedef   struct 
{ 
  int   begin; 
  int   end; 
  int   weight; 
}edge; 

typedef   struct 
{ 
  int   adj; 
  int   weight; 
}AdjMatrix[MAX][MAX]; 

typedef   struct 
{ 
  AdjMatrix   arc; 
  int   vexnum,   arcnum; 
}MGraph; 
void   CreatGraph(MGraph   *);/*函数申明*/ 
void   MiniSpanTree(MGraph   *); 
int     Find(int   *,   int   ); 

void   CreatGraph(MGraph   *G)/*构件图*/ 
{ 
  int   i,   j,n,   m; 

  printf( "please   input   the   number   of   edges   and   points: "); 
  scanf( "%d   %d ",&G-> arcnum,&G-> vexnum); 

        for   (i   =   1;   i   <=   G-> vexnum;   i++)/*初始化图*/ 
  { 
    for   (   j   =   1;   j   <=   G-> vexnum;   j++) 
    { 
      G-> arc[i][j].adj   =   G-> arc[j][i].adj   =   0; 
    } 
  } 

  for   (   i   =   1;   i   <=   G-> arcnum;   i++)/*输入边和权值*/ 
  { 
    printf( "\n   please   input   the   edge   which   has   2   points "); 
    scanf( "%d   %d ",&n,&m); 
    while(n   <   0   | |   n   >   G-> vexnum   | |   m   <   0   | |   n   >   G-> vexnum) 
    { 
      printf( "ERROR!   Please   input   again: "); 
      scanf( "%d%d ",&n,&m); 
    } 

    G-> arc[n][m].adj   =   G-> arc[m][n].adj   =   1; 
    getchar(); 
    printf( "\n   please   input   the   QUAN   betwwen   VEX   %d   and   VEX   %d: ",   n,   m); 
    scanf( "%d ",&G-> arc[n][m].weight); 
  } 
} 


void   MiniSpanTree(MGraph   *G)/*生成最小生成树*/ 
{ 
  int   i,   j,   n,   m; 
  int   k   =   1; 
        int   parent[M]; 

  edge   edges[M]; 

  for   (   i   =   1;   i   <   G-> vexnum;   i++) 
  { 
    for   (j   =   i   +   1;   j   <=   G-> vexnum;   j++) 
    { 
      if   (G-> arc[i][j].adj   ==   1) 
      { 
        edges[k].begin   =   i; 
        edges[k].end   =   j; 
        edges[k].weight   =   G-> arc[i][j].weight; 
              k++; 
      } 

    } 
  } 


        printf( "kruscal   is:\n "); 
  for   (i   =   1;   i   <=   G-> arcnum;   i++)/*核心部分*/ 
  { 
    n   =   Find(parent,   edges[i].begin); 
    m   =   Find(parent,   edges[i].end); 
    if   (n   !=   m) 
    { 
          parent[n]   =   m; 
          printf( " < <   %d,   %d   > >       %d\n ",   edges[i].begin,   edges[i].end,   edges[i].weight); 
    } 
  } 
} 

int   Find(int   *parent,   int   f)/*找尾*/ 
{ 
  while   (   parent[f]   >   0) 
  { 
    f   =   parent[f]; 
  } 
        return   f; 
} 
/*Graph   kruscal   END*/ 


/*depth-first   search*/ 
/*定义图*/ 
typedef   struct{ 
    int   V[M]; 
    int   R[M][M]; 
    int   vexnum; 
}Graph; 

/*创建图*/ 
void   creatgraph(Graph   *g,int   n) 
{ 
    int   i,j,r1,r2; 
    g-> vexnum=n; 
    /*顶点用i表示*/ 
    for(i=1;i <=n;i++) 
    { 
        g-> V[i]=i; 
    } 
    /*初始化R*/ 
    for(i=1;i <=n;i++) 
      for(j=1;j <=n;j++) 
        { 
            g-> R[i][j]=0; 
        } 
    /*输入R*/ 
    printf( "Please   input   R(0,0   END):\n "); 
    scanf( "%d,%d ",&r1,&r2); 
    while(r1!=0&&r2!=0) 
      { 
        g-> R[r1][r2]=1; 
        g-> R[r2][r1]=1; 
        scanf( "%d,%d ",&r1,&r2); 
      } 
} 

/*全局变量：访问标志数组*/ 
int   visited[M]; 
/*访问顶点*/ 
void   visitvex(Graph   *g,int   vex) 
{ 
  printf( "%d   ",g-> V[vex]); 
} 

/*获取第一个未被访问的邻接节点*/ 
int   firstadjvex(Graph   *g,int   vex) 
{ 
  int   w,i; 
  for(i=1;i <=g-> vexnum;i++) 
    { 
      if(g-> R[vex][i]==1&&visited[i]==0) 
        { 
            w=i; 
            break; 
        } 
      else 
        { 
            w=0; 
        } 
    } 
    return   w; 
} 
/*获取下一个未被访问的邻接节点(深度遍历)*/ 
int   nextadjvex(Graph   *g,int   vex,int   w) 
{ 
    int   t; 
    t=firstadjvex(g,w); 
    return   t; 
} 
/*深度递归遍历*/ 
    void   dfs(Graph   *g,int   vex) 
      { 
        int   w; 
        visited[vex]=1; 
        visitvex(g,vex); 
        for(w=firstadjvex(g,vex);w> 0;w=nextadjvex(g,vex,w)) 
            if(!visited[w]) 
              { 
  dfs(g,w); 
              } 
      } 

      void   dfstraverse(Graph   *g) 
      { 
          int   i; 
          for(i=1;i <=g-> vexnum;i++) 
              visited[i]=0; 
          for(i=1;i <=g-> vexnum;i++) 
              if(!visited[i]) 
                  {dfs(g,i);} 
      } 
/*depth   first   search   END*/ 


main() 
{ 
    int   a; 
    int   n; 
    Graph   *z=(Graph   *)malloc(sizeof(Graph)); 
    char   menu; 
    MGraph   *G; 
    G=(MGraph*)malloc(sizeof(MGraph)); 

  printf( "please   choose\n "); 
  printf( "1.kruskal\n "); 
  printf( "2.depth-first   search\n "); 
  printf( "3.exit\n "); 
  scanf( "%d ",&a); 
  while(a!=3) 
  {switch(a) 
        {case   1: 
                        if   (G   ==   NULL) 
                          { 
                            printf( "memory   allcation   failed,goodbye "); 
                            exit(1); 
                          } 
                        CreatGraph(G); 
                        MiniSpanTree(G); 
                        break; 
          case   2: 
                        printf( "Please   input   the   number   of   vertex:\n ");   
                        scanf( "%d ",&n);   
                        creatgraph(z,n);   
                        printf( "Depth_first:\n ");   
                        dfstraverse(z);   
                        printf( "\n "); 
                        break; 
        } 
      printf( "please   choise\n "); 
      printf( "1.kruskal\n "); 
      printf( "2.depth-first   search\n "); 
      printf( "3.exit\n "); 
      scanf( "%d ",&a); 
  } 
}