?? bo7-1.cpp
字號:
// 操作結果: 返回v的第一個鄰接頂點的序號。若頂點在G中沒有鄰接頂點,則返回-1
int i,j=0,k;
k=LocateVex(G,v); // k為頂點v在圖G中的序號
if(G.kind==DN||G.kind==AN) // 網
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的鄰接頂點
// 操作結果: 返回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) // 網
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中頂點有相同特征
// 操作結果: 在圖G中增添新頂點v(不增添與頂點相關的弧,留待InsertArc()去做)
int i;
strcpy(G.vexs[G.vexnum],v); // 構造新頂點向量
for(i=0;i<=G.vexnum;i++)
{
if(G.kind%2) // 網
{
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; // 初始化相關信息指針
G.arcs[i][G.vexnum].info=NULL;
}
G.vexnum+=1; // 圖G的頂點數加1
}
Status DeleteVex(MGraph &G,VertexType v)
{ // 初始條件: 圖G存在,v是G中某個頂點。操作結果: 刪除G中頂點v及其相關的弧
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) // 網
m=INFINITY;
for(j=0;j<G.vexnum;j++)
if(G.arcs[j][k].adj!=m) // 有入弧或邊
{
if(G.arcs[j][k].info) // 有相關信息
free(G.arcs[j][k].info); // 釋放相關信息
G.arcnum--; // 修改弧數
}
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) // 有相關信息
free(G.arcs[k][j].info); // 釋放相關信息
G.arcnum--; // 修改弧數
}
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--; // 更新圖的頂點數
return OK;
}
Status InsertArc(MGraph &G,VertexType v,VertexType w)
{ // 初始條件: 圖G存在,v和W是G中兩個頂點
// 操作結果: 在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++; // 弧或邊數加1
if(G.kind%2) // 網
{
printf("請輸入此弧或邊的權值: ");
scanf("%d",&G.arcs[v1][w1].adj);
}
else // 圖
G.arcs[v1][w1].adj=1;
printf("是否有該弧或邊的相關信息(0:無 1:有): ");
scanf("%d%*c",&i);
if(i)
{
printf("請輸入該弧或邊的相關信息(<%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; // 指向同一個相關信息
}
return OK;
}
Status DeleteArc(MGraph &G,VertexType v,VertexType w)
{ // 初始條件: 圖G存在,v和w是G中兩個頂點
// 操作結果: 在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 // 網
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]; // 訪問標志數組(全局量)
Status(*VisitFunc)(VertexType); // 函數變量
void DFS(MGraph G,int v)
{ // 從第v個頂點出發遞歸地深度優先遍歷圖G。算法7.5
VertexType w1,v1;
int w;
visited[v]=TRUE; // 設置訪問標志為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的鄰接頂點遞歸調用DFS
}
void DFSTraverse(MGraph G,Status(*Visit)(VertexType))
{ // 初始條件: 圖G存在,Visit是頂點的應用函數。算法7.4
// 操作結果: 從第1個頂點起,深度優先遍歷圖G,并對每個頂點調用函數Visit
// 一次且僅一次。一旦Visit()失敗,則操作失敗
int v;
VisitFunc=Visit; // 使用全局變量VisitFunc,使DFS不必設函數指針參數
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE; // 訪問標志數組初始化(未被訪問)
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v); // 對尚未訪問的頂點調用DFS
printf("\n");
}
typedef VRType QElemType; // 隊列類型
#include"c3-2.h" // BFSTraverse()用
#include"bo3-2.cpp" // BFSTraverse()用
void BFSTraverse(MGraph G,Status(*Visit)(VertexType))
{ // 初始條件: 圖G存在,Visit是頂點的應用函數。算法7.6
// 操作結果: 從第1個頂點起,按廣度優先非遞歸遍歷圖G,并對每個頂點調用函數
// Visit一次且僅一次。一旦Visit()失敗,則操作失敗。
// 使用輔助隊列Q和訪問標志數組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; // 設置訪問標志為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,"有向網\0");
strcpy(s1,"弧\0");
break;
case AG: strcpy(s,"無向圖\0");
strcpy(s1,"邊\0");
break;
case AN: strcpy(s,"無向網\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("%11d",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);
}
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -