?#include?“iostream.h“
?#include
?#include
?#include?/*?malloc（）等?*/
?#include?/*?INT_MAX等?*/
?#include?/*?EOF（=^Z或F6）NULL?*/
?#include?/*?atoi（）?*/
?#include?/*?eof（）?*/
?#include?/*?floor（）ceil（）abs（）?*/
?#include?/*?exit（）?*/
?#define?TRUE?1
?#define?FALSE?0
?#define?OK?1
?#define?ERROR?0
?#define?INFEASIBLE?-1
?typedef?int?Status;?/*?Status是函數的類型其值是函數結果狀態代碼，如OK等?*/
?typedef?int?Boolean;?/*?Boolean是布爾類型其值是TRUE或FALSE?*/
?#define?MAX_NAME?5?/*?頂點字符串的最大長度+1?*/
?#define?MAX_INFO?20?/*?相關信息字符串的最大長度+1?*/
?typedef?int?VRType;
?typedef?char?InfoType;
?typedef?char?VertexType[MAX_NAME];




/*??圖的數組（鄰接矩陣）存儲表示?*/
?#define?INFINITY?INT_MAX?/*?用整型最大值代替∞?*/
?#define?MAX_VERTEX_NUM?20?/*?最大頂點個數?*/
?typedef?enum{DGDNAGAN}GraphKind;?/*?{有向圖有向網無向圖無向網}?*/
?typedef?struct
?{
???int?adj;?/*?頂點關系類型。對無權圖，用1（是）或0（否）表示相鄰否；?*/
	???????/*?對帶權圖，c則為權值類型?*/
???InfoType?*info;?/*?該弧相關信息的指針（可無）?*/
?}ArcCellAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
?typedef?struct
?{
???VertexType?vexs[MAX_VERTEX_NUM];?/*?頂點向量?*/
???AdjMatrix?arcs;?/*?鄰接矩陣?*/
???int?vexnumarcnum;?/*?圖的當前頂點數和弧數?*/
???GraphKind?kind;?/*?圖的種類標志?*/
?}MGraph;

?
?typedef?int?InfoType1;?/*?存放網的權值?*/
?typedef?char?VertexType[MAX_NAME];?/*?字符串類型?*/
??/*?圖的鄰接表存儲表示?*/
?#define?MAX_VERTEX_NUM?20
?typedef?struct?ArcNode
?{
???int?adjvex;?/*?該弧所指向的頂點的位置?*/
???struct?ArcNode?*nextarc;?/*?指向下一條弧的指針?*/
???InfoType1?*info;?/*?網的權值指針）?*/
?}ArcNode;?/*?表結點?*/
?typedef?struct
?{
???VertexType?data;?/*?頂點信息?*/
???ArcNode?*firstarc;?/*?第一個表結點的地址指向第一條依附該頂點的弧的指針?*/
?}VNodeAdjList[MAX_VERTEX_NUM];?/*?頭結點?*/
?typedef?struct
?{
???AdjList?vertices;
???int?vexnumarcnum;?/*?圖的當前頂點數和弧數?*/
???int?kind;?/*?圖的種類標志?*/
?}ALGraph;


?
??int?LocateVex（MGraph?GVertexType?u）
?{?/*?初始條件:圖G存在u和G中頂點有相同特征?*/
???/*?操作結果:若G中存在頂點u則返回該頂點在圖中位置;否則返回-1?*/
???int?i;
???for（i=0;i?????if（strcmp（uG.vexs[i]）==0）
???????return?i;
???return?-1;
?}


?Status?CreateDG（MGraph?*G）
?{?/*?采用數組（鄰接矩陣）表示法構造有向圖G?*/
???int?ijklIncInfo;
???char?s[MAX_INFO]*info;
???VertexType?vavb;
???printf（“請輸入有向圖G的頂點數:“）;
???scanf（“%d“&（*G）.vexnum）;
???printf（“請輸入有向圖G的弧數?:“）;
???scanf（“%d“&（*G）.arcnum）;
???printf（“弧是否含其它信息（是:1否:0）:?“）;
???scanf（“%d“&IncInfo）;
???printf（“請輸入“）;
???printf（“%d“（*G）.vexnum）;
???printf（“個頂點的值（<%d個字符）:\n“MAX_NAME）;
???for（i=0;i<（*G）.vexnum;++i）?/*?構造頂點向量?*/
?????scanf（“%s“（*G）.vexs[i]）;
???for（i=0;i<（*G）.vexnum;++i）?/*?初始化鄰接矩陣?*/
?????for（j=0;j<（*G）.vexnum;++j）
?????{
???????（*G）.arcs[i][j].adj=0;?/*?圖?*/
???????（*G）.arcs[i][j].info=NULL;
?????}
???printf（“請輸入“）;
???printf（“%d“（*G）.arcnum）;
???printf（“條弧的弧尾?弧頭（以空格作為間隔）:?\n“）;
???for（k=0;k<（*G）.arcnum;++k）
???{
?????scanf（“%s%s%*c“vavb）;??/*?%*c吃掉回車符?*/
?????i=LocateVex（*Gva）;
?????j=LocateVex（*Gvb）;
?????（*G）.arcs[i][j].adj=1;?/*?有向圖?*/
?????if（IncInfo）
?????{
?????