欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C语言数据结构与算法---图的存储结构(邻接矩阵、邻接表)

程序员文章站 2023-12-25 18:13:57
...

一. 邻接矩阵

数组表示法

1. 无向图

图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

C语言数据结构与算法---图的存储结构(邻接矩阵、邻接表)
有 n 个顶点,则邻接矩阵是一个 n*n 的方阵

C语言数据结构与算法---图的存储结构(邻接矩阵、邻接表)

  • 完全图的邻接矩阵,对角元素为0,其余为1
  • 对角线上是自身与自身间,没有连接关系;
  • 无向图的边数组是一个对称矩阵;
  • 顶点的度:这个顶点 Vi 在邻接矩阵中第 i 行(或第 j 列)元素之和。如V1的度为 0+1+0+1+0 = 2
  • 求顶点 Vi 的邻接点就是将第 i 行元素扫描一遍,arc[i][j] 为 1 就是邻接点

2. 有向图

C语言数据结构与算法---图的存储结构(邻接矩阵、邻接表)

  • 主对角线数值依然为 0 ,矩阵不对称
  • 第 i 行:以结点 Vi 为尾的弧(出度边)
  • 第 i 列:以结点 Vi 为头的弧(入度边)
  • 顶点 Vi 的入度 = 第 i 列数之和;
  • 顶点 Vi 的出度 = 第 i 行数之和。
    如:V1 的度为 3(入列出行)
  • 求顶点 Vi 的邻接点就是将第 i 行元素扫描一遍,arc[i][j] 为 1 就是邻接点

3. 网图

权图:C语言数据结构与算法---图的存储结构(邻接矩阵、邻接表)
这里“∞”表示一个计算机允许的、大于所有边上权值的值。 是一个不可能的极限值
C语言数据结构与算法---图的存储结构(邻接矩阵、邻接表)

4. 邻接矩阵的建立

结构:

#define MAXWEX 100  //最大顶点数
#define INFINITY 65535 //表示∞

typedef struct
{
	char vesx[MAXWEX];  //顶点表
	int arc[MAXWEX][MAXWEX];  //邻接矩阵(边表)
	int numv;  //顶点数
	int nume;  //边数
}MGraph;

建立无向网的邻接矩阵
算法思想:
C语言数据结构与算法---图的存储结构(邻接矩阵、邻接表)

void CreateMGraph(MGraph* G)
{
	int i, j, k, w;
	printf("请分别输入顶点数和边数:\n");
	scanf("%d %d",&G->numv,&G->nume);
	//读入顶点信息
	for (i = 0; i < G->numv; i++)
	{
		scanf("%c",&G->vesx[i]);
	}
	
	for (i = 0; i < G->nume; i++)
	{
		for (j = 0; j < G->nume; j++)
		{
			G->arc[i][j] = INFINITY;  //初始化为∞
		}	
	}

	//建立邻接矩阵
	for (k = 0; k < G->nume; k++)
	{
		printf("请输入边(Vi,Vj)的下标i,j,和权值w:\n");
		scanf("%d %d %d", &i, &j, &w);
		G->arc[i][j] = w;
		G->arc[i][j] = G->arc[j][i];  //无向图矩阵对称
	}
}
  1. 构造无向图时只需:
  • 初始化邻接矩阵时,w = 0;
  • 构造邻接矩阵时,w = 1;
  1. 构造有向网时只需:
  • 仅为G->arc[i][j]赋值,无需使G->arc[i][j] = G->arc[j][i]
  1. 构造有向图时只需同时满足1、2

5. 邻接矩阵的优劣

好处:
C语言数据结构与算法---图的存储结构(邻接矩阵、邻接表)
坏处:

C语言数据结构与算法---图的存储结构(邻接矩阵、邻接表)
时间复杂度:n个顶点e条边创建O(n+n²+e) ,初始化 O(n²)

二. 邻接表

数组与链表相结合

邻接表表示法

  • 顶点用一个一维数组存储,每个数据还需要存储指向第一个邻接点的指针
  • 每个顶点的所有邻接点构成一个单链表
    • 无向图称为顶点 Vi 的边表,有向图称为顶点 Vi 作为弧尾的出边表
      C语言数据结构与算法---图的存储结构(邻接矩阵、邻接表)

1.无向图

C语言数据结构与算法---图的存储结构(邻接矩阵、邻接表)特点:

  1. 邻接表不唯一
  2. 若无向图中有 n 个顶点、e 条边,则其邻接表需 n 个头结点和 2e 个表结点
  3. 无向图中顶点 Vi 的为第 i 个单链表中结点数

2.有向图

把顶点当弧尾建立的邻接表,这样很容易就可以得到每个顶点的出度

C语言数据结构与算法---图的存储结构(邻接矩阵、邻接表)
有时为了便于确定顶点的入度或以顶点为弧头的弧,也可以建立一个有向图的逆邻接表

3.网图

在边表结点定义中再增加一个数据域来存储权值即可

4. 邻接表的建立

结构:

//边表结点
typedef struct EdgeNode
{
	int adjvex;  //该顶点对应的下标
	int weight;  //权值,非网图不需要
	struct EdgeNode* next; //指向下一个邻接点
}EdgeNode;

//顶点表结点
typedef struct VertexNode
{
	char data; //存储顶点信息
	EdgeNode* fistedge; //边表头指针
}VertexNode,AdjList[MAXWEX];

typedef struct
{
	AdjList adjList;  //顶点表
	int nume;  //图中当前边数
	int numv;  //图中当前顶点数
}GraphAdjList;

无向图领接表的建立:

void CreateALGraph(GraphAdjList* G)
{
	int i, j, k;
	EdgeNode* e; //边表结点
	printf("请分别输入顶点数和边数:\n");//若有权值,可在加入 w
	scanf("%d %d",&G->numv,&G->nume);
	//读入顶点信息
	for (i = 0; i < G->numv; i++)
	{
		scanf("%c", &G->adjList[i].data); //输入顶点信息
		G->adjList[i].fistedge = NULL;    //边表置为空表
	}

	//建立边表
	for (k = 0; k < G->nume; k++)
	{
		printf("请输入边(Vi,Vj)上的顶点序号:\n");
		scanf("%d %d", &i, &j);

		//类似于头插法
		e = (EdgeNode*)malloc(sizeof(EdgeNode));
		e->adjvex = j;   //邻接序号为 j -> i 指向的顶点的下标
		//e->weight = w;//存储该边的权值
		e->next = G->adjList[i].fistedge;  //将 e 的指针指向当前顶点指向的结点
		G->adjList[i].fistedge = e;   //将当前顶点是指针指向 e
		//对于无向图而言,对称的
		e = (EdgeNode*)malloc(sizeof(EdgeNode));
		e->adjvex = i;    //邻接序号为 i -> j 指向的顶点的下标
		//e->weight = w;//存储该边的权值
		e->next = G->adjList[j].fistedge;  //将 e 的指针指向当前顶点指向的结点
		G->adjList[j].fistedge = e;   //将当前顶点是指针指向 e
	}
}

邻接表的遍历:

//不能传指针,防止遍历时改变原来结构
void PrintGraphAdjList(GraphAdjList G)
{
	for (int i = 0; i < G.numv; i++)
	{
		EdgeNode* p = G.adjList[i].fistedge;
		printf("该顶点为 %c:\n", G.adjList[i].data);
		while (p)
		{
			printf("(%c,%c),权值为 %d \n", G.adjList[i].data, G.adjList[p->adjvex].data, p->weight);
			p = p->next;
		}
		printf("\n");
	}
}

时间复杂度:n个顶点e条边 O(n+e)

5. 邻接表的优劣

C语言数据结构与算法---图的存储结构(邻接矩阵、邻接表)

三. 邻接矩阵与邻接表的关系

  1. 邻接表中每个链表对应于邻接矩阵中的第一行,链表中结点的个数等于一行中非零元素的个数
  2. 对于任意图,邻接矩阵是唯一的,但是邻接表不唯一(连接次序与顶点编号无关)
  3. 邻接矩阵空间复杂度:O(n²);邻接表的空间复杂度是: O(n+e)
  4. 邻接矩阵多用于稠密图;邻接表多用于稀疏图

上一篇:

下一篇: