什么是图?定义与基本概念,邻接矩阵C语言示例代码

2022-07-1716:34:25数据结构与算法Comments731 views字数 1294阅读模式

1. 什么是图文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

图论(graph theory) 是数学的一个分支,它以 图 为研究的对象。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

图论本身是应用数学的一部分,历史上图论曾经被很多数学家各自独立建立过。关于图论的最早文字记载最早出现在欧拉 1736 年的论著中,也就是著名的柯尼斯堡(Konigsberg)问题(七桥问题)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

2. 图的定义文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

一个图G是一个二元组,即序偶<V,E>,或记作G=<V,E> ,其中V是有限非空集合,称为G的顶点集,V中的元素称为顶点或结点;E称为 G的边的集合,所有的边ei都属于E,都有v中的结点与之对应,称ei为 G的边。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

3. 图的基本概念文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

l  无向图:每条边都是无向边的图。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

l  有向图:每条边都是有向边的图。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

l  混合图:在一个图中,有些边是有向边,另一些边是无向边,则该图为混合图。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

l  有限图:一个图的点集和边集都是有穷集的图。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

l  零图:边集为空集的图。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

l  平凡图:仅有一个结点而没有边构成的图。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

l  关联:若有ei=(u,v) 且ei属于E ,则称u是和v相关联的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

l  孤立点:无边关联的点。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

l  自环:若一条边所关联的两个结点重合,则称此边为自环。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

l  邻接:关联于同一条边的两个点  和  称为邻接的;关联于同一个点的两条边  和  是邻接的(或相邻的)。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

4.两个定理:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

什么是图?定义与基本概念,邻接矩阵C语言示例代码文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

l  推论:在任意图中,度数为奇数的点必然有偶数个。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

什么是图?定义与基本概念,邻接矩阵C语言示例代码文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

l  推论:即所有点入度之和等于出度之和。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

(这个比较好理解,就如同问世界上的上坡多还是下坡多一样,答案是一样多)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

由上面的概念可知,树或者是森林,就是一种特殊的图。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

5. 最简单的存储——邻接矩阵文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

邻接矩阵的英文名是 adjacency matrix。它的形式是 bool adj[n][n],这里面n是节点个数,adj[i][j]表示i和j之间是否有边。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

如果边有权值,也可以直接用 int adj[n][n] ,直接把边权存进去。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

它的优点是可以在O(1)时间内得到一条边是否存在,缺点是需要占用O(n^2)的空间。对于一个稀疏的图(边相对于点数的平方比较少)来说,用邻接矩阵来存储的话,成本偏高。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

其代码可以表示为(假设各边长度均为1):文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
 
using namespace std;
 
const int maxn=105;
int adj[maxn][maxn]={0};    //定义邻接矩阵
 
int x,y;    //输入两条边
int n,m;    //供输入n对边 ,m个顶点 (x,y <= m) 
 
int main(){
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        adj[x-1][y-1]=1;
        adj[y-1][x-1]=1;
    }
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            cout<<adj[i][j]<<' ';
        }
        cout<<endl;
    }
    return 0;
}
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25196.html
  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/25196.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定