图的基本操作--邻接矩阵类型

本文作者：韩申权
作者博客：http://www.cnblogs.com/hsqdboke
转载请注明出处，侵权必究，保留最终解释权！

程序1

/* 定义邻接矩阵类型 */

typedef int  adjmatrix[n+1][n+1];

 

/* 建立图的邻接矩阵 */

void CreatMatrix(adjmatrix GA)

 

/* 从初始点v出发深度优先遍历邻接矩阵GA表示的图 */

void DfsMatrix(adjmatrix GA,int v)

 

/*从初始点v出发广度优先遍历邻接矩阵GA表示的图*/

void BfsMatrix(adjmatrix GA,int v)

例如：

//2012年5月22日20:37:07
//用邻接矩阵构造一个无向图 并进行DFS和BFS搜索
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_V 20 //定义最大顶点数20
#define OVERFLOW -1
int p=1,q=1;
int visited[21];
char ver[21][10];
typedef int adjmatrix[MAX_V+1][MAX_V+1];
typedef int QElemType;
typedef struct
{
adjmatrix d;
int v,e;
}Graph;
void CreateG(adjmatrix d,int n,int e)
{
int i,j,k;
printf("请分别输入顶点1到顶点%d的信息:",n);
for(i=1;i<=n;i++)
{
//getchar();
scanf("%s",ver[i]);
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
d[i][j]=0;
for(k=1;k<=e;k++)
{
printf("请输入第%d条边的信息:",k);
scanf("%d%d",&i,&j);
//i和j分别为边的两个顶点
if(i>n||j>n)exit(OVERFLOW);
d[i][j]=1;
d[j][i]=1;
}
}
int FAV(adjmatrix d,int v,int n)//求第一个邻接点v为当前顶点 n为总的顶点数

{
int i;
for(i=1;i<=n;i++)
if(d[v][i]==1)return i;
return 0;
}
int NAV(adjmatrix d,int v,int w,int n)//求相对于其邻接点w的下一个邻接点，w为v的当前邻接点
{
int i;
for(i=w+1;i<=n;i++)
if(d[v][i]==1)return i;
return 0;
}
void visit(int v)
{
if(p)
{printf("%s",ver[v]);p=0;}
else
printf("->%s",ver[v]);
}
void visit1(int v)
{
if(q)
{printf("%s",ver[v]);q=0;}
else
printf("->%s",ver[v]);
}
void DFS(adjmatrix d,int v,int n)
{
int w;
visited[v]=1;
visit(v);
for(w=FAV(d,v,n);w;w=NAV(d,v,w,n))
if(!visited[w])DFS(d,w,n);
}
void DFSTraverse(adjmatrix d,int v,int n)//v为初始点
{
int i;
memset(visited,0,sizeof(visited));
printf("从初始点%d进行DFS的结果为:n",v);
DFS(d,v,n);
for(i=1;i<=n;i++)
if(!visited[i])DFS(d,i,n);
printf("n");
}
//BFS函数需要的基本函数
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode ,*Queuep;
typedef struct
{
Queuep front;
Queuep rear;
}LinkQueue;
void InitQueue(LinkQueue *Q) //初始队列
{
Q->front=Q->rear=(Queuep)malloc(sizeof(QNode));
if(!Q->front)exit(OVERFLOW);
Q->front->next=NULL;
}
int QueueEmpty(LinkQueue *Q)//判空
{
if(Q->front==Q->rear)return 1;
else return 0;
}
void Enqueue (LinkQueue *Q,QElemType e)//添加元素到队尾
{
Queuep p;
p=(Queuep)malloc(sizeof(QNode));
if(!p)exit(OVERFLOW);
p->data=e;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
}
void Dequeue(LinkQueue *Q,QElemType *e)//删除队首元素
{
Queuep p;
p=Q->front->next;
*e=p->data;
Q->front->next=p->next;
if(Q->rear==p)Q->rear=Q->front;
free(p);
}
void BFSTraverse(adjmatrix d,int v,int n) //BFS遍历图
{
int i,w,u;
LinkQueue Q;
memset(visited,0,sizeof(visited));
printf("从初始点%d进行BFS的结果为:n",v);
InitQueue(&Q);
visited[v]=1;
visit1(v);
Enqueue(&Q,v);
while(!QueueEmpty(&Q))
{
Dequeue(&Q,&u);
for(w=FAV(d,u,n);w;w=NAV(d,u,w,n))
if(!visited[w])
{
visited[w]=1;
visit1(w);
Enqueue(&Q,w);
}
}
for(i=1;i<=n;i++)
if(!visited[i])
{
visited[i]=1;
visit1(i);
Enqueue(&Q,i);
while(!QueueEmpty(&Q))
{
Dequeue(&Q,&u);
for(w=FAV(d,u,n);w;w=NAV(d,u,w,n))
if(!visited[w])
{
visited[w]=1;
visit1(w);
Enqueue(&Q,w);
}
}
}
printf("n");
}
int main()
{
Graph G;
int vf;
printf("请分别输入顶点数、边数: ");
scanf("%d%d",&G.v,&G.e);
printf("请输入DFS的初始点:");
scanf("%d",&vf);
CreateG(G.d,G.v,G.e);
DFSTraverse(G.d,vf,G.v);
BFSTraverse(G.d,vf,G.v);
printf("n");
return 0;
}

本文作者：韩申权
作者博客：http://www.cnblogs.com/hsqdboke
转载请注明出处，侵权必究，保留最终解释权！