Graph

带权路径长度最短-最优二叉树

回路 简单路径 简单回路 连通 连通图 连通分量-图中最大的连通子图 无向图

强连通图 强连通分量 有向图

有根的图 图的根 边带权的图为网络 无向网络 有向网络

图的存储

1.邻接矩阵

n个顶点的图 A[i,j]=1 i->j 有边； 0 i->j 无边

n个顶点的网络 wij,0(i=j),无穷

邻接矩阵只表示顶点之间的关系，使用顺序表存储图中顶点数值(顶点表)

2.邻接表

顶点表（n个元素）的顺序表（每个元素至少应包含一个指针字段first，用来指向每个链表的第一个结点）+

图的存储算法：

//顶点表中元素类型

struct node{

int degree;//顶点的度

arcnode *first ;//链表的首指针

}

struct arcnode{

int vertext; //相邻的顶点字号

int weight ;//边的权值

arcnode * next ;//指向链表的下一个结点

}

node adjlist[n0+1];//顶点表

int n ;//图的顶点数

void setgraph(){

int i,j,w;

//init

cin>>n;

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

adjlist[i].degree = 0;

adjlist[i].first = NULL;

}

//读入第一条边

cin>>i>>j>>w;

while((i>=1)&&(i<=n)){

//存入邻接表

p=adjlist[i].first;

while((p!=NULL)&&(p->vertext!=j)){

p=p->next;

}

if(p==NULL){

p = new arcnode;

p->vertext=j;

p->weight = w;

p->next=adjlist[i].first;

adjlist[i].first = p ;

++(adjlist[j].degree);

}

cin>>i>>j>>w;//读入下一条边

}

}

遍历：

1.深度遍历 2.广度遍历

定义一个顶点是否被访问过的标记数组 mark[i]

深度遍历的特点"后进先出" -使用栈

广度遍历的特点"先进先出"-使用队列

深度遍历算法：

void deeptrarverse(int x){

int mark[n0+1] , k;

int s[n0+1],t;

arcnode *p;

for(k=1;k<=n;k++) mark[k]=0;

cout<

mark[x]=1;

t=1;s[t]=x;//将深度经过的结点压入栈中

do{

k=s[t];//始终对栈顶元素进行操作

p=adjlist[k].first;//临时的首指针

while(p&&mark[p->vertex]){

p=p->next;//存在和栈顶元素的链接，但已被访问过，向下遍历查找无访问过的结点

}

if(p==NULL){

t--;//邻接的结点全部访问过则弹出栈顶元素

}else{

x=p->vertex;//未访问过则进行访问并把它置于栈顶重复上面操作

cout<

mark[x]=1;

s[++t]=x;

}

}while(t)//栈空结束

}

广度遍历：

void widetraverse(int x){

int q[n0+1],f=1,r=2;

cout<

q[1]=x;

arcnode * p ;

for( int k=0;k

mark[x]=1;

do{

k=q[f++];

p=adjlist[k].first;

while(p){//如果x的邻接结点未访问，一次访问全部的邻接结点放入队尾

if(mark[p->vertex]==0){

cout<vertex<<" ";

mark[p->vertex]=1;

q[r++]=p->vertex;

}

p=p->next;

}

}while(f!=r)

}

图的生成树

深度优先生成树 广度优先生成树

最小生成树 最短路径

在无回路的有向网络中，假设只有一个入度为0的顶点（源点）和一个出度为0的点（汇点） ，之间最长的路径为关键路径

单源最短路径问题：