无向完全图是图中每对顶点之间恰好有一条边的简单图，已知无向完全图有7个顶点，它有多少边？

6+5+4+3+2+1

对于一个有向图，如果每个节点都存在到达其他节点的路径，则称为强连通，如果一个图，如下，删除谁之后还是强联通？

查看每个点的入度出度，唯一路径不能删，结合排除法

在一个无向图中，任意两点都存在路径相连，称为连通图，四阶连通图如下，如果想要它不再是连通图，至少去掉几条边？

计算每个顶点的度，选择最小的度断开连接

下图，以A0为起点进行深搜，可能的顺序有？

略

如果一个无向图有16条边，每个顶点度均为2，有多少个顶点？

手拉手围一圈

有n个节点，m条边的连通图，去掉多少边，才能变成树？

n个节点的树有n-1条边，m-(n-1)

有四个没有区别的点构成无向连通图的个数是？

---------------------------------

单源最短路算法：已知图，求从一个点出发，到达其他点的最短距离

dijkstra算法

算法过程

1、初始化邻接矩阵与dijx数组

2、标记已访问起始点

3.1、遍历dijx数组，找到未访问最小值

3.2、标记当前点

3.3、从当前点出发，到达各个顶点，比较更新dijx数组的值

3.4、重复3.1-3.3，直到所有点都标记访问

4、当前dijx数组记录的就是从x点到达各个顶点的最小距离

int jz[105][105]={};

int n,m,a,b,l;

int dijx[105]={};

int visx[105]={};

memset(dijx,0x3f,sizeof(dijx));

memset(jz,0x3f,sizeof(jz));

cin>>n>>m;

for(int i=0;i<m;i++){

   cin>>a>>b>>l;

   jz[a][b]=jz[b][a]=l;

}

int x;

cin>>x;

for(int i=1;i<=n;i++){

   if(jz[x][i]!=jz[0][0]) dijx[i]=jz[x][i];

}

visx[x]=1;

while(true){

   int k=0;

   for(int i=1;i<=n;i++){

       if(visx[i]!=1&&dijx[i]<dijx[k]){

           k=i;

       }

   }

   if(k==0) break;

   visx[k]=1;

   for(int i=1;i<=n;i++){

       if(jz[k][i]!=jz[0][0]&&visx[i]!=1){

           if(dijx[i]>dijx[k]+jz[k][i]){

               dijx[i]=dijx[k]+jz[k][i];

           }

       }

   }

}

for(int i=1;i<=n;i++){

   cout<<dijx[i]<<" ";

}

1、写出dijkstra算法的函数形式【尽量完美，下节课 检查】

2、memset原理（按字节存）

如果把0x3f换成1，存的数据是多少？

下节课

题目出题方向

算法优化