NO IMAGE

/*—————————-Graph的定義與操作———————————

基本操作:
1、 CreateGraph(&G,V,VR);
    初始條件:V是圖的頂點集,VR是圖中弧的集合;
    操作結果:按V和VR的定義構成圖?
    ?
2、 DestoryGraph(&G);
    初始條件:圖G存在;
    操作結果:銷燬圖G。

3、 LocateVex(G,u);
    初始條件:圖G存在,u和G中頂點有相同的特徵;
    操作結果:若圖G存在頂點u,則返回該頂點在圖中的位置;否則返回其它資訊。?
    ?
4、 GetVex(G,v);
    初始條件:圖G存在,v是G中的某個頂點;
    操作結果: 返回v的值。

5、 PutVex(&G,v,value);
    初始條件:圖G存在,v是G中的某個頂點;
    操作結果: 對v賦值value。

6、 FirstAdjVex(G,v);
    初始條件:圖G存在,v是G中的某個頂點;
    操作結果: 返回v的第一個鄰接頂點。若頂點在G中沒有鄰接頂點,則返回“空”。?

7、 NextAdjVex(G,v,w);
    初始條件:圖G存在,v是G中的某個頂點,w是v的鄰接頂點;
    操作結果: 返回v的(相對於w的)下一個鄰接頂點。若w是v的最後一個鄰接頂點,
              則返回“空”。?

8、 InsertVex(&G,v);
    初始條件:圖G存在,v和G中頂點有相同的特徵;
    操作結果:在圖G中增加新頂點v。

9、 DeleteVex(&G,v);
    初始條件:圖G存在,v是G中的某個頂點;
    操作結果: 刪出圖G中頂點v及其相關的弧?

10、InsertArc(&G,v,w);
    初始條件:圖G存在,v和w是G中的兩個頂點;
    操作結果: 在G中增添弧<v,w>,若G是無向的,則還要增添對稱弧<w,v>。

11、DFSTraverse(G,Visit());
    初始條件:圖G存在,Visit()是G頂點的應用函式;
    操作結果: 對圖進行深度優先遍歷。在遍歷過程中對每個頂點呼叫函式Visit()一次
              且僅一次。一旦Visit()失敗,則操作失敗。

12、BFSTraverse(G,Visit());
    初始條件:圖G存在,Visit()是G頂點的應用函式;
    操作結果: 對圖進行廣度優先遍歷。在遍歷過程中對每個頂點呼叫函式Visit()一次
              且僅一次。一旦Visit()失敗,則操作失敗。

——————————————————————————*/

/*=============================鄰接矩陣的儲存結構=============================*/
#include<stdio.h>

#define  OK                 1
#define  ERROR              -1
#define  TRUE               1
#define  FALSE              0
#define  ADJACENCY          1
#define  UNADJACENCY        0
#define  NETWORK_INFINITY   32767
#define  MAX_VERTEX_NUM     20

int visited[MAX_VERTEX_NUM];
typedef int VRType;
typedef int VertexType;
typedef char InfoType;

typedef enum{ DG,DN,UDG,UDN }GraphKind;
typedef struct ArcCell {
   VRType  adj;
   InfoType *info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct {
   VertexType  vexs[MAX_VERTEX_NUM];
   AdjMatrix   arcs;
   int         vexnum,arcnum;
   GraphKind   kind;
}AMGraph;

/*========================鄰接矩陣的基本操作的實現============================*/

/*———————–1、 CreateGraph(&G,V,VR)—————————–*/
int CreateGraph( AMGraph *G )
{
   int choice=0;
   printf(” 1-Directed Graph          /n”);
   printf(” 2-Directed Network        /n”);
   printf(” 3-UnDirected Graph        /n”);
   printf(” 4-UnDirected Network      /n/n”);
   do{ if(choice<1||choice>4)printf(” Choose: “);scanf(“%d”,&choice);}
   while(choice<1||choice>4);
   G->kind = (GraphKind)(choice);

   switch(G->kind){
     case  DG 1: return CreateDG(G);
     case  DN 1: return CreateDN(G);
     case UDG 1: return CreateUDG(G);
     case UDN 1: return CreateUDN(G);
     default : return ERROR;
   }
}

int CreateDG( AMGraph *G )
{
   int IncInfo,i,j,k;    VertexType v1,v2;
   printf(“/n/n The Graph’s number of Vertex :”); scanf(“%d”,&(G->vexnum));
   printf(” The Graph’s number of Arcnum :”); scanf(“%d”,&(G->arcnum));
   printf(” The Graph’s incinfo:”); scanf(“%d”, &IncInfo);  printf(“/n”);
   /*頂點編號或者名稱*/
   for(i = 0;i < G -> vexnum ;i ){ printf(” The Graph’s %d Vertex’s NAME:”,i 1); scanf(“%d”,(G->vexs) i); }
   /*初始化鄰接矩陣*/
   for(i=0;i< G->vexnum ;i )
     for(j=0;j< G->vexnum ;j ){ (G->arcs)[i][j].adj = UNADJACENCY; (G->arcs)[i][j].info = NULL ; }
   /* 構造鄰接矩陣 */
   for(k = 0;k < G -> arcnum;k ){
     printf(“/n The %d Arc ./n”,k 1);
     printf(” The tail vertex:”);do{ scanf(“%d”,&v1);if((v1<=0)||(v1>G->vexnum))printf(” ERROR/n The tail vertex:”); }while((v1<=0)||(v1>G->vexnum));
     printf(” The head vertex:”);do{ scanf(“%d”,&v2);if((v2<=0)||(v2>G->vexnum))printf(” ERROR/n The head vertex:”); }while((v2<=0)||(v2>G->vexnum));
     i = LocateVex(*G,v1); j = LocateVex(*G,v2);
     (G->arcs)[i][j].adj = ADJACENCY;
     if(IncInfo){
       printf(” Enter %d arc’s IncInfo:”,k 1);
       scanf(“%s”,(G->arcs)[i][j].info ); fflush(stdin);
     }
     printf(“/n”);
   }
   return OK;
}

int CreateDN(AMGraph *G )
{
   int IncInfo,i,j,k;    VertexType v1,v2,w;
   printf(“/n/n The Graph’s number of Vertex :”); scanf(“%d”,&(G->vexnum));
   printf(” The Graph’s number of Arcnum :”); scanf(“%d”,&(G->arcnum));
   printf(” The Graph’s incinfo:”); scanf(“%d”, &IncInfo);  printf(“/n”);

   /*頂點編號或者名稱*/
   for(i = 0;i < G -> vexnum ;i ){ printf(” The Graph’s %d Vertex’s NAME:”,i 1); scanf(“%d”,(G->vexs) i); }
   /*初始化鄰接矩陣*/
   for(i=0;i< G->vexnum ;i )
     for(j=0;j< G->vexnum ;j ){ (G->arcs)[i][j].adj = NETWORK_INFINITY; (G->arcs)[i][j].info = NULL ; }
   /* 構造鄰接矩陣 */
   for(k = 0;k < G -> arcnum;k ){
     printf(“/n The %d Arc ./n”,k 1);
     printf(” The tail vertex:”);do{ scanf(“%d”,&v1);if((v1<=0)||(v1>G->vexnum))printf(” ERROR/n The tail vertex:”); }while((v1<=0)||(v1>G->vexnum));
     printf(” The head vertex:”);do{ scanf(“%d”,&v2);if((v2<=0)||(v2>G->vexnum))printf(” ERROR/n The head vertex:”); }while((v2<=0)||(v2>G->vexnum));
     printf(” The arc  weight:”);scanf(“%d”,&w);
     i = LocateVex(*G,v1); j = LocateVex(*G,v2);
     (G->arcs)[i][j].adj = w;
     if(IncInfo){
       printf(” Enter %d arc’s IncInfo:”,k 1);
       scanf(“%s”,(G->arcs)[i][j].info ); fflush(stdin);
     }
     printf(“/n”);
   }
   return OK;
}

int CreateUDG( AMGraph *G )
{
   int IncInfo,i,j,k;    VertexType v1,v2;
   printf(“/n/n The Graph’s number of Vertex :”); scanf(“%d”,&(G->vexnum));
   printf(” The Graph’s number of Arcnum :”); scanf(“%d”,&(G->arcnum));
   printf(” The Graph’s incinfo:”); scanf(“%d”, &IncInfo);  printf(“/n”);
   /*頂點編號或者名稱*/
   for(i = 0;i < G -> vexnum ;i ){ printf(” The Graph’s %d Vertex’s NAME:”,i 1); scanf(“%d”,(G->vexs) i); }
   /*初始化鄰接矩陣*/
   for(i=0;i< G->vexnum ;i )
     for(j=0;j< G->vexnum ;j ){ (G->arcs)[i][j].adj = UNADJACENCY; (G->arcs)[i][j].info = NULL ; }
   /* 構造鄰接矩陣 */
   for(k = 0;k < G -> arcnum;k ){
     printf(“/n The %d Arc ./n”,k 1);
     printf(” The tail vertex:”);do{ scanf(“%d”,&v1);if((v1<=0)||(v1>G->vexnum))printf(” ERROR/n The tail vertex:”); }while((v1<=0)||(v1>G->vexnum));
     printf(” The head vertex:”);do{ scanf(“%d”,&v2);if((v2<=0)||(v2>G->vexnum))printf(” ERROR/n The head vertex:”); }while((v2<=0)||(v2>G->vexnum));
     i = LocateVex(*G,v1); j = LocateVex(*G,v2);
     (G->arcs)[i][j].adj = ADJACENCY;
     if(IncInfo){
       printf(” Enter %d arc’s IncInfo:”,k 1);
       scanf(“%s”,(G->arcs)[i][j].info ); fflush(stdin);
     }
     (G->arcs)[j][i] = (G->arcs)[i][j];
     printf(“/n”);
   }
   return OK;
}
int CreateUDN( AMGraph *G )
{
   int IncInfo,i,j,k;
   VertexType v1,v2,w;

   printf(“/n/n The Graph’s number of Vertex :”); scanf(“%d”,&(G->vexnum));
   printf(” The Graph’s number of Arcnum :”); scanf(“%d”,&(G->arcnum));
   printf(” The Graph’s incinfo:”); scanf(“%d”, &IncInfo);  printf(“/n”);

   /*頂點編號或者名稱*/
   for(i = 0;i < G -> vexnum ;i ){
     printf(” The Graph’s %d Vertex’s NAME:”,i 1); scanf(“%d”,(G->vexs) i);
   }
   /*初始化鄰接矩陣*/
   for(i=0;i< G->vexnum ;i )
     for(j=0;j< G->vexnum ;j ){
      (G->arcs)[i][j].adj = NETWORK_INFINITY; (G->arcs)[i][j].info = NULL ;
     }
   /* 構造鄰接矩陣 */
   for(k = 0;k < G -> arcnum;k ){
     printf(“/n The %d Arc ./n”,k 1);
     printf(” The tail vertex:”);do{ scanf(“%d”,&v1);if((v1<=0)||(v1>G->vexnum))printf(” ERROR/n The tail vertex:”); }while((v1<=0)||(v1>G->vexnum));
     printf(” The head vertex:”);do{ scanf(“%d”,&v2);if((v2<=0)||(v2>G->vexnum))printf(” ERROR/n The head vertex:”); }while((v2<=0)||(v2>G->vexnum));
     printf(” The arc  weight:”);scanf(“%d”,&w);
     i = LocateVex(*G,v1); j = LocateVex(*G,v2);
     (G->arcs)[i][j].adj = w;
     if(IncInfo){
       printf(” Enter %d arc’s IncInfo:”,k 1);
       scanf(“%s”,(G->arcs)[i][j].info ); fflush(stdin);
     }
     (G->arcs)[j][i] = (G->arcs)[i][j];
     printf(“/n”);
   }
   return OK;
}

 

/*—————————-3、 LocateVex(G,u)——————————*/
int LocateVex( AMGraph G,VertexType u )
{
   int ivex;
   for(ivex = 0;ivex < G.vexnum ;ivex )
     if(u == G.vexs[ivex])
       return ivex;
   return ERROR;
}

/*————————6、 FirstAdjVex(G,v)—————————-*/
/*操作結果: 返回v的第一個鄰接頂點。若頂點在G中沒有鄰接頂點,則返回“空”。*/
int FirstAdjVex(AMGraph G,int ivex)
{
   int jvex;
   for(jvex =0;jvex < G.vexnum;jvex )
     if(G.arcs[ivex][jvex].adj == ADJACENCY)  return jvex;
   if(jvex >= G.vexnum)  return ERROR;
}

/*————————-7、 NextAdjVex(G,v,w)—————————-*/
/*操作結果:返回v的(相對於w的)下一個鄰接頂點。若w是v的最後一個鄰接頂點,則返回“空”。 */

int NextAdjVex(AMGraph G,int ivex ,int jw)
{
   for(jw =1 ;jw < G.vexnum;jw )
     if(G.arcs[ivex][jw].adj == ADJACENCY) return jw;
   if(jw >= G.vexnum)   return  ERROR;
}
/*————————–11、深度優先遍歷———————————*/
/* int visited[MAX_VERTEX_NUM] */
void VisitFunc(AMGraph G,int v)
{
  printf(“%6d”,G.vexs[v]);
}

void DFS( AMGraph G,int v )
{
   int w;
   visited[v] = TRUE; VisitFunc(G,v);
   for(w = FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))
     if(!visited[w])  DFS(G,w);
}

void DFSTraverse( AMGraph G,int v )
{
   for(v=0;v<G.vexnum;v ) visited[v] = FALSE;
   for(v=0;v<G.vexnum;v )
     if(!visited[v]) DFS(G,v);
}

 

/*============================================================================*/

/*============================主函式main()====================================*/
int main( void )
{
   int i,j,ivex;
   AMGraph G;
   CreateGraph( &G );

   printf(“The Adjacency Matrix is:/n”);
   for(i = 0;i < G.vexnum;i ){
     for(j = 0;j < G.vexnum;j )
       printf(“%6d”,G.arcs[i][j].adj);
     printf(“/n”);
   }

   printf(“DFSTraverse AMGraph:/n”);
   DFSTraverse(G,ivex);
   getch();

}