#ifndef ALGRAPH_H
#define ALGRAPH_H
#include "head.h" 
typedef char VertexType[20];
/**-----圖的鄰接表存儲表示------*/
typedef struct ArcNode
{
  int adjvex; //該弧所指向的頂點的位置
  struct ArcNode*  nextarc; //指向下一條弧的指針
  int weight; //該弧相關信息
}ArcNode ;

typedef struct VNode
{
  VertexType data ; //頂點信息
  ArcNode* firstarc ; //指向第一條依附該頂點的弧的指針
}VNode,AdjList[MAX_VERTEX_NUM];

typedef struct 
{
  AdjList vertices ; 
  int vexnum;//圖的當前頂點總數
  int arcnum ;//圖的弧數總數
  GraphKind  kind ;  //圖的種類標志  
} ALGraph ;
//孩子兄弟結點存儲結構 
typedef struct CSNode
{ 
  int data;
  struct CSNode* firstchild;
  struct CSNode* nextsibing;        
}CSNode,*CSTree; 

/**---針對鄰接表表示的圖的一些基本操作----*/
Status initALGraph(ALGraph* G);
//圖的初始化，從文件ALGraph.txt中讀入，構造圖的鄰接表
Status DestroyALGraph(ALGraph* G);
//對圖G進行空間的釋放，從此之后就在也不能用G了

int LocalVex(ALGraph* G,VertexType data);
//初始條件：圖G存在，data和G中的頂點有相同的特征
//操作結果：若G中存在頂點data，則返回該頂點在圖中的位置，否則返回其它信息
int LocalArc(ALGraph* G,VertexType v_data,VertexType w_data);
//初始條件：圖G存在，由<v_data,w_data>確定的弧<v,w>存在于圖G中
//操作結果：返回<v,w>的權值，大于0，要是不存在該弧，則返回-1
int getArc(ALGraph* G,int v,int w); 
//初始條件：圖G存在，弧的起點w和終點v
//操作結果：返回弧的權值，要是弧不屬于圖G，則返回-1
int isArc(ALGraph* G,VertexType v_data,VertexType w_data);
//初始條件：圖G存在，v_data，w_data和G中的頂點有相同的特征
//操作結果：若圖G中存在<v,w>則返回 true,否則返回false
Status updateArc(ALGraph* G,VertexType v_data,VertexType w_data,int weight);
//初始條件：圖G存在，v_data，w_data和G中的頂點有相同的特征，且存在<v,w>這條弧
//操作結果：把<v,w>這條弧的權值改為weight,成功返回OK，失敗返回ERROR 
int VexOutDegree(ALGraph* G,VertexType data);
//初始條件：圖G存在，data和G中的頂點有相同的特征
//操作結果:返回頂點data的出度，
int VexInDegree(ALGraph* G,VertexType data);
//初始條件：圖G存在，data和G中的頂點有相同的特征
//操作結果：返回頂點data的入度
Status InsertVex(ALGraph* G, VertexType v);
//初始條件：圖G存在，v和圖中的頂點有相同特征
//操作結果： 在圖G中增加新頂點v,字母樹中加入該頂點的信息
Status DeleteVex(ALGraph* G,VertexType v);
//初始條件：圖G存在，v是G中的某個頂點
//操作結果：刪除G中的頂點及與其相關的弧,刪除它在字母樹的信息，并做相應調整
int InsertArc(ALGraph* G,VertexType v_data,VertexType w_data,int weight);
 //初始條件：圖G存在，v和w是G中的兩個頂點,其信息值分別為v_data和w_data
 //操作結果：在G中增加弧<v,w>,且弧的權值是weight,若G是無向的，則還要增添對稱弧<w,v>
Status DeleteArc(ALGraph* G,VertexType v_data,VertexType w_data);
//初始條件：圖G存在，v和w是G中的兩個頂點,其信息值分別為v_data和w_data
//操作結果：在G中，刪除弧<v,w>,若G是無向的，則還要刪除對稱弧<w,v>

Status DFSTraverse(ALGraph* G,int* visited);
//初始條件：圖G存在，visited數組是圖中頂點的訪問情況
//操作結果：從頂點1起，對全圖G進行深度優先遍歷，同時把遍歷到的頂點的visited置為true;
Status DFS(ALGraph* G,VertexType v,int* visited);
//初始條件：圖G存在，v是G中的某個頂點，visited數組是圖中頂點的訪問情況
//操作結果：從頂點v開始，對圖G進行一次深度優先遍歷,同時把遍歷到的頂點的visited置為true;

Status BFSTraverse(ALGraph* G,int* visited);
//初始條件：圖G存在，visited數組是圖中頂點的訪問情況
//操作結果：從頂點1起，對全圖G進行廣度優先遍歷,同時把遍歷到的頂點的visited置為true;

Status BFS(ALGraph* G,int v,int* visited);
//初始條件：圖G存在，v是圖G中的某個頂點，visited數組是圖中頂點的訪問情況
//操作結果：從頂點v開始，對圖進行一次遍歷，同時把遍歷到的頂點的visited置為true;

/*強連通分量的計算
E1：正向深度優先遍歷，計算遍歷結束序，記入finished向量中；
E2：按照finished倒序選擇起點，逆向深度優先遍歷，每一趟遍歷所經過的頂點以及與這些頂點相關的弧構成一個強連通分量。
*/

Status DFSFinished(ALGraph* G, int v, int visited[], int finished[], int* count);
//初始條件：圖G存在，頂點v在G中，finished向量和visited向量，count值；
//從頂點v出發，正向深度優先遍歷，計算遍歷結束序，記入finished向量中；

int** get_list(ALGraph* G);
//初始條件：存在圖G，是用鄰接表存儲的
//操作結果：返回逆向的鄰接矩陣，
 
Status DFSConnect(ALGraph* G,int* visited,int**  Matrix,int i);
//初始條件：存在連通圖G,和訪問向量visited,和該圖的逆向鄰接矩陣Matrix,和i為遍歷的起點
//操作結果：輸出強連通分量的頂點集，
int get_connect(ALGraph* G,int finished[],int* visited,int**  Matrix);
//初始條件：存在連通圖G，和遍歷完成序finished,和訪問向量visited,和該圖的逆向鄰接矩陣Matrix
//操作結果：輸出強連通分量的頂點集，

Status count_connect(ALGraph* G);
//初始條件：存在連通圖G
//操作結果：輸出強連通分量的頂點集，
void DFSTree(ALGraph* G,int v,CSTree* T,int* visited);
//從第v個頂點出發深度優先遍歷圖G，建立以T為根的生成樹 

void DFSForest(ALGraph* G,CSTree* T);
//建立無向圖G的深度優先生成森林
//（最左）孩子（右）兄弟鏈表T 
void ForestTraverse(CSTree* T) ; 
Status MiniSpanTree_PRIM(ALGraph* G,VertexType data);
//初始條件：無向圖G存在，data是與頂點有相同特征的頂點
//操作結果：輸出G的最小生成樹

Status MiniSpanTree_Kruskal(ALGraph* G);
//初始條件：無向圖G存在,data是與頂點有相同特征的頂點
//操作結果：輸出G的最小生成樹
 
Status FindArticul(ALGraph* G);
//連通圖G以鄰接表作為存儲結構，查找并輸出G上的全部關節點
 
Status DFSArticul(ALGraph* G,int v,int* count,int* visited,int* low);
//從第v個頂點出發深度優先遍歷圖G，查找并輸出關節點，
//count為第幾個訪問，visited記錄頂點初訪問到的次序

Status TopologicalSort(ALGraph* G);
//有向圖G采用鄰接表存儲結構，若G無回路，則輸出G的
//頂點的一個拓撲序列 成功返回OK，失敗返回ERROR
Status TopologicalOrder(ALGraph* G,stack* T,int* ve);
//有向網G采用鄰接表存儲結構，求各頂點事件的最早發生時間ve
//T為拓撲序列頂點棧，S為零入度頂點棧
Status CriticalPath(ALGraph* G);
//G為有向網，輸出G的各項關鍵活動
 
#endif