12.11数据结构-图

无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。

有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。  

含有n个顶点的无向完全图有n×(n-1)/2条边。

含有n个顶点的有向完全图有n×(n-1)条边。

顶点的度：在无向图中，顶点v的度是指依附于

顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID (v)；

顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD (v)。

该顶点的边数，通常记为TD (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);
}