国产一级a片免费看高清,亚洲熟女中文字幕在线视频,黄三级高清在线播放,免费黄色视频在线看

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#define INFINITY 1000

#define max_name 50

#define max_vertex_num 50

typedef char vertex[max_name];//頂點(diǎn)名字串

typedef int adjMatrix[max_vertex_num][max_vertex_num];//鄰接距陣

typedef struct 

{vertex adjvex; //鄰接矩陣

 int lowcost;    //權(quán)值

}close[max_vertex_num];//定義一個(gè)結(jié)構(gòu)以便在后面closedge 使用

typedef struct//定義圖

{

 vertex vexs[max_vertex_num]; //頂點(diǎn)集

 adjMatrix arcs; //邊

 int vexnum,arcnum;//點(diǎn)個(gè)數(shù)，邊個(gè)數(shù)

}MGraph;

int LocateVex(MGraph G,vertex u)//若G中存在頂點(diǎn)u,則返回該點(diǎn)在圖中位置;否則返回其他信息;

{

  int i;

  for(i=0;i<G.vexnum;++i)

  if(strcmp(u,G.vexs[i])==0)

  return i;

  return 1;

}

void CreateGraph(MGraph &G)

{

  int i,j,k,w;

  vertex v1,v2;

  printf("輸入無向圖頂點(diǎn)數(shù)和邊數(shù):  \n");

  scanf("%d  %d",&G.vexnum,&G.arcnum);

  printf("輸入各頂點(diǎn)的值：\n", G.vexnum);

  for(i=0;i<G.vexnum;++i) //構(gòu)造頂點(diǎn)集

    scanf("%s",&G.vexs[i]);

    for(i=0;i<G.vexnum;++i) //初始化鄰接方陣

       for(j=0;j<G.vexnum;++j)

                                                       G.arcs[i][j]=INFINITY;

  printf("輸入一條邊依附的頂點(diǎn)及權(quán)值： \n",G.arcnum);//輸入一條邊依附的頂點(diǎn)及權(quán)值

  for(k=0;k<G.arcnum;++k)

  {

    scanf("%s%s%d",v1,v2,&w);

    i=LocateVex(G,v1);//v1在圖中位置

    j=LocateVex(G,v2);//v2在圖中位置

    G.arcs[i][j]=G.arcs[j][i]=w; //置于對(duì)稱弧

  }

}

int minimum(close c,MGraph G)//求出下一個(gè)節(jié)點(diǎn) 第k個(gè)頂點(diǎn)

{

  int i=0,j,k,min;

  min=INFINITY;

  //初始化

  k=-1;

  for(j=0;j<=G.vexnum;j++)//求最小

   if(c[j].lowcost<min&&c[j].lowcost>0)

    {

      min=c[j].lowcost;

      k=j;

    }

  return k;

}

void PRIM(MGraph G,vertex u)

{

  int i,j,k=0;

  close closedge;//一個(gè)結(jié)構(gòu)

  bool isbreak=false;

  k=LocateVex(G,u);//u在圖中位置 返回G.vexs[i]中下標(biāo)

  for(j=0;j<=G.vexnum;++j) //輔助數(shù)組初始化 closedge從O 開始

  {  

                                                    if(j!=k)//沒有自己到自己的

                                                     closedge[k].lowcost=0;

                                                     strcpy(closedge[j].adjvex,u);

       closedge[j].lowcost=G.arcs[k][j];//列

  }

  int flag[1000];

  flag[0]=0;

  int count=1;

  for(i=1;i<G.vexnum;++i)

  {

    k=minimum(closedge,G);

                                                  if(k==-1)

                                                  {

                                                    isbreak=true;

                                                    break;

                                                  }

printf("%s-%s%d\n",closedge[k].adjvex,G.vexs[k],G.arcs[k][LocateVex(G,closedge[k].adjvex)]); //輸出生成樹的邊

    closedge[k].lowcost=0; // 第k個(gè)頂點(diǎn)并入U集

                                                  flag[count]=k;

                                                  count++;

    for(j=0;j<G.vexnum;++j)

      if(G.arcs[k][j]<closedge[j].lowcost)//新頂點(diǎn)并入U后重新選擇最小邊

      {

        strcpy(closedge[j].adjvex,G.vexs[k]);

        closedge[j].lowcost=G.arcs[k][j];

      }

  }

  if(isbreak)

  {

printf("此圖不連通，無最小支撐樹 ！\n訪問過的點(diǎn)為：\n");

for(i=0;i<count;i++)

{

 printf("%s  ",G.vexs[flag[i]]);

}

printf("\n");

  }

}

void main()

{

  MGraph G;

  CreateGraph(G);

  printf("最小生成樹的各條邊為: \n");

  PRIM(G,G.vexs[0]);

圖1結(jié)果如下:

 注釋 :圖1中有7個(gè)點(diǎn)10條邊, 最后結(jié)果輸出最小生成樹為:

    圖1最小權(quán)值W=5+1+2+3+4+1= 16