用邻接表和邻接矩阵分别表示图
时间: 2023-09-21 15:09:03 浏览: 47
邻接表是一种表示图的数据结构,它使用链表的形式来表示每个顶点的邻居节点。具体来说,对于每个顶点,用一个节点来表示它,并将它所有的邻居节点连接成一个链表。这种方式可以有效地表示稀疏图,因为只有存在边的节点才会被存储在链表中。邻接表可以用数组和链表来实现。
邻接矩阵则是使用二维数组来表示图的连接情况。二维数组的每个元素表示的是两个顶点之间是否存在边,如果存在边则对应元素的值为1,否则为0。如果是有向图,则邻接矩阵不一定是对称的。邻接矩阵可以用一个二维数组来表示,其中第i行第j列的元素表示第i个节点到第j个节点是否有边相连。这种方式可以有效地表示稠密图,因为每个节点都需要存储它到其他节点的连接情况。
相关问题
c语言用邻接表和邻接矩阵分别表示图并输出每个节点的度代码
邻接表表示图并输出每个节点的度的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大结点数
typedef struct ArcNode { // 弧结点类型
int adjvex; // 邻接点在顶点数组中的下标
struct ArcNode* next; // 指向下一个邻接点的指针
} ArcNode;
typedef struct VertexNode { // 顶点类型
char data; // 顶点信息
ArcNode* firstarc; // 指向第一个邻接点的指针
} VertexNode, AdjList[MAX_VERTEX_NUM];
typedef struct Graph { // 图类型
AdjList vertices; // 顶点数组
int vexnum, arcnum; // 顶点数、弧数
} Graph;
// 初始化图
void InitGraph(Graph* G) {
G->vexnum = G->arcnum = 0;
for (int i = 0; i < MAX_VERTEX_NUM; ++i) {
G->vertices[i].data = '\0';
G->vertices[i].firstarc = NULL;
}
}
// 添加结点
void AddVertex(Graph* G, char ch) {
G->vertices[G->vexnum].data = ch;
++G->vexnum;
}
// 添加边
void AddEdge(Graph* G, int v1, int v2) {
ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = v2;
p->next = G->vertices[v1].firstarc;
G->vertices[v1].firstarc = p;
++G->arcnum;
}
// 输出每个结点的度
void PrintDegree(Graph* G) {
for (int i = 0; i < G->vexnum; ++i) {
int degree = 0;
ArcNode* p = G->vertices[i].firstarc;
while (p) {
++degree;
p = p->next;
}
printf("结点%c的度为%d\n", G->vertices[i].data, degree);
}
}
int main() {
Graph G;
InitGraph(&G);
AddVertex(&G, 'A');
AddVertex(&G, 'B');
AddVertex(&G, 'C');
AddVertex(&G, 'D');
AddEdge(&G, 0, 1);
AddEdge(&G, 0, 2);
AddEdge(&G, 1, 2);
AddEdge(&G, 2, 0);
AddEdge(&G, 2, 3);
AddEdge(&G, 3, 3);
PrintDegree(&G);
return 0;
}
```
邻接矩阵表示图并输出每个节点的度的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_VERTEX_NUM 100 // 最大结点数
typedef struct Graph { // 图类型
char vexs[MAX_VERTEX_NUM]; // 顶点数组
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vexnum, arcnum; // 顶点数、弧数
} Graph;
// 初始化图
void InitGraph(Graph* G) {
G->vexnum = G->arcnum = 0;
memset(G->arcs, 0, sizeof(G->arcs));
}
// 添加结点
void AddVertex(Graph* G, char ch) {
G->vexs[G->vexnum] = ch;
++G->vexnum;
}
// 添加边
void AddEdge(Graph* G, int v1, int v2) {
G->arcs[v1][v2] = 1;
++G->arcnum;
}
// 输出每个结点的度
void PrintDegree(Graph* G) {
for (int i = 0; i < G->vexnum; ++i) {
int degree = 0;
for (int j = 0; j < G->vexnum; ++j) {
if (G->arcs[i][j]) {
++degree;
}
}
printf("结点%c的度为%d\n", G->vexs[i], degree);
}
}
int main() {
Graph G;
InitGraph(&G);
AddVertex(&G, 'A');
AddVertex(&G, 'B');
AddVertex(&G, 'C');
AddVertex(&G, 'D');
AddEdge(&G, 0, 1);
AddEdge(&G, 0, 2);
AddEdge(&G, 1, 2);
AddEdge(&G, 2, 0);
AddEdge(&G, 2, 3);
AddEdge(&G, 3, 3);
PrintDegree(&G);
return 0;
}
```
邻接表法和邻接矩阵法存储图
邻接表法和邻接矩阵法是两种常见的图的存储方式。
邻接表法:邻接表法是通过链表的方式来存储图的连接关系。对于无向图,每个节点的链表中存储的是与该节点相邻的节点;对于有向图,每个节点的链表中存储的是该节点的出边所指向的节点。邻接表法一般用于稀疏图的存储,因为它可以节省存储空间。
邻接矩阵法:邻接矩阵法是通过二维数组来存储图的连接关系。对于无向图,矩阵中第 i 行第 j 列的元素表示节点 i 和节点 j 是否相邻;对于有向图,矩阵中第 i 行第 j 列的元素表示从节点 i 到节点 j 是否存在一条有向边。邻接矩阵法一般用于稠密图的存储,因为它可以快速地判断两个节点是否相邻。
邻接表法和邻接矩阵法各有优缺点,具体选择哪种存储方式,需要根据具体的应用场景来决定。