algraph.h

完全由C语言实现的图的相关操作

#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