建立图(dg/dn/udg/udn)的邻接矩阵/邻接表。
时间: 2023-12-26 12:01:45 浏览: 67
邻接矩阵是用二维数组来表示图中各个顶点之间的连接关系的数据结构。对于有向图(dg)和无向图(udg),邻接矩阵都是一个n*n的矩阵,其中n表示图中顶点的个数。矩阵的每个元素a[i][j]表示顶点i到顶点j是否有边相连,如果有则为1,否则为0。
而邻接表是一种由单链表或者数组构成的数据结构,用于表示图中各个顶点的邻接关系。对于有向图(dg)和无向图(udg),邻接表的构建方式略有不同。对于有向图,邻接表中每个顶点都对应一个链表,链表中存储了该顶点指向的其他顶点;而对于无向图,邻接表中每个顶点也都对应一个链表,链表中存储了与该顶点相连的其他顶点。
邻接矩阵和邻接表都是用来表示图的连接关系的数据结构,它们各有优缺点。邻接矩阵在查找两个顶点之间的连接关系时更为高效,但是当图中边的数量较少时会浪费空间;而邻接表则更适合于表示稀疏图,节省了空间,但在查找两个顶点之间的连接关系时效率稍低。根据实际的使用情况,可以选择使用邻接矩阵或邻接表来表示图的连接关系。
相关问题
根据图的邻接表的类型定义,创建一个无向图,并输出该图 思路
根据图的邻接表的类型定义,创建一个无向图的步骤如下:
1. 定义一个邻接表类型的结构体变量,包括顶点集合、边集合、顶点数、边数和图的类型。
2. 读入顶点数和边数,并将其赋值给邻接表类型的结构体变量。
3. 读入每个顶点的值,并将其存储在邻接表类型的结构体变量的顶点集合中。
4. 读入每条边的信息,包括起点、终点和权值(如果有),并将其存储在邻接表类型的结构体变量的边集合中。
5. 根据边集合中的信息,构建每个顶点的邻接表,将邻接表存储在邻接表类型的结构体变量的顶点集合中。
6. 输出邻接表类型的结构体变量,即可得到创建的无向图。
下面是一个示例代码,用于创建一个无向图并输出该图:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 20 /*最大顶点数*/
typedef enum{DG,DN,UDG,UDN} GraphKind; /*有向图,有向网,无向图,无向网*/
typedef struct ENode /*表结点类型*/
{
int adjvex;
struct ENode *nextarc;
int weight;
}ENode;
typedef int VexType;
typedef struct VNode /*头结点类型*/
{
VexType vex;
ENode *firstarc;
}VNode, AdjList[MAXVEX]; /*邻接表类型定义*/
typedef struct {
AdjList vertices; /*用邻接表存储顶点集合及边集合*/
int vexnum,edgenum;
GraphKind kind;
}ALGraph; /*邻接表存储的图的类型定义*/
void CreateGraph(ALGraph *G)
{
int i, j, k, w;
ENode *e;
printf("请输入顶点数和边数:");
scanf("%d%d", &G->vexnum, &G->edgenum);
printf("请输入顶点信息:");
for (i = 0; i < G->vexnum; i++)
{
scanf("%d", &G->vertices[i].vex);
G->vertices[i].firstarc = NULL;
}
printf("请输入边信息:");
for (k = 0; k < G->edgenum; k++)
{
printf("请输入第%d条边的起点和终点:", k + 1);
scanf("%d%d", &i, &j);
e = (ENode*)malloc(sizeof(ENode));
e->adjvex = j;
e->nextarc = G->vertices[i].firstarc;
G->vertices[i].firstarc = e;
e = (ENode*)malloc(sizeof(ENode));
e->adjvex = i;
e->nextarc = G->vertices[j].firstarc;
G->vertices[j].firstarc = e;
}
}
void PrintGraph(ALGraph G)
{
int i;
ENode *p;
printf("该无向图的邻接表为:\n");
for (i = 0; i < G.vexnum; i++)
{
printf("%d: ", G.vertices[i].vex);
p = G.vertices[i].firstarc;
while (p != NULL)
{
printf("%d ", G.vertices[p->adjvex].vex);
p = p->nextarc;
}
printf("\n");
}
}
int main()
{
ALGraph G;
CreateGraph(&G);
PrintGraph(G);
return 0;
}
```
#include "stdlib.h" #include "stdio.h" #include "malloc.h" #define INFINITY 32767 #define MAX_VERTEX_NUM 20 typedef enum{FALSE,TRUE}visited_hc; typedef enum{DG,DN,UDG,UDN}graphkind_hc; typedef struct arccell_hc {int adj; int *info; }arccell_hc,adjmatrix
抱歉,代码片段似乎不完整,而且缺少一些关键的部分。但是,我可以为您提供一些有关图的基本知识和一些代码实现的建议。
在代码片段中,似乎定义了一个邻接矩阵的结构体,其中adj表示边的权重,info表示边的其他信息。此外,还定义了一个枚举类型graphkind_hc,表示图的类型(有向图、有向网、无向图、无向网)。
在这个基础上,可以定义一个图的结构体,包含顶点数组、边数组(邻接矩阵或邻接表)、顶点数、边数、图的类型等信息。
例如,可以定义一个邻接矩阵表示的有向图的结构体如下:
```
typedef struct {
int vex[MAX_VERTEX_NUM];
arccell_hc arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum,arcnum;
graphkind_hc kind;
}MGraph;
```
其中,vex是顶点数组,arcs是邻接矩阵,vexnum表示顶点数,arcnum表示边数,kind表示图的类型。
接下来,可以实现一些基本的图操作函数,如创建图、遍历图、查找图中的路径等。
例如,下面是一个创建有向图的函数:
```
void CreateDG(MGraph *G) {
int i,j,k,w;
printf("请输入顶点数和边数:");
scanf("%d%d",&G->vexnum,&G->arcnum);
printf("请输入顶点信息:");
for(i=0;i<G->vexnum;i++) {
scanf("%d",&G->vex[i]);
}
for(i=0;i<G->vexnum;i++) {
for(j=0;j<G->vexnum;j++) {
G->arcs[i][j].adj=INFINITY;
G->arcs[i][j].info=NULL;
}
}
printf("请输入边信息:");
for(k=0;k<G->arcnum;k++) {
printf("请输入第%d条边的起点、终点和权重:",k+1);
scanf("%d%d%d",&i,&j,&w);
G->arcs[i][j].adj=w;
}
G->kind=DG;
}
```
该函数首先从用户输入中获取顶点数和边数,然后依次输入顶点信息和边信息,并构建邻接矩阵表示的有向图。
接下来是一个深度优先遍历的函数:
```
void DFS(MGraph G,int v,visited_hc *visited) {
int i;
visited[v]=TRUE;
printf("%d ",G.vex[v]);
for(i=0;i<G.vexnum;i++) {
if(G.arcs[v][i].adj!=INFINITY && !visited[i]) {
DFS(G,i,visited);
}
}
}
```
该函数从指定顶点v开始,依次遍历与之相邻的未访问过的顶点,直到所有顶点都被访问过。
类似地,可以实现广度优先遍历、查找图中的最短路径等操作。以此类推,可以根据具体的需求来实现更多的图操作函数。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![.rar](https://img-home.csdnimg.cn/images/20210720083646.png)