各种基本算法实现小结（四）—— 图及其遍历

各种基本算法实现小结（四）—— 图及其遍历

（均已测试通过）

====================================================================

图——深度优先和广度优先算法

无向图用二维邻接矩阵表示

测试环境：VC 6.0 (C)

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define INFINITY 32767
#define MAX_VEX 20
#define QUEUE_SIZE (MAX_VERTEX+1)
#define DataType char  /* vertext's info  */
int *visited; /* Node: visited flag with dynamic array, good idea ! */
/* init queue for bfs */
struct _node
{
    int v_num;
    struct _node *next;
};
typedef struct _node node, *pnode;
struct _queue
{
    pnode front;
    pnode rear;
};
typedef struct _queue queue, *pqueue;
struct _graph
{
    DataType *vexs;
    int arcs[MAX_VEX][MAX_VEX];
    int vexnum, arcnum;
};
typedef struct _graph graph, *pgraph;
/* operation of queue */
queue init_queue()
{
    queue qu;
    qu.front=qu.rear=(pnode)malloc(sizeof(node));
    if(qu.front == NULL)
        exit(1);
    qu.rear->next=NULL;
    return qu;
}
void en_queue(pqueue pqu, int v_num)
{
    pnode pn;
    pn=(pnode)malloc(sizeof(node));
    if(pqu->front == NULL)
        exit(1);
    pn->v_num=v_num;
    pn->next=NULL;
    pqu->rear->next=pn;
    pqu->rear=pqu->rear->next;
}
int isempty_queue(pqueue pqu)
{
    if(pqu->front == pqu->rear)
        return 1;
    else
        return 0;
}
int de_queue(pqueue pqu)
{
    pnode pn;
	int d;
    if(isempty_queue(pqu))
        return -1;
	pn=pqu->front;
    d=pn->v_num;
    pqu->front=pn->next;
	free(pn);
    return d;
}
int locate(graph g, DataType data)
{
    int i;
    for(i=0;i<g.vexnum;i++)
        if(g.vexs[i] == data)
            return i;
     return -1;
}
graph create_graph()
{
    int i,j,w, s1,s2;
    DataType ch1,ch2,tmp;
    graph g;
	printf("g sizeof: %d/n", sizeof(g));
    printf("Enter vexnum arcnum:");
    scanf("%d %d", &g.vexnum, &g.arcnum);
    tmp=getchar();
    g.vexs=(DataType *)malloc(sizeof(DataType));
	if(g.vexs == NULL)
		exit(1);
    printf("Enter %d vertext,please.../n", g.vexnum);
    for(i=0;i<g.vexnum;i++)
    {
        printf("vex %d: ", i);
        scanf("%c", &g.vexs[i]);
        tmp=getchar();
        //visited[i]=0;
    }
    for(i=0;i<g.vexnum;i++)
        for(j=0;j<g.vexnum;j++)
            g.arcs[i][j]=INFINITY;
     printf("Enter %d arcs:/n", g.arcnum);
     for(i=0;i<g.arcnum;i++)
     {
        printf("arc %d: ", i);
        scanf("%c %c %d", &ch1, &ch2, &w);
        tmp=getchar();
        s1=locate(g, ch1);
        s2=locate(g, ch2);
        g.arcs[s1][s2]=g.arcs[s2][s1]=w; /* NOTE: weight */
     }
	 return g;
}
int firstvex_graph(graph g, int k)
{
    int i;
    if(k>=0 && k<g.vexnum)
        for(i=0;i<g.vexnum;i++)
            if(g.arcs[k][i] != INFINITY)
                return i;
     return -1;
}
int nextvex_graph(graph g, int i, int j)
{
    int k;
    if(i>=0 && i<g.vexnum && j>=0 && j<g.vexnum)
        for(k=j+1; k<g.vexnum; k++)
            if(g.arcs[i][k] != INFINITY)
                return k;
     return -1;
}
void dfs(graph g, int k)
{
    int i;
    if(k == -1)
    {
        for(i=0;i<g.vexnum;i++)
            if(!visited[i])
                dfs(g,i);
     }
     else
     {
        visited[k]=1;
        printf("%c ", g.vexs[k]);
        for(i=firstvex_graph(g,k);i>=0;i=nextvex_graph(g,k,i))
            if(!visited[i])
                dfs(g,i);
     }
}
void bfs(graph g)
{
    int i,j,k;
    queue qu;
    qu=init_queue();
    for(i=0;i<g.vexnum;i++)
        if(!visited[i])
        {
            visited[i] =1;
            printf("%c ", g.vexs[i]);
            en_queue(&qu, i);
            while(!isempty_queue(&qu))
            {
                k=de_queue(&qu);
                for(j=firstvex_graph(g,k); j>=0;j=nextvex_graph(g,k,j))
                    if(!visited[j])
                    {
                        visited[j]=1;
                        printf("%c ", g.vexs[j]);
                        en_queue(&qu, j);
                    }
            }
        }
}
void main()
{
	int i;
    graph g;
    g=create_graph();
	visited=(int *)malloc(g.vexnum*sizeof(int));
	for(i=0;i<g.vexnum;i++)
		visited[i]=0;
    printf("/n/n dfs:");
    dfs(g,-1);
	for(i=0;i<g.vexnum;i++)
		visited[i]=0;
    printf("/n bfs:");
    bfs(g);
	
	if(visited)
		free(visited);
	printf("/n");
}

运行结果：

======================================================

图 ——深度优先

测试环境：VS2008 (C)

#include "stdafx.h"
#include <stdlib.h>
#include <malloc.h>
#define MAX_VEX 20
#define INFINITY 65535
int *visited;
struct _node
{
	int vex_num;
	struct _node *next;
};
typedef struct _node node, *pnode;
struct _graph
{
	char *vexs;
	int arcs[MAX_VEX][MAX_VEX];
	int vexnum, arcnum;
};
typedef struct _graph graph, *pgraph;
int locate(graph g, char ch)
{
	int i;
	for(i=1; i<=g.vexnum; i++)
		if(g.vexs[i]==ch)
			return i;
	return -1;
}
graph create_graph()
{
	int i, j, w, p1, p2;
	char ch1, ch2;
	graph g;
	printf("Enter vexnum arcnum: ");
	scanf("%d %d", &g.vexnum, &g.arcnum);
	getchar();
	for(i=1; i<=g.vexnum; i++)
		for(j=1; j<g.vexnum; j++)
			g.arcs[i][j]=INFINITY;
	g.vexs=(char *)malloc(sizeof(char));
	printf("Enter %d vexnum.../n", g.vexnum);
	for(i=1; i<=g.vexnum; i++)
	{
		printf("vex %d: ", i);
		scanf("%c", &g.vexs[i]);
		getchar();
	}
	printf("Enter %d arcnum.../n", g.arcnum);
	for(i=1; i<=g.arcnum; i++)
	{
		printf("arc %d: ", i);
		scanf("%c %c %d", &ch1, &ch2, &w);
		getchar();
		p1=locate(g, ch1);
		p2=locate(g, ch2);
		g.arcs[p1][p2]=g.arcs[p2][p1]=w;
	}
	return g;
}
int firstvex_graph(graph g, int i)
{
	int k;
	if(i>=1 && i<=g.vexnum)
		for(k=1; k<=g.vexnum; k++)
			if(g.arcs[i][k]!=INFINITY)
				return k;
	return -1;
}
int nextvex_graph(graph g, int i, int j)
{
	int k;
	if(i>=1 && i<=g.vexnum && j>=1 && j<=g.vexnum)
		for(k=j+1; k<=g.vexnum; k++)
			if(g.arcs[i][k]!=INFINITY)
				return k;
	return -1;
}
void dfs(graph g, int i)
{
	int k, j;
	if(!visited[i])
	{
		visited[i]=1;
		printf("%c", g.vexs[i]);
		for(j=firstvex_graph(g, i); j>=1; j=nextvex_graph(g, i, j))
			if(!visited[j])
				dfs(g, j);
	}
}
void dfs_graph(graph g)
{
	int i;
	visited=(int *)malloc((g.vexnum+1)*sizeof(int));
	for(i=1; i<=g.vexnum; i++)
		visited[i]=0;
	for(i=1; i<g.vexnum; i++)
		if(!visited[i])
			dfs(g, i);
}
int _tmain(int argc, _TCHAR* argv[])
{
	graph g;
	g=create_graph();
	dfs_graph(g);
	printf("/n");
	return 0;
}

======================================================

图 ——广度优先

测试环境：VS2008 (C)

#include "stdafx.h"
#include <stdlib.h>
#include <malloc.h>
#define MAX_VEX 20
#define INFINITY 65535
int *visited;
struct _node
{
	int data;
	struct _node *next;
};
typedef struct _node node, *pnode;
struct _queue
{
	pnode front;
	pnode rear;
};
typedef struct _queue queue, *pqueue;
queue init_queue()
{
	pnode pn=NULL;
	queue qu;
	pn=(pnode)malloc(sizeof(node));
	if(pn==NULL)
		printf("init queue, malloc is fail.../n");
	pn->data=-1;
	pn->next=NULL;
	qu.front=qu.rear=pn;
	return qu;
}
int empty_queue(queue qu)
{
	if(qu.rear==qu.front)
		return 0;
	else
		return 1;
}
void en_queue(pqueue pqu, int data)
{
	pnode pn=NULL;
	if(pqu->rear==NULL)
		return;
	pn=(pnode)malloc(sizeof(node));
	pn->data=data;
	pn->next=pqu->rear->next;
	pqu->rear->next=pn;
	pqu->rear=pn;
}
int de_queue(pqueue pqu)
{
	int data;
	pnode pn=NULL;
	if(pqu->front->next==NULL)
		return -1;
	
	pn=pqu->front->next;
	pqu->front=pqu->front->next;
	data=pn->data;
	free(pn);
	return data;
}
struct _graph
{
	char *vexs;
	int arcs[MAX_VEX][MAX_VEX];
	int vexnum, arcnum;
};
typedef _graph graph, *pgraph;
int locate(graph g, char ch)
{
	int i;
	for(i=1; i<=g.vexnum; i++)
		if(g.vexs[i]==ch)
			return i;
	return -1;
}
graph create_graph()
{
	int i, j, w, p1, p2;
	char ch1, ch2;
	graph g;
	printf("Enter vexnum arcnum: ");
	scanf("%d %d", &g.vexnum, &g.arcnum);
	getchar();
	for(i=1; i<=g.vexnum; i++)
		for(j=1; j<g.vexnum; j++)
			g.arcs[i][j]=INFINITY;
	g.vexs=(char *)malloc((g.vexnum+1)*sizeof(char));
	printf("Enter %d vexnum.../n", g.vexnum);
	for(i=1; i<=g.vexnum; i++)
	{
		printf("vex %d: ", i);
		scanf("%c", &g.vexs[i]);
		getchar();
	}
	printf("Enter %d arcnum.../n", g.arcnum);
	for(i=1; i<=g.arcnum; i++)
	{
		printf("arc %d: ", i);
		scanf("%c %c %d", &ch1, &ch2, &w);
		getchar();
		p1=locate(g, ch1);
		p2=locate(g, ch2);
		g.arcs[p1][p2]=g.arcs[p2][p1]=w;
	}
	return g;
}
int firstvex_graph(graph g, int i)
{
	int k;
	if(i>=1 && i<=g.vexnum)
		for(k=1; k<=g.vexnum; k++)
			if(g.arcs[i][k]!=INFINITY)
				return k;
	return -1;
}
int nextvex_graph(graph g, int i, int j)
{
	int k;
	if(i>=1 && i<=g.vexnum && j>=1 && j<=g.vexnum)
		for(k=j+1; k<=g.vexnum; k++)
			if(g.arcs[i][k]!=INFINITY)
				return k;
	return -1;
}
void bfs(graph g)
{
	int i, ivex, inextvex;
	visited=(int *)malloc((g.vexnum+1)*sizeof(int));
	for(i=1; i<=g.vexnum; i++)
		visited[i]=0;
	queue qu=init_queue();
	for(i=1; i<=g.vexnum; i++)
	{
		if(!visited[i])
		{
			visited[i]=1;
			printf("%c", g.vexs[i]);
			en_queue(&qu, i);
		}
		
		while(!empty_queue(qu))
		{
			ivex=de_queue(&qu);
			for(inextvex=firstvex_graph(g, ivex); inextvex>=1; inextvex=nextvex_graph(g, ivex, inextvex))
				if(!visited[inextvex])
				{
					visited[inextvex]=1;
					printf("%c", g.vexs[inextvex]);
					en_queue(&qu, inextvex);
				}
		}
	}
}
int _tmain(int argc, _TCHAR* argv[])
{
	graph g;
	g=create_graph();
	bfs(g);
	printf("/n");
	return 0;
}

======================================================

图 ——深度优先和广度优先算法2（网摘）

本文引用网址：http://bbs.bccn.net/thread-155311-1-1.html（编程论坛）

看到本算法在网上转载较多，比较流行，且能直接运行

但发现大多转载中，也把DFS与BFS正好写反了，对此本文已修正

此外，本算法混用了C与C++，不够单纯，申请的指针空间也未及时释放

测试环境：VC 6.0 (C)

#include <stdio.h>
#include <malloc.h>
#define INFINITY 32767
#define MAX_VEX 20 
#define QUEUE_SIZE (MAX_VEX+1) 
bool *visited;  
typedef struct
{
	char *vexs;                    //顶点向量
	int arcs[MAX_VEX][MAX_VEX];    //邻接矩阵
	int vexnum,arcnum;             //图的当前顶点数和弧数
}Graph;
//队列类
class Queue
{
	public:
	void InitQueue(){
	base=(int *)malloc(QUEUE_SIZE*sizeof(int));
    front=rear=0;
}
void EnQueue(int e)
{
    base[rear]=e;
    rear=(rear+1)%QUEUE_SIZE;
}
void DeQueue(int &e)
{
    e=base[front];
    front=(front+1)%QUEUE_SIZE;
}
public:
	int *base;
	int front;
	int rear;
};
//图G中查找元素c的位置
int Locate(Graph G,char c)
{
	for(int i=0;i<G.vexnum;i++)
		if(G.vexs[i]==c) 
			return i;
	
	return -1;
}
//创建无向网
void CreateUDN(Graph &G){
	int i,j,w,s1,s2;
	char a,b,temp;
	printf("输入顶点数和弧数: ");
	scanf("%d%d",&G.vexnum,&G.arcnum);
	temp=getchar(); //接收回车
	G.vexs=(char *)malloc(G.vexnum*sizeof(char)); //分配顶点数目
	printf("输入%d个顶点./n",G.vexnum);
	for(i=0;i<G.vexnum;i++) //初始化顶点
	{ 
		printf("输入顶点%d: ",i);
		scanf("%c",&G.vexs[i]);
		temp=getchar(); //接收回车 
	}
	for(i=0;i<G.vexnum;i++) //初始化邻接矩阵
		for(j=0;j<G.vexnum;j++)
			G.arcs[i][j]=INFINITY;
	printf("输入%d条弧./n",G.arcnum);
	for(i=0;i<G.arcnum;i++)
	{ //初始化弧
		printf("输入弧%d: ",i);
		scanf("%c %c %d",&a,&b,&w); //输入一条边依附的顶点和权值
		temp=getchar(); //接收回车
		s1=Locate(G,a);
		s2=Locate(G,b);
		G.arcs[s1][s2]=G.arcs[s2][s1]=w;
	}
}
//图G中顶点k的第一个邻接顶点
int FirstVex(Graph G,int k)
{
	if(k>=0 && k<G.vexnum) //k合理
		for(int i=0;i<G.vexnum;i++)
			if(G.arcs[k][i]!=INFINITY) return i;
  return -1;
}
//图G中顶点i的第j个邻接顶点的下一个邻接顶点
int NextVex(Graph G,int i,int j)
{
	if(i>=0 && i<G.vexnum && j>=0 && j<G.vexnum) //i,j合理
		for(int k=j+1;k<G.vexnum;k++)
			if(G.arcs[i][k]!=INFINITY) 
				return k;
  return -1;
}
//深度优先遍历
void DFS(Graph G,int k)
{
	int i;
	if(k==-1) //第一次执行DFS时,k为-1
	{
		for(i=0;i<G.vexnum;i++)
			if(!visited[i]) 
				DFS(G,i); //对尚未访问的顶点调用DFS
	}
	else
	{ 
		visited[k]=true;
		printf("%c ",G.vexs[k]); //访问第k个顶点
		for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
			if(!visited[i]) //对k的尚未访问的邻接顶点i递归调用DFS
				DFS(G,i); 
	}
}
//广度优先遍历
void BFS(Graph G)
{
	int k;
	Queue Q; //辅助队列Q
	Q.InitQueue();
	for(int i=0;i<G.vexnum;i++)
		if(!visited[i]) //i尚未访问
		{ 
			visited[i]=true;
			printf("%c ",G.vexs[i]);
			 Q.EnQueue(i); //i入列
			while(Q.front!=Q.rear)
			{
				Q.DeQueue(k); //队头元素出列并置为k
				for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
					if(!visited[w]) //w为k的尚未访问的邻接顶点
					{ 
						visited[w]=true;
						printf("%c ",G.vexs[w]);
						Q.EnQueue(w);
					}
			}
		}
}
//主函数
void main(){
	int i;
	Graph G;
	CreateUDN(G);
	visited=(bool *)malloc(G.vexnum*sizeof(bool)); 
	printf("/n深度优先遍历: "); 
	for(i=0;i<G.vexnum;i++)
		visited[i]=false;
	DFS(G,-1); /* NODE: DFS */
	printf("/n广度优先遍历: "); 
	for(i=0;i<G.vexnum;i++)
		visited[i]=false;
	BFS(G); /* NODE: BFS */
	printf("/n程序结束./n");
}

运行结果：

======================================================

#include <iostream.h> 
#include <stdlib.h> 
#define INFINITY 0 
#define MAX_VERTEX_NUM 10 //最大顶点数 
#define MAX_EDGE_NUM 40 //最大边数 
typedef enum {DG,DN,UDG,UDN}Graphkind; 
typedef char VertexType; //顶点数据类型 
typedef struct ArcCell 
{ 
int adj; //无权图，1或0表示相邻否；带权图则是权值。 
//int *info; 
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; 
typedef struct 
{ 
VertexType vexs[MAX_VERTEX_NUM]; //顶点向量 
AdjMatrix arcs; //邻接矩阵 
int vexnum,arcnum; //图的当前顶点数和弧数。 
Graphkind kind; 
}MGraph; 
int LocateVex(MGraph G,VertexType v1) 
{ 
int i; 
for(i=0;i<G.vexnum;i++) 
if(G.vexs[i]==v1) 
return i; 
return -1; 
} 
int CreatUDN(MGraph &G) 
// 采用数组表示法，构造无向网 G 
{ 
VertexType v1,v2; 
int w,j; 
cout<<"输入图的顶点数"<<endl; 
cin>>G.vexnum; 
cout<<"输入图的弧数"<<endl; 
cin>>G.arcnum; 
for(int i=0;i<G.vexnum;i++) 
{ 
cout<<"输入顶点向量"<<endl; 
cin>>G.vexs[i]; 
} 
for(i=0;i<G.vexnum;i++) 
for(j=0;j<G.vexnum;j++) 
{ 
G.arcs[i][j].adj=INFINITY; 
} 
for(int k=0;k<G.arcnum;++k) //构造邻接矩阵 
{ 
cout<<"输入边依附的两个顶点"<<endl; 
cin>>v1>>v2; 
cout<<"输入此边的权值"<<endl; 
cin>>w; 
i=LocateVex(G,v1); 
j=LocateVex(G,v2); 
G.arcs[i][j].adj=w; 
G.arcs[j][i].adj=G.arcs[i][j].adj; 
} 
return 1; 
} 
void dispMGraph(MGraph G) 
{ 
cout<<"图的邻接矩阵图是："<<endl; 
for(int i=0;i<G.vexnum;i++) 
{ 
for(int j=0;j<G.vexnum;j++) 
cout<<" "<<G.arcs[i][j].adj; 
cout<<endl; 
} 
} 
void main() 
{ 
MGraph G; 
CreatUDN(G); 
dispMGraph(G); 
} 
// 邻接表 表示: 
#include <iostream.h> 
#include <stdlib.h> 
#define MAX_VERTEX_NUM 20 //最大顶点数 
#define MAX_EDGE_NUM 40 //最大边数 
int visited[ MAX_VERTEX_NUM]; 
typedef int VertexType ; //顶点数据类型 
typedef struct ArcNode 
{ 
int adjvex; 
int weight; 
struct ArcNode *nextarc; 
}ArcNode; 
typedef struct VNode 
{ 
VertexType data; 
ArcNode *firstarc; 
}VNode,AdjList[MAX_VERTEX_NUM]; 
typedef struct 
{ 
AdjList vertices; 
int vexnum,arcnum; 
int kind; 
}ALGraph; 
void CreateDG(ALGraph &G) 
{ 
int i,j,k; 
ArcNode *p; 
cout<<"创建一个图:"<<endl; 
cout<<"顶点数:"; cin>>G.vexnum;cout<<endl; 
cout<<"边数:"; cin>>G.arcnum; cout<<endl; 
for(i=0;i<G.vexnum;i++) 
{ 
G.vertices[i].data=i; 
G.vertices[i].firstarc=NULL; 
} 
for(k=0;k<G.arcnum;k++) 
{ 
cout<<"请输入第"<<k+1<<"条边:"; 
cin>>i>>j; 
p=(ArcNode*)malloc(sizeof(ArcNode)); 
p->adjvex=j; 
p->nextarc=G.vertices[i].firstarc; 
G.vertices[i].firstarc=p; 
} 
} 
void Disp(ALGraph G) 
{ 
int i,j; 
ArcNode *p; 
cout<<"输出图为:"<<endl; 
for(i=0;i<G.vexnum;i++) 
{ 
p=G.vertices[i].firstarc; 
j=0; 
while(p!=NULL) 
{ 
cout<<"("<<i<<","<<p->adjvex<<")"; 
p=p->nextarc; 
j=1; 
} 
if(j==1) 
cout<<endl; 
} 
} 
void dfs(ALGraph G,int v) //深度优先遍历 
{ 
ArcNode *p; 
cout<<v<<" "; 
visited[v]=1; 
p=G.vertices[v].firstarc; 
while(p!=NULL) 
{ if(!visited[p->adjvex]) 
dfs(G,p->adjvex); 
p=p->nextarc; 
} 
return ; 
} 
void dfs1(ALGraph G) 
{ 
int i; 
for(i=0;i<G.vexnum;i++) 
if(visited[i]==0) 
dfs(G,i); 
} 
void main() 
{ 
ALGraph G; 
CreateDG(G); 
int v; 
Disp(G); 
cout<<"输入顶点:"; 
cin>>v; 
cout<<"深度优先序列:"; 
dfs1(G); 
cout<<endl; 
} 

评论

1 楼 sunboy_2050 2012-09-11  

转载我的文章，请在“显要”位置注明出处和链接！！！其它几篇也一样！！！