图论基础
2024-08-14 09:23:21
发布于:浙江
图论基础
概念:
是由一种由顶点和边组成的数据结构,其中顶点代表图中的对象,边代表他们之间的关系。
顶点: 是图当中的基本单元,代表一个实体或者一个抽象概念
边: 顶点之间的连线,代表顶点之间的关系。
图的种类:
无向图: 由着没有方向的边所组成的图,边代表了两个顶点之间的双向关系,也被称之为是无向网络或者无向图形。
有向图: 由有方向的边组成的图,被称之为是有向网络或有向图形,有向边会从一个顶点指向另一个顶点,代表一个方向的关系。 (在有向图当中,顶点也被称之为起点或者终点)。
带权图: 边带有权值的图叫做带权图。
权值: 经过边所需要的时间、金钱或者长度等计量数值。
自环: 一条边的起点和终点都是一个顶点
重边: 两个顶点之间存在多条起点终点相同的边。
多重图:有自环和重边的。
简单图:没有自环和重边。
度: 通常指一个顶点连接的边的总数.
无向图当中度指的就是这个顶点连接的边总数
有向图当中度分为入度和出度,入度保存以该顶点作为终点的边的总数,出度保存以该顶点作为起点的边的总数。
**路径:**一个顶点到达另一个顶点的连续边组成的序列
简单路径: 路径当中没有重复经过的顶点
**非简单路径:**路径当中有重复经过的顶点
路径长度: 经过了几个顶点的数量称之为是路径长度。
环路: 一条路径的起点和终点都是一个顶点,称之为是环路(顶点可重复)
简单环路: 环路上没有重复的顶点,除了起点和终点之外。
连通性: 图当中任意两点都存在路径,称之为连通图。
**完全图:**任意两点之间都存在边.
无向完全图必须包含n*(n-1) /2条边
有向完全图必须包含n*(n-1)条边
邻接矩阵
以二维数组G作为保存每两个顶点之间是否存在边/权值的做法。
通常以表示,其中i代表起点,j代表终点,假如点i与点j之间存在着一条边,那么,如果存在权值,那么,其余初始化为int类型最大值。
#include<bits/stdc++.h>
using namespace std;
int G[105][105]; // G来保存每两个顶点之间是否存在边
int main(){
int n,m;
cin >> n >> m ;
while(m--){
int u,v;
//输入起点和终点u和v
cin >> u >> v;
G[u][v] = 1;
}
for(int i = 1 ; i <= n ; i ++ ){
for(int j = 1 ; j <= n ; j ++ ){
// 输出每两个顶点之间的关系
cout << G[i][j] << " ";
}
cout << endl;
}
return 0;
}
全部评论 6
Yuilice牢失太师了太师了没入受
2024-08-14 来自 广东
2不是,哥们
2024-08-14 来自 浙江
1
Yuilice牢失太师了太师了没入受
2024-08-14 来自 浙江
26
2024-08-30 来自 浙江
0老师太强了
2024-08-14 来自 云南
064wl
2024-08-14 来自 云南
0
“盖可快去部署爆能器”
2024-08-14 来自 浙江
0🤓👍
2024-08-14 来自 浙江
0
有帮助,赞一个