一、prim算法实现

二、最短路径

三、图的邻接表存储


一、prim算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<stdio.h>
#include<stdlib.h>
 
#define VEXNUM 6//顶点数
#define ARCNUM 10//边数
#define MAX_VAL 100//先定义最大权值；
 
int  s_set[VEXNUM+1], s_count; //标记被加入最小生成树的点与数量
int  vs_count; //标记原来树中节点的数目；
 
struct  Graph{
     int  vexs[VEXNUM+1]; //顶点数组；
     int  a[VEXNUM+1][VEXNUM+1]; //邻接矩阵；
     int  val[VEXNUM+1][VEXNUM+1]; //权值；
};
typedef  struct { //记录已加入最小生成树的边的情况：端点、权值；
    int  a;
    int  v;
    int  cost;
}closedge;
 
void  create( struct  Graph *); //创建图；
void  prim(closedge  clo[ARCNUM], struct  Graph *); //实现prim
 
void  main()
{  
     closedge  clo[ARCNUM];
     struct  Graph *g=NULL;
     g=( struct  Graph *) malloc ( sizeof ( struct  Graph)); //分配空间；
     create(g);
     prim(clo,g);
}
 
void  prim(closedge  clo[ARCNUM], struct  Graph *g){
     int  i,j,k,q,w;
     for (i=1;i<=VEXNUM;i++){
         s_set[i]=0;
     }
     
     s_count=0;
     vs_count=VEXNUM;
     s_set[1]=1;s_count++;
     vs_count--;
 
     while ( true ){
         int  x=MAX_VAL;
         for (j=1;j<=VEXNUM;j++){ 
             if (s_set[j]==1){   
                 for (k=1;k<=VEXNUM;k++){ 
                     if ((k!=j)&&(s_set[k]==0)){ 
                         if (x>(g->val[k][j])&&g->val[k][j]!=0) 
                         {
                             x=g->val[k][j];
                             q=j;w=k;
                         }
                     }
                 }
             }
         }
         clo[s_count-1].a=q;clo[s_count-1].v=w;clo[s_count-1].cost=x;
         printf ( "结点A：%d   结点B：%d   边：%d\n" ,clo[s_count-1].a,clo[s_count-1].v,clo[s_count-1].cost);
         s_set[w]=1;s_count++;
         vs_count--;
         if (vs_count==0)
             break ;
     }
}
 
void  create( struct  Graph *g)
{
     int  i,j,n,x,y,z;
     FILE  *fp;
     fp= fopen ( "E:\\prim.txt" , "r" );
     for (n=1;n<=VEXNUM;n++)
         g->vexs[n]=n; 
     for (i=1; i<=VEXNUM; i++)
         for (j=1; j<=VEXNUM; j++){
             g->a[i][j] = 0;
             g->a[j][i] = g->a[i][j];
         }
     for (i=0; i<ARCNUM; i++){
         //fscanf(fp,"%d,%d,%d",&x,&y,&z);错误输入格式
         fscanf (fp, "%d%d%d" ,&x,&y,&z); // printf("%d %d %d\n",x,y,z);
         g->a[x][y] = 1;
         g->a[y][x]=g->a[x][y];
         g->val[x][y]=z;
         g->val[y][x]=g->val[x][y];
     }
     fclose (fp);
     for (i=1; i<=VEXNUM; i++)
     {
         for (j=1; j<=VEXNUM; j++)
             if (g->val[i][j]<0)
                 g->val[i][j]=0;
     }
/**可以显示图的邻接矩阵
     for(i=1; i<=VEXNUM; i++)
     {
         for(j=1; j<=VEXNUM; j++)
         {
                 printf("%d\t",g->a[i][j]);
         }
          printf("\n");
     }
     printf("\n");printf("\n");printf("\n");
     for(i=1; i<=VEXNUM; i++)
     {
         for(j=1; j<=VEXNUM; j++)
             if(g->val[i][j]>0)
                 printf("%d\t",g->val[i][j]);
             else{
                 g->val[i][j]=0;
                 printf("%d\t",g->val[i][j]);
             }
          printf("\n");
     }
*/
}

二、最短路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include<stdio.h>
#include<stdlib.h>
 
#define VEXNUM 6//顶点数
#define ARCNUM 10//边数
#define INT_MAX 10000//先定义最大权值；
 
struct  Graph{
     int  vexs[VEXNUM+1]; //顶点数组；
     int  a[VEXNUM+1][VEXNUM+1]; //邻接矩阵；
     int  val[VEXNUM+1][VEXNUM+1]; //权值；
};
 
void  create( struct  Graph *); //创建图；
void  min_length( struct  Graph *);
 
void  main()
{  
     struct  Graph *g=NULL;
     g=( struct  Graph *) malloc ( sizeof ( struct  Graph)); //分配空间；
     create(g);
     min_length(g);
}
 
void  create( struct  Graph *g)
{
     int  i,j,n,x,y,z;
     FILE  *fp;
     fp= fopen ( "E:\\min1.txt" , "r" );
     for (n=1;n<=VEXNUM;n++)
         g->vexs[n]=n; 
     for (i=1; i<=VEXNUM; i++)
         for (j=1; j<=VEXNUM; j++){
             g->a[i][j] = 0;
             g->a[j][i] = g->a[i][j];
         }
     for (i=0; i<ARCNUM; i++){
         //fscanf(fp,"%d,%d,%d",&x,&y,&z);错误输入格式
         fscanf (fp, "%d%d%d" ,&x,&y,&z); // printf("%d %d %d\n",x,y,z);
         g->a[x][y] = 1;
         g->a[y][x]=g->a[x][y];
         g->val[x][y]=z;
         g->val[y][x]=g->val[x][y];
     }
     fclose (fp);
     for (i=1; i<=VEXNUM; i++)
     {
         for (j=1; j<=VEXNUM; j++)
             if (g->val[i][j]<0)
                 g->val[i][j]=0;
     }
 
     for (i=1; i<=VEXNUM; i++)
     {
         for (j=1; j<=VEXNUM; j++)
         {
                 printf ( "%d\t" ,g->a[i][j]);
         }
          printf ( "\n" );
     }
     printf ( "\n" ); printf ( "\n" ); printf ( "\n" );
     for (i=1; i<=VEXNUM; i++)
     {
         for (j=1; j<=VEXNUM; j++)
             if (g->val[i][j]>0)
                 printf ( "%d\t" ,g->val[i][j]);
             else {
                 g->val[i][j]=0;
                 printf ( "%d\t" ,g->val[i][j]);
             }
          printf ( "\n" );
     }
}
 
void  min_length( struct  Graph *g)
{
     int  disk[VEXNUM+1];
     int  pre[VEXNUM+1];
     int  i,k,x,y;
     int  s=1;
     for (i=1;i<=VEXNUM;i++){
         pre[i]=0;
         if (g->a[1][i]==1)
             disk[i]=g->val[1][i];
         else
             disk[i]=INT_MAX;
     }
     
     disk[1]=0;pre[1]=1;
printf ( "删除结点：1\n" );
 
     while (s<VEXNUM){
         int  min=INT_MAX;
         for (i=1;i<=VEXNUM;i++)
             if (pre[i]==0&&min>disk[i])
                 min=disk[i];
         for (i=1;i<=VEXNUM;i++)
             if (pre[i]==0&&min==disk[i]){
                 k=i;
                 break ;
             }       pre[k]=1;
printf ( "删除结点：%d\n" ,k);
         for (i=1;i<=VEXNUM;i++)
         {
             if (pre[i]==0&&g->a[k][i]==1){
                 x=disk[i];y=disk[k]+g->val[i][k];
                 if (x>y)
                     disk[i]=y;
             }
         }
         s++;
     }
for (i=1;i<=VEXNUM;i++)
     printf ( "disk[%d]=%d\n" ,i,disk[i]); //for(i=1;i<=VEXNUM;i++)
 
}
 
 
 
 
floyd:任意点之间最短路径
typedef  struct          
{        
     char  vertex[VertexNum];                                 //顶点表         
     int  edges[VertexNum][VertexNum];                        //邻接矩阵,可看做边表         
     int  n,e;                                                //图中当前的顶点数和边数         
}MGraph; 
 
void  Floyd(MGraph g)
{
  　　 int  A[MAXV][MAXV];
  　　 int  path[MAXV][MAXV];
  　　 int  i,j,k,n=g.n;
  　　 for (i=0;i<n;i++)
     　　 for (j=0;j<n;j++)
     　　{ 　　
              A[i][j]=g.edges[i][j];
          　　 path[i][j]=-1;
      　 }
  　　 for (k=0;k<n;k++)
  　　{ 
       　　 for (i=0;i<n;i++)
          　　 for (j=0;j<n;j++)
              　　 if (A[i][j]>(A[i][k]+A[k][j]))
              　　{
                    　　A[i][j]=A[i][k]+A[k][j];
                    　　path[i][j]=k;
               　 } 
     　} 
}

三、图的邻接表存储

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h>  
#include <stdlib.h>  
   
#define  MaxVertexNum 4783  
   
typedef  char  VertexType;   //自定义定点类型,有11837
int [] array =  new  int {1,7,8,9,8,3,9,3,5,4,1},自定义数组
typedef  struct  node    //边表节点  
{  
    int  adjvex;  
    node* next;  
}EdgeNode;  
   
typedef  struct      //顶点表节点  
{  
    VertexType vertex;  
    EdgeNode* firstedge;  
}VertexNode;  
   
typedef  VertexNode AdjList[MaxVertexNum];   //自定义定点表节点类型
   
typedef  struct   
{   
     AdjList adjlist;  
     int  n,e;   //顶点数跟边数
}ALGraph;  //图的结构体 
   
void  create(ALGraph*);  
   
void  main()  
{  
    ALGraph* G= (ALGraph*) malloc ( sizeof (ALGraph));   //创建图变量，并且分配空间
    create(G);  
    for  ( int  i=0;i< G->n;i++)  
    {  
        printf ( "%d->" ,i);  
        while (G->adjlist[i].firstedge!=NULL)  
        {  
             printf ( "%d->" ,G->adjlist[i].firstedge->adjvex);  
             G->adjlist[i].firstedge=G->adjlist[i].firstedge->next;  
   
        }  
        printf ( "\n" );  
    }  
}  
void  create(ALGraph* G)  
{  
     int  i,j,k,w,v;  
     EdgeNode *s;  
     printf ( "读入顶点数和边数" );  
     scanf ( "%d,%d" ,&G->n,&G->e);  
   
     
    for  (i=0;i<G->n;i++)  //初始化 
    {  
        fflush (stdin);   //用来清空输入缓存，以便不影响后面输入的东西
        printf ( "建立顶点表" );  
        G->adjlist[i].vertex= getchar ();  
        G->adjlist[i].firstedge=NULL;  
    }  
    printf ( "建立边表\n" );  
    for  (k=0;k<G->e;k++)  
    {  
        printf ( "读入(vi-vj)的顶点对序号" );  
        scanf ( "%d,%d" ,&i,&j);  
        s=(EdgeNode*) malloc ( sizeof (EdgeNode));  
        s->adjvex=j;  
        s->next=G->adjlist[i].firstedge;   //插入表头  
        G->adjlist[i].firstedge=s;  
        //如果是无向图，则需要创建下面操作
       /* s=(EdgeNode*)malloc(sizeof(EdgeNode));  
        s->adjvex=i;  
        s->next=G->adjlist[j].firstedge;  
        G->adjlist[j].firstedge=s;  */
   
    }  
}