文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机硬件及网络 > 邻接矩阵和邻接表
侵权投诉

邻接矩阵和邻接表

C代码


#include<stdio.h>
#include<malloc.h>
#define MAXV 100
#define INF 32767

typedef int Infotype;


//以下定义邻接矩阵类型
typedef struct
{
int no; //顶点编号
Infotype info; //顶点其余的信息
}VertexType;
typedef struct
{
int edges[MAXV][MAXV]; //邻接矩阵
int n,e; //顶点数,弧数
VertexType vexs[MAXV]; //存放顶点信息
}MGraph;

//一下定义邻接表类型
typedef struct ANode //弧的节点结构类型
{
int adjvex; //该弧的终点位置
struct ANode *nextarc;
Infotype info; //弧的相关信息
} ArcNode;
typedef struct Vnode //邻接表头结点类型
{
VertexType data; //顶点信息
ArcNode *firstarc; //指向第一条弧
}VNode;
typedef VNode AdjList[MAXV];
typedef struct
{
AdjList adjlist;
int n,e;
}ALGraph;

void MatToList(MGraph g,ALGraph *&G) //将邻接矩阵 g 转换为邻接表 G
{
int i,j,n=g.n;
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
for(i=0;i<n;i++)
G->adjlist[i].firstarc=NULL;
for(i=0;i<n;i++)
for(j=n-1;j>=0;j--)
if(g.edges[i][j]!=0)
{
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=j;
p->info=g.edges[i][j];
p->nextarc=G->adjlist[i].firstarc;
G->adjlist[i].firstarc=p;
}
G->n=n;
G->e=g.e;
}

void ListToMat(ALGraph *G,MGraph &g) //邻接表G转换为邻接矩阵g
{
int i,j,n=G->n;
ArcNode *p;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
g.edges[i][j]=0;
for(i=0;i<n;i++)
{
p=G->adjlist[i].firstarc;
while(p!=NULL)
{
g.edges[i][p->adjvex]=p->info;
p=p->nextarc;
}
}
g.n=n;
g.e=G->e;
}

void DispMat(MGraph g) //输出邻接矩阵
{
int i,j;
for(i=0;i<g.n;i++)
{
for(j=0;j<g.n;j++)

if(g.edges[i][j]==INF)
printf("%3s","∞");
else if(i==j)
printf("%3d",0);
else
printf("%3d",g.edges[i][j]);
printf("\n");
}
}


void DispAdj(ALGraph *G) //输出邻接表
{
int i;
ArcNode *p;
for(i=0;i<G->n;i++)
{
p=G->adjlist[i].firstarc;
if(p!=NULL) printf("%3d:",i);
while(p!=NULL)
{
printf("%3d",p->adjvex);
p=p->nextarc;
}
printf("\n");
}
}

void main()
{
int i,j;
MGraph g,g1;
ALGraph *G;
int A[MAXV][6]={
{0,5,0,7,0,0},
{0,0,4,0,0,0},
{8,0,0,0,0,9},
{0,0,5,0,0,6},
{0,0,0,5,0,0},
{3,0,0,0,1,0}
};

g.n=6; g.e=10;
for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++)
g.edges[i][j]=A[i][j];
printf("\n");
printf("有向图G的邻接矩阵是:\n");
DispMat(g);
G=(ALGraph *)malloc(sizeof(ALGraph));
printf("图G的邻接矩阵转换成邻接表:\n");
MatToList(g,G);
DispAdj(G);
printf("图G的邻接表转换成邻接矩阵:\n");
ListToMat(G,g1);
DispMat

第1页

热门文档

相关文档

  • 图的邻接矩阵和邻接表相互转换

    图的邻接矩阵和邻接表相互转换 图的邻接矩阵存储方法具有如下几个特征:1)无向图的邻接矩阵一定是一个对称矩阵。 2)对于无向图的邻接矩阵的第 i 行非零元素的...

  • 邻接矩阵与邻接表

    [MAXV]; //邻接矩阵 int n,e; //顶点数,弧数 VertexType vexs[MAXV]; //存放顶点信息 }MGraph; //一下定义邻接表类型 typedef struct ANode //弧的节点...

  • 邻接矩阵和邻接表

    邻接矩阵和邻接表_计算机软件及应用_IT/计算机_专业资料。邻接矩阵和邻接表 动画演示邻接矩阵 j i mapp[ i ][ j ] 0 0 0 0 0 0 0 0 0 1 0 0 0...

  • 实现图的邻接矩阵和邻接表存储

    实现图的邻接矩阵和邻接表存储_工学_高等教育_教育专区。严蔚敏版数据结构实现图的存储实验报告实现图的邻接矩阵和邻接表存储 实现图的邻接矩阵和邻接表存储 1. ...

  • 实现图的邻接矩阵和邻接表存储

    实现图的邻接矩阵和邻接表存储实现图的邻接矩阵和邻接表存储隐藏>> #include<stdio.h> #include<malloc.h> #define MAXV 100 //以下定义邻接矩阵类型 typedef ...

  • 分别以邻接矩阵和邻接表作为图的存储结构

    分别以邻接矩阵和邻接表作为图的存储结构, 给出连通图的深度优先 分别以邻接矩阵和邻接表作为图的存储结构, 遍历的递归算法算法思想: (1)访问出发点 vi,并将其...

  • 邻接矩阵与邻接表实验报告.doc

    邻接矩阵与邻接表实验报告.doc_工学_高等教育_教育专区。邻接矩阵和邻接表的深度优先搜索和广度优先搜索西安邮电学院 数据结构设计报告题 目:邻接矩阵和邻接表的...

  • 邻接矩阵邻接表,电科0901 朱立刚 04092013

    二、 概要设计 1 定义邻接矩阵和邻接表的结构体, 以及栈和队列的结构体。 2 邻接矩阵的深度优先遍历:首先访问元第一个元素并置访 问标志,只要所有有效元素未被...

  • 以邻接表和邻接矩阵做存储结构求最短路径

    设图中各边的权值都相等,试以邻接矩阵和邻接表为存储结构,分别写出算法: (1)求顶点vi到顶点vj(i<>j)的最短路径 (2)求源点vi到其余各顶点的最短路径 要求...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email