/*—————————-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();
}