精华内容
下载资源
问答
  • c语言写的有向图的邻接表的实现,通过使用图的邻接表实现图的存储结构存储。
  • 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++知识点有所帮助。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语言实现有向网) [ ]为方便理解。 首先先为图的邻接表画一个模型, 邻接表可以分为两部分(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++实现有向图邻接表的构建代码,供大家参考,具体内容如下数据结构里面一道基础题,分享下自己写法,验证可跑。#include#includeconst int MAX = 20;using namespace std;struct ArcNode {...
  • c语言实现数据结构中有向图和无向图邻接表的建立、插入、删除操作
  • c语言实现无向图的邻接表储存

    万次阅读 多人点赞 2016-03-02 21:46:51
    一种邻接表储存结构,这里以无向图为例,输入图的参数,构造并输出图的邻接表。 #include #include #define MAX_VERTEX_NUM 100 typedef struct ArcNode{ int adjvex;//该边的另一个顶点的位置 struct ...
  • 本章介绍邻接表无向图。在"图的理论基础"中已经对图进行了理论介绍,这里就不再对图的概念进行重复说明了。... 邻接表向图的介绍2. 邻接表向图的代码说明3. 邻接表向图的完整源码转载请注明出处:http://ww...
  • 编写程序,输入图的类型(0:无向图,1:有向图)、图中顶点数、边数、边的偶对,建立图的邻接表。如果是无向图,计算并输出每个顶点的度;如果是有向图,计算并输出每个顶点的的入度和出度。 Input 输入: 图的...
  • NULL 博文链接:https://touch-2011.iteye.com/blog/1070798
  • 有向图的邻接表实现 初学图的邻接表存储方式,费了很多的时间去理解它。走了很多弯路,终于用代码上实现了这个存储结构,在这里把的感悟和过程做个总结,希望能帮到和我一样的初学者。 对于以下这个图 它的邻接表...
  • 本章介绍邻接表有向图。在"图的理论基础"中已经对图进行了理论介绍,这里就不再对图的概念进行重复说明了。和以往一样,本文会先给出C语言的实现;后续再分别给出C++和Java版本的实现。...3. 邻接表有向图的完整...
  • 对无向图的每个顶点vi建立一个单链表,第i个单链表中的结点表示依附于顶点vi的边(对于有向图则是以顶点vi为尾的弧)。这个单链表就称为顶点vi的边(对于有向图则称为出边) 边的头指针和顶点的数据信息采用...
  • 邻接表(adjacency list)是对图中的每个顶点建立一个邻接关系的单链表,并把它们的表头指针用向量存储的一种图的表示方法。...对于有向图来说,等于vi的出边数、或出边邻接点数或出度数。边结点通...
  • 我们把数组与链表相结合的存储方法称为邻接表(Adjacency List)。 邻接表的处理办法是这样的: 图中顶点用一个一维数组存储,当然顶点也可以用单链表来存储,不过...如图1-1就是一个无向图的邻接表结构。 图1-1. 从图
  • 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;...
  • 有向图:在有向图中,顶点对<V,W>是有序,表示它从V到W一条有向边。所以,<W,V>表示和<V,W>不同边,顶点指向不同。有向图中顶点对用尖括号表示<>,<x,y>
  • 本章介绍邻接表无向图。在"图的理论基础"中已经对图进行了理论介绍,这里就不再对图的概念进行重复说明了。和以往一样,本文会先给出C语言的实现;后续再分别给出C++和Java版本的实现。...3. 邻接表向图的完整...
  • 将无向图的邻接矩阵存储转换为对应的邻接表存储 思路:遍历邻接矩阵,将各个顶点关联的边所对应的顶点存储到邻接表所对应的顶点表的边表上,并连接起来。 #include<stdio.h> #include<stdlib.h> #...
  • ps: 1.部分内容我设置了隐藏,...这次内容主要难点在删除吧,因为邻接多重表的结构,每个结点都两个指针指向他 所以要分别找到这两个结点,让他们后续指针跳过删除结点 下面直接上代码吧 #include<stdio...
  • 多种表示方法,这里主要介绍邻接矩阵、邻接表和边集数组这三种方法邻接矩阵邻接矩阵(adjacency matrix)是表示图形中顶点之间相邻关系矩阵。设G=(V,E)是具有n个顶点的图,顶点序号依次为0、1、2、…、n-1,则G...

空空如也

空空如也

1 2 3 4 5 6
收藏数 117
精华内容 46
关键字:

有向图的邻接表c语言

c语言 订阅