#include?“DS.h“
#include?“ALGraph.h“


/*查找頂點v在鄰接表存儲法中的下標*/
int?LocateVex1（ALGraph?G?char?v）
{
????int?i;
????for（i?=?0;?i?????????if（G.vertices[i].data?==?v）
????????????return?i;???????????????/*找到頂點返回下標*/
????return?-1;
}

/*在鄰接表中插入頂點v的鄰接點w*/
int?InsertList1（ALGraph?&G?int?i?int?j）
{
???????ArcNode?*p;
???????if（i==-1||j==-1||i==j）
????????return?ERROR;
???????p=（ArcNode?*）malloc（sizeof（ArcNode））;
???????p->adjvex=j;???????/*插入鄰接點*/
???????p->nextarc=NULL;
???????if（!G.vertices[i].firstarc）
????????G.vertices[i].firstarc=p;??/*頭插法*/
???????else
???????{
????????p->nextarc=G.vertices[i].firstarc->nextarc;
????????G.vertices[i].firstarc->nextarc=p;
???????}
????return?1;
}
/*請寫出有向帶權圖的鄰接表的生成函數*/
int?CreateDN1（ALGraph?&G）
{
????int?i?j?kw;
????char?v1?v2;
????printf（“請輸入有向圖G的頂點數和邊數：“）;
????scanf（“%d?%d“?&G.vexnum?&G.arcnum）;
????printf（“請輸入%d個頂點名字（以空格區分）：“?G.vexnum）;
????for（i?=?0;?i?????{
????????scanf（“?%c“?&G.vertices[i].data）;??/*請注意輸入格式*/
????????G.vertices[i].firstarc?=?NULL;?/*鄰接表初始化為空*/
????}
????for（k?=?1;?k?<=?G.arcnum;?k++）
????{
????????printf（“請輸入第%d條邊的兩個頂點（以字符表示，字符間以空格區分）和權值：“?k）;
????????scanf（“?%c?%c?%d“?&v1?&v2&w）;??/*請注意輸入格式*/
????????i?=?LocateVex1（G?v1）;???????/*確定v1和v2的下標*/
????????j?=?LocateVex1（G?v2）;
????????InsertList1（G?i?j）;???/*生成各自的鄰接表（記錄權值）*/
????}
????return?OK;
}


/*查找頂點v在鄰接矩陣存儲法中的下標*/
int?LocateVex（MGraph?G?char?v）
{
????int?i;
????for（i?=?0;?i?????????if（G.vexs[i]?==?v）
????????????return?i;
????return?-1;
}

/*請寫出有向帶權圖的鄰接矩陣的生成函數*/
Status?CreateDN（MGraph?&G）
{
????int?i?j?k?value;
????char?v1?v2;
????printf（“請輸入圖G的頂點數和邊數：“）;
????scanf（“%d?%d“?&G.vexnum?&G.arcnum）;
????printf（“請輸入%d個頂點名字（以空格區分）：“?G.vexnum）;
????for（i?=?0;?i?????????scanf（“?%c“?&G.vexs[i]）;??/*請注意輸入格式*/
????for（i?=?0;?i?????????for（j?=?0;?j?????????????G.arcs[i][j]?=?MAX;
????for（k?=?1;?k?<=?G.arcnum;?k++）
????{
????????printf（“請輸入第%d條邊的兩個頂點（以字符表示，字符間以空格區分）及權值：“?k）;
????????scanf（“?%c?%c?%d“?&v1?&v2?&value）;??/*請注意輸入格式*/
????????i?=?LocateVex（G?v1）;???????/*確定v1和v2的下標*/
????????j?=?LocateVex（G?v2）;
????????if（i?>=?0?&&?j?>=?0）????????/*修改鄰接矩陣的信息*/
????????????G.arcs[i][j]?=?value;
????}
????return?OK;
}


/*在鄰接表中插入頂點v的鄰接點w*/
int?InsertList（ALGraph?&G?int?i?int?j）
{
???????ArcNode?*p;
???????if（i==-1||j==-1||i==j）
????????return?ERROR;
???????p=（ArcNode?*）malloc（sizeof（ArcNode））;
???????p->adjvex=j;???????/*插入鄰接點*/
???????p->nextarc=NULL;
???????if（!G.vertices[i].firstarc）
????????G.vertices[i].firstarc=p;??/*頭插法*/
???????else
???????{
????????p->nextarc=G.vertices[i].firstarc->nextarc;
????????G.vertices[i].firstarc->nextarc=p;
???????}
????return?1;
}


/*鍵盤輸入數據，分別建立一個有向圖的鄰接表和一個無向圖的鄰接矩陣。
（2）輸出該鄰接表和鄰接矩陣。
（3）以有向圖的鄰接表為基礎輸出它的拓撲排序序列。
（4）以無向圖的鄰接矩陣為基礎實現最小生成樹的PRIM算法。
（5）以有向圖的鄰接矩陣為基礎實現Dijkstra算法輸出單源點到其它頂點的

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2018-07-02?21:48??minTree\
?????文件?????????744??2018-06-24?15:56??minTree\ALGraph.h
?????目錄???????????0??2018-07-02?21:48??minTree\bin\
?????目錄???????????0??2018-07-02?21:48??minTree\bin\Debug\
?????文件???????39910??2018-06-24?16:12??minTree\bin\Debug\minTree.exe
?????文件?????????281??2018-06-24?15:42??minTree\DS.h
?????文件????????8905??2018-06-24?16:06??minTree\main.cpp
?????文件?????????336??2018-06-02?14:56??minTree\MGraph.h
?????文件????????1262??2018-06-02?16:13??minTree\minTree.cbp
?????文件????????1111??2018-06-24?16:12??minTree\minTree.depend
?????文件?????????740??2018-06-24?16:23??minTree\minTree.layout
?????目錄???????????0??2018-07-02?21:48??minTree\obj\
?????目錄???????????0??2018-07-02?21:48??minTree\obj\Debug\
?????文件???????13971??2018-06-24?16:12??minTree\obj\Debug\main.o
?????文件????????3836??2018-06-24?16:12??minTree\obj\Debug\SqStack.o
?????文件????????1060??2018-06-02?15:29??minTree\SqStack.cpp
?????文件?????????539??2018-06-24?15:57??minTree\SqStack.h