C语言 图

///////////////stdafx.h//////////////

#include
#include
#include
#include

#define SAFE_CHEACK(point) if(!point) return
#define CHEACK(point) if(!point) exit(-1)
#define SAFE_FREE(point) {if(point){free(point);point=NULL;}}

#define bool int
#define false 0
#define true 1

typedef int ElemType;

typedef struct QNode
{
ElemType vex;
struct QNode* next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;


LinkQueue* InitQueue();
QNode* NewNode(int vex);
void CopyNode(QNode* Node1,QNode* Node2);
void DestroyQueue(LinkQueue* Q);
void ClearQueue(LinkQueue* Q);
QNode* DeQueue(LinkQueue* Q);
bool QueueEmpty(LinkQueue* Q);
unsigned int GetLength(LinkQueue* Q);
void EnQueue(LinkQueue* Q,QueuePtr e);
QNode* LocateNode(LinkQueue* Q,int pos);



typedef struct CSNode{
ElemType data;
struct CSNode *firstchild,*nextsibling;
}CSNode,*CTree;

void TraverseCTree(CTree forest,void (*visit)(CTree node));
void DestroyCTree(CTree forest);
CSNode* NewTreeNode(int data);
void PrintTreeNode(CTree node);
//////Queue.c///////////////////
#include "stdAfx.h"

LinkQueue* InitQueue()
{
LinkQueue* Q=(LinkQueue*)malloc(sizeof(LinkQueue));
CHEACK(Q);
Q->front=Q->rear=NULL;
return Q;
}
QNode* NewNode(int vex)
{
QNode* Node=(QNode*)malloc(sizeof(QNode));
CHEACK(Node);
Node->next=NULL;
Node->vex=vex;
return Node;
}

void CopyNode(QNode* Node1,QNode* Node2)
{
if(NULL == Node1 || NULL == Node2)return;
Node1->vex=Node2->vex;
Node1->next=Node2->next;
return;
}
void DestroyQueue(LinkQueue* Q)
{
QNode* Node=Q->front;
if(NULL == Q)return;
while(NULL != Node)
{
Node=Q->front->next;
SAFE_FREE(Q->front);
Q->front=Node;
}
SAFE_FREE(Q);
Q=NULL;
}
void ClearQueue(LinkQueue* Q)
{
QNode* Node=Q->front;
SAFE_CHEACK(Q);
SAFE_CHEACK(Q->front);

while(NULL != Node)
{
Node->vex=0;
Node=Node->next;
}
}
bool QueueEmpty(LinkQueue* Q)
{
if(Q->front==Q->rear && Q->front==NULL)return true;
else return false;
}
unsigned int GetLength(LinkQueue* Q)
{
QueuePtr QPtr=Q->front;
int count=0;
if(NULL == Q || NULL ==Q->front)return 0;

while(NULL != QPtr)
{
QPtr=QPtr->next;
count++;
}
return count;
}

void EnQueue(LinkQueue* Q,QueuePtr e)
{
SAFE_CHEACK((Q&&e));
if(QueueEmpty(Q))
{
Q->front=Q->rear=e;
return;
}
Q->rear->next=e;
Q->rear=e;
e->next=NULL;
}
QNode* DeQueue(LinkQueue* Q)
{
QNode* tmp;
if(QueueEmpty(Q))
{
return NULL;
}
tmp=Q->front;
Q->front=Q->front->next;
if(!Q->front)Q->rear=NULL;
tmp->next=NULL;
return tmp;
}


QNode* LocateNode(LinkQueue* Q,int pos)
{
int TPos=0;
QNode* Node=Q->front;
if(NULL==Q)return NULL;

while(NULL != Node)
{
if(TPos == pos || (-1 == pos && NULL ==Node->next))
{
return Node;
}
Node=Node->next;
++TPo

s;
}
return NULL;
}

/////////森林.c//////////////////////////
#include "stdAfx.h"



void TraverseCTree(CTree forest,void (*visit)(CTree node))
{
CTree tmp;

tmp=forest;
while(tmp){visit(tmp);tmp=tmp->nextsibling;}
tmp=forest;

while(tmp){
TraverseCTree(tmp->firstchild,visit);
tmp=tmp->nextsibling;
}
}
CSNode* NewTreeNode(int data)
{
CSNode* node=(CTree)malloc(sizeof(CSNode));
node->data=data;
node->firstchild=node->nextsibling=NULL;
return node;
}
void PrintTreeNode(CTree node)
{
printf("%d ",node->data);
}
void DestroyCTree(CTree forest)
{
if(forest->firstchild)DestroyCTree(forest->firstchild);
if(forest->nextsibling)DestroyCTree(forest->nextsibling);
SAFE_FREE(forest);
}
////////graph.c//////////////////////////
#include "stdAfx.h"

#define MAX_ARC_WEIGHT 100
#define MAX_STR_LEN 20
#define MAX_VERTEX_NUM 100
typedef char* VertexName;
typedef enum{DG,UDG,DN,UDN}GraphType;
typedef struct ArcCell{
int w;
int vet_x,vet_y;
//char* info;
}ArcCell,*AdjMatrix;
typedef struct
{
VertexName vetx[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
GraphType type;
}NGraph;

/*typedef struct
{
int* IdxVisited;
int NumVisited;
}Collection;*/

AdjMatrix CreateMatrix(GraphType type,int vexarcs)
{
int i=0;
AdjMatrix matrix=(AdjMatrix)malloc(sizeof(ArcCell)*vexarcs);
memset(matrix,0,sizeof(ArcCell)*vexarcs);
if(type==DG || type==UDG)
while(ielse
while(ireturn matrix;
}
NGraph* CreateCraphFromConsole()
{
int i=0;
int vexnum;
AdjMatrix matrix;
int arcsnum=0;
NGraph* graph;
char tmp[MAX_STR_LEN];

VertexName vex[MAX_VERTEX_NUM];

graph=(NGraph*)malloc(sizeof(NGraph));
memset(graph,0,sizeof(NGraph));

printf("请输入Graph的类型(有向图：0 无向图：1 有向网：2 无向网:3 ) :");
scanf("%d",&graph->type);
printf("请输入Graph的结点数:");
scanf("%d",&vexnum);
while(i{
vex[i]=(char*)malloc(sizeof(char)*MAX_STR_LEN);
memset(vex[i],0,sizeof(char)*MAX_STR_LEN);
printf("请输入第%d结点名称：",i+1);
scanf("%s",tmp);
strcpy(vex[i],tmp);
i++;
}
printf("请输入弧的数量：");
scanf("%d",&arcsnum);
matrix=CreateMatrix(graph->type,arcsnum);

graph->arcnum=arcsnum;
graph->arcs=matrix;
for(i=0;ivetx[i]=vex[i];
graph->vexnum=vexnum;

return graph;
}
int** TransToUnCpresMatx(NGraph* graph)//将NGraph中压缩的矩阵解压
{
int i=0;
int** matrix=(int**)malloc(sizeof(int*)*(graph->vexnum+1));//第一个单元不用
memset(matrix,0,sizeof(int*)*(graph->vexnum+1));

for(i=1;i<=graph->vexnum;i++)
{
matrix[i]=(int*)malloc(sizeof(int)*(graph->vexnum+1));
memset(matrix[i],0,sizeof(

int)*(graph->vexnum+1));
}
for(i=0;iarcnum;i++)
{
if(graph->type==DG ||graph->type==UDG)
{
matrix[graph->arcs[i].vet_x][graph->arcs[i].vet_y]=1;
if(graph->type==UDG)
matrix[graph->arcs[i].vet_y][graph->arcs[i].vet_x]=1;
}
else
{
matrix[graph->arcs[i].vet_x][graph->arcs[i].vet_y]=graph->arcs[i].w;
if(graph->type==UDN)
matrix[graph->arcs[i].vet_y][graph->arcs[i].vet_x]=graph->arcs[i].w;
}
}
return matrix;
}
void PrintArcsMatrix(NGraph* graph)
{
int i=0;
CHEACK(graph);
printf("\n");
for(;iarcnum;i++)
{
if(graph->type==DG ||graph->type==UDG)
printf("(%s %s)",graph->vetx[graph->arcs[i].vet_x-1],graph->vetx[graph->arcs[i].vet_y-1]);
else
printf("(%s %d %s)",graph->vetx[graph->arcs[i].vet_x-1],graph->arcs[i].w,graph->vetx[graph->arcs[i].vet_y-1]);
}
printf("\n");
}
void PrintNArcs(NGraph G,int index)
{
printf("(%s %d %s) ",G.vetx[G.arcs[index].vet_x-1],G.arcs[index].w,G.vetx[G.arcs[index].vet_y-1]);
//printf("%d ",index);
}
void PrintNode(NGraph* graph,int v)
{
printf("%s ",graph->vetx[v]);
}
int FirstAdjVex(NGraph* graph,int **matrix,int v)
{
int i;
for(i=1;i<=graph->vexnum;i++)
if(matrix[v][i] && i!=v)
return i;
return -1;
}
int NextAdjVex(NGraph* graph,int **matrix,int v,int w)
{
int i;
for(i=w+1;i<=graph->vexnum;i++)
if(matrix[v][i] && i!=v)
return i;
return -1;
}
void DFS(NGraph* graph,int** matrix,bool*visited,int v)
{
int w;
visited[v]=true;
PrintNode(graph,v-1);
for(w=FirstAdjVex(graph,matrix,v);w>=0;w=NextAdjVex(graph,matrix,v,w))
if(!visited[w])DFS(graph,matrix,visited,w);
}
void DFSTraverse(NGraph* graph/*,void(*visit(NGraph* graph,int x,int y))*/)//深度优先遍历图
{
bool *visited;
int i=0;
int** matrix;

visited=(bool*)malloc(sizeof(bool)*(graph->vexnum+1));
CHEACK(visited);
memset(visited,0,sizeof(bool)*(graph->vexnum+1));
matrix=TransToUnCpresMatx(graph);

for(i=1;i<=graph->vexnum;i++)
if(!visited[i])DFS(graph,matrix,visited,i);

SAFE_FREE(visited);
for(i=1;i<=graph->vexnum;i++)SAFE_FREE(matrix[i]);
SAFE_FREE(matrix);
}
void BFSTraverse(NGraph* graph)
{
LinkQueue* queue=InitQueue();
bool *visited;
int i=0,w,v;
int** matrix;
QNode* node;
visited=(bool*)malloc(sizeof(bool)*(graph->vexnum+1));
CHEACK(visited);
memset(visited,0,sizeof(bool)*(graph->vexnum+1));
matrix=TransToUnCpresMatx(graph);

for(i=1;i<=graph->vexnum;i++)
{
if(!visited[i])
{
visited[i]=true;
PrintNode(graph,i-1);
EnQueue(queue,NewNode(i));
while(!QueueEmpty(queue))
{
node=DeQueue(queue);
v=node->vex;
for(w=FirstAdjVex(graph,matrix,v);w>=0;w=NextAdjVex(graph,matrix,v,w))
{
if(!visited[w])
{
PrintNode(graph,w-1);
visited[w]=true;
EnQueue(queue,NewNode(w));
}
}
SAFE_FREE(node);

}
}
}
DestroyQueue(queue);
SAFE_FREE(visited);
for

(i=1;i<=graph->vexnum;i++)SAFE_FREE(matrix[i]);
SAFE_FREE(matrix);
}
void DFSTree(NGraph *graph,int** matrix,bool* visited,CTree tree,int v)
{
int w;
bool first=true;
CTree p,q;
PrintTreeNode(tree);
visited[v]=true;

for(w=FirstAdjVex(graph,matrix,v);w>=0;w=NextAdjVex(graph,matrix,v,w))
{
if(!visited[w])
{
p=NewTreeNode(w);
if(first)
{
q=tree->firstchild=p;
}
else
{
q->nextsibling=p;
q=p;
}
DFSTree(graph,matrix,visited,q,w);
}
}
}
int DFSForest(NGraph* graph,CTree* tree)
{
bool *visited;
int i=0;
int num_tree=0;
CTree p,q;
int** matrix;

visited=(bool*)malloc(sizeof(bool)*(graph->vexnum+1));
CHEACK(visited);
memset(visited,0,sizeof(bool)*(graph->vexnum+1));
matrix=TransToUnCpresMatx(graph);
*tree=NULL;
printf("\n");
for(i=1;i<=graph->vexnum;i++)
{
if(!visited[i])
{
num_tree++;
p=NewTreeNode(i);
if(!*tree){q=*tree=p;}
else {q->nextsibling=p;q=p;}
printf("第%d棵树：",num_tree);
DFSTree(graph,matrix,visited,q,i);
printf("\n");
}
}
SAFE_FREE(visited);
for(i=1;i<=graph->vexnum;i++)SAFE_FREE(matrix[i]);
SAFE_FREE(matrix);
return num_tree;
}
bool IsConnectedGraph(NGraph G)
{
int i,j,flag=0;
int** matrix;
matrix=TransToUnCpresMatx(&G);
for(i=1;i<=G.vexnum;i++)
{
for(j=1;j<=G.vexnum;j++)
{
if(matrix[i][j] && i!=j)flag=1;
}
if(!flag)return false;
}

for(i=1;i<=G.vexnum;i++)SAFE_FREE(matrix[i]);
SAFE_FREE(matrix);
return true;
}
int GetMinWeight(NGraph G,int x,int y)
{
int weight=MAX_ARC_WEIGHT;
int i=0;
for(;i{
if(G.type==DG|| G.type==DN)
{
if(G.arcs[i].vet_x==x && G.arcs[i].vet_y==y && G.arcs[i].w{
weight=G.arcs[i].w;
}
}
else
{
if((G.arcs[i].vet_x==x && G.arcs[i].vet_y==y ) ||
(G.arcs[i].vet_x==y && G.arcs[i].vet_y==x )
&& G.arcs[i].w{
weight=G.arcs[i].w;
}
}
}
return weight;
}
int GetArcsIndex(NGraph G,int x,int y,int w)
{
int i=0;
for(;i{
if(G.type==UDG || G.type==UDN)
{
if((G.arcs[i].vet_x==x && G.arcs[i].vet_y==y)||
(G.arcs[i].vet_x==y && G.arcs[i].vet_y==x)
&& G.arcs[i].w==w)
{
return i;
}
}
else
{
if(G.arcs[i].vet_x==x && G.arcs[i].vet_y==y && G.arcs[i].w==w)
return i;
}
}
return i;
}
int GetNextNodeIndex(NGraph G,int* IdxVisited,int* IdxArcsVisited)
{
int i=1;
int j;
int x=0,y=0,weight=MAX_ARC_WEIGHT;
int tmp;
int index;
int** matrix;
matrix=TransToUnCpresMatx(&G);

for(;i<=G.vexnum;i++)
{
if(IdxVisited[i])
{
for(j=FirstAdjVex(&G,matrix,i);j>=0;j=NextAdjVex(&G,matrix,i,j))
{
if(!IdxVisited[j])
{
tmp=GetMinWeight(G,i,j);
if(weight>tmp)
{
weight=tmp;
x=i;
y=j;
}

}
}
}
}

index=GetArcsIndex(G,x,y,weight);
IdxArcsVisited[0]+=1;
IdxArcsVisited[IdxArcsV

isited[0]]=index;
for(i=1;i<=G.vexnum;i++)SAFE_FREE(matrix[i]);
SAFE_FREE(matrix);
return y;
}
void MiniSpanTree_PRIM(NGraph G,/*VertexName name*/int vex_index)//这里采用顶点编号索引顶点，而不采用顶点名称
{
if(G.type==DG||G.type==UDG)
{
printf("图没有最小树！\n");
return;
}
else if(!IsConnectedGraph(G))
{
printf("网不是连通的，没有最小树！\n");
return;
}
//第一个单元用于存储动态生成最小树过程中最小树上的结点数，其他单元是标志位，1表示为最小树的结点，
//IdxVisited[x]=1表示第x个结点是最小树上的结点，IdxVisited[x]=0则反之。
//IdxArcsVisited存储态生成最小树过程中最小树上的弧的索引，第一个存储单元用于存储弧的数最小树上弧的数量
int index;
int* IdxVisited=(int*)malloc(sizeof(int)*(G.vexnum+1));
int* IdxArcsVisited=(int*)malloc(sizeof(int)*(G.vexnum));
memset(IdxVisited,0,sizeof(int)*(G.vexnum+1));
memset(IdxArcsVisited,0,sizeof(int)*(G.vexnum));
IdxVisited[vex_index]=1;
IdxVisited[0]+=1;
while(IdxVisited[0]{
index=GetNextNodeIndex(G,IdxVisited,IdxArcsVisited);
IdxVisited[index]=1;
IdxVisited[0]+=1;
}
for(index=1;index<=IdxArcsVisited[0];index++)
{
PrintNArcs(G,IdxArcsVisited[index]);
}
SAFE_FREE(IdxArcsVisited);
SAFE_FREE(IdxVisited);
}
void DFSFindPoint(NGraph G,int vex,int* visited,int**matrix,int*low,int* count)
{
int min;
int v=vex,w;
visited[vex]=min=++(*count);
bool flag=false;
for(w=FirstAdjVex(&G,matrix,v);w>=0;w=NextAdjVex(&G,matrix,v,w))
{
if(!visited[w])
{
DFSFindPoint(G,w,visited,matrix,low,count);
if(low[w]if(low[w]>=visited[vex]&&!flag)
{
printf("%s ",G.vetx[vex-1]);
flag=true;
}
}
else if(visited[w]}

low[vex]=min;
}
void TraceArcPoint(NGraph G)//寻找并输出关节点
{
int **matrix;
int *visited;
int* low;
int v,w;
int count=0;

matrix=TransToUnCpresMatx(&G);
visited=(int*)malloc(sizeof(int)*(G.vexnum+1));//第一个存储单元不用
memset(visited,0,sizeof(int)*(G.vexnum+1));
low=(int*)malloc(sizeof(int)*(G.vexnum+1));//第一个存储单元不用
memset(low,0,sizeof(int)*(G.vexnum+1));
count=1;
visited[1]=count;

v=FirstAdjVex(&G,matrix,1);
printf("graph的关键结点是：\n");
DFSFindPoint(G,v,visited,matrix,low,&count);
if(count{
printf("%s ",G.vetx[0]);
for(w=FirstAdjVex(&G,matrix,1);w>=0;w=NextAdjVex(&G,matrix,1,w))
if(!visited[w])DFSFindPoint(G,w,visited,matrix,low,&count);
}
printf("\n");
SAFE_FREE(visited);
SAFE_FREE(low);
for(v=1;v<=G.vexnum;v++)SAFE_FREE(matrix[v]);
SAFE_FREE(matrix);
}
bool IsLocked(NGraph G,int** matrix)
{
int row,col;
for(col=1;col<=G.vexnum;col++)
{
for(row=1;row<=G.vexnum;row++)
{
if(matrix[row][col])break;
}
if(row==G.vexnum+1)return false;
}
return true;
}

int SearchNode(NGraph G,int** matrix,bool* visited,int vex)
{
int i;
for(i=1;i<=G.vexnum;i++)
{
if(matrix[i][vex] && visited[i]==0)return SearchNode(G,matrix,visited,i);
}
return vex;
}
void DFS_Sort(NGraph G,int** matrix,bool* visited,int vex)
{
int v,w;
v=SearchNode(G,matrix,visited,vex);
if(!visited[v])
{
printf("%s ",G.vetx[v-1]);
visited[v]=1;
}
for(w=FirstAdjVex(&G,matrix,v);w>=0;w=NextAdjVex(&G,matrix,v,w))
{
DFS_Sort(G,matrix,visited,w);
}
}
void TraceTopoSort(NGraph G) //拓扑排序
{
bool *visited;
int** matrix;
int i;
if(G.type==UDG||G.type==UDN)
{
printf("无向网和无向图不支持拓扑排序！\n");
return;
}
visited=(bool*)malloc(sizeof(bool)*(G.vexnum+1));//第一个存储单元不用
memset(visited,0,sizeof(bool)*(G.vexnum+1));
matrix=TransToUnCpresMatx(&G);
if(IsLocked(G,matrix))
{
printf("无法拓扑排序！为死锁图！\n");
return;
}
printf("拓扑排序结果:\n");
DFS_Sort(G,matrix,visited,1);
printf("\n");
SAFE_FREE(visited);
for(i=1;i<=G.vexnum;i++)SAFE_FREE(matrix[i]);
SAFE_FREE(matrix);
}
void DestroyGraph(NGraph* graph)
{
int i=0;
SAFE_FREE(graph->arcs);
for(i=0;iarcnum;i++)SAFE_FREE(graph->vetx[i]);
SAFE_FREE(graph);
}
void main()
{
NGraph *graph;
//CTree forest;
//int num_tree;
graph=CreateCraphFromConsole();
/*printf("所有的弧为:");
PrintArcsMatrix(graph);
printf("Depth-First-Traverse:\n");
DFSTraverse(graph);
printf("\nBreadth-First-Traverse:\n");
BFSTraverse(graph);
printf("Graph的生成树数目：%d\n",num_tree=DFSForest(graph,&forest));
MiniSpanTree_PRIM(*graph,1);
TraceArcPoint(*graph);*/
//DestroyCTree(forest);
//TraceTopoSort(*graph);
DestroyGraph(graph);
system("pause");
}