有向图的邻接表c语言

有向图的邻接表(C语言)
2013-06-17 12:25:35
c语言写的有向图的邻接表的实现，通过使用图的邻接表实现图的存储结构存储。
收起

c语言邻接表的构建_C语言建立有向图的邻接表及其遍历操作

2020-12-23 13:59:13

1 /*C语言建立有向图的邻接表及其遍历操作*/2 #include"stdio.h"3 #include"stdlib.h"4 //图的邻接矩阵储存结构5 typedef charelemtype;6 #define maxsize 107 #define queuesize 1008 //边结点的类型定义9 typedef ...

1 /*C语言建立有向图的邻接表及其遍历操作*/
2 #include"stdio.h"
3 #include"stdlib.h"
4 //图的邻接矩阵储存结构
5 typedef charelemtype;6 #define maxsize 10
7 #define queuesize 100
8 //边结点的类型定义
9 typedef structedgenode10 {11     int adjvex;//存放邻接的点在顶点表的下标，邻接点
12     struct edgenode *next;//指向Vi下一个邻接点的边结点
13     int weight;/*权值*/
14 }edgenode;15 //顶点结点类型定义
16 typedef structvexnode17 {18     elemtype data; //存储顶点的名称或其相关信息
19     edgenode *firstedge;//边表头指针
20 }vexnode;21 //图的邻接表数据类型
22 typedef struct{23     vexnode vexlist[maxsize];//顶点表
24     intn,e;25 }graph;26 //在图g中查找顶点v,存在顶点数组中的下标，不存在返回-1
27 intlocatevex(graph g,elemtype v)28 {29     inti;30     for(i=0;i
35 voidprint(graph g)36 {37     inti;38     edgenode *p;39     printf("图的邻接表表示：");40     for(i=0;i%d",p->adjvex);p=p->next;45 }46 }47     printf("\n");48 }49 void creategraph(graph *g){50     inti,j,k;51 elemtype v1,v2;52     edgenode *s;53     printf("请输入图的顶点数及边数\n");54     printf("顶点数 n=");scanf("%d",&g->n);55     printf("边  数 e=");scanf("%d",&g->e);56     printf("请输入图的顶点信息：\n");getchar();57     for(i=0;i<=g->n;i++){58         scanf("%c",&g->vexlist[i].data); //构造顶点信息
59         g->vexlist[i].firstedge=NULL;60 }61     printf("请输入图的边的信息：\n");62     for(k=0;ke;k++)63 {64         printf("请输入第%d条边的两个端点下标：",k+1);65         scanf("%c%c",&v1,&v2);getchar();//输入一条边的两个顶点
66         i=locatevex(*g,v1);67         j=locatevex(*g,v2);68         if(i>=0&&j>=0){69         //建立无向图的邻接表
70         /*s=(edgenode *)malloc(sizeof(edgenode));71 s->adjvex=j;72 s->next=g->vexlist[i].firstedge;73 g->vexlist[i].firstedge=s;74
75 s=(edgenode *)malloc(sizeof(edgenode));76 s->adjvex=i;77 s->next=g->vexlist[j].firstedge;78 g->vexlist[j].firstedge=s;*/
79             //建立有向图的邻接表
80             s=(edgenode *)malloc(sizeof(edgenode));81             s->adjvex=j;82             s->next=g->vexlist[i].firstedge;83             g->vexlist[i].firstedge=s;84 }85 }86 }87 int visited[maxsize];/*访问标志数组*/
88  /*从第i个顶点出发递归地深度优先遍历图G*/
89 void DFS(graph g,inti)90 {91     edgenode *p;92     printf("%3c",g.vexlist[i].data);/*访问第i个项点*/
93     visited[i]=1;94     p=g.vexlist[i].firstedge;95     while(p!=NULL)    {96         if(visited[p->adjvex]==0)97           DFS(g,p->adjvex);/*对i的尚未访问的邻接顶点j递归调用DFS*/
98         p=p->next;99 }100 }101 void DFStraverse(graph  g) /*对图G进行深度优先遍历*/
102 {103     intv;104     for (v=0; v
105     for  (v=0; v
106 /*从第v个顶点出发递归地深度优先遍历图G*/
107         if (!visited[v])DFS(g,v);108 }109 //循环队列存储结构定义
110 typedef structcirqueue111 {112     elemtype  *data;      //队列存储空间的首地址
113     int front;         //队头位置：指向当前队头元素
114     int rear;    //队尾位置：指向当前队尾元素的下一位置
115 }cirqueue;             //循环队列116 //构造空队，如果成功，返回1，如果失败，返回0
117 int initqueue(cirqueue *q)118 {119     q->data=(elemtype *)malloc(queuesize*sizeof(cirqueue));120     if (q->data==NULL)return 0; //存储分配失败
121     q->front=q->rear=0;122     return 1;123 }124 //插入元素e为Q的新的队尾元素 ,如果成功，返回1，如果失败，返回0
125 int enqueue (cirqueue *q,elemtype e)126 {127     if ((q->rear+1) % queuesize == q->front)128         return 0; //队列满
129     q->data[q->rear] =e;130     q->rear = (q->rear+1) % queuesize; //队尾后移一位
131     return 1;132 }133 //若队列不空，则删除Q的队头元素，用e返回其值,并返回1；否则返回0
134 int dequeue (cirqueue *q,int *e)135 {136     if (q->front == q->rear)  return 0; //队列为空
137     *e = q->data[q->front];138     q->front = (q->front+1) %queuesize; //队头后移一位
139     return 1;140 }141 //若栈不空，则用e返回队头元素,并返回1；否则返回0
142 int getfront(cirqueue q,elemtype *e)143 {144     if (q.front == q.rear)  return 0; //队列为空
145     *e=q.data[q.front];146     return  1;147 }148 //若队列为空栈，则返回1，否则返回0
149 int queueempty(cirqueue q)//栈非空
150 {151     if(q.front == q.rear)return 1; //队列为空
152     else return 0;153 }154 //返回队列的元素个数，即队列的长度
155 intqueuelength(cirqueue q)156 {157     return (q.rear-q.front+queuesize) %queuesize;158 }159 //【算法6-10：利用邻接矩阵实现连通图的广度优先搜索遍历】
160 intBFSvisited[maxsize];161 cirqueue q;162 /*从第k个顶点出发广度优先遍历图G,G以邻接矩阵表示。*/
163 void BFS(graph g,intk){164     inti;165     edgenode *p;166     initqueue(&q);/*初始化队列*/
167     printf("%3c",g.vexlist[k].data);/*访问第k个项点*/
168     visited[k]=1;169     enqueue(&q,k);/*第k个顶点进队*/
170     while(queueempty(q)==0) {/*队列非空*/
171         dequeue(&q,&i);172         p=g.vexlist[i].firstedge;/*获取第1个邻接点*/
173         while(p!=NULL){174             if(visited[p->adjvex]==0){175                 /*访问第i个顶点的末曾访问的顶点*/
176                 printf("%3c",g.vexlist[p->adjvex].data);177                 visited[p->adjvex]=1;178                 enqueue(&q,p->adjvex);/*第k个顶点进队*/
179 }180             p=p->next;181 }182 }183 }184 void BFStraverse(graph  g) //对图G进行广度优先遍历
185 {186     intv;187     for (v=0; v
188         visited[v]=0;189     for  (v=0; v
190         if (!visited[v])BFS(g,v);191        //从第v个顶点出发递归地深度优先遍历图G
192 }193 intmain()194 {195 graph g;196     creategraph(&g);197 print(g);198     printf("\n");199     printf("图的深度优先遍历序列：\n");200 DFStraverse(g);201     printf("\n");202     printf("图的广度优先遍历序列：\n");203 BFStraverse(g);204     printf("\n");205     return 0;206 }

收起

展开全文

C语言建立有向图的邻接表及其遍历操作

千次阅读 多人点赞 2018-12-29 17:27:32

C语言建立有向图的邻接表及其遍历操作 1 /*C语言建立有向图的邻接表及其遍历操作*/ 2 #include"stdio.h" 3 #include"stdlib.h" 4 //图的邻接矩阵储存结构 5 typedef char elemtype; 6 #...

C语言建立有向图的邻接表及其遍历操作
1 /*C语言建立有向图的邻接表及其遍历操作*/
  2 #include"stdio.h"
  3 #include"stdlib.h"
  4 //图的邻接矩阵储存结构
  5 typedef char elemtype;
  6 #define maxsize 10
  7 #define queuesize 100
  8 //边结点的类型定义
  9 typedef struct edgenode
 10 {
 11     int adjvex;//存放邻接的点在顶点表的下标，邻接点
 12     struct edgenode *next;//指向Vi下一个邻接点的边结点
 13     int weight;/*权值*/
 14 }edgenode;
 15 //顶点结点类型定义
 16 typedef struct vexnode
 17 {
 18     elemtype data; //存储顶点的名称或其相关信息
 19     edgenode *firstedge;//边表头指针
 20 }vexnode;
 21 //图的邻接表数据类型
 22 typedef struct{
 23     vexnode vexlist[maxsize];//顶点表
 24     int n,e;
 25 }graph;
 26 //在图g中查找顶点v,存在顶点数组中的下标，不存在返回-1
 27 int locatevex(graph g,elemtype v)
 28 {
 29     int i;
 30     for(i=0;i<g.n;i++)
 31         if(g.vexlist[i].data==v)return i;
 32     return -1;
 33 }
 34 //打印图信息
 35 void print(graph g)
 36 {
 37     int i;
 38     edgenode *p;
 39     printf("图的邻接表表示：");
 40     for(i=0;i<g.n;i++){
 41         printf("\n%4c",g.vexlist[i].data);
 42         p=g.vexlist[i].firstedge;
 43         while(p!=NULL){
 44             printf("-->%d",p->adjvex);p=p->next;
 45         }
 46     }
 47     printf("\n");
 48 }
 49 void creategraph(graph *g){
 50     int i,j,k;
 51     elemtype v1,v2;
 52     edgenode *s;
 53     printf("请输入图的顶点数及边数\n");
 54     printf("顶点数 n=");scanf("%d",&g->n);
 55     printf("边  数 e=");scanf("%d",&g->e);
 56     printf("请输入图的顶点信息：\n");getchar();
 57     for(i=0;i<=g->n;i++){
 58         scanf("%c",&g->vexlist[i].data); //构造顶点信息
 59         g->vexlist[i].firstedge=NULL;
 60     }
 61     printf("请输入图的边的信息：\n");
 62     for(k=0;k<g->e;k++)
 63     {
 64         printf("请输入第%d条边的两个端点下标：",k+1);
 65         scanf("%c%c",&v1,&v2);getchar();//输入一条边的两个顶点
 66         i=locatevex(*g,v1);
 67         j=locatevex(*g,v2);
 68         if(i>=0&&j>=0){
 69         //建立无向图的邻接表
 70         /*s=(edgenode *)malloc(sizeof(edgenode));
 71         s->adjvex=j;
 72         s->next=g->vexlist[i].firstedge;
 73         g->vexlist[i].firstedge=s;
 74 
 75         s=(edgenode *)malloc(sizeof(edgenode));
 76         s->adjvex=i;
 77         s->next=g->vexlist[j].firstedge;
 78         g->vexlist[j].firstedge=s;*/
 79             //建立有向图的邻接表
 80             s=(edgenode *)malloc(sizeof(edgenode));
 81             s->adjvex=j;
 82             s->next=g->vexlist[i].firstedge;
 83             g->vexlist[i].firstedge=s;
 84         }
 85     }
 86 }
 87 int visited[maxsize];/* 访问标志数组*/
 88  /*从第i个顶点出发递归地深度优先遍历图G*/
 89 void DFS(graph g,int i)
 90 {
 91     edgenode *p;
 92     printf("%3c",g.vexlist[i].data);/*访问第i个项点*/
 93     visited[i]=1;
 94     p=g.vexlist[i].firstedge;
 95     while(p!=NULL)    {
 96         if(visited[p->adjvex]==0)
 97           DFS(g,p->adjvex);/*对i的尚未访问的邻接顶点j递归调用DFS*/
 98         p=p->next;
 99     }
100 }
101 void DFStraverse(graph  g) /*对图G进行深度优先遍历*/
102 {
103     int v;
104     for (v=0; v<g.n;v++)visited[v]=0; /*初始化标志数组*/
105     for  (v=0; v<g.n;v++) /*保证非连通图的遍历*/
106 /*从第v个顶点出发递归地深度优先遍历图G*/
107         if (!visited[v])DFS(g,v);        
108 }
109 //循环队列存储结构定义
110 typedef struct  cirqueue
111 {
112     elemtype  *data;      //队列存储空间的首地址
113     int front;         //队头位置：指向当前队头元素
114     int rear;    //队尾位置：指向当前队尾元素的下一位置
115 }cirqueue;             // 循环队列
116 //构造空队，如果成功，返回1，如果失败，返回0
117 int initqueue(cirqueue *q)
118 {
119     q->data=(elemtype *)malloc(queuesize*sizeof(cirqueue));
120     if (q->data==NULL)return 0; // 存储分配失败 
121     q->front=q->rear=0;    
122     return 1;
123  }
124 // 插入元素e为Q的新的队尾元素 ,如果成功，返回1，如果失败，返回0
125 int enqueue (cirqueue *q,elemtype e)
126 { 
127     if ((q->rear+1) % queuesize == q->front) 
128         return 0; //队列满
129     q->data[q->rear] = e;
130     q->rear = (q->rear+1) % queuesize; //队尾后移一位
131     return 1;
132 }
133 //若队列不空，则删除Q的队头元素，用e返回其值,并返回1；否则返回0
134 int dequeue (cirqueue *q,int *e) 
135 {
136     if (q->front == q->rear)  return 0; //队列为空
137     *e = q->data[q->front];
138     q->front = (q->front+1) %queuesize; //队头后移一位
139     return 1;
140 }
141 //若栈不空，则用e返回队头元素,并返回1；否则返回0
142 int getfront(cirqueue q,elemtype *e)
143 {
144     if (q.front == q.rear)  return 0; //队列为空
145     *e=q.data[q.front];
146     return  1;
147  }
148 //若队列为空栈，则返回1，否则返回0 
149 int queueempty(cirqueue q)//栈非空
150 { 
151     if(q.front == q.rear)return 1; //队列为空
152     else return 0;
153 }
154 //返回队列的元素个数，即队列的长度
155 int queuelength(cirqueue q)
156 { 
157     return (q.rear-q.front+queuesize) % queuesize;
158 }
159 //【算法6-10：利用邻接矩阵实现连通图的广度优先搜索遍历】
160 int BFSvisited[maxsize];
161 cirqueue q;
162 /*从第k个顶点出发广度优先遍历图G,G以邻接矩阵表示。*/
163 void BFS(graph g,int k){
164     int i;
165     edgenode *p;
166     initqueue(&q);/*初始化队列*/
167     printf("%3c",g.vexlist[k].data);/*访问第k个项点*/
168     visited[k]=1;    
169     enqueue(&q,k);/*第k个顶点进队*/
170     while(queueempty(q)==0) {/*队列非空*/
171         dequeue(&q,&i);
172         p=g.vexlist[i].firstedge;/*获取第1个邻接点*/
173         while(p!=NULL){
174             if(visited[p->adjvex]==0){
175                 /*访问第i个顶点的末曾访问的顶点*/
176                 printf("%3c",g.vexlist[p->adjvex].data);
177                 visited[p->adjvex]=1;
178                 enqueue(&q,p->adjvex);/*第k个顶点进队*/
179             }
180             p=p->next;
181         }        
182     }
183 }
184 void BFStraverse(graph  g) //对图G进行广度优先遍历
185 {
186     int v;
187     for (v=0; v<g.n;v++) //初始化标志数组
188         visited[v]=0; 
189     for  (v=0; v<g.n;v++) //保证非连通图的遍历
190         if (!visited[v])BFS(g,v); 
191        //从第v个顶点出发递归地深度优先遍历图G
192 }
193 int main()
194 {
195     graph g;
196     creategraph(&g);
197     print(g);
198     printf("\n");
199     printf("图的深度优先遍历序列：\n");
200     DFStraverse(g);
201     printf("\n");
202     printf("图的广度优先遍历序列：\n");
203     BFStraverse(g);
204     printf("\n");
205     return 0;
206 }

程序运行截图：

收起

展开全文

c 数据结构

c语言邻接表的构建_C/C++知识点之C语言建立有向图的邻接表及其遍历操作

2020-12-23 13:59:11

本文主要向大家介绍了C/C++知识点之C语言建立有向图的邻接表及其遍历操作，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。1/**/2#include"stdio.h"3#include"stdlib.h"4//图的邻接矩阵储存结构5...

本文主要向大家介绍了C/C++知识点之C语言建立有向图的邻接表及其遍历操作，通过具体的内容向大家展示，希望对大家学习C/C++知识点有所帮助。
1 /**/
2 #include"stdio.h"
3 #include"stdlib.h"
4 //图的邻接矩阵储存结构
5 typedef char elemtype;
6 #define maxsize 10
7 #define queuesize 100
8 //边结点的类型定义
9 typedef struct edgenode
10 {
11     int adjvex;//存放邻接的点在顶点表的下标，邻接点
12     struct edgenode *next;//指向Vi下一个邻接点的边结点
13     int weight;/*权值*/
14 }edgenode;
15 //顶点结点类型定义
16 typedef struct vexnode
17 {
18     elemtype data; //存储顶点的名称或其相关信息
19     edgenode *firstedge;//边表头指针
20 }vexnode;
21 //图的邻接表数据类型
22 typedef struct{
23     vexnode vexlist[maxsize];//顶点表
24     int n,e;
25 }graph;
26 //在图g中查找顶点v,存在顶点数组中的下标，不存在返回-1
27 int locatevex(graph g,elemtype v)
28 {
29     int i;
30     for(i=0;i
31         if(g.vexlist[i].data==v)return i;
32     return -1;
33 }
34 //打印图信息
35 void print(graph g)
36 {
37     int i;
38     edgenode *p;
39     printf("图的邻接表表示：");
40     for(i=0;i
41         printf("\n%4c",g.vexlist[i].data);
42         p=g.vexlist[i].firstedge;
43         while(p!=NULL){
44             printf("-->%d",p->adjvex);p=p->next;
45         }
46     }
47     printf("\n");
48 }
49 void creategraph(graph *g){
50     int i,j,k;
51     elemtype v1,v2;
52     edgenode *s;
53     printf("请输入图的顶点数及边数\n");
54     printf("顶点数 n=");scanf("%d",&g->n);
55     printf("边  数 e=");scanf("%d",&g->e);
56     printf("请输入图的顶点信息：\n");getchar();
57     for(i=0;i<=g->n;i++){
58         scanf("%c",&g->vexlist[i].data); //构造顶点信息
59         g->vexlist[i].firstedge=NULL;
60     }
61     printf("请输入图的边的信息：\n");
62     for(k=0;ke;k++)
63     {
64         printf("请输入第%d条边的两个端点下标：",k+1);
65         scanf("%c%c",&v1,&v2);getchar();//输入一条边的两个顶点
66         i=locatevex(*g,v1);
67         j=locatevex(*g,v2);
68         if(i>=0&&j>=0){
69         //建立无向图的邻接表
70         /*s=(edgenode *)malloc(sizeof(edgenode));
71         s->adjvex=j;
72         s->next=g->vexlist[i].firstedge;
73         g->vexlist[i].firstedge=s;
74
75         s=(edgenode *)malloc(sizeof(edgenode));
76         s->adjvex=i;
77         s->next=g->vexlist[j].firstedge;
78         g->vexlist[j].firstedge=s;*/
79             //建立有向图的邻接表
80             s=(edgenode *)malloc(sizeof(edgenode));
81             s->adjvex=j;
82             s->next=g->vexlist[i].firstedge;
83             g->vexlist[i].firstedge=s;
84         }
85     }
86 }
87 int visited[maxsize];/* 访问标志数组*/
88  /*从第i个顶点出发递归地深度优先遍历图G*/
89 void DFS(graph g,int i)
90 {
91     edgenode *p;
92     printf("%3c",g.vexlist[i].data);/*访问第i个项点*/
93     visited[i]=1;
94     p=g.vexlist[i].firstedge;
95     while(p!=NULL)    {
96         if(visited[p->adjvex]==0)
97           DFS(g,p->adjvex);/*对i的尚未访问的邻接顶点j递归调用DFS*/
98         p=p->next;
99     }
100 }
101 void DFStraverse(graph  g) /*对图G进行深度优先遍历*/
102 {
103     int v;
104     for (v=0; v
105     for  (v=0; v
106 /*从第v个顶点出发递归地深度优先遍历图G*/
107         if (!visited[v])DFS(g,v);
108 }
109 //循环队列存储结构定义
110 typedef struct  cirqueue
111 {
112     elemtype  *data;      //队列存储空间的首地址
113     int front;         //队头位置：指向当前队头元素
114     int rear;    //队尾位置：指向当前队尾元素的下一位置
115 }cirqueue;             // 循环队列
116 //构造空队，如果成功，返回1，如果失败，返回0
117 int initqueue(cirqueue *q)
118 {
119     q->data=(elemtype *)malloc(queuesize*sizeof(cirqueue));
120     if (q->data==NULL)return 0; // 存储分配失败
121     q->front=q->rear=0;
122     return 1;
123  }
124 // 插入元素e为Q的新的队尾元素 ,如果成功，返回1，如果失败，返回0
125 int enqueue (cirqueue *q,elemtype e)
126 {
127     if ((q->rear+1) % queuesize == q->front)
128         return 0; //队列满
129     q->data[q->rear] = e;
130     q->rear = (q->rear+1) % queuesize; //队尾后移一位
131     return 1;
132 }
133 //若队列不空，则删除Q的队头元素，用e返回其值,并返回1；否则返回0
134 int dequeue (cirqueue *q,int *e)
135 {
136     if (q->front == q->rear)  return 0; //队列为空
137     *e = q->data[q->front];
138     q->front = (q->front+1) %queuesize; //队头后移一位
139     return 1;
140 }
141 //若栈不空，则用e返回队头元素,并返回1；否则返回0
142 int getfront(cirqueue q,elemtype *e)
143 {
144     if (q.front == q.rear)  return 0; //队列为空
145     *e=q.data[q.front];
146     return  1;
147  }
148 //若队列为空栈，则返回1，否则返回0
149 int queueempty(cirqueue q)//栈非空
150 {
151     if(q.front == q.rear)return 1; //队列为空
152     else return 0;
153 }
154 //返回队列的元素个数，即队列的长度
155 int queuelength(cirqueue q)
156 {
157     return (q.rear-q.front+queuesize) % queuesize;
158 }
159 //【算法6-10：利用邻接矩阵实现连通图的广度优先搜索遍历】
160 int BFSvisited[maxsize];
161 cirqueue q;
162 /*从第k个顶点出发广度优先遍历图G,G以邻接矩阵表示。*/
163 void BFS(graph g,int k){
164     int i;
165     edgenode *p;
166     initqueue(&q);/*初始化队列*/
167     printf("%3c",g.vexlist[k].data);/*访问第k个项点*/
168     visited[k]=1;
169     enqueue(&q,k);/*第k个顶点进队*/
170     while(queueempty(q)==0) {/*队列非空*/
171         dequeue(&q,&i);
172         p=g.vexlist[i].firstedge;/*获取第1个邻接点*/
173         while(p!=NULL){
174             if(visited[p->adjvex]==0){
175                 /*访问第i个顶点的末曾访问的顶点*/
176                 printf("%3c",g.vexlist[p->adjvex].data);
177                 visited[p->adjvex]=1;
178                 enqueue(&q,p->adjvex);/*第k个顶点进队*/
179             }
180             p=p->next;
181         }
182     }
183 }
184 void BFStraverse(graph  g) //对图G进行广度优先遍历
185 {
186     int v;
187     for (v=0; v
188         visited[v]=0;
189     for  (v=0; v
190         if (!visited[v])BFS(g,v);
191        //从第v个顶点出发递归地深度优先遍历图G
192 }
193 int main()
194 {
195     graph g;
196     creategraph(&g);
197     print(g);
198     printf("\n");
199     printf("图的深度优先遍历序列：\n");
200     DFStraverse(g);
201     printf("\n");
202     printf("图的广度优先遍历序列：\n");
203     BFStraverse(g);
204     printf("\n");
205     return 0;
206 }
本文由职坐标整理并发布，希望对同学们有所帮助。了解更多详情请关注职坐标编程语言C/C+频道！

收起

展开全文

有向图的邻接表的建立，深度遍历并输出（c语言实现有向网）

千次阅读 2019-03-25 01:25:33

图的邻接表表示法（c语言实现有向网） [ ]为方便理解。首先先为图的邻接表画一个模型，邻接表可以分为两部分（1.表头节点，2.弧节点）如上图，因为写的代码是有向网，所以选择上图，首先在脑海里建立一个模型 ...

有向图的邻接表的建立，深度遍历并输出（c语言实现有向网）

[ ]为方便理解。 首先先为图的邻接表画一个模型，
邻接表可以分为两部分（1.表头节点，2.弧节点）
如上图，因为写的代码是有向网，所以选择上图，首先在脑海里建立一个模型
代码如下

#include<stdio.h>
#include<stdlib.h>
int visited[20]; //顶点的访问标志 
 
//*邻接表用两部分表示  1顶点节点包含（data firstarc） 2弧节点包含(adjvex, *next weigh) 
typedef enum {DG/*有向图*/,DN/*有向网*/,UDG/*无向图*/,UDN/*无向网*/} GraphKind;

typedef struct ArcNode{
	int adjvex;//该弧指向顶点的位置 
  struct ArcNode *next;//指向下一条弧的指针 
	int  weigh;//弧的权值 
}ArcNode;


typedef struct vertexNode{ 
	int data;//顶点数据 
	 ArcNode * firstarc;//指向该顶点第一条弧的指针 
}vertexNode; 

typedef struct{
	vertexNode vertex[20];
	int vexnum;
	int arcnum;//图的顶点数量和弧的数量 
	//GraphKind kind；//图的种类 
} AdjList; 

int creat(AdjList *a)
{
	int i,j,n;
	int sum;//sum和arcnum一样代表图中总的弧数 
	ArcNode *p1,*p2,c;
	printf("请输入图顶点的总个数和弧的总个数\n");
	scanf("%d %d",&a->vexnum,&a->arcnum);
	sum=a->arcnum; 
	for(i=0;i<a->vexnum;i++)
    	a->vertex[i].firstarc=NULL;//初始化和顶点第一个相邻的弧为空; 
	for(i=0;i<a->vexnum;i++)
	{
	 	
	printf("***请输入第%d个顶点的值***\n",i);
	scanf("%d",&a->vertex[i].data);
	 if(sum==0) continue;
	printf("请输入和本顶点相关弧的个数\n");
	scanf("%d",&n); 
	 
	for(j=0;j<n;j++)
	{
		if(j==0)
		{

		  int q;
			p1=p2=( ArcNode*)malloc(sizeof(ArcNode));
			//p1=p2=&c;
			p1->next=p2->next=NULL;
			a->vertex[i].firstarc=p1;
			printf("请输入与第%d个顶点相邻的，第%d个相邻的弧顶点(位置) 以及弧的权值\n",i,j);
			scanf("%d %d",&p1->adjvex,&p1->weigh);
			//printf("%d %d",p1->adjvex,p2->weigh);	
			sum--;		 			 
		}
		else{
			p2=(ArcNode*)malloc(sizeof(ArcNode));
			p2->next=NULL;
			p1->next=p2;
			printf("请输入第%d个顶点 第%d个相邻的弧顶点 以及两个顶点间弧的权值\n",i,j);
			scanf("%d %d",&p2->adjvex,&p2->weigh);	
			sum--;		
		}
		
	}
	printf("**************************\n");
	
		
	}
}

void print( AdjList a)//输出矩阵 
{
    int i,j;
    for(i=0;i<a.vexnum;i++)
    {
    	ArcNode *p;
    	p=a.vertex[i].firstarc;
    	printf(" [%d]",a.vertex[i].data);
    	
        while(p)
        {
        	printf("----->");
        	printf("[%d %d]",p->adjvex,p->weigh);
        	p=p->next; 
        
		}
        
    	printf("\n");
	}
	
}
void traverseGraph( AdjList a){//深度优先遍历图 
     int i,j;
     for(i=0;i<a.vexnum;i++)
     visited[i]=0;//标志全部顶点为访问
	 for(i=0;i<a.vexnum;i++)
	 {
	 	if(!visited[i]) 
	 	DepthFirstSearch(a,i); 
	 } 
	
}

int  DepthFirstSearch(AdjList a,int i){
	ArcNode *p;
	printf(" %d",a.vertex[i].data);
	visited[i]=1;
	p=a.vertex[i].firstarc;
	while(p)
	{
		if(!visited[p->adjvex])
		DepthFirstSearch(a,p->adjvex); 
		p=p->next; 
	}
	
}
int main()
{   AdjList a;

      creat(&a);
      print(a);//邻接表形式输出图
      printf("***深度遍历图***\n");
	  traverseGraph(a); //深度优先遍历图

 } 

测试了下

收起

展开全文

c语言邻接表的构建_C++实现有向图邻接表的构建
2021-01-14 00:24:27
本文实例为大家分享了C++实现有向图邻接表的构建代码，供大家参考，具体内容如下数据结构里面的一道基础题，分享下自己的写法，验证可跑。#include#includeconst int MAX = 20;using namespace std;struct ArcNode {...
收起
数据结构 c语言 有向图和无向图邻接表的建立、插入、和删除操作
千次阅读 多人点赞 2020-05-05 16:12:00
c语言实现数据结构中有向图和无向图邻接表的建立、插入、删除操作
收起
数据结构算法指针
c语言实现无向图的邻接表储存
万次阅读 多人点赞 2016-03-02 21:46:51
图有一种邻接表储存结构，这里以无向图为例，输入图的参数，构造并输出图的邻接表。 #include #include #define MAX_VERTEX_NUM 100 typedef struct ArcNode{ int adjvex;//该边的另一个顶点的位置 struct ...
收起
数据结构
c语言邻接表的构建_邻接表无向图(一)之 C语言详解
2021-02-01 01:27:28
本章介绍邻接表无向图。在"图的理论基础"中已经对图进行了理论介绍，这里就不再对图的概念进行重复说明了。... 邻接表无向图的介绍2. 邻接表无向图的代码说明3. 邻接表无向图的完整源码转载请注明出处：http://ww...
收起
C语言利用图的邻接表的存储方式实现求有向图的入度和出度以及无向图的度数
千次阅读 多人点赞 2018-11-11 16:51:16
编写程序，输入图的类型（0：无向图，1：有向图）、图中顶点数、边数、边的偶对，建立图的邻接表。如果是无向图，计算并输出每个顶点的度；如果是有向图，计算并输出每个顶点的的入度和出度。 Input 输入：图的...
收起
邻接表存储的有向图的基本操作(C语言实现)
2019-03-23 01:48:14
NULL 博文链接：https://touch-2011.iteye.com/blog/1070798
收起
c语言实现图的邻接表存储方式
2019-11-23 09:21:07
有向图的邻接表实现初学图的邻接表存储方式，费了很多的时间去理解它。走了很多弯路，终于用代码上实现了这个存储结构，在这里把的感悟和过程做个总结，希望能帮到和我一样的初学者。对于以下这个图它的邻接表...
收起
邻接表有向图(一)之 C语言详解
2014-05-12 09:29:00
本章介绍邻接表有向图。在"图的理论基础"中已经对图进行了理论介绍，这里就不再对图的概念进行重复说明了。和以往一样，本文会先给出C语言的实现；后续再分别给出C++和Java版本的实现。...3. 邻接表有向图的完整...
收起
数据结构——无向图创建邻接表以及深度遍历、广度遍历（C语言版）
2020-12-22 20:55:12
对无向图的每个顶点vi建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对于有向图则是以顶点vi为尾的弧）。这个单链表就称为顶点vi的边表（对于有向图则称为出边表）边表的头指针和顶点的数据信息采用...
收起
数据结构单链表
数据结构图的基本操作c语言_C语言：数据结构-图的存储结构-邻接表
2020-11-29 08:33:39
邻接表(adjacency list)是对图中的每个顶点建立一个邻接关系的单链表，并把它们的表头指针用向量存储的一种图的表示方法。...对于有向图来说，等于vi的出边数、或出边邻接点数或出度数。边结点通...
收起
【数据结构】图的存储结构之邻接表（C语言）
2020-07-08 20:29:08
我们把数组与链表相结合的存储方法称为邻接表（Adjacency List）。邻接表的处理办法是这样的：图中顶点用一个一维数组存储，当然顶点也可以用单链表来存储，不过...如图1-1就是一个无向图的邻接表结构。图1-1. 从图
收起
指针链表数据结构
数据结构（C语言）-07-图-由依次输入的顶点数目，弧数目，和各个弧信息建立有向图的邻接表
千次阅读 2018-08-19 23:34:19
int LocateVex(AdjList G,VertexData x)/求顶点位置函数*/ { int j=0,k; for(k=0;kvexnum,k++) if(G-vertex[k]==x) ...int CreatDN(AdjList G)/创建一个有向图*/ { int i,j,k;...
收起
数据结构
数据结构-图的创建(邻接矩阵，邻接表)C语言实现
千次阅读 2020-06-04 18:54:59
有向图：在有向图中，顶点对<V,W>是有序的，表示它从V到W的一条有向边。所以，<W,V>表示的和<V,W>不同的边，顶点的指向不同。有向图中顶点对用尖括号表示<>，<x,y>
收起
数据结构链表单链表指针
邻接表无向图(一)之 C语言详解
2014-05-08 17:20:00
本章介绍邻接表无向图。在"图的理论基础"中已经对图进行了理论介绍，这里就不再对图的概念进行重复说明了。和以往一样，本文会先给出C语言的实现；后续再分别给出C++和Java版本的实现。...3. 邻接表无向图的完整...
收起
数据结构——邻接矩阵转邻接表（C语言）
2020-10-09 15:59:56
将无向图的邻接矩阵存储转换为对应的邻接表存储思路：遍历邻接矩阵，将有各个顶点关联的边所对应的顶点存储到邻接表所对应的顶点表的边表上，并连接起来。 #include<stdio.h> #include<stdlib.h> #...
收起
数据结构 c语言实现无向图邻接多重表的建立、插入、删除
多人点赞 2020-05-07 11:57:54
ps: 1.部分内容我设置了隐藏，...这次的内容主要难点在删除吧，因为邻接多重表的结构，每个结点都有两个指针指向他所以要分别找到这两个结点，让他们的后续指针跳过删除的结点下面直接上代码吧 #include<stdio...
收起
数据结构算法指针链表
无向图加权邻接矩阵怎么存储_C语言：数据结构-图的存储结构-邻接矩阵
2021-01-13 14:23:02
它有多种表示方法，这里主要介绍邻接矩阵、邻接表和边集数组这三种方法邻接矩阵邻接矩阵(adjacency matrix)是表示图形中顶点之间相邻关系的矩阵。设G=(V,E)是具有n个顶点的图，顶点序号依次为0、1、2、…、n-1，则G...
收起