无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。
有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。 
含有n个顶点的无向完全图有n×(n-1)/2条边。
含有n个顶点的有向完全图有n×(n-1)条边。
顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD (v)。
顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID (v)；
顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD (v)。
在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系：
在具有n个顶点、e条边的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？与边数之和的关系：
回路（环）：第一个顶点和最后一个顶点相同的路径。
简单路径：序列中顶点不重复出现的路径。
简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。
子图：若图G=（V，E），G'=（V'，E'），如果: V'ÍV 且E' Í E ，则称图G'是G的子图。
连通图：在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。
连通分量：非连通图的极大连通子图称为连通分量。
一个n个顶点的连通无向图，其边的个数至少为（ n-1 ）
因为它如果是个树的话，边就最少了
连通（Connected）
无向图中的连通：在无向图中，如果任意两个顶点之间存在一条路径，那么这个图就是连通的。即从一个顶点出发，可以通过边访问到任何其他顶点。
有向图中的连通：在有向图中，如果从任意两个顶点中的一个可以通过有向边到达另一个，那么这两个顶点是连通的。但需要注意，这并不意味着整个图是连通的，仅是针对特定的顶点。
强连通（Strongly Connected）
有向图中的强连通：在有向图中，如果图中的每一对顶点 都能相互到达，那么这个图是强连通的。强连通要求顶点之间的路径是双向的。
对于无向图，强连通的概念并不适用，因为无向图的每条边本身就是双向的，通常直接称为“连通”。
总结
- 连通：在无向图中，任意两个顶点都有路径相连；在有向图中，特定的两个顶点之间有一条路径。
- 强连通：仅适用于有向图，表示任意两个顶点之间既可以从一个到达另一个，也可以从另一个到达前者。
要连通具有n个顶点的有向图，至少需要（ n-1 ）条边。
只要连通就行，不用强连通。所以画个单边的树就行
由握手定理知A正确，
在无向图中，握手定理表述为：所有顶点的度数之和等于边数的 2 倍。
通俗来讲，假如把图中的顶点看成是人，边看成是两个人握手，那么每个人握手的次数（即顶点的度数）加起来，就等于总的握手次数的 2 倍，因为每一条边（一次握手）会在两个顶点（两个人）的度数中各被计算一次。
BC错误，画个单边树，得到b错误，画个三角形得到c错误。
图的遍历
① 在图中，如何选取遍历的起始顶点？
在图中，任何两个顶点之间都可能存在边，顶点是没有确定的先后次序的，所以，顶点的编号不唯一。为了定义操作的方便，将图中的顶点按任意顺序排列起来，比如，按顶点的存储顺序。然后选取下标小的顶点
② 从某个起点始可能到达不了所有其它顶点，怎么办？
解决方案：多次调用从某顶点出发遍历图的算法。
③ 因图中可能存在回路，某些顶点可能会被重复访问，那么如何避免遍历不会因回路而陷入死循环?
解决方案：附设访问标志数组visited[n] 。
④ 在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点？
解决方案：深度优先遍历和广度优先遍历。
邻接矩阵的DFS和BFS：
#include<iostream>
using namespace std;
int visited[10] = { 0 };
class MGraph
{
public:
MGraph(char a[], int n, int e);
~MGraph() {};
void DFS(int v);
void BFS(int v);
private:
char vertex[10];
int edge[10][10];
int vertexNum, edgeNum;
};
MGraph::MGraph(char a[], int n, int e)
{
int i, j, k;
vertexNum = n;
edgeNum = e;
for (i = 0; i < vertexNum; i++)
vertex[i] = a[i];
for (i = 0; i < vertexNum; i++)
for (j = 0; j < vertexNum; j++)
edge[i][j] = 0;
for (k = 0; k < edgeNum; k++)
{
cin >> i >> j;
edge[i][j] = 1;
edge[j][i] = 1;
}
}
void MGraph::DFS(int v)
{
int j;
cout << vertex[v];
visited[v] = 1;
for(j =0;j<vertexNum;j++)
if (edge[v][j] == 1 && visited[j] == 0)
DFS(j);
}
void MGraph::BFS(int v)
{
cout << vertex[v];
visited[v] = 1;
int w, j, Q[10];
int front = -1, rear = -1;
Q[++rear] = v;
while (front != rear)
{
w = Q[++front];
for(j = 0;j<vertexNum;j++)
if (edge[w][j] == 1 && visited[j] == 0)
{
cout << vertex[j];
visited[j] = 1;
Q[++rear] = j;
}
}
}
int main()
{
int i;
char ch[] = { 'A','B','C','D','E' };
MGraph MG(ch, 5, 6);
for (i = 0; i < 10; i++)
visited[i] = 0;
cout << "深搜：" << endl;
MG.DFS(0);
for (i = 0; i < 10; i++)
visited[i] = 0;
cout << endl;
cout << "广搜" << endl;
MG.BFS(0);
}邻接表：
#include<iostream>
using namespace std;
int visited[10] = { 0 };
struct EdgeNode
{
int adjvex;
EdgeNode* next;
};
struct VertexNode
{
char vertex;
EdgeNode* firstEdge;
};
class ALGraph
{
public:
ALGraph(char a[], int n, int e);
~ALGraph() ;
void DFS(int v);
void BFS(int v);
private:
VertexNode adjlist[10];
int vertexNum, edgeNum;
};
ALGraph::ALGraph(char a[], int n, int e)
{
int i, j, k;
EdgeNode* s = nullptr;
vertexNum = n;
edgeNum = e;
for (i = 0; i < vertexNum; i++)
{
adjlist[i].vertex = a[i];
adjlist[i].firstEdge = nullptr;
}
for (k = 0; k < edgeNum; k++)
{
cin >> i >> j;
s = new EdgeNode;
s->adjvex = j;
s->next = adjlist[i].firstEdge;
adjlist[i].firstEdge = s;
}
}
ALGraph::~ALGraph()
{
EdgeNode* p = nullptr, * q = nullptr;
for (int i = 0; i < vertexNum; i++)
{
p = q = adjlist[i].firstEdge;
while (p != nullptr)
{
p = p->next;
delete q;
q = p;
}
}
}
void ALGraph::DFS(int v)
{
int j;
EdgeNode* p = nullptr;
cout << adjlist[v].vertex;
visited[v] = 1;
p = adjlist[v].firstEdge;
while (p != nullptr)
{
j = p->adjvex;
if (visited[j] == 0)
DFS(j);
p = p->next;
}
}
void ALGraph::BFS(int v)
{
int w, j, Q[10];
int front = -1, rear = -1;
EdgeNode* p = nullptr;
cout << adjlist[v].vertex;
visited[v] = 1;
Q[++rear] = v;
while (front != rear)
{
w = Q[++front];
p = adjlist[w].firstEdge;
while (p != nullptr)
{
j = p->adjvex;
if (visited[j] == 0)
{
cout << adjlist[j].vertex;
visited[j] = 1;
Q[++rear] = j;
}
p = p->next;
}
}
}
int main()
{
int i;
char ch[] = { 'A','B','C','D','E' };
ALGraph ALG(ch, 5, 6);
ALG.DFS(0);
for (i = 0; i < 10; i++)
visited[i] = 0;
cout << endl;
ALG.BFS(0);
}