图的邻接矩阵Word格式文档下载.docx
《图的邻接矩阵Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《图的邻接矩阵Word格式文档下载.docx（18页珍藏版）》请在冰点文库上搜索。
{
j=k;
break;
}
returnj;
}
voidCreateDN（AdjMatrix*G）
inti,j,k,weight;
VertexDatav1,v2;
printf（"
输入图的顶点数和弧数\n"
）;
scanf（"
%d%d"
&
vexnum,&
arcnum）;
初始化邻接矩阵\n"
for（i=0;
i<
i++）
{
for（j=0;
j<
j++）
G->
arcs[i][j].adj=INFINITY;
}
for（j=0;
%d"
G->
arcs[i][j].adj）;
\n"
printf（"
输入图的顶点\n"
{
fflush（stdin）;
scanf（"
%c"
vertex[i]）;
输入一条弧的两个顶点及权值\n"
for（k=0;
arcnum;
scanf（"
%c%c%d"
v1,&
v2,&
weight）;
i=LocateVertex（G,v1）;
j=LocateVertex（G,v2）;
arcs[i][j].adj=weight;
voidDepthFistSearch（AdjMatrix*G,intv0）
{intvj;
%c"
vertex[v0]）;
visited[v0]=True;
for（vj=0;
vj<
vj++）
if（!
visited[vj]&
&
arcs[v0][vj].adj!
=INFINITY）
DepthFistSearch（G,vj）;
voidoutputMatrix（AdjMatrix*G,intn）
{inti,j;
n;
{for（j=0;
voidmain（）
{
AdjMatrix*G,p;
G=&
p;
CreateDN（G）;
outputMatrix（G,G->
vexnum）;
按图的邻接矩阵得到的深度优先遍历序列:
DepthFistSearch（G,0）;
广度优先遍历;
#include"
#include<
stdio.h>
#defineMaxNode40
#defineM20
{intadjvex;
structArcNode*nextarc;
{intvertex;
structArcNode*firstarc;
}vernode;
typedefvernodeadjlist[MaxNode];
intqueue[MaxNode];
voiddfs（adjlistg,intk,intvisited[]）
ArcNode*p;
intw;
visited[k]=1;
%d->
"
g[k].vertex）;
p=g[k].firstarc;
while（p!
=NULL）
w=p->
adjvex;
if（visited[w]==0）
dfs（g,w,visited）;
p=p->
nextarc;
voidbfs（adjlistg,intk,intvisited[]）
intfront=0,rear=1,w;
k）;
queue[rear]=k;
while（front!
=rear）
front=（front+1）%M;
w=queue[front];
p=g[w].firstarc;
if（visited[p->
adjvex]==0）
visited[p->
adjvex]=1;
p->
adjvex）;
rear=（rear+1）%M;
queue[rear]=p->
;
voidtrave_bfs（adjlistg,intn）
inti,visited[MaxNode];
for（i=1;
=n;
visited[i]=0;
if（visited[i]==0）
bfs（g,i,visited）;
\b\b\n"
voidprint（adjlistg,intn）
ArcNode*q;
inti;
输出无向图的邻接链表示：
\t%d\t"
i）;
g[i].vertex）;
q=g[i].firstarc;
while（q!
q->
q=q->
voidmain（）
ArcNode*p,*q;
adjlistg;
inti,j,n,k,e;
输入图中顶点的个数,边数:
n,&
e）;
for（k=1;
{
getchar（）;
\t第%d个顶点信息:
%d"
g[k].vertex）;
g[k].firstarc=NULL;
=e;
第%d条边的起点,终点:
i,&
j）;
q=（ArcNode*）malloc（sizeof（ArcNode））;
q->
adjvex=j;
nextarc=g[i].firstarc;
g[i].firstarc=q;
p=（ArcNode*）malloc（sizeof（ArcNode））;
p->
adjvex=i;
nextarc=g[j].firstarc;
g[j].firstarc=p;
print（g,n）;
图的广度优先搜索:
trave_bfs（g,n）;
3.附加题建立一个图（自己决定存储结构），打印其拓扑排序果。
stdlib.h"
#defineERROR0
#defineTRUE1
#defineOK1
#defineFALSE0
#defineOVERFLOW-2
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
#defineINFINITY1000
#defineMAX_VERTEX_NUM20
typedefenum{DG,DN,UDG,UDN}GraphKind;
typedefintVertexType;
typedefintElemType;
intadjvex;
typedefstructVNode
VertexTypedata;
ArcNode*firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
AdjListvertices;
intvexnum,arcnum;
}ALGraph;
ElemType*base;
ElemType*top;
intstacksize;
}SqStack;
intInitStack（SqStack&
S）
S.base=（ElemType*）malloc（STACK_INIT_SIZE*sizeof（ElemType））;
if（!
S.base）
exit（OVERFLOW）;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
intStackEmpty（SqStackS）
if（S.top-S.base>
0）
return0;
else
return1;
intPush（SqStack&
S,ElemTypee）
if（S.top-S.base>
=S.stacksize）
S.base=（ElemType*）realloc（S.base,
（S.stacksize+STACKINCREMENT）*sizeof（ElemType））;
exit（OVERFLOW）;
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
*S.top=e;
S.top++;
intPop（SqStack&
S,ElemType&
e）
if（S.top==S.base）
returnERROR;
S.top--;
e=*S.top;
voidCreateALGraph（ALGraph&
G）
顶点数，弧数:
%d,%d"
G.vexnum,&
G.arcnum）;
G.vexnum;
G.vertices[i].data=i;
G.vertices[i].firstarc=NULL;
intout,in;
G.arcnum;
弧尾，弧头:
out,&
in）;
ArcNode*arc=（ArcNode*）malloc（sizeof（ArcNode））;
arc->
adjvex=in;
nextarc=NULL;
if（G.vertices[out].firstarc!
arc->
nextarc=G.vertices[out].firstarc;
G.vertices[out].firstarc=arc;
voidOutput（ALGraphG）
G.vertices[i].data）;
ArcNode*p=NULL;
p=G.vertices[i].firstarc;
while（p）
printf（"
-->
p=p->
putchar（'
\n'
voidFindinDegree（ALGraphG,intindegree[]）
indegree[i]=0;
indegree[p->
adjvex]++;
intTopologicalSort（ALGraphG）
inti,count,k;
SqStackS;
InitStack（S）;
intindegree[MAX_VERTEX_NUM];
FindinDegree（G,indegree）;
i++）
indegree[i]）
Push（S,i）;
count=0;
while（!
StackEmpty（S））
Pop（S,i）;
%d--%d\t"
i,G.vertices[i].data）;
++count;
for（p=G.vertices[i].firstarc;
p=p->
nextarc）
k=p->
if（!
（--indegree[k]））
Push（S,k）;
if（count<
G.vexnum）
else
returnOK;
intdegree[MAX_VERTEX_NUM];
ALGraphG;
CreateALGraph（G）;
邻接表G为:
Output（G）;
各顶点的入度分别为:
FindinDegree（G,degree）;
%d\t"
degree[i]）;
\n拓扑排序结果为:
TopologicalSort（G）;
升级会员 