图论基础

今天发现寒假学的图论基础还挺有用，今天贴下代码

邻接矩阵：

 1 #include<stdio.h>
 2 #include<string.h>
 3 
 4 int map[100][100];
 5 
 6 void init()
 7 {
 8     memset(map,0,sizeof(map));
 9 }
10 
11 void add(int u, int v, int w)
12 {
13    map[u][v]=w;
14 }
15 
16 int main()
17 {
18     int n,m,u,v,w;
19     init();
20     scanf("%d%d",&n,&m);
21     while(m--)
22     {
23         scanf("%d%d%d",&u,&v,&w);
24         add(u,v,w);
25         add(v,u,w);
26     }
27     for(int i=1;i<=n;i++)
28     {
29         printf("与%d相关联的顶点有:
",i);
30      for(int j=1;j<=n;j++)
31          if(map[i][j]!=0)
32              printf("%d ",j);
33         printf("
");
34     }
35     return 0;
36 }

邻接表——边表：

 1 #include<stdio.h>
 2 #include<string.h>
 3 struct node
 4 {
 5     int u,v,w;
 6     int next;
 7 } g[100];
 8 
 9 int head[100],t=0;
10 
11 void init()
12 {
13     t = 0;
14     memset(head,-1,sizeof(head));
15 }
16 
17 void add(int u, int v, int w)
18 {
19     g[t].u = u;
20     g[t].v = v;
21     g[t].w = w;
22     g[t].next = head[u];
23     head[u] = t;
24     t++;
25 }
26 
27 int main()
28 {
29     int n,m,u,v,w;
30     init();
31     scanf("%d%d",&n,&m);
32     while(m--)
33     {
34         scanf("%d%d%d",&u,&v,&w);
35         add(u,v,w);
36         add(v,u,w);
37     }
38     for(int i=1;i<=n;i++)
39     {
40         printf("与%d相关联的顶点有:
",i);
41     for(int j=head[i]; j!=-1; j=g[j].next)
42         printf("%d ",g[j].v);
43         printf("
");
44     }
45     return 0;
46 }

邻接表——链表：

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 struct node
 5 {
 6    int u;
 7    int v;
 8    int w;
 9    struct node* next;
10 }*head[100];
11 
12 void init()
13 {
14    memset(head,NULL,sizeof(head));
15 }
16 
17 void add(int u, int v, int w)
18 {
19    struct node *p = (struct node*)malloc(sizeof(struct node));
20    p->u = u;
21    p->v = v;
22    p->w = w;
23    p->next = head[u];
24    head[u] = p;
25 }
26 
27 int main()
28 {
29     int n,m,u,v,w;
30     init();
31     scanf("%d%d",&n,&m);
32     while(m--)
33     {
34         scanf("%d%d%d",&u,&v,&w);
35         add(u,v,w);
36         add(v,u,w);
37     }
38     for(int i=1;i<=n;i++)
39     {
40         printf("与%d相关联的顶点有:
",i);
41         for(struct node* p = head[i]; p != NULL; p = p->next)
42         printf("%d ",p->v);
43         printf("
");
44     }
45     return 0;
46 }