图论：具有至少两个顶点的简单无向图中一定存在度相同的结点

设有n个节点，则每个节点的度数只能取0，1，2，3，。。。，n-1，
因为如果某个点的度数取n，则一定存在自环或者重边。
下面分情况讨论：
1、如果存在大于等于2个节点度数为0，结论显然成立
2、如果仅存在1个节点度数为0，则剩余n-1个节点度数不能取n-1（否则存在自环或者重边），则由抽屉原理，n-1个节点度数在1，2，。。。，n-2这n-2个数中取，必然存在两个节点度数相等
3、如果不存在度数为0的节点，则n个节点的度数在1，2，。。。，n-1这n-1个数中取，由抽屉原理，必然存在两个节点度数相等

若无向图G =（V，E）中含7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是：
A.6
B.15
C.16
D.21

(n-1)*(n-2)/2+1

6 * 5/2+1=16

设无向图的顶点个数为N，则该图最多有多少条边？
A.N−1
B.N(N−1)/2
C.N(N+1)/2
D.N​2
​

用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。（F） (1分)

解析：使用邻接表占用空间与这个图是有向图还是无向图有关。

如果是无向图，那么空间就是n+2e;如果是有向图就是n+e。（n为节点数，e为边数）。

用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关==（T）==。 (1分)

解析：邻接矩阵G[x][y]表示x->y这条边的权重，因此n各节点需要两两组合，空间大小为n^2。

如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G中一定有回路。==（F） ==(2分)

解析：因为不论是bfs还是dfs我们在遍历的时候都进行了标记也就是当一个节点被标记了的时候这个节点就不会重复访问。

因此两次bfs才访问完所有的节点不是因为有回路而是因为这个图有两个连通分量。

如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G一定有2个连通分量。（T）

设N个顶点E条边的图用邻接表存储，则求每个顶点入度的时间复杂度为： (2分)
O(N)
O(N​2​​)
O(N+E)
O(N×E)

解析：邻接表求入度需要遍历整个邻接表也就是n+e，而求出度是n。

在N个顶点的无向图中，所有顶点的度之和不会超过顶点数的多少倍？ (2分)
1
2
(N−1)/2
N−1

解析：形成一棵树。

对于一个具有N个顶点的无向图，要连通所有顶点至少需要多少条边？ (2分)
N−1
N
N+1
N/2

具有N（N>0）个顶点的无向图至多有多少个连通分量？ (2分)
0
1
N−1
N

解析：无边

一个有N个顶点的强连通图至少有多少条边？ (2分)
N−1
N
N+1
N(N−1)

解析：无向图有n-1个即可，有向图需要加一个形成环。

对于有向图，其邻接矩阵表示比邻接表表示更易于： (2分)
求一个顶点的入度
求一个顶点的出边邻接点
进行图的深度优先遍历
进行图的广度优先遍历

https://blog.csdn.net/qq_43446165/article/details/102841019

一、文章说明:

1. C++语言实现；
2. 有向图的存储结构为: 邻接矩阵；
3. 这篇文章的代码是我根据B站UP主懒猫老师所写的，能成功运行，VS里面显示有很多警告。而且还可能存在有未调试出的BUG，请多多指教。
4. 观看懒猫老师的视频后，才方便理解博主代码，不然可能理解起来会很吃力。

二、 算法思想与实现思路:

请前往B站观看 up主 懒猫老师 的教学视频;
——附:老师思路清楚，并且通过形象的PPT动画来模拟算法实现过程，非常有利于理解整个算法过程！

视频链接:
1.算法思想:
懒猫老师-数据结构-(46)最短路径(Dijkstra算法，迪杰斯特拉算法，单源最短路径)

2.算法实现过程:
懒猫老师-数据结构-(47)最短路径(Dijkstra算法实现，迪杰斯特拉算法，单源最短路径)

三、3个核心函数:

1.迪杰斯特拉算法函数；

void Dijkstra(AMGraph g)
{
	int start;
	char c;
	cout << "请输入最小路径的源点:" << "\t";
	cin >> c;                                                
	start = g.Locate_vex(c);                                        //利用定位函数查找源点在顶点表当中的序号；

	//1.用动态分配的方式，为路径path， 路径权值dist, 算法思想中的S数组开辟空间。
	//注意这里path，dist,S数组单元的序号所对应的顶点和类 AMGraph中顶点表 vexs 所对应的顶点是一样的！

	int* path = new int[g.vexnum];                                  //空间大小为 图的顶点个数,vexnum;
	int* dist = new int[g.vexnum];
	int* S = new int[g.vexnum];


	//2. 初始化这三个数组；
	for (int i = 0; i < g.vexnum; i++)
	{
		dist[i] = g.arcs[start][i];
		if (dist[i] != Maxlnt) path[i] = start;
		else path[i] = -1;
	}

	for (int i = 0; i < g.vexnum; i++)
	{
		S[i] = 0;                                                    // 0代表未进入算法思想的S集合，1代表已经进入。
	}
	S[start] = 1;                                                    // 将源点加入S集合。
	int num = 1;                                                     //计数变量，循环控制条件;
	int min;

    //3. 正式进入算法，求源点到其它顶点的最短路径。
	while (num < g.vexnum)
	{
		min = findMinDist(dist, S, g.vexnum);                        //查找在当前顶点所邻接后继结点的边中，具有最小权值的后继结点的序号。
		S[min] = 1;
		for (int i = 0; i < g.vexnum; i++)                           //对路径数组path 和路径权值数组dist 进行更新。
		{
			if ((S[i] == 0) && (dist[i] > dist[min] + g.arcs[min][i]))
			{
				dist[i] = dist[min] + g.arcs[min][i];
				path[i] = min;
			}
		}
		num++;
	}
	displayPath(dist, path, start, g);
	delete[]path;
	delete[]dist;
	delete[]S;
}

2.findMinDist()函数;
函数功能:
查找当前结点与后继邻接顶点中具有最小权值的边，的邻接顶点的序号

int findMinDist(int dist[], int S[], int n)
{
	int MIN = Maxlnt + 1;
	int mark = -1;
	for (int i = 0; i < n; i++)
	{
		if (S[i] == 0)
		{
			if (dist[i] < MIN)
			{
				MIN = dist[i];
				mark = i;
			}
		}
	}
	return mark;
}

3. 路径输出函数displayPath();
函数功能:

• 一、如果对于除了源点的其它顶点，如果源点是可达该顶点的，则输出其的最小路径和权值
• 二、输出源点所到达不了的顶点，说明这源点和这个顶点之间不存在有最短路径。

void displayPath(int dist[], int path[], int start, AMGraph g)
{
	char* road = new char[g.vexnum];
	int number;                                      //number 用来表示源点到第i号顶点路径的长度；
	for (int i = 0; i < g.vexnum; i++)
	{
		int j = i;                                   //这里j可以从充当一个指针，一开始指向每条路径的终点。
		if (j != start && dist[j] != Maxlnt)         //注意这里j指向的终点必须是可达源点的，所以要加上判断条件 dist[j] 不可以等于无穷大 Maxlnt ;
		{
			number = -1;

			//1.利用while循环，从最短路径的终点向源点逐步衍生，逐步扩大road数组
			while (g.vexs[j] != g.vexs[start])        //当j 指向源点的时候，循环结束。
			{
				number++;
				road[number] = g.vexs[j];
				j = path[j];                          //j指向当前顶点的，前驱邻接顶点。
				if (j == start)                       //如果 j 指向源点了，将源点加入road 数组，数组中存储的就是逆序的路径了，number为路径的长度。
				{
					number++;
					road[number] = g.vexs[j];
				}
			}

			//2.利用for循环,将路径数组逆序输出即可得到 源点到第 i 号顶点的最小路径。
			cout << endl << g.vexs[start] << " to " << g.vexs[i] << " " << "路径权值:" << dist[i] << "\t" << "路径为: ";
			for (int k = number; k >= 0; k--)
			{
				if (k == 0)
				{
					cout << road[k] << endl;
				}
				else cout << road[k] << "—>";
			}
			cout << endl;
		}
	}

	//3.布尔变量adjust, 用来判断源点是否有到达不了的顶点, 如果有则利用for循环输出。
	bool adjust = true;
	for (int i = 0; i < g.vexnum; i++)
	{
		if (dist[i] == Maxlnt)
		{
			adjust = false;
			break;
		}
	}
	if (adjust == false)
	{
		cout << endl << "源点:" << g.vexs[start] << "到达不了的顶点为:" << "\t";
		for (int i = 0; i < g.vexnum; i++)
		{
			if (dist[i] == Maxlnt)
				cout << g.vexs[i] << "\t";
		}
		cout << endl << endl;
	}
	delete[]road;
}

四、完整代码:

说明: 为了更方便地调试程序，我将算法具体实现写成了一个小小系统的形式，
所以代码会比较冗长，注释也比较多，阅读起来可能很不舒适。

#include<iostream>
#include<string>
using namespace std;

#define Maxlnt 32767
#define MVNum 20
#define OK 1

class AMGraph
{
private:
	char vexs[MVNum];                              //顶点表;
	int arcs[MVNum][MVNum];                        //边表;
	int vexnum, arcnum;                            //点的数量和边的数量;
public:
	bool creat_graph();
	int Locate_vex(char c);                        //顶点定位函数,定位顶点在顶点表当中的数字；
	void print();                                  // 图的信息打印函数;

	friend void displayPath(int dist[], int path[], int start, AMGraph g); // 路径输出函数;
	friend void Dijkstra(AMGraph g);


};

int AMGraph::Locate_vex(char c)
{
	for (int i = 0; i < vexnum; i++)
	{
		if (c == vexs[i]) return i;
	}
	return -1;
}

bool AMGraph::creat_graph()
{
	cout << "请依次输入图的顶点数目和边数:" << "\t";
	cin >> vexnum >> arcnum;
	cout << endl << "请依次输入" << vexnum << "个顶点:" << "\t";
	for (int i = 0; i < vexnum; i++)
	{
		cin >> vexs[i];
	}
	for (int i = 0; i < vexnum; i++)
	{
		for (int j = 0; j < vexnum; j++)
		{
			if (i == j) arcs[i][j] = 0;
			else arcs[i][j] = Maxlnt;
		}
	}
	cout << endl;
	for (int k = 0; k < arcnum; k++)
	{
		char v1, v2;
		int w;
		cout << "请分别输入第" << k + 1 << "条有向边的起点，终点和权值:" << "\t";
		cin >> v1 >> v2 >> w;
		int i = Locate_vex(v1);
		int j = Locate_vex(v2);
		arcs[i][j] = w;
	}
	return OK;
}

void AMGraph::print()
{
	cout << endl << "顶点表的信息:" << endl;
	for (int i = 0; i < vexnum; i++)
	{
		cout << vexs[i] << " ";
	}
	cout << endl << endl;
	cout << "邻接矩阵的信息为:" << endl;

	// 这里for循环 从-1 开始打印邻接矩阵表格;
	for (int i = -1; i < vexnum; i++)
	{
		for (int j = -1; j < vexnum; j++)
		{
			//i=-1的时候, 需要输出边表中,  以i为起点的边所对应的终点;
			if (i == -1)
			{
				if (j == -1)cout << " " << "\t";
				else cout << vexs[j] << "\t";
				if (j == vexnum - 1) //换行条件控制
					cout << endl;
			}

			else
			{

				//j=-1的时候，需要输出边表中,  以j为终点的边所对应的起点: 
				if (j == -1)cout << vexs[i] << "\t";
				else
				{
					if (arcs[i][j] == Maxlnt)
						cout << "∞" << "\t";
					else cout << arcs[i][j] << "\t";
					if (j == vexnum - 1) //换行条件控制
						cout << endl;
				}
			}
		}
	}
}

int findMinDist(int dist[], int S[], int n)
{
	int MIN = Maxlnt + 1;
	int mark = -1;
	for (int i = 0; i < n; i++)
	{
		if (S[i] == 0)
		{
			if (dist[i] < MIN)
			{
				MIN = dist[i];
				mark = i;
			}
		}
	}
	return mark;
}

void displayPath(int dist[], int path[], int start, AMGraph g)
{
	char* road = new char[g.vexnum];
	int number;                                      //number 用来表示源点到第i号顶点路径的长度；
	for (int i = 0; i < g.vexnum; i++)
	{
		int j = i;                                   //这里j可以从充当一个指针，一开始指向每条路径的终点。
		if (j != start && dist[j] != Maxlnt)         //注意这里j指向的终点必须是可达源点的，所以要加上判断条件 dist[j] 不可以等于无穷大 Maxlnt ;
		{
			number = -1;

			//1.利用while循环，从最短路径的终点向源点逐步衍生，逐步扩大road数组
			while (g.vexs[j] != g.vexs[start])        //当j 指向源点的时候，循环结束。
			{
				number++;
				road[number] = g.vexs[j];
				j = path[j];                          //j指向当前顶点的，前驱邻接顶点。
				if (j == start)                       //如果 j 指向源点了，将源点加入road 数组，数组中存储的就是逆序的路径了，number为路径的长度。
				{
					number++;
					road[number] = g.vexs[j];
				}
			}

			//2.利用for循环,将路径数组逆序输出即可得到 源点到第 i 号顶点的最小路径。
			cout << endl << g.vexs[start] << " to " << g.vexs[i] << " " << "路径权值:" << dist[i] << "\t" << "路径为: ";
			for (int k = number; k >= 0; k--)
			{
				if (k == 0)
				{
					cout << road[k] << endl;
				}
				else cout << road[k] << "—>";
			}
			cout << endl;
		}
	}

	//3.布尔变量adjust, 用来判断源点是否有到达不了的顶点, 如果有则利用for循环输出。
	bool adjust = true;
	for (int i = 0; i < g.vexnum; i++)
	{
		if (dist[i] == Maxlnt)
		{
			adjust = false;
			break;
		}
	}
	if (adjust == false)
	{
		cout << endl << "源点:" << g.vexs[start] << "到达不了的顶点为:" << "\t";
		for (int i = 0; i < g.vexnum; i++)
		{
			if (dist[i] == Maxlnt)
				cout << g.vexs[i] << "\t";
		}
		cout << endl << endl;
	}
	delete[]road;
}

void Dijkstra(AMGraph g)
{
	int start;
	char c;
	cout << "请输入最小路径的源点:" << "\t";
	cin >> c;                                                
	start = g.Locate_vex(c);                                        //利用定位函数查找源点在顶点表当中的序号；

	//1.用动态分配的方式，为路径path， 路径权值dist, 算法思想中的S数组开辟空间。
	//注意这里path，dist,S数组单元的序号所对应的顶点和类 AMGraph中顶点表 vexs 所对应的顶点是一样的！

	int* path = new int[g.vexnum];                                  //空间大小为 图的顶点个数,vexnum;
	int* dist = new int[g.vexnum];
	int* S = new int[g.vexnum];


	//2. 初始化这三个数组；
	for (int i = 0; i < g.vexnum; i++)
	{
		dist[i] = g.arcs[start][i];
		if (dist[i] != Maxlnt) path[i] = start;
		else path[i] = -1;
	}

	for (int i = 0; i < g.vexnum; i++)
	{
		S[i] = 0;                                                    // 0代表未进入算法思想的S集合，1代表已经进入。
	}
	S[start] = 1;                                                    // 将源点加入S集合。
	int num = 1;                                                     //计数变量，循环控制条件;
	int min;

    //3. 正式进入算法，求源点到其它顶点的最短路径。
	while (num < g.vexnum)
	{
		min = findMinDist(dist, S, g.vexnum);                        //查找在当前顶点所邻接后继结点的边中，具有最小权值的后继结点的序号。
		S[min] = 1;
		for (int i = 0; i < g.vexnum; i++)                           //对路径数组path 和路径权值数组dist 进行更新。
		{
			if ((S[i] == 0) && (dist[i] > dist[min] + g.arcs[min][i]))
			{
				dist[i] = dist[min] + g.arcs[min][i];
				path[i] = min;
			}
		}
		num++;
	}
	displayPath(dist, path, start, g);
	delete[]path;
	delete[]dist;
	delete[]S;
}

void menu()
{
	cout << "****《迪杰斯特拉算法求最短路径》*****" << endl;
	cout << "**1. 图的建立" << endl;
	cout << "**2. 输出图的信息" << endl;
	cout << "**3. 求图的最短路径" << endl;
	cout << "**4. 退出" << endl;
	cout << "____________________________________________" << endl;
}

void deletescreen()
{
	system("pause");
	system("cls");
}

int main()
{
	void menu();
	void deletescreen();
	AMGraph g1;
	//menu();
	string choose;
	while (true)
	{
		menu();
		cin >> choose;
		if (choose == "1")
		{
			g1.creat_graph();
			cout << endl << "图建立成功！" << endl;
			deletescreen();
		}
		else if (choose == "2")
		{
			g1.print();
			deletescreen();
		}
		else if (choose == "3")
		{
			Dijkstra(g1);
			deletescreen();
		}
		else if (choose == "4")
		{
			cout << "退出成功！" << endl;
			exit(0);
		}
		else
		{
			cout << "输入有误！请重新输入" << endl;
			deletescreen();
		}
	}
	return 0;
}

五、测试情况:

测试一:

求图片中
1.源点为A到其它顶点的最小路径
2.源点为D到其它顶点的最小路径

测试结果:
1.建图

2.图的信息:

3.A到其它顶点的最小路径

4.D到其它顶点的最小路径

测试二:
1.测试案例:

2.求以 0 作为源点，到其它顶点的最短路径:

感谢你的收看，希望这可以帮助到你。