depth-first-traverse.c

此代码为“图的深度优先遍历”的源代码

 #include<stdio.h>
#include<stdlib.h>

#define MaxSize 50
#define MaxVertices 20
#define MaxWeight 10000

typedef char DataType;

typedef struct
{
	DataType list[MaxSize];
	int size;
}Seqlist;

typedef struct Graph
{
	Seqlist Vertices;
	int Edge[MaxVertices][MaxVertices];
	int NumOfEdges;
}AdjMGraph;
 
typedef struct edge
{
	int row;
	int col;
	int weight;
}EdgeInformation;

void ListInitiate(Seqlist *L);
int ListInsert(Seqlist *L,int i,DataType x);
int ListDelete(Seqlist *L,int i,DataType *x);
int ListGet(Seqlist L,int i,DataType *x);
void InitiateGraph(AdjMGraph *G,int n);
void InsertVertex(AdjMGraph *G,DataType Vertex);                                                       /*函数声明！！！同时起提升作用！！！*/
void InsertEdge(AdjMGraph *G,int v1,int v2,int weight);
void DeleteVertices(AdjMGraph *G,int v);
void DeleteEdge(AdjMGraph *G,int v1,int v2);
int GetFirstVertex(AdjMGraph G,int v);
int GetNextVertex(AdjMGraph G,int v1,int v2);
void CreatGraph(AdjMGraph *G,DataType v[],int n,EdgeInformation E[],int e);  
void DFSTraverse(AdjMGraph G);
void DFS(AdjMGraph G,int v);

int visited[MaxVertices];

void ListInitiate(Seqlist *L)
{
	L->size=0;
}

int ListInsert(Seqlist *L,int i,DataType x)               /*原先int i 与DataType x的顺序是颠倒的，与后面调用时的不一致，故出错！*/
{                                                                          /*！！！当形参较多时，要主要顺序！！！此处可这样计：先知道放在哪里，再知道放些什么！*/
	int j;
	if(i<0||i>L->size)               /*原错写成i<=0，其实在第0个位置删除也是可以的,,,,原错写成i>L->MaxSize！！！*/
	{
		printf("i is wrong!\n");
		return 0;
	}
	else if(L->size>=MaxSize)
	{
		printf("The list is full.");
		return 0;
	}
	else
	{
		for(j=L->size;j>i;j--)
		L->list[j]=L->list[j-1];
		L->list[i]=x;
		L->size++;
	      return 1;
	}
}

int ListDelete(Seqlist *L,int i,DataType *x)
{
	int j;
	if(i<0||i>MaxSize-1)           /*应写i>MaxSize-1，而不是i>MaxSize!*/
	{
		printf("i is wrong!\n");
		return 0;
	}
	else if(L->size<=0)
	{
		printf("The list is empty.");
		return 0;
	}
	else
	{
		*x=L->list[i];
		for(j=i;j<L->size-1;j++)
		L->list[j]=L->list[j+1];
		L->size--;
	      return 1;
	}
}

int ListGet(Seqlist L,int i,DataType *x)
{
	if(i<0||i>L.size-1)
	{
		printf("i is wrong!");
		return 0;
	}
	else 
	{
		*x=L.list[i];
		return 1;
	}
}
	
void InitiateGraph(AdjMGraph *G,int n)
{
	int i,j;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
	          {
				if(i==j)
					G->Edge[i][j]=0;
				else G->Edge[i][j]=MaxWeight;
			}
	ListInitiate(&G->Vertices);
	G->NumOfEdges=0;                         /*原错写成NumOfEdges=0！注意数据项！*/
}

void InsertVertex(AdjMGraph *G,DataType Vertex)
{
	ListInsert(&G->Vertices,G->Vertices.size,Vertex);               /*原错写成G->Vertex.size!!!还是忽视了数据项*/
}

void InsertEdge(AdjMGraph *G,int v1,int v2,int weight)
{
	if(v1<0||v2<0||v1>MaxVertices||v2>MaxVertices)
	{
		printf("v1 or v2 is wrong!");
	     exit(0);
	}
	G->Edge[v1][v2]=weight;                        /*原错写成G->Edge[i][j]，对“v1,v2表示结点的编号且与i,j功能类似”未深入理解！！！*/
	G->NumOfEdges++;
}

void DeleteVertices(AdjMGraph *G,int v)                /*原写成DataType vertex*/
{
	int i,j,n=G->Vertices.size;
	DataType x;
	if(v<0||v>=G->Vertices.size)
	{printf("Cannot Delete Vertcies,v is not exit!");exit(1);}
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			if((i==v||j==v)&&G->Edge[i][j]<MaxWeight&&G->Edge[i][j]>0)   /*原错写成(i=v||j=v)！！！主要，表示相等应用两个等号！*/
				G->NumOfEdges--;               
			}
	}
	for(i=v;i<n;i++)
	for(j=0;j<n;j++)
	G->Edge[i][j]=G->Edge[i+1][j];
	for(j=v;j<n;j++)
	for(i=0;i<n;i++)
	G->Edge[i][j]=G->Edge[i][j+1];
	ListDelete(&G->Vertices,v,&x);
}
	
void DeleteEdge(AdjMGraph *G,int v1,int v2)
{
	if(v1<0||v2<0||v1>MaxVertices||v2>MaxVertices)
	{
		printf("v1 or v2 is wrong!");
	     exit(0);
	}
	G->Edge[v1][v2]=MaxWeight;
	G->NumOfEdges--;
}

int GetFirstVertex(AdjMGraph G,int v)
{
	int col;
	if(v<0||v>MaxVertices)
	{
		printf("v is wrong");
		exit(0);
	}
	for(col=0;col<G.Vertices.size;col++)
	if(G.Edge[v][col]>0&&G.Edge[v][col]<MaxWeight)
		return col;
	return -1;
}

int GetNextVertex(AdjMGraph G,int v1,int v2)
{ 
	int col;
	if(v1<0||v2<0||v1>MaxVertices||v2>MaxVertices)
	{
		printf("v1 or v2 is wrong!");
	     exit(0);
	}
	for(col=v2+1;col<G.Vertices.size;col++)
	if(G.Edge[v1][col]>0&&G.Edge[v1][col]<MaxWeight)
		return col;
	return -1;
}

void CreatGraph(AdjMGraph *G,DataType v[],int n,EdgeInformation E[],int e)   /*注意DataType v[]，主要：n个结点，e条边！*/
{                                                                                                          /*结点和边的信息都用数组存储*/
	int i,j;
	InitiateGraph(G,n);
	for(i=0;i<n;i++)
	InsertVertex(G,v[i]);
	for(j=0;j<e;j++)
	InsertEdge(G,E[j].row,E[j].col,E[j].weight);
}
 
void Visit(DataType x)
{
	printf("%c  ",x);
}

void DFS(AdjMGraph G, int v)                  /*这个函数应放在DNFTraverse()前，否则报错为Tyep mismatch in function···*/
{
	int w;
	Visit(G.Vertices.list[v]);
	visited[v]=1;
	w=GetFirstVertex(G,v);
	while(w!=-1)
	{
		if(visited[w]==0)
			DFS(G,w);
		w=GetNextVertex(G,v,w);
	}
}

void DFSTraverse(AdjMGraph G)
{
	int i;
	for(i=0;i<G.Vertices.size;i++)
	visited[i]=0;
	for(i=0;i<G.Vertices.size;i++)
	{
		if(visited[i]==0)
		DFS(G,i);
	}
}




void main()
{
	AdjMGraph mygraph;
	char vertex[]={'A','B','C','D','E'};
	EdgeInformation Edge[]={{0,1,10},{0,4,20},{1,3,30},{2,1,40},{3,2,50}};
	int n=5,e=5;int i,j;
	
	CreatGraph(&mygraph,vertex,n,Edge,e); /*原错写成vertex[],Edge[]！！！在函数调用时，应只写数组名，不要把中括号带上！！！*/
	
	printf("My own to traverse the graph is:\n");
	for(i=0;i<mygraph.Vertices.size;i++)
	printf("%c   ",mygraph.Vertices.list[i]);
	printf("\n");
	
	printf("The Depth First Traverse is:\n");
	DFSTraverse(mygraph);
	                                                                 /*不能写free(visited);否则报错为NULL pointer assignment!为什么？？？*/
	
}