?? bo7-1.c
字號:
/* 操作結(jié)果: 返回v的第一個鄰接頂點的序號。若頂點在G中沒有鄰接頂點,則返回-1 */
int i,j=0,k;
k=LocateVex(G,v); /* k為頂點v在圖G中的序號 */
if(G.kind==DN||G.kind==AN) /* 網(wǎng) */
j=INFINITY;
for(i=0;i<G.vexnum;i++)
if(G.arcs[k][i].adj!=j)
return i;
return -1;
}
int NextAdjVex(MGraph G,VertexType v,VertexType w)
{ /* 初始條件: 圖G存在,v是G中某個頂點,w是v的鄰接頂點 */
/* 操作結(jié)果: 返回v的(相對于w的)下一個鄰接頂點的序號, */
/* 若w是v的最后一個鄰接頂點,則返回-1 */
int i,j=0,k1,k2;
k1=LocateVex(G,v); /* k1為頂點v在圖G中的序號 */
k2=LocateVex(G,w); /* k2為頂點w在圖G中的序號 */
if(G.kind==DN||G.kind==AN) /* 網(wǎng) */
j=INFINITY;
for(i=k2+1;i<G.vexnum;i++)
if(G.arcs[k1][i].adj!=j)
return i;
return -1;
}
void InsertVex(MGraph *G,VertexType v)
{ /* 初始條件: 圖G存在,v和圖G中頂點有相同特征 */
/* 操作結(jié)果: 在圖G中增添新頂點v(不增添與頂點相關(guān)的弧,留待InsertArc()去做) */
int i;
strcpy((*G).vexs[(*G).vexnum],v); /* 構(gòu)造新頂點向量 */
for(i=0;i<=(*G).vexnum;i++)
{
if((*G).kind%2) /* 網(wǎng) */
{
(*G).arcs[(*G).vexnum][i].adj=INFINITY; /* 初始化該行鄰接矩陣的值(無邊或弧) */
(*G).arcs[i][(*G).vexnum].adj=INFINITY; /* 初始化該列鄰接矩陣的值(無邊或弧) */
}
else /* 圖 */
{
(*G).arcs[(*G).vexnum][i].adj=0; /* 初始化該行鄰接矩陣的值(無邊或弧) */
(*G).arcs[i][(*G).vexnum].adj=0; /* 初始化該列鄰接矩陣的值(無邊或弧) */
}
(*G).arcs[(*G).vexnum][i].info=NULL; /* 初始化相關(guān)信息指針 */
(*G).arcs[i][(*G).vexnum].info=NULL;
}
(*G).vexnum+=1; /* 圖G的頂點數(shù)加1 */
}
Status DeleteVex(MGraph *G,VertexType v)
{ /* 初始條件: 圖G存在,v是G中某個頂點。操作結(jié)果: 刪除G中頂點v及其相關(guān)的弧 */
int i,j,k;
VRType m=0;
k=LocateVex(*G,v); /* k為待刪除頂點v的序號 */
if(k<0) /* v不是圖G的頂點 */
return ERROR;
if((*G).kind==DN||(*G).kind==AN) /* 網(wǎng) */
m=INFINITY;
for(j=0;j<(*G).vexnum;j++)
if((*G).arcs[j][k].adj!=m) /* 有入弧或邊 */
{
if((*G).arcs[j][k].info) /* 有相關(guān)信息 */
free((*G).arcs[j][k].info); /* 釋放相關(guān)信息 */
(*G).arcnum--; /* 修改弧數(shù) */
}
if((*G).kind==DG||(*G).kind==DN) /* 有向 */
for(j=0;j<(*G).vexnum;j++)
if((*G).arcs[k][j].adj!=m) /* 有出弧 */
{
if((*G).arcs[k][j].info) /* 有相關(guān)信息 */
free((*G).arcs[k][j].info); /* 釋放相關(guān)信息 */
(*G).arcnum--; /* 修改弧數(shù) */
}
for(j=k+1;j<(*G).vexnum;j++) /* 序號k后面的頂點向量依次前移 */
strcpy((*G).vexs[j-1],(*G).vexs[j]);
for(i=0;i<(*G).vexnum;i++)
for(j=k+1;j<(*G).vexnum;j++)
(*G).arcs[i][j-1]=(*G).arcs[i][j]; /* 移動待刪除頂點之后的矩陣元素 */
for(i=0;i<(*G).vexnum;i++)
for(j=k+1;j<(*G).vexnum;j++)
(*G).arcs[j-1][i]=(*G).arcs[j][i]; /* 移動待刪除頂點之下的矩陣元素 */
(*G).vexnum--; /* 更新圖的頂點數(shù) */
return OK;
}
Status InsertArc(MGraph *G,VertexType v,VertexType w)
{ /* 初始條件: 圖G存在,v和W是G中兩個頂點 */
/* 操作結(jié)果: 在G中增添弧<v,w>,若G是無向的,則還增添對稱弧<w,v> */
int i,l,v1,w1;
char *info,s[MAX_INFO];
v1=LocateVex(*G,v); /* 尾 */
w1=LocateVex(*G,w); /* 頭 */
if(v1<0||w1<0)
return ERROR;
(*G).arcnum++; /* 弧或邊數(shù)加1 */
if((*G).kind%2) /* 網(wǎng) */
{
printf("請輸入此弧或邊的權(quán)值: ");
scanf("%d",&(*G).arcs[v1][w1].adj);
}
else /* 圖 */
(*G).arcs[v1][w1].adj=1;
printf("是否有該弧或邊的相關(guān)信息(0:無 1:有): ");
scanf("%d%*c",&i);
if(i)
{
printf("請輸入該弧或邊的相關(guān)信息(<%d個字符)：",MAX_INFO);
gets(s);
l=strlen(s);
if(l)
{
info=(char*)malloc((l+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[v1][w1].info=info;
}
}
if((*G).kind>1) /* 無向 */
{
(*G).arcs[w1][v1].adj=(*G).arcs[v1][w1].adj;
(*G).arcs[w1][v1].info=(*G).arcs[v1][w1].info; /* 指向同一個相關(guān)信息 */
}
return OK;
}
Status DeleteArc(MGraph *G,VertexType v,VertexType w)
{ /* 初始條件: 圖G存在,v和w是G中兩個頂點 */
/* 操作結(jié)果: 在G中刪除弧<v,w>,若G是無向的,則還刪除對稱弧<w,v> */
int v1,w1;
v1=LocateVex(*G,v); /* 尾 */
w1=LocateVex(*G,w); /* 頭 */
if(v1<0||w1<0) /* v1、w1的值不合法 */
return ERROR;
if((*G).kind%2==0) /* 圖 */
(*G).arcs[v1][w1].adj=0;
else /* 網(wǎng) */
(*G).arcs[v1][w1].adj=INFINITY;
if((*G).arcs[v1][w1].info) /* 有其它信息 */
{
free((*G).arcs[v1][w1].info);
(*G).arcs[v1][w1].info=NULL;
}
if((*G).kind>=2) /* 無向,刪除對稱弧<w,v> */
{
(*G).arcs[w1][v1].adj=(*G).arcs[v1][w1].adj;
(*G).arcs[w1][v1].info=NULL;
}
(*G).arcnum--;
return OK;
}
Boolean visited[MAX_VERTEX_NUM]; /* 訪問標(biāo)志數(shù)組(全局量) */
Status(*VisitFunc)(VertexType); /* 函數(shù)變量 */
void DFS(MGraph G,int v)
{ /* 從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖G。算法7.5 */
VertexType w1,v1;
int w;
visited[v]=TRUE; /* 設(shè)置訪問標(biāo)志為TRUE(已訪問) */
VisitFunc(G.vexs[v]); /* 訪問第v個頂點 */
strcpy(v1,*GetVex(G,v));
for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w))))
if(!visited[w])
DFS(G,w); /* 對v的尚未訪問的序號為w的鄰接頂點遞歸調(diào)用DFS */
}
void DFSTraverse(MGraph G,Status(*Visit)(VertexType))
{ /* 初始條件: 圖G存在,Visit是頂點的應(yīng)用函數(shù)。算法7.4 */
/* 操作結(jié)果: 從第1個頂點起,深度優(yōu)先遍歷圖G,并對每個頂點調(diào)用函數(shù)Visit */
/* 一次且僅一次。一旦Visit()失敗,則操作失敗 */
int v;
VisitFunc=Visit; /* 使用全局變量VisitFunc,使DFS不必設(shè)函數(shù)指針參數(shù) */
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE; /* 訪問標(biāo)志數(shù)組初始化(未被訪問) */
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v); /* 對尚未訪問的頂點調(diào)用DFS */
printf("\n");
}
typedef VRType QElemType; /* 隊列類型 */
#include"c3-2.h" /* BFSTraverse()用 */
#include"bo3-2.c" /* BFSTraverse()用 */
void BFSTraverse(MGraph G,Status(*Visit)(VertexType))
{ /* 初始條件: 圖G存在,Visit是頂點的應(yīng)用函數(shù)。算法7.6 */
/* 操作結(jié)果: 從第1個頂點起,按廣度優(yōu)先非遞歸遍歷圖G,并對每個頂點調(diào)用函數(shù) */
/* Visit一次且僅一次。一旦Visit()失敗,則操作失敗。 */
/* 使用輔助隊列Q和訪問標(biāo)志數(shù)組visited */
int v,u,w;
VertexType w1,u1;
LinkQueue Q;
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE; /* 置初值 */
InitQueue(&Q); /* 置空的輔助隊列Q */
for(v=0;v<G.vexnum;v++)
if(!visited[v]) /* v尚未訪問 */
{
visited[v]=TRUE; /* 設(shè)置訪問標(biāo)志為TRUE(已訪問) */
Visit(G.vexs[v]);
EnQueue(&Q,v); /* v入隊列 */
while(!QueueEmpty(Q)) /* 隊列不空 */
{
DeQueue(&Q,&u); /* 隊頭元素出隊并置為u */
strcpy(u1,*GetVex(G,u));
for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))
if(!visited[w]) /* w為u的尚未訪問的鄰接頂點的序號 */
{
visited[w]=TRUE;
Visit(G.vexs[w]);
EnQueue(&Q,w);
}
}
}
printf("\n");
}
void Display(MGraph G)
{ /* 輸出鄰接矩陣G */
int i,j;
char s[7],s1[3];
switch(G.kind)
{
case DG: strcpy(s,"有向圖\0");
strcpy(s1,"弧\0");
break;
case DN: strcpy(s,"有向網(wǎng)\0");
strcpy(s1,"弧\0");
break;
case AG: strcpy(s,"無向圖\0");
strcpy(s1,"邊\0");
break;
case AN: strcpy(s,"無向網(wǎng)\0");
strcpy(s1,"邊\0");
}
printf("%d個頂點%d條%s的%s\n",G.vexnum,G.arcnum,s1,s);
for(i=0;i<G.vexnum;++i) /* 輸出G.vexs */
printf("G.vexs[%d]=%s\n",i,G.vexs[i]);
printf("G.arcs.adj:\n"); /* 輸出G.arcs.adj */
for(i=0;i<G.vexnum;i++)
{
for(j=0;j<G.vexnum;j++)
printf("%6d",G.arcs[i][j].adj);
printf("\n");
}
printf("G.arcs.info:\n"); /* 輸出G.arcs.info */
printf("頂點1(弧尾) 頂點2(弧頭) 該%s信息：\n",s1);
if(G.kind<2) /* 有向 */
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
{
if(G.arcs[i][j].info)
printf("%5s %11s %s\n",G.vexs[i],G.vexs[j],G.arcs[i][j].info);
}
else /* 無向 */
{
for(i=0;i<G.vexnum;i++)
for(j=i+1;j<G.vexnum;j++)
if(G.arcs[i][j].info)
printf("%5s %11s %s\n",G.vexs[i],G.vexs[j],G.arcs[i][j].info);
}
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -