一、点用边连起来就叫做图，严格意义上讲，图是一种数据结构，定义为：graph=（V，E）。V是一个非空有限集合，代表顶点（节点），E代表边的集合。（来自信息学奥赛一本通）
二、图的基础概念。
1、有向图：简单来说就是一条边只能从前点指向后点，而不能后点指向前点。
2、无向图：参照上面，一条边既能从前点指向后点，又能从后点指向前点。
3、节点的度：在无向图中，与节点相连的边的数目。
4、入度：以这个节点为终点的边的数目。
5、出度：以这个节点为起点的边的数目。
6、权值：简单来说就是边的长度。
7、连通：能从一个点通过边到达另一个点则称这两个点连通。
8、回路：图中存在起点和终点相同的路径则成为回路。
9、完全图：一个n阶的完全无向图含有n*（n-1）/2条边；一个n阶的完全有向图含有n*（n-1）条边。
稠密图：一个边数接近完全图的图。
稀疏图：一个边数远远少于完全图的图。
（这两个定义有点迷）
10、强连通分量：有向图中任意两点都连通的最大子图。特殊的，单个点也算一个强连通分量。
三、图的存储
1、邻接矩阵法
我们定义一个二维数组G[i][j]表示从i到j有一条权值为G[i][j]的边。
注意的几个点：
（1）开始要将数组初始化为无穷大表示无法到达。
（2）无向图要同时存储G[i][j]和G[j][i]这个是显而易见的。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int G[501][501],n; int main() { memset(G,0x7f,sizeof(G));//初始化数组 cin>>n;//边数 for(int k=1;k<=n;k++) { int i,j,w; cin>>i>>j>>w;//分别输入两点和边的权值 G[i][j]=w; G[j][i]=w;//有向图可去掉此行 } }
2、邻接表储存
这种是通过链表储存的，但大多只需要数组模拟即可。
这时代码其实就和链表很像了……
#include<iostream> #include<cstdio> #include<cstring> #define N 1001 #define M 100001 using namespace std; int head[N],num_edge,n,m; struct Edge { int next,to,dis;//next表示这条边的下一条边的编号，to表示终点，dis表示边的长度 }edge[M];//结构体 void add_edge(int from,int to,int dis) { edge[++num_edge].next=head[from]; edge[num_edge].to=to; edge[num_edge].dis=dis; head[from]=num_edge; } int main() { num_edge=0; cin>>n>>m; for(int k=1;k<=n;k++) { int i,j,w; cin>>i>>j>>w;//输入点和边的权值 add_edge(i,j,w); add_edge(j,i,w);//有向图可去掉 } /* 遍历 for(int i=head[i];i;i=edge[i].next) { …… } */ }