【数据结构】图的快速入门

🐋作者简介：博主是一位.Net开发者，同时还是RPA和低代码平台的践行者。
🐬个人主页：会敲键盘的肘子
🐰系列专栏：数据结构与算法
🦀专栏简介：图解经典算法，C#代码实现，算法升级版。
🐶座右铭：总有一天你所坚持的会反过来拥抱你。

🌈写在前面：

本文主要介绍了图的基本概念、表示方式和快速入门案例。

---

活动地址：CSDN21天学习挑战赛

👉本文关键字：数据结构、无向图、有向图、带权图、邻接矩阵、邻接表、C#

1️⃣ 背景

♈ 为什么要有图这种数据结构？

线性表和树的局限性

• 线性表局限于一个直接前驱和一个直接后继的关系。

• 树只能有一个直接前驱也就是父节点。

所以当我们需要表示多对多的关系时， 这里我们就用到了图。

2️⃣ 图的基本概念

♈ 概念

图是一种数据结构，其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。

♉ 顶点、边、路径

图中A、B、C、D、E表示顶点；

连接顶点的线条表示边；

路径: 比如从 D -> C 的路径有

1. D->B->C
2. D->A->B->C

♊ 无向图

如上图，边上没有指向箭头的图称为无向图。

♋ 有向图

如图，边上有指向箭头的图称为有向图。

♌ 带权图

这种边带权值的图也叫网。

3️⃣ 图的表示方式

图的表示方式有两种：二维数组表示（邻接矩阵）；链表表示（邻接表）。

♈ 邻接矩阵

邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵是的row和col表示的是1....n个点。

说明:
标号为A的结点的相关联结点为 B，顾第一行 0 1 0 0 0，不关联的置为0；
标号为B的结点的相关联结点为 C D，顾第一行 0 0 1 1 0，不关联的置为0；
…

♉ 邻接表

邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在，会造成空间的一定损失。
邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成。

说明:
标号为0的结点的相关联结点为 1 3 4
标号为1的结点的相关联结点为 0 2 3
标号为2的结点相关联的结点为 1 3 4
…

4️⃣ 图的代码实现

	public class Graph
    {
        private List vertexList; //存储顶点集合
        private int[,] edges; //存储图对应的邻结矩阵
        private int numOfEdges; //表示边的数目
        private bool[] isVisited;//定义给数组boolean[], 记录某个结点是否被访问

		//构造器
		public Graph(int n)
		{
			//初始化矩阵和vertexList
			edges = new int[n,n];
			vertexList = new List(n);
			numOfEdges = 0;

		}

		//图中常用的方法
		//返回结点的个数
		public int getNumOfVertex()
		{
			return vertexList.Count;
		}
		//得到边的数目
		public int getNumOfEdges()
		{
			return numOfEdges;
		}
		//返回结点i(下标)对应的数据 0->"A" 1->"B" 2->"C"
		public String getValueByIndex(int i)
		{
			return vertexList[i];
		}
		//返回v1和v2的权值
		public int getWeight(int v1, int v2)
		{
			return edges[v1,v2];
		}
		//插入结点
		public void insertVertex(string vertex)
		{
			vertexList.Add(vertex);
		}
		//添加边
		/**
		 * 
		 * @param v1 表示点的下标即使第几个顶点  "A"-"B" "A"->0 "B"->1
		 * @param v2 第二个顶点对应的下标
		 * @param weight 表示 
		 */
		public void insertEdge(int v1, int v2, int weight)
		{
			edges[v1,v2] = weight;
			edges[v2,v1] = weight;
			numOfEdges++;
		}
	}	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

---

⭐写在结尾：

文章中出现的任何错误请大家批评指出，一定及时修改。

希望看在这里的小伙伴能给个三连支持！