今天来浅谈一下图，听说自己写总结的人grade++，rp++。
像我这样可爱的人怎么能错过这个机会呢嘤嘤嘤。
毕竟图至少啃了15day++。
恩曾经的小弱渣从来都是仰望高端玩家虐图论
听说noip上一年考两道大图(つд⊂)而小弱渣还没学到
吓得本宝宝虎躯一震！！
恩废话不多说，来开正文。
-------------------我是萌哒哒的分割线--------------------
刚开始先学图的储存。
邻接矩阵就是跟二维数组长得一毛（mu）一样奇奇怪怪的东xi
1 #include<iostream> 2 using namespace std; 3 int n,a[100][100]; 4 int main() 5 { 6 cin>>n; 7 //直接给出邻接矩阵，直接读。 8 for(int i=1;i<=n;i++) 9 for(int j=1;j<=n;j++) 10 cin>>a[i][j]; 11 //给出两个顶点和权值 12 for(int i=1;i<=n;i++) 13 { 14 int xx,yy,vv; 15 cin>>xx>>yy>>vv; 16 a[xx][yy]=vv; 17 //双向图时 18 a[yy][xx]=vv; 19 } 20 //给出每个顶点的临界点 21 for(int i=1;i<=n;i++) 22 { 23 int k; 24 cin>>k; 25 for(int j=1;j<=k;j++) 26 { 27 int x; 28 cin>>x; 29 a[i][x]=1; 30 a[x][i]=1; 31 } 32 } 33 return 0; 34 }
2.邻接表
第一次看这玩意的时候内心万般草泥马奔过。
这TM都是什么玩意
后来经过滑稽大师cdc柴大叔的指导下，莫名其妙知道了些什么
然而教材太过简单，时常还会有些错的
小弱渣花了一整节自习课照着书上画了一幅图，发现！原来！跟书上一毛（mu）一样。本宝宝不开心，哦是十分不开心。
这大概是这个样子的
1 #include<iostream> 2 using namespace std; 3 int n; 4 int link[10010],len=0; 5 struct ha 6 { 7 int y,v,next; 8 }e[10010]; 9 void insert(int xx,int yy,int vv) 10 { 11 e[++len].next=link[xx]; 12 link[xx]=len; 13 e[len].y=yy; 14 e[len].v=vv; 15 } 16 int main() 17 { 18 cin>>n; 19 int xx,yy,vv; 20 for(int i=1;i<=n;i++) 21 { 22 cin>>xx>>yy>>vv; 23 insert(xx,yy,vv); 24 insert(yy,xx,vv); 25 } 26 return 0; 27 }
如果出现重边！邻接矩阵必须判断！！
-----------------我是萌萌哒的分割线------------------
DFS：以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点；当没有未访问过的顶点时，则回到上一个顶点，继续试探访问别的顶点，直到所有的顶点都被访问过。
原文：http://www.cnblogs.com/Kaike/p/5916221.html
