图的两种存储结构及基本算法_图的存储结构算法

图的两种存储结构及基本算法由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“图的存储结构算法”。

一、图的邻接矩阵存储

1.存储表示

#definevexnum10

typedefstruct{

vextypevexs[vexnum];

intarcs[vexnum][vexnum];}mgraph;

2.建立无向图的邻接矩阵算法

voidcreat(mgraph*g, inte){for(i=0;i

scanf(“%c”,&g->vexs[i]);

for(i=0;i

for(j=0;j

g->arcs[i][j]=0;

for(k=0;k

scanf(“%d,%d”,&i,&j);

g->arcs[i][j]=1;g->arcs[j][i]=1;} }

3.建立有向图的邻接矩阵算法

voidcreat(mgraph*g, inte){for(i=0;i

scanf(“%c”,&g->vexs[i]);

for(i=0;i

for(j=0;j

g->arcs[i][j]=0;

for(k=0;k

scanf(“%d,%d,%d”,&i,&j,&w);

g->arcs[i][j]=w;}

}

二、图的邻接表存储

1.邻接表存储表示

#definevexnum10

typedefstructarcnode{

intadjvex;

structarcnode*nextarc;

}Arcnode;

typedefstructvnode{

vextypedata;

Arcnode*firstarc;

}Vnode;

typedefstruct{

Vnodevertices[vexnum];

intvexnum,arcnum;

}algraph;

2.建立无向图的邻接表算法：

voidcreat(algraph*g, inte){

for(i=0;i

scanf(“%c”,&g->vertices[i]->data);

g->vertices[i]->firstarc=NULL;}

for(k=0;k

scanf(“%d,%d”,&i,&j);

q=(Arcnode*)malloc(sizeof(Arcnode));p=(Arcnode*)malloc(sizeof(Arcnode));p->adjvex=j;

p->nextarc=g->vertices[i]->firstarc;

g->vertices[i]->firstarc=p;

q->adjvex=i;

q->nextarc=g->vertices[j]->firstarc;

g->vertices[j]->firstarc=q;}

}

3.建立有向图邻接表算法：

voidcreat(algraph*g, inte){

for(i=0;i

scanf(“%c”,&g->vertices[i]->data);

g->vertices[i]->firstarc=NULL;}

for(k=0;k

scanf(“%d,%d”,&i,&j);

p=(Arcnode*)malloc(sizeof(Arcnode));p->adjvex=j;

p->nextarc=g->vertices[i]->firstarc;

g->vertices[i]->firstarc=p;}

}

三、图的遍历

1.连通图的深度优先搜索遍历

intvisited[vexnum]={0};

voiddfs(mgraph*g, inti){

printf(“%3c”,g->vexs[i]);

visited[i]=1;

for(j=0;j

if((g->arcs[i][j]==1)&&(!visited[j]))

dfs(g, j);}

2.联通图的广度优先搜索遍历

intvisited[vexnum]={0};

voidbfs(mgraph*g, intk){

intq[20], f, r;

f=0;r=0;

printf(“%3c”,g->vexs[k]);

visited[k]=1;

q[r]=k;r++;

while(r!=f){

i=q[f];f++;

for(j=0;j

if((g->arcs[i][j]==1)&&!visited[j]){

printf(“%3c”,g->vexs[j]);

visited[j]=1;

q[r]=j;r++;}

}

}

4.求图的联通分量

intvisited[vexnum]={0};

voidcomponent(mgraph*g){

intcount=0;

for(j=0;j

if(!visited[j]){

count++;

printf(“n第%d个联通分量:”, count);dfs(g, j);}

printf(“n 共有%d个联通分量。n”, count);}