图的存储方式
二维数组：
可以表示出有向图与无向图，权重，还有入度与出度（同一行）
链式存储：
可以表示出有向图与无向图，权重，还有入度与出度（主要：同一条链）
运用：
Dfs：深度优先
深度优先一般是求多少种情况，与递归密切相关。
也就是说深度优先是先算深度（与递归的深度一样）
请看1005文件或
http://zhjnc.acmclub.com/index.php?app=problem_title&id=702&problem_id=1104
#include<stdio.h>
#include<string.h>
char v[9],g[9][9];//v用来表示状态，是否被访问了
int n,ans;
void dfs(int k,int cur)
{
int i,j;
if(k==0) ans++; //深度
else for(i=cur-1;i>=k-1;i--) //宽度（广度）
{
for(j=0;j<n;j++)
if(g[i][j]=='#'&&v[j]==0)
{
v[j]=1; //访问后
dfs(k-1,i);
v[j]=0; //状态复原
}
}
}
int main()
{
int k,i;
while(scanf("%d%d",&n,&k)!=EOF,n!=-1||k!=-1)
{
memset(v,0,sizeof(v));
for(i=0;i<n;i++)
scanf("%s",g[i]);
ans=0;
dfs(k,n);
printf("%d\n",ans);
}
return 0;
}
Bfs: 广度优先
广度优先一般是求最短路径，与队列密切相关。
也就是说广度优先是先算宽度（与递归的宽度一样），也就是先把每一步的可走的情况全部入队。
http://zhjnc.acmclub.com/index.php?app=problem_title&id=702&problem_id=1101
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
struct num
{
int x,y,step;
}star;
bool v[8][8];
int f[][2]={{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};
int bfs(int ex,int ey)
{ int i;
queue<struct num> q;//队列
memset(v,false,sizeof(v));
v[star.x][star.y]=true;
q.push(star);
star.step=0;
num head,tem;
while(!q.empty())
{
head=q.front();
q.pop();
for(i=0;i<8;i++)//宽度（广度）
{ tem.x=head.x;
tem.y=head.y;
tem.x+=f[i][0];
tem.y+=f[i][1];
tem.step=head.step+1;
if(!v[tem.x][tem.y]&&tem.x>=0&&tem.x<8&&tem.y>=0&&tem.y<8)
{
if(tem.x==ex&&tem.y==ey) return tem.step;
v[tem.x][tem.y]=true;//状态位不会复原
q.push(tem); //所有的宽度入队
}
}
}
}
int main(int argc, char* argv[])
{
char s[2],e[2];
int ex,ey;
while(~scanf("%s%s",s,e))
{
star.x=s[0]-'a';
star.y=s[1]-'0'-1;
ex=e[0]-'a';
ey=e[1]-'0'-1;
if(!strcmp(s,e))
printf("To get from %s to %s takes 0 knight moves.\n",s,e);
else
printf("To get from %s to %s takes %d knight moves.\n",s,e,bfs(ex,ey));
}
return 0;
}
深度优先和广度优先的相同点和区别
相同点：他们一般都会有状态位来描述是否已经被访问了。它们都是开始点假设结束点都最后才知道，也就是结束的点是随机的，哪个点都有可能。（还有一种算法直接知道结束点和开始点）。它们都需要明确知道宽度和深度，而且是有一定规律的。
区别：深度优先的状态位可以恢复但广度优先的状态位不会恢复，因此这也说明了广度优先适合求最短路径，而不能求所有的情况。深度优先可以求出所有情况，因此也可以求出最长和最短路径，只不过深度优先求最短路径的时间会大大多于广度优先的时间。有权重的图且它们的大小不同一般不会用广度优先。
直接知道开始点和结束点（用深度优先会超时）（有向和无向图都可以）这道题很重要。
http://zhjnc.acmclub.com/index.php?app=problem_title&id=702&problem_id=1120
1 #include<stdio.h>
2 #include<string.h>
3 const int inf=1000000000;
4 int n,g[10][10];
5 void floyd()
6 {
7 int i,j,k;
8 for(k=0;k<n;k++)
9 for(i=0;i<n;i++)
10 for(j=0;j<n;j++)
11 if(g[i][k]+g[k][j]<g[i][j])//有向图时，还注意i!=j,j!=k,k!=i;
12 g[i][j]=g[i][k]+g[k][j];
13 }
14 int main()
15 {
16 int m,a,b,l,i,j;
17 while(scanf("%d%d",&n,&m)!=EOF)
18 {
19 for(i=0;i<n;i++)
20 for(j=0;j<n;j++)
21 g[i][j]=inf;
22 while(m--)
23 {
24 scanf("%d%d%d",&a,&b,&l);
25 g[a-1][b-1]=g[b-1][a-1]=l;
26 }
27 floyd();
28 scanf("%d%d",&a,&b);
29 if(g[a-1][b-1]==inf)
30 puts("No path");
31 else
32 printf("%d\n",g[a-1][b-1]);
33 }
34 return 0;
35 }
图生成树（也可以求图最长和最短路径）参考tushu.txt
普里姆Prim：分a,b两组，a组是头节点，每个节点的最小边。也就是数组排序问题了（二维数组）
int c[6][6]=
{ {0,0,0,0,0,0},
{0,0,6,9,5,13},
{0,6,0,6,7,8},
{0,9,6,0,9,3},
{0,5,6,9,0,3},
{0,13,8,3,3,0}};
void prim(int n)
{
int i,j,lowcost[10],cost[10],min,k;
for(i=2;i<=n;i++)
{lowcost[i]=c[1][i];
cost[i]=1;
}
cost[1]=0;
for(i=2;i<=n;i++)
{ min=999999;
k=i;
for(j=2;j<=n;j++)
{
if(lowcost[j]<min&&cost[j]!=0)
{ min=lowcost[j];
k=j;
}
}
printf("<%d,%d> ",cost[k],k);
cost[k]=0;
for(j=2;j<=n;j++)
{
if(c[k][j]<lowcost[j]&&cost[j]!=0)
{lowcost[j]=c[k][j];
cost[j]=k;}
}
}
}
克鲁斯卡尔：先把边排序，然后一个一个的链接。也就是数组中排序问题了（二维数组）
struct edg
{
int t,l,w;
}num[20];
int set[6];
int seeks(int v)
{
while(set[v]>0)
v=set[v];
return v;
}
void krush(int e)
{
int j,i;
for(i=1;i<=5;i++)
set[i]=0;
j=1,i=1;
while(j<=5&&i<e)
{
int v1=seeks(num[i].t);
int v2=seeks(num[i].l);
if(v1!=v2)
{
printf("(%d,%d) ",num[i].t,num[i].l);
set[v1]=v2;
j++;
}
i++;
}
}
与深度优先广度优先的区别
深度优先广度优先：适合于一张二维数组表，可以上下左右移动。二这两个算法更加适合于图和边的运用
相同：它们也需要有一个数组来记录状态。它们的开始点和结束点都是随机的。
图的拓扑结构：（邻接表）
也就是入度和出度，入度为零的点可以拆出来，然后它连接的点的入度减一。