classic algorithm - decoqt/mywiki GitHub Wiki

#define MaxVertices 100 
typedef struct {
	Vertextype vex[MaxVertices];
	int arc[MaxVertices][MaxVertices];
	int vexnum,arcnum;
}MGraph;

#define MaxVertices 100 
typedef struct {
	int adjvex;
	//Weighttype cost ;
	struct ArcNode *nextarc;
}ArcNode;

typedef struct{
	VertexType data;
	ArcNode *firstarc;
}Vnode,AdjList[Maxvertices];

tyepdef struct{
	int vexnum,arcnum;
	Adjlist vertices;
}AlGraph;

#define MaxVertices 100 
enum VisitIf{unvisited,visited};	
tyepdef struct EBox {
	VisitIf mark; // 访问标记
	int ivex,jvex; // 该边依附的两个顶点的位置
	EBox *ilink,*jlink; // 分别指向依附这两个顶点的下一条边
	InfoType *info; // 该边信息指针
}EBox;

typedef struct VexBox{
	VertexType data;
	EBox *firstedge; // 指向第一条依附该顶点的边
}VexBox;

typedef struct  {
	VexBox adjmulist[MaxVertices];
	int vexnum,edgenum; // 无向图的当前顶点数和边数
}AMLGraph;

#define MaxVertices 100 
tyepdef struct ArcBox {
	int tailvex,headvex; // 该边依附的两个顶点的位置
	struct ArcBox *hlink,*tlink; // 分别为弧头相同和弧尾相同的弧的链域
	InfoType *info; // 该边信息指针
}Arcbox;

typedef struct VexNode{
	VertexType data;
	Arcbox *firstin,firstout; // 指向第一条依附该顶点的边
}VexNode;

typedef struct  {
	VexNode xlist[MaxVertices];
	int vexnum,edgenum; // 无向图的当前顶点数和边数
}OLGraph;

void BFSTraverse(Graph G)
{
	for (i = 0; i<G.vexnum; i++)
		visited[i] = 0;
	for(i=0; i<G.vexnum;i++){
		if(!visited[i])
			BFS(G,i);
	}	}

void DFSTraverse(Graph G)
{
	for (i = 0; i<G.vexnum; i++)
		visited[i] = 0;
	for(i=0; i<G.vexnum;i++){
		if(!visited[i])
			DFS(G,i);
	}	}

void(Graph G,Tree T){
	T={};U={w};
	while(!(V-U))
		if(weight(u,v) is minimum among u belongs U,and v belongs(V-U)){
			T = T plus {(u,v)}
			U= U plus v
		} 
}

void Kruskal(Graph G,Tree T)
{
	T = V;
	numS = n;//不连通分量
	while(numS>1){
		select minimum weight (u,v) from E;
		if(u,v belongs different connected components){
			T = T plus (u,v);
			numS--;
		}
	}
}

u := Extract_Min(Q) 在顶点集合 Q 中搜索有最小的 d[u] 值的顶点 u。  这个
顶 点被从集合 Q 中删除并返回给用户。

function Dijkstra(G, w, s)
	for each vertex v in V[G]                        // 初始化
		d[v] := infinity
		previous[v] := undefined
	d[s] := 0
	S := empty set
	Q := set of all vertices
	while Q is not an empty set                      // Dijkstra演算法主體
		u := Extract_Min(Q)
		S := S union {u}
		for each edge (u,v) outgoing from u
			if d[v] > d[u] + w(u,v)             // 拓展边（u,v）
				d[v] := d[u] + w(u,v)
				previous[v] := u

s := empty sequence 
u := t
while defined u                                        
	insert u to the beginning of S
	u := previous[u]

DIJKSTRA(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)
S ← Ø
Q ← V[G]                                 //V*O（1）
while Q ≠ Ø
	do u ← EXTRACT-MIN(Q)     //EXTRACT-MIN，V*O（V），V*O（lgV）
	S ← S ∪{u}
	for each vertex v ∈ Adj[u]
		do RELAX(u, v, w)       //松弛技术，E*O（1），E*O（lgV）。

for k ← 1 to n do  	 	
	for i ← 1 to n do  
		for j ← 1 to n do  
			if (Di,k + Dk,j < Di,j) then  
				Di,j ← Di,k + Dk,j;  
				


BELLMAN-FORD(G, w, s)
INITIALIZE-SINGLE-SOURCE(G, s)   //对每个顶点初始化 ，O(V) 
for i ← 1 to |V[G]| - 1
	do for each edge (u, v) ∈ E[G]
		do RELAX(u, v, w)    //针对每个顶点(V-1个)，都运用松弛技术O(E)，计为O（(v-1)*E)）
for each edge (u, v) ∈ E[G]
	do if d[v] > d[u] + w(u, v)
		then return FALSE     //检测图中每条边，判断是否包含负权回路，
                                //若d[v]>d[u]+w(u，v)，则表示包含，返回FALSE，
return TRUE                      //不包含负权回路，返回TRUE

#include "stdio.h"
#define MAX_VERTEX_NUM 20
#include "conio.h"
#include "stdlib.h"
#define STACK_INIT_SIZE 16
#define STACKINCREMENT 5

typedef  int SElemType;
typedef char VertexType;

typedef struct{
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;

//我们依然用邻接表来作图的存储结构
typedef struct ArcNode{
	int adjvex;
	struct ArcNode *nextarc;
	int info;
}ArcNode;  //表结点类型

typedef struct VNode{
	VertexType data;
	int count;
	ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM]; //头结点

typedef struct{
	AdjList vertices;  //邻接表
	int vexnum,arcnum;
}ALGraph;

 int InitStack(SqStack &S)
{
	S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
	if(!S.base) exit(-1);
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return 1;
}//InitStack

int Push(SqStack &S,SElemType e)
{
	if((S.top-S.base)>=S.stacksize)｛
		S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
		 if(!S.base) exit(-1);
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}//if
	*(S.top++)=e;
	return 1;
}//Push

int Pop(SqStack &S,SElemType &e)
{
	if(S.top==S.base) return 0;
	e=*(S.top--);      
	return 1;
}//Pop

int StackEmpty(SqStack &S)
{
	if(S.top==S.base) return 1;
	else return 0;
}//StackEmpty

int LocateVex(ALGraph G,char u)
{
	int i;
	for (i=0;i<G.vexnum;i++){
		if(u==G.vertices[i].data) 
			return i;
	}
	if (i==G.vexnum) 
		printf("Error u!\n");exit(1);
	return 0;
}

void CreateALGraph_adjlist(ALGraph &G)
{    
	int i,j,k,w; 
	char v1,v2,enter;
	ArcNode *p;
	printf("Input vexnum & arcnum:\n");
	scanf("%d",&G.vexnum);
	scanf("%d",&G.arcnum);
	printf("Input Vertices(以回车隔开各个数据):\n");
	for (i=0;i<G.vexnum;i++){    
		scanf("%c%c",&enter,&G.vertices[i].data);//注意点
		G.vertices[i].firstarc=NULL;
	}//for
	printf("Input Arcs(v1,v2,w)以回车分开各个数据:\n");
	for (k=0;k<G.arcnum;k++){
		scanf("%c%c",&enter,&v1);
    		scanf("%c%c",&enter,&v2);
		i=LocateVex(G,v1);
		j=LocateVex(G,v2);
		p=(ArcNode*)malloc(sizeof(ArcNode));
		p->adjvex=j;  
		p->nextarc=G.vertices[i].firstarc; //前插法,即每次都插入到头结点的后面
		G.vertices[i].firstarc=p;
		printf("Next\n");	
	}//for     
	return;
}//CreateALGraph_adjlist

void FindInDegree(ALGraph &G)
{
	int i,j;
	for(i=0;i<G.vexnum;i++){
		G.vertices[i].count=0;
	}//for
	for(j=0;j<G.vexnum;j++){
		for(ArcNode *p=G.vertices[j].firstarc;p;p=p->nextarc)
			G.vertices[p->adjvex].count++;
	}//for
}//FindInDegree

int TopoSort(ALGraph &G)
{
	SqStack S;
	FindInDegree(G);
	InitStack(S);
	for(int i=0;i<G.vexnum;i++)
		if(G.vertices[i].count==0) 
			Push(S,i);
	
	int countt=0;
	while(!StackEmpty(S)){
		int i,m;
		m=Pop(S,i);
		printf(" %c",G.vertices[i].data); ++countt;
		for(ArcNode *p=G.vertices[i].firstarc;p;p=p->nextarc){  
			int k=p->adjvex;
			if(!(--G.vertices[k].count)) 
				Push(S,k);
		}//for
	}//while
	if(countt<G.vexnum) 
		return false;
	else
		return true;
}//TopoSort

int TopoSort_DFS(ALGraph &G)
{
	SqStack S;
	InitStack(S);
	for(int i=0;i<G.vexnum;i++){
		visited[i] = 0;
	}
	for(int i=0;i<G.vexnum;i++)
		if(!visited[i])
			DFS_L(G,i)
	
	int countt=0;
	while(!StackEmpty(S)){
		Pop(S,i);printf(" %c",G.vertices[i].data); ++countt;
	}//while
	
	if(countt < G.vexnum) return false;
	else return true;
}//TopoSort_DFS

void DFS_L(Graph G,int i)
{		
	visited[i] = 1;
	for (ArcNode *p = G.verticles[i].firstarc;p;p = p->nextarc){
		int w  = p->adjvex;
		if(!visited[w])
			DFS_L(G,w);
	}
	push(S,i);
}
	
int main()
{
	ALGraph G;
	CreateALGraph_adjlist(G);
	if(TopoSort(G))
		return true;
}

//S is vertices of 0 degree ;T stands for vertices
int ToplogicalOrder(ALGraph &G,Stack &T)
{
	SqStack S;
	FindInDegree(G);
	InitStack(S);
	ve[0..G.vexnum-1]=0;//**changes: calculate ve[k]**
	for(int i=0;i<G.vexnum;i++)
		if(G.vertices[i].count==0) 
			Push(S,i);
			
	int countt=0;
	while(!StackEmpty(S)){
		Pop(S,j);Push(T,j);++countt;
		for(ArcNode *p=G.vertices[j].firstarc;p;p=p->nextarc){  
			int k=p->adjvex;
			if(!(--G.vertices[k].count)) 
				Push(S,k);
			if(ve[j]+*(p->info)>ve[k])
				ve[k]=ve[j]+*(p->info);
		}//for  *(p->info)=dut(<j,k>)
	}//while
	if(countt<G.vexnum) 
		return false;   // 该有向网有回路
	else
		return true;
}//TopoSort

status CriticalPath(ALGraph G)
{
	Stack T;
		inta,j,k,el,ee,dut;
		chartag;

	if(!ToplogicalOrder(G,T)) return ERROR;
	vl[0..G.vexnum-1]=ve[G.vexnum-1];
	while(!StackEmpty(T))
		for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc){
			k=p->adjvex; dut=*(p->info);
			if(vl[k]-dut<vl[j]) 
				vl[j]=vl[k]-dut;
		}
	for(j=0;j<G.vexnum;++j)
		for(p=G.vertices[j].firstarc;p;p=p->nextarc){
			k=p>adjvex; dut=*(p->info);
			ee=ve[j]; el=vl[k];
			tag=(ee==el)?’*’：’’；
			printf(j,k,dut,ee,el,tag);
	}
}

void GraphPFS(Graph G, int src)
{
	PQinit(G, src);
	while (!PQempty()) {
		int v = PQdelmax(); // 取出优先级最大的顶点
		Update(v);
		Link t;
		for (t = G->adj[v]; t != NULL; t = t->next) {
			if (ShouldInsert(t))
					PQinsert(t, v); // 顶点t->v加入优先队列
			else if (ShouldChange(t))
					PQchange(t, v); // 改变顶点t->v的优先级
				}
		}
}