图论 一、什么是图 1、图是（vertex，node顶点和 边（edge）组成。 2、分类 （1）无向图（无指向） 例如：亲属关系，路程图 （2）有向图（边有指向） 例如：流程图 （3）带权图（边上带权值） 权值可表示时间、价值等 ———无向图 1、如果两顶点之间有边连接，那么视两顶点相邻，相邻结点的序列称为路径。起点和终点重合的称为圈。任意两点都有路径连接，称为连通。顶点连接的边数称为顶点的度。 2、没有圈的连通图称为树， ———有向图 1、以顶点为起点的边的集合的大小称为顶点的入度，为终点的大小为出度。没有圈的有向图称为DAG。 二、图的表示 1、邻接矩阵 把边和结点用具体的数据结构保存下来，主要有邻接矩阵和邻接表。 使用二维数组来表示，个g[i][j]来表示顶点i和j关系。如果i和j连接值就为1，否则为0.无向图g[i][j]=g[j][i],有向图只需标注g[i][j].带权值使g[i][j]值为权值，0仍为权值，无连接为INF。 2、邻接表 表示从顶点到其他点边数集合 例：g[v].push_back(e)//顶点v，其他顶点e。 3、点多边比较稀疏的时候使用邻接表，但实现复杂，并且不易遍历。 三、图的搜索 主要通过DFS实现 例题： 给定一个具有n个顶点的图，相连的两顶点不同色，是否能实现？
#include <iostream> #define MAX 1000 int Graph[MAX][MAX];//存储图的序号 int color[MAX];//存储各个顶点的颜色 1或-1 using namespace std; int dfs(int point,int c)//把点point染成c色，并且从顶点point开始深度搜索，如果不满足就返回0 { color[point] = c; int i; for(i = 1;i <= Graph[point][0];i++) //对每一个相邻顶点判断 { // 如果相邻顶点的颜色相同，则返回0 if(color[Graph[point][i]] == c) return 0; // 如果相邻顶点还没有染色，则染成-c,并深度搜索判断真假 if(color[Graph[point][i]] == 0 && !dfs(Graph[point][i],-c)) return 0; } //如果所有顶点都满足，就返回1 return 1; } int main(void) { int N,i,j,flag = 1; // N是图顶点个数 cin>>N; for(i = 0;i < N;i++){ cin>>Graph[i][0]; //用Graph[i][0]来存储相邻顶点个数 for(j = 1;j <= Graph[i][0];j++){ cin>>Graph[i][j]; } } //读取图 for(i = 0;i < N;i++){ if(color[i] == 0) //如果点i还没有染色，就染成1 { if(!dfs(i,1)){ //如果判断为假，则退出 cout<<"NO"; flag = 0; break; } } } if(flag == 1) //如果判断为真，则输出YES cout<<"YES"; return 0; }四、最短路径 1、单源最短路径问题。 固定起点求他到其他点最短路径。d[v]表示起点到V顶点距离。 实现代码
#include <iostream> #define MAX_E 1000 #define INF 1e9 using namespace std; struct edge{int from,int to,int cost}; edge es[MAX_E];//边的集合 int d[MAX_E];//最短距离 int v,e;//顶点和边 void shortpath(int s)//s为起点 { for(int i=0;i<v;i++) d[i]=INF; d[s]=0; while(true)// { bool update=false; for(int i=0;i<e;i++)//遍历所有边 { egde e=es[i]; if(d.[e.from]!=INF&&d[e.to]>d[e.from]+e.cost)) { d[e.to]=d[e.from]+e.cost; update=true; } } if(!uopdate) break;//不再能更新，找出所有起点到其他顶点最短路径。 } }最近总结 今天还是跟着做了一场比赛，一如既往的糟糕，心态快炸了，做到3个小时的时候，提交六个题，只上传成功一个，其他全部pending，当时快感觉做不下去了，看了榜单，QAQ。队友打气最后还是硬着头皮做了。题目的思维题，总是搞错，总想着暴力枚举，递归出奇迹，下次一定要多读题，多思考。
