昆明网站设计电话,帮忙网页设计师,网站建设负责传资料不,在线制作图片免费的软件无向完全图#xff1a;在无向图中#xff0c;如果任意两个顶点之间都存在边#xff0c;则称该图为无向完全图。
有向完全图#xff1a;在有向图中#xff0c;如果任意两个顶点之间都存在方向相反的两条弧#xff0c;则称该图为有向完全图。
含有n个顶点的无向完全图有…无向完全图在无向图中如果任意两个顶点之间都存在边则称该图为无向完全图。
有向完全图在有向图中如果任意两个顶点之间都存在方向相反的两条弧则称该图为有向完全图。
含有n个顶点的无向完全图有n×(n-1)/2条边。
含有n个顶点的有向完全图有n×(n-1)条边。 顶点的度在无向图中顶点v的度是指依附于该顶点的边数通常记为TD (v)。
顶点的入度在有向图中顶点v的入度是指以该顶点为弧头的弧的数目记为ID (v)
顶点的出度在有向图中顶点v的出度是指以该顶点为弧尾的弧的数目记为OD (v)。 在具有n个顶点、e条边的无向图G中各顶点的度之和与边数之和的关系 在具有n个顶点、e条边的有向图G中各顶点的入度之和与各顶点的出度之和的关系与边数之和的关系 回路环第一个顶点和最后一个顶点相同的路径。
简单路径序列中顶点不重复出现的路径。
简单回路简单环除了第一个顶点和最后一个顶点外其余顶点不重复出现的回路。 子图若图GVEGVE如果: 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
#includeiostream
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;jvertexNum;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;jvertexNum;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);
}
邻接表
#includeiostream
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);
}
