1.图相关概念

图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
注意：
(1)线性表中我们把数据元素叫元素，树中将数据元素叫结点，在图中的数据元素叫做顶点；
(2)线性表中可以没有数据元素，称为空表，树中没有结点，称为空树，但是，在图中，不允许没有顶点；
(3)线性表中，相邻数据元素之间具有线性关系，树结构中，相邻两层的结构具有层次关系，但是在图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。

1.1 无向图

如图中，顶点A到B之间的边没有方向，则称这条边为无向边，用无序偶对(A,B)来表示。如果图中任意两个顶点之间的边都是无向边，则该图为无向图，上述图就是一个无向图，由于是无方向的，连接顶点A与D的边，可以表示成无序对(A,D)，也可以写成(D,A)。
对于上述的无向图G来说，G=(V,{E})，其中顶点集合V={A,B,C,D}；边集合E={(A,B),(B,C),(C,D),(D,A),(A,C)}。

1.2 有向图

如图中，顶点A到B之间的边有方向，则称这条边为有向边，也称为弧，用有序偶对来表示。B称为弧尾，A称为弧头。
如果图中任意两个顶点之间的边都是有向边，则该图为有向图，上图就是一个有向图。连接顶点A与D的有向边就是弧，A是弧尾，D是弧头，表示弧，不能写成。
对于上述的有向图G来说，G=(V,{E})，其中顶点集合V={A,B,C,D}；边集合E={,,,}。
注意：
无向图(边)用“()”表示，有向图(弧)用“<>”表示。

1.3 其他类型图

在图中，如果不存在顶点到其自身的边，且同一条边不重复出现，这样的图称为简单图。
在无向图中，如果任意两个顶点之间都存在边，这种图称为无向完全图。
有很少条边或弧的图称为稀疏图，反之称为稠密图。
有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权，这些权可以表示从一个顶点到另一个顶点的距离或耗费，这种带权的图通常称为网。

1.4 图的边数

无向完全图的边数为n*(n-1)/2
有向完全图的弧数为n*(n-1)

2. 图的存储结构

2.1 邻接矩阵和邻接表

邻接矩阵：邻接就是顶点到顶点，其存储方式是用两个数组来表示，一个一维数组来存储图中的顶点信息，一个二维数组来存储图中的边或者弧的信息。
也就是上图中a的邻接顶点有3个，分别为b,c,d，b的邻接顶点有2个，分别为a,c，c的邻接顶点有3个，分别为a,b,d，d的邻接顶点有2个，分别为a,c。
一维数组表示顶点信息，二维数组表示边信息，即：
vertex[4]，说明有4个顶点。
Edge[0][1] =1，说明下标为0的顶点到下标为1的顶点右边。
邻接表：将顶点存入数组，并对顶点与其连接的顶点进行链式存储，这种数组与链表相结合的存储方法称为邻接表。
一维数组存储顶点，链表存储当前顶点相关连的边。

2.2 邻接矩阵的相关代码实现

2.1中的图的邻接矩阵为：

#define SIZE 10
class Graph
{
private:
	int MaxVertex;//顶点的最大个数
	int NumVertex;//顶点的实际个数
	char* Vertex;//存储顶点的一维数组
	int Edge[SIZE][SIZE];//int **Edge  存储顶点边的信息，即一条边
	int NumEdge;//边的实际条数
public:
	Graph();//对private的属性进行初始化
	~Graph();
	void InsertVertex(char v);//插入顶点
	void InsertEdge(char v1,char v2);//插入顶点v1到顶点v2的边
	void PrintGraph();//打印图
	int GetVertexIndex(char v);//获得顶点v在顶点数组中的下标
	void DelVertex(char v);//删除顶点
	void DelEdge(char v1,char v2);//删除边
};
Graph::Graph()
{
	MaxVertex = SIZE;
	NumVertex = NumEdge = 0;
	Vertex = new char[MaxVertex];
	for (int i = 0; i < MaxVertex; i++)
	{
		for (int j = 0; j < MaxVertex; j++)
		{
			Edge[i][j] = 0;
		}
	}
}
Graph::~Graph()
{
	if (Vertex != nullptr)
	{
		delete[]Vertex;
		Vertex = nullptr;
	}

}
void Graph::InsertVertex(char v)
{
	if (NumVertex >= MaxVertex)
	{
		return;
	}
	Vertex[NumVertex++] = v;
}
int Graph::GetVertexIndex(char v)
{
	int i;
	for (i = 0; i < NumVertex; i++)
	{
		if (v == Vertex[i])
		{
			return i;
		}
	}
	return -1;
}
void Graph::DelEdge(char v1, char v2)
{
	int p1 = GetVertexIndex(v1);
	int p2 = GetVertexIndex(v2);
	if (p1 == -1 || p2 == -1)
	{
		return;
	}
	Edge[p1][p2] = Edge[p2][p1] = 0;
	NumEdge--;
}
void Graph::InsertEdge(char v1, char v2)
{
	int p1 = GetVertexIndex(v1);
	int p2 = GetVertexIndex(v2);
	if (p1 == -1 || p2 == -1)
	{
		return;
	}
	//将p1和p2所对应的二维数组的值改为1，说明两个顶点之间有边。
	Edge[p1][p2] = Edge[p2][p1] = 1;
	NumEdge++;
}
void Graph::DelVertex(char v)
{
	int vindex = GetVertexIndex(v);
	if (vindex == -1)
	{
		return;
	}
	int DelEdge = 0;
	//计算和当前顶点A相关联的边数
	for (int i = 0; i < NumVertex; i++)
	{
		if (Edge[vindex][i] == 1)
		{
			DelEdge++;
		}
	}
	//将顶点数组中要删除的顶点后面的前移
	for (int i = 0; i < NumVertex - 1; i++)
	{
		Vertex[i] = Vertex[i + 1];
	}
	//左移  行不动，移动列
	for (int i = vindex; i < NumVertex - 1; i++)//列
	{
		for (int j = 0; j < NumVertex; j++)//行
		{
			Edge[j][i] = Edge[j][i + 1];
		}
	}
	//上移  列不动，移动行
	for (int i = vindex; i < NumVertex - 1; i++)//行
	{
		for (int j = 0; j < NumVertex - 1; j++)//列
		{
			Edge[i][j] = Edge[i+1][j];
		}
	}
	NumVertex--;
	NumEdge = NumEdge - DelEdge;

}
void Graph::PrintGraph()
{
	int i, j;
	cout << "  ";
	for (i = 0; i < NumVertex; i++)
		cout << Vertex[i] << " ";
		cout << endl;

	for (i = 0; i < NumVertex; ++i)
	{
		cout << Vertex[i] << " ";
		for (j = 0; j < NumVertex; j++)
			cout << Edge[i][j] << " ";
			cout << endl;

	}
}
int main()
{
	Graph g;
	//插入顶点
	g.InsertVertex('a');
	g.InsertVertex('b');
	g.InsertVertex('c');
	g.InsertVertex('d');
	//插入边
	g.InsertEdge('a', 'b');
	g.InsertEdge('a', 'c');
	g.InsertEdge('a', 'd');
	g.InsertEdge('b', 'c');
	g.InsertEdge('c', 'd');
	//打印图
	g.PrintGraph();

	g.DelEdge('a', 'c');
	g.PrintGraph();

	g.DelVertex('a');
	g.PrintGraph();
	return 0;
}
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166

运行结果：

注意：其中的代码比较简单，就是在删除顶点的时候注意——删除顶点也就是顶点数组和边数组都要发生变化
首先，计算和当前顶点相关联的边，DelEdge
其次，对一维数组和二维数组进行操作：方法一：覆盖；方法二：移动

2.3 邻接表的相关代码实现