您现在的位置： &
数据结构第七章《图》算法设计题[1]
数据结构第七章《图》算法设计题[1]
五、算法设计题
　　1．（单独命题考生做）设无向图G有n个顶点，m条边。试编写用邻接表存储该图的算法。（设顶点值用1～n或0～n-1编号） 【南京航空航天大学 1996 十二 （10分）】
　　2．请用流程图或类高级语言(pascal或c)表示算法。已知有向图有n个顶点,请写算法,根据用户输入的偶对建立该有向图的邻接表。即接受用户输入的&vi,vj&(以其中之一为0标志结束),对于每条这样的边,申请一个结点,并插入到的单链表中,如此反复,直到将图中所有边处理完毕。提示：先产生邻接表的n个头结点（其结点数值域从1到n）。【上海大学 2000 四 （16分）】
　　3．设无向图G有n个点e条边，写一算法建立G的邻接多表，要求该算法时间复杂性为O（n+e），且除邻接多表本身所占空间之外只用O（1）辅助空间。【东南大学 1995 六（16分） 1997 二 （15分）】
　　4．给出以十字链表作存储结构，建立图的算法，输入(i,j,v)其中i,j为顶点号，v为权值。【河海大学 1998 六 （10分）】
　　5．设有向G图有n个点(用1,2,…,n表示),e条边,写一算法根据其邻接表生成其反向邻接表,要求算法复杂性为O(n+e)。【东南大学 1996 三 （13分）】
　　6．写出从图的邻接表表示转换成邻接矩阵表示的算法，用类PASCAL语言（或C语言）写成过程形式。【南开大学 1998 四 (16分)】
　　7．设已给出图的邻接矩阵，要求将邻接矩阵转换为邻接表，用类pascal语言写为过程形式。【南开大学 1998 四 ( 14分)】　　　　8．试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径（i&&j）。注意：算法中涉及的图的基本操作必须在存储结构上实现。【哈尔滨工业大学 2001 九 （12分）】
　　9．已知无向图采用邻接表存储方式，试写出删除边（i，j）的算法。 【东南大学 1999 三 （10分）】
　　10．假设有向图以邻接表存储，试编写算法删除弧&Vi，Vj&的算法。【北京轻工业学院 1997 五（10分）】
　　11．假设有向图以十字链表存储，试编写算法，插入弧&Vi,Vj&。【北京轻工业学院 1998 四 （14分）】
　　[1] &[] &[] &[] &[] &[] &[] &
&&&主编推荐
&&&热门试卷
&&&最新视频
&&&热门阅读
&&&最新问答
&&&&&&&&&&&&&&&
希赛网 版权所有 & &&&&增值电信业务经营许可证湘B2-你的位置： &&
邻接表有向图(一)之 C语言详解
邻接表有向图(一)之 C语言详解
邻接表有向图的介绍邻接表有向图是指通过邻接表表示的有向图。上面的图G2包含了&A,B,C,D,E,F,G&共7个顶点，而且包含了&&A,B&,&B,C&,&B,E&,&B,F&,&C,E&,&D,C&,&E,B&,&E,D&,&F,G&&共9条边。上图右边的矩阵是G2在内存中的邻接表示意图。每一个顶点都包含一条链表，该链表记录了&该顶点所对应的出边的另一个顶点的序号&。例如，第1个顶点(顶点B)包含的链表所包含的节点的数据分别是&2,4,5&；而这&2,4,5&分别对应&C,E,F&的序号，&C,E,F&都属于B的出边的另一个顶点。邻接表有向图的代码说明1. 基本定义// 邻接表中表对应的链表的顶点
typedef struct _ENode
// 该边所指向的顶点的位置
struct _ENode *next_
// 指向下一条弧的指针
}ENode, *PEN
// 邻接表中表的顶点
typedef struct _VNode
// 顶点信息
ENode *first_
// 指向第一条依附该顶点的弧
typedef struct _LGraph
// 图的顶点的数目
// 图的边的数目
VNode vexs[MAX];
}LG(01) LGraph是邻接表对应的结构体。 vexnum是顶点数，edgnum是边数；vexs则是保存顶点信息的一维数组。 (02) VNode是邻接表顶点对应的结构体。 data是顶点所包含的数据，而firstedge是该顶点所包含链表的表头指针。 (03) ENode是邻接表顶点所包含的链表的节点对应的结构体。 ivex是该节点所对应的顶点在vexs中的索引，而nextedge是指向下一个节点的。2. 创建矩阵这里介绍提供了两个创建矩阵的方法。一个是用已知数据，另一个则需要用户手动输入数据。2.1 创建图(用已提供的矩阵)/*
* 创建邻接表对应的图(用已提供的数据)
LGraph* create_example_lgraph()
char c1, c2;
char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
char edges[][2] = {
{'A', 'B'},
{'B', 'C'},
{'B', 'E'},
{'B', 'F'},
{'C', 'E'},
{'D', 'C'},
{'E', 'B'},
{'E', 'D'},
{'F', 'G'}};
int vlen = LENGTH(vexs);
int elen = LENGTH(edges);
int i, p1, p2;
ENode *node1, *node2;
LGraph* pG;
if ((pG=(LGraph*)malloc(sizeof(LGraph))) == NULL )
return NULL;
memset(pG, 0, sizeof(LGraph));
// 初始化"顶点数"和"边数"
pG-&vexnum =
pG-&edgnum =
// 初始化"邻接表"的顶点
for(i=0; i&pG-& i++)
pG-&vexs[i].data = vexs[i];
pG-&vexs[i].first_edge = NULL;
// 初始化"邻接表"的边
for(i=0; i&pG-& i++)
// 读取边的起始顶点和结束顶点
c1 = edges[i][0];
c2 = edges[i][1];
p1 = get_position(*pG, c1);
p2 = get_position(*pG, c2);
// 初始化node1
node1 = (ENode*)malloc(sizeof(ENode));
node1-&ivex = p2;
// 将node1链接到"p1所在链表的末尾"
if(pG-&vexs[p1].first_edge == NULL)
pG-&vexs[p1].first_edge = node1;
link_last(pG-&vexs[p1].first_edge, node1);
return pG;
}该函数的作用是创建一个邻接表有向图。实际上，该方法创建的有向图，就是上面的图G2。2.2 创建图(自己输入)/*
* 创建邻接表对应的图(自己输入)
LGraph* create_lgraph()
char c1, c2;
int i, p1, p2;
ENode *node1, *node2;
LGraph* pG;
// 输入"顶点数"和"边数"
printf("input vertex number: ");
scanf("%d", &v);
printf("input edge number: ");
scanf("%d", &e);
if ( v & 1 || e & 1 || (e & (v * (v-1))))
printf("input error: invalid parameters!n");
return NULL;
if ((pG=(LGraph*)malloc(sizeof(LGraph))) == NULL )
return NULL;
memset(pG, 0, sizeof(LGraph));
// 初始化"顶点数"和"边数"
pG-&vexnum =
pG-&edgnum =
// 初始化"邻接表"的顶点
for(i=0; i&pG-& i++)
printf("vertex(%d): ", i);
pG-&vexs[i].data = read_char();
pG-&vexs[i].first_edge = NULL;
// 初始化"邻接表"的边
for(i=0; i&pG-& i++)
// 读取边的起始顶点和结束顶点
printf("edge(%d): ", i);
c1 = read_char();
c2 = read_char();
p1 = get_position(*pG, c1);
p2 = get_position(*pG, c2);
// 初始化node1
node1 = (ENode*)malloc(sizeof(ENode));
node1-&ivex
// 将node1链接到"p1所在链表的末尾"
if(pG-&vexs[p1].first_edge == NULL)
pG-&vexs[p1].first_edge = node1;
link_last(pG-&vexs[p1].first_edge, node1);
return pG;
}create_lgraph()是读取用户的输入，将输入的数据转换成对应的有向图。邻接表有向图的完整源码点击查看：
&&作者：skywang12345 &&
最新热门tag一个有向图的邻接表存储结构如下图示
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
一个有向图的邻接表存储结构如下图示
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口无向图的邻接表和逆邻接表是不是一样的？？
[问题点数：40分，结帖人symshuai88]
无向图的邻接表和逆邻接表是不是一样的？？
[问题点数：40分，结帖人symshuai88]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
本帖子已过去太久远了，不再提供回复功能。