连通图:在无向图中,若每一对顶点之间都有路径.则为连通图.
连通分量:无向图中的极大连通子图.
一个连通图的生成树,是含有该连通图的全部顶点的一个极小连通子图.
强连通图:有向图中,任意一对顶点Vi->vj[有路径可达j],同时vj->vi
弱连通图:任意一对顶点vi->vj 但是vj不能到vi
5.2图的存储结构
一、邻接矩阵
图：
          {
            1 有直接边
  A[i,j]=
            0 无直接边
          }
<1>A[i,i]=0;主对角线元素为0，没有环
<2>无向图是对称矩阵,
<3>无向图中顶点的度：第i行非0元素的个数=第i列非0元素的个数.
<4>有向图中顶点的度：入度 [第i列非0元素的个数]+  出度[第i行非0元素的个数]
#define vnum 20
typedef struct graph
{
VertexType vexs[vnum];//顶点信息放在一维数组
int arcs[vnum][vnum];//邻接矩阵
int vexnum,arcnum;//顶点的实际个数，边的实际个数
}GraphTp;
更简单的形式：
#defein vnum 20
typedef  int GraphTP[vnum][vnum];
网:带权的图
      { Wij 直接边的权值
a[i,j]=
       OO 无直接边
      }

<1>A[i,i]=0;主对角线元素为OO，没有环
<2>无向图是对称矩阵,
<3>无向图中顶点的度：第i行非OO元素的个数=第i列非0)元素的个数.
<4>有向图中顶点的度：入度 [第i列非OO元素的个数]+  出度[第i行非00元素的个数]
****:
 G(V,E)无向图：
***:
   用邻接矩阵n*n;用邻接表n+2e
 有向图：用邻接表n+e
逆邻接表：入边表(有向图n+e)
邻接表：出边表，链式存储 (无，有向图)
表头结点：vertex firstarc [顶点信息，第一条边]
表结点形式:adjvex nextarc  [顶点序号静态下标,下一条边]
typedef struct node1
{
int adjvex;//顶点序号
strcut node *nextarc;//下一条边
}node1;
typedef struct node2
{
int vertex;//顶点编号
struct node1*firstarc;// 第一条边
}node2;
typedef struct graph
{
 node2 adjlist[vnum];
int vexnum,arcnum;//顶点个数，边的个数
};
for(int i=0;i<vexnum;i++)
struct node1*p=adjlist[i].firstarc;
adjlist[i].vextec
p->adjvex;p=p->nextarc;

逆邻接表：入边表(有向图n+e)
十字链表：出边表+入边表 (有向图)
data firstin firstout
顶点信息  入边  出边

防战士网
G: