图的邻接矩阵和邻接表存储
目录
邻接矩阵存储法
简介
编辑
邻接矩阵举例
无向图邻接矩阵
有向图邻接矩阵
当各条边带有权值时
邻接矩阵算法实现
结构体定义和函数声明
函数的实现
邻接表存储法
简介
邻接表的算法实现
结构体定义和函数声明
函数的实现
邻接矩阵和邻接表的差别
邻接矩阵存储法
简介
邻接矩阵是表示顶点之间邻接关系的矩阵，图的邻接矩阵存储使用两个数组来 表示图，一个一维数组存储图中的顶点信息，一个二维数组存储图中的边的信息。
邻接矩阵举例
无向图邻接矩阵
有向图邻接矩阵
当各条边带有权值时
邻接矩阵算法实现
结构体定义和函数声明
#define GRAPHMATRIXUTIL_H_
//图的邻接矩阵表示
typedef struct GRAPHMATRIX_STRU
{
int size;//图中结点个数
int** graph;//二维数组保存图
}GraphMatrix;
//初始化图
GraphMatrix* InitGraph(int num);//num 图中结点个数 用邻接矩阵表示图
//将数据读入图
void ReadGraph(GraphMatrix* graphMatrix);//graphMatrix 图
//将图的结构显示
void WriteGraph(GraphMatrix* graphMatrix);
函数的实现
#define _CRT_SECURE_NO_WARNINGS
#include "graphmatrixutil.h"
#include<stdlib.h>
#include<stdio.h>
GraphMatrix* InitGraph(int num)
{
int i;
int j;
GraphMatrix* graphMatrix = (GraphMatrix*)malloc(sizeof(GraphMatrix));
graphMatrix->size = num;//图中结点个数
//给图分配空间
graphMatrix->graph = (int**)malloc(sizeof(int*) * graphMatrix->size);
for (i = 0; i < graphMatrix->size; i++)
{
graphMatrix->graph[i] = (int*)malloc(sizeof(int) * graphMatrix->size);
}
//给图中所有元素设置初值
for (i = 0; i < graphMatrix->size; i++)
{
for (j = 0; j < graphMatrix->size; j++)
{
graphMatrix->graph[i][j] = INT_MAX;//INT_MAX是C语言中的常量，表示最大的整数
}
}
return graphMatrix;
}
//将数据读入图，输入方式：点 点 权值，如果权值为0，则输入结束
void ReadGraph(GraphMatrix* graphMatrix)
{
int vex1, vex2, weight;
printf("请输入，输入方式：点 点 权值，如果权值为0，则输入结束");
scanf("%d%d%d", &vex1, &vex2, &weight);
while (weight != 0)
{
graphMatrix->graph[vex1][vex2] = weight;
scanf("%d%d%d", &vex1, &vex2, &weight);
}
}
//将图的结构显示出来，输出方式为：点，点，权值
void WriteGraph(GraphMatrix* graphMatrix)
{
int i, j;
printf("图的结构如下：输出方式为：点，点，权值\n");
for (i = 0; i < graphMatrix->size; i++)
{
for (j = 0; j < graphMatrix->size; j++)
{
if (graphMatrix->graph[i][j] < INT_MAX)
{
printf("%d %d %d\n", i, j, graphMatrix->graph[i][j]);
}
}
}
}
邻接表存储法
简介
邻接表的算法实现
结构体定义和函数声明
#define GRAPHLISTUTIL_H
typedef struct GRAPHLISTNODE_STRU
{
int nodeno;//图中结点的编号
struct GRAPHLISTNODE_STRU* next;//指向下一个结点的指针
}GraphListNode;
typedef struct GRAPHLIST_STRU
{
int size;//图中结点的个数
GraphListNode* graphListArray;//图的邻接表
}GraphList;
//初始化图
GraphList* InitGraph(int num);
//读图
void ReadGraph(GraphList* graphList);
void WriteGraph(GraphList* graphList);
函数的实现
#define _CRT_SECURE_NO_WARNINGS
#include "graphlistutil.h"
#include<stdlib.h>
#include<stdio.h>
//初始化
GraphList* InitGraph(int num)
{
int i;
GraphList* graphList = (GraphList*)malloc(sizeof(GraphList));
graphList->size = num;
graphList->graphListArray = (GraphListNode*)malloc(sizeof(GraphListNode) * num);
for (i = 0; i < graphList->size; i++)
{
graphList->graphListArray[i].next = NULL;
graphList->graphListArray[i].nodeno = i;
}
return graphList;
}
//将数据读入图,输入方式：点 点，点为-1结束
void ReadGraph(GraphList* graphList)
{
int vex1, vex2;
GraphListNode* tempNode = NULL;
printf("请输入：输入方式：点 点，点为-1结束\n");
scanf("%d%d", &vex1, &vex2);
while (vex1 >= 0 && vex2 >= 0)
{
tempNode = (GraphListNode*)malloc(sizeof(GraphListNode));
tempNode->nodeno = vex2;
tempNode->next = NULL;
//寻找到要插入结点的地方，为了方便放在头部
tempNode->next = graphList->graphListArray[vex1].next;
graphList->graphListArray[vex1].next = tempNode;
scanf("%d%d", &vex1, &vex2);
}
}
//图结构显示
void WriteGraph(GraphList* graphList)
{
int i;
GraphListNode* tempNode = NULL;
for (i = 0; i < graphList->size; i++)
{
tempNode = graphList->graphListArray[i].next;
while (tempNode != NULL)
{
printf("结点%d和%d相连\n", i, tempNode->nodeno);
tempNode = tempNode->next;
}
}
}
邻接矩阵和邻接表的差别
