软件工程

本类阅读TOP10
·PHP4 + MYSQL + APACHE 在 WIN 系统下的安装、配置
·Linux 入门常用命令(1)
·Linux 入门常用命令(2)
·使用 DCPROMO/FORCEREMOVAL 命令强制将 Active Directory 域控制器降级
·DirectShow学习(八)： CBaseRender类及相应Pin类的源代码分析
·基于ICE方式SIP信令穿透Symmetric NAT技术研究
·Windows 2003网络负载均衡的实现
·一网打尽Win十四种系统故障解决方法
·数百种 Windows 软件的免费替代品列表
·收藏---行百里半九十

→ 分类导航
VC语言Delphi
VB语言ASP
PerlJava
Script数据库
其他语言游戏开发
文件格式网站制作
软件工程.NET开发
对于图的遍历的四种问题

作者：未知 来源：月光软件站 加入时间：2005-2-28　月光软件站

图建立，输入示例：
input the number for vexnum and arcnum:8 9

input8char for vexs(use -enter- to change):a
b
c
d
e
f
g
h

input9arc(char -enter- char -enter- weigh):
0:a
b
11

1:a
c
11

2:b
d
11

3:b
e
11

4:d
h
23

5:e
h
11

6:c
f
11

7:c
g
11

8:f
g
11

遍历建立的矩阵：
88 11 11 88 88 88 88 88
11 88 88 11 11 88 88 88
11 88 88 88 88 11 11 88
88 11 88 88 88 88 88 23
88 11 88 88 88 88 88 11
88 88 11 88 88 88 11 88
88 88 11 88 88 11 88 88
88 88 88 23 11 88 88 88
遍历的结果：
a
b
d
h
e
c
f
g
(邻接矩阵图深度遍历结果)

实际图形示例：
                                                                
                                a

                      b                    c

              d            e          f ------g

                      h 
                  (其他是上下连起)
代码：

邻接表图的广度遍历


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

#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20

#define MAXQSIZE 10 //最大队列长度
#define FALSE  0
#define TRUE  1

typedef int VRType;
typedef char VertexType;
typedef int Status;
typedef int  QElemType; 

typedef struct
{
 QElemType *base;
 int  front;
 int  rear;
} SqQueue;

typedef struct ArcNode
{
 int adjvex;
 struct ArcNode *nextarc;
}ArcNode;

typedef struct VNode
{
 VertexType data;
 ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct
{
 AdjList vertices;
 int vexnum, arcnum;
}ALGraph;

bool visited[MAX_VERTEX_NUM];
Status (*VisitFunc)(int v);
int w;

void CreateGraph(ALGraph &G);
void BFSTraverse(ALGraph G, Status (*Visit)(int v));
Status printGraph(int v);
int FirstAdjVex(ALGraph G, int v);
int NextAdjVex(ALGraph G, int v, int w);

Status InitQueue(SqQueue &);
Status EnQueue(SqQueue &, QElemType);
Status DeQueue(SqQueue &, QElemType &);
Status  QueueEmpty(SqQueue);


void main( void )
{

 int i;
 ALGraph G;
 ArcNode *p;
 
 CreateGraph(G);

 for(i= 0; i < G.vexnum; i++)
 {
  cout<<i<<"   "<<G.vertices[i].data;
  p = G.vertices[i].firstarc;
  while(p != NULL)
  {
   cout<<"--->";
   cout<<(G.vertices[p->adjvex].data);
   p = p->nextarc;   
  }
  cout<<endl;
 }
 BFSTraverse(G, printGraph);
}
void CreateGraph(ALGraph &G)
{
 int i, j = 0, k = 0;
 char hand, tide;
 ArcNode *p;
 
 cout<<"input the number for vexnum and arcnum:";
 cin>>G.vexnum>>G.arcnum;
 cout<<endl;
 cout<<"input"<<G.vexnum<<"char for vexs:";
 for(i=0; i < G.vexnum; i++)
  cin>>G.vertices[i].data;
 cout<<endl;
 for(i=0;i<G.vexnum;++i)
  G.vertices[i].firstarc=NULL;
 cout<<"input"<<G.arcnum<<"arc(char-enter-char):"<<endl;
 j = 0;
 k = 0;
 for(i=0; i < G.arcnum; i++)
 {
  cout<<i<<":";
  cin>>hand;
  cin>>tide;
  while (hand != G.vertices[j].data)
   j++;
  while (tide != G.vertices[k].data)
   k++;
  p=new ArcNode;
  p->adjvex=j;
  p->nextarc=G.vertices[j].firstarc;
  G.vertices[k].firstarc=p;
  p=new ArcNode;
  p->adjvex=k;
  p->nextarc=G.vertices[j].firstarc;
  G.vertices[j].firstarc=p;
  
  j = 0;
  k = 0;
  cout<<endl;
 }
}

void BFSTraverse(ALGraph G, Status (*Visit)(int v))
{
 SqQueue  Q;
 QElemType   u;

 InitQueue(Q);

 for(int v=0; v < G.vexnum;++v)
  visited[v]=FALSE;
 for(v=0; v<G.vexnum;++v)
  if(!visited[v])
  {
   visited[v]=TRUE;
   EnQueue(Q, v);
   Visit(v);
   while(QueueEmpty(Q))
   {
    DeQueue(Q, u);
    for(w = FirstAdjVex(G, u); w; w = NextAdjVex(G, u, w))
     if(! visited[w])
     {
      visited[w]=TRUE;
      Visit(w);
      EnQueue(Q, w);
     }
   }
  }
}

int FirstAdjVex(ALGraph G, int v)
{
 ArcNode *p;
 p = G.vertices[v].firstarc;
 while(p != NULL)
 {
  if(visited[p->adjvex] != 1)
   return p->adjvex;
  p = p->nextarc;
 }
 return 0;
}

int NextAdjVex(ALGraph G, int v, int w)
{
 ArcNode *p;
 p = G.vertices[v].firstarc;
 while(p != NULL)
 {
  if(visited[p->adjvex] != 1 && p->adjvex != w)
   return p->adjvex;
  p = p->nextarc;
 }
 return 0;
}

Status printGraph(int v)
{
 printf("%c", v + 'a');
 cout<<endl;
 return 1;
}

Status InitQueue(SqQueue & queue)
{
 queue.base = (QElemType *) malloc(MAXQSIZE * sizeof(QElemType));
 
 if (!queue.base)
  return FALSE;
 queue.front = queue.rear = 0;

 return TRUE;
}

///////////////////////////////////////////////////////////////////////
//
// 函数名       : EnQueue
// 功能描述     : 插入元素到队列
// 参数         : SqQueue &queue
// 参数         : QElemType element
// 返回值       : Status
//
///////////////////////////////////////////////////////////////////////
Status EnQueue(SqQueue &queue, QElemType element)
{
 //先判断是不是没满的队列
 if ((queue.rear + 1)  % MAXQSIZE == queue.front)
  return FALSE;
 queue.base[queue.rear] = element;

 queue.rear = (queue.rear + 1) % MAXQSIZE;

 return TRUE;
}


///////////////////////////////////////////////////////////////////////
//
// 函数名       : DeQueue
// 功能描述     : 删除队列的头结点
// 参数         : SqQueue &queue
// 参数         : QElemType &element
// 返回值       : Status
//
///////////////////////////////////////////////////////////////////////
Status DeQueue(SqQueue &queue, QElemType &element)
{
 //判断队列是不是空的
 if (queue.front == queue.rear)
  return FALSE;
 element = queue.base[queue.front];
 queue.front = (queue.front + 1) % MAXQSIZE;
 
 return TRUE;
}

Status  QueueEmpty(SqQueue queue)
{
 if (queue.front == queue.rear)
  return FALSE;
 else
  return TRUE;

}

邻接表图的深度遍历

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

#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20

typedef int VRType;
typedef char VertexType;
typedef int Status;


typedef struct ArcNode
{
 int adjvex;
 struct ArcNode *nextarc;
}ArcNode;

typedef struct VNode
{
 VertexType data;
 ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct
{
 AdjList vertices;
 int vexnum, arcnum;
}ALGraph;

bool visited[MAX_VERTEX_NUM];
Status (*VisitFunc)(int v);
int w;

void CreateGraph(ALGraph &G);
void DFSTraverse(ALGraph G, Status (*Visit)(int v));
Status printGraph(int v);
int FirstAdjVex(ALGraph G, int v);
int NextAdjVex(ALGraph G, int v, int w);
void DFS(ALGraph G, int v);


void main( void )
{

 int i;
 ALGraph G;
 ArcNode *p;
 
 CreateGraph(G);

 for(i= 0; i < G.vexnum; i++)
 {
  cout<<i<<"   "<<G.vertices[i].data;
  p = G.vertices[i].firstarc;
  while(p != NULL)
  {
   cout<<"--->";
   cout<<(G.vertices[p->adjvex].data);
   p = p->nextarc;   
  }
  cout<<endl;
 }
 DFSTraverse(G, printGraph);
}
void CreateGraph(ALGraph &G)
{
 int i, j = 0, k = 0;
 char hand, tide;
 ArcNode *p;
 
 cout<<"input the number for vexnum and arcnum:";
 cin>>G.vexnum>>G.arcnum;
 cout<<endl;
 cout<<"input"<<G.vexnum<<"char for vexs:";
 for(i=0; i < G.vexnum; i++)
  cin>>G.vertices[i].data;
 cout<<endl;
 for(i=0;i<G.vexnum;++i)
  G.vertices[i].firstarc=NULL;
 cout<<"input"<<G.arcnum<<"arc(char-enter-char):"<<endl;
 j = 0;
 k = 0;
 for(i=0; i < G.arcnum; i++)
 {
  cout<<i<<":";
  cin>>hand;
  cin>>tide;
  while (hand != G.vertices[j].data)
   j++;
  while (tide != G.vertices[k].data)
   k++;
  p=new ArcNode;
  p->adjvex=j;
  p->nextarc=G.vertices[j].firstarc;
  G.vertices[k].firstarc=p;
  p=new ArcNode;
  p->adjvex=k;
  p->nextarc=G.vertices[j].firstarc;
  G.vertices[j].firstarc=p;
  
  j = 0;
  k = 0;
  cout<<endl;
 }
}

void DFSTraverse(ALGraph G, Status (*Visit)(int v))
{
 int j;
 VisitFunc = Visit;
 for( j=0; j<G.vexnum; j++)
  visited[j] = 0;
 for(j=0; j<G.vexnum; j++)
  if(!visited[j])
   DFS(G, j);
}

void DFS(ALGraph G, int v)
{
 
 visited[v]=1;
 VisitFunc(v);
 for(w=FirstAdjVex(G, v); w; w=NextAdjVex(G, v, w))
  if(!visited[w])
   DFS(G, w);
}

int FirstAdjVex(ALGraph G, int v)
{
 ArcNode *p;
 p = G.vertices[v].firstarc;
 while(p != NULL)
 {
  if(visited[p->adjvex] != 1)
   return p->adjvex;
  p = p->nextarc;
 }
 return 0;
}

int NextAdjVex(ALGraph G, int v, int w)
{
 ArcNode *p;
 p = G.vertices[v].firstarc;
 while(p != NULL)
 {
  if(visited[p->adjvex] != 1 && p->adjvex != w)
   return p->adjvex;
  p = p->nextarc;
 }
 return 0;
}

Status printGraph(int v)
{
 printf("%c", v + 'a');
 cout<<endl;
 return 1;
}

邻接矩阵的广度遍历

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

#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20

#define MAXQSIZE 10 //最大队列长度
#define FALSE  0
#define TRUE  1

typedef int VRType;
typedef int InfoType;
typedef char VertexType;
typedef int Status;
typedef int  QElemType; 

typedef struct
{
 QElemType *base;
 int  front;
 int  rear;
} SqQueue;

typedef struct ArcCell
{
 VRType adj;
 InfoType *info;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
 VertexType vexs[MAX_VERTEX_NUM];
 AdjMatrix arcs;
 int vexnum, arcnum;
}MGraph;

bool visited[MAX_VERTEX_NUM];
Status (*VisitFunc)(int v);
int w;

void CreateGraph(MGraph &G);
void BFSTraverse(MGraph G, Status (*Visit)(int v));
Status printGraph(int v);
int FirstAdjVex(MGraph G, int v);
int NextAdjVex(MGraph G, int v, int w);

Status InitQueue(SqQueue &);
Status EnQueue(SqQueue &, QElemType);
Status DeQueue(SqQueue &, QElemType &);
Status  QueueEmpty(SqQueue);

void main( void )
{
 int i, j;
 MGraph G;
 
 CreateGraph(G);
 for(i = 0; i < G.vexnum; i++)
 {
  for(j = 0; j < G.vexnum; j++)
  {
   cout<<G.arcs[i][j].adj;
   cout<<" ";
  }
  cout<<endl;
 }
 BFSTraverse(G, printGraph);
}
void CreateGraph(MGraph &G)
{
 int weigh;
 int i, j = 0, k = 0;
 char hand, tide;
 
 cout<<"input the number for vexnum and arcnum:";
 cin>>G.vexnum>>G.arcnum;

 for(i = 0; i < G.vexnum; i++)
 {
  for(j = 0; j < G.vexnum; j++)
   G.arcs[i][j].adj = 88;
 }

 cout<<endl;
 cout<<"input"<<G.vexnum<<"char for vexs(use -enter- to change):";
 for(i=0; i < G.vexnum; i++)
  cin>>G.vexs[i];
 cout<<endl;
 cout<<"input"<<G.arcnum<<"arc(char -enter- char -enter- weigh):"<<endl;
 j = 0;
 k = 0;
 for(i=0; i < G.arcnum; i++)
 {
  cout<<i<<":";
  cin>>hand;
  cin>>tide;
  cin>>weigh;
  while (hand != G.vexs[j])
   j++;
  while (tide != G.vexs[k])
   k++;
  G.arcs[j][k].adj = weigh;
  G.arcs[k][j].adj = weigh;
  j = 0;
  k = 0;
  cout<<endl;
 }
}

void BFSTraverse(MGraph G, Status (*Visit)(int v))
{

 SqQueue  Q;
 QElemType   u;

 InitQueue(Q);

 for(int v=0; v < G.vexnum;++v)
  visited[v]=FALSE;
 for(v=0; v<G.vexnum;++v)
  if(!visited[v])
  {
   visited[v]=TRUE;
   Visit(v);
   EnQueue(Q, v);
   while(QueueEmpty(Q))
   {
    DeQueue(Q, u);
    for(w = FirstAdjVex(G, u); w; w = NextAdjVex(G, u, w))
     if(! visited[w])
     {
      visited[w]=TRUE;
      Visit(w);
      EnQueue(Q, w);
     }
   }
  }
}

int FirstAdjVex(MGraph G, int v)
{
 int j;
 for(j = 0; j < G.vexnum; j++)
 {
  if(G.arcs[v][j].adj != 88 && visited[j] != 1)
   return j;
 }
 return 0;
}

int NextAdjVex(MGraph G, int v, int w)
{
 int j;
 for(j = 0; j < G.vexnum; j++)
 {
  if(G.arcs[v][j].adj != 88 && j != w && visited[j] != 1)
   return j;
 }
 return 0;
}

Status printGraph(int v)
{
 printf("%c", v + 'a');
 cout<<endl;
 return 1;
}

Status InitQueue(SqQueue & queue)
{
 queue.base = (QElemType *) malloc(MAXQSIZE * sizeof(QElemType));
 
 if (!queue.base)
  return FALSE;
 queue.front = queue.rear = 0;

 return TRUE;
}

///////////////////////////////////////////////////////////////////////
//
// 函数名       : EnQueue
// 功能描述     : 插入元素到队列
// 参数         : SqQueue &queue
// 参数         : QElemType element
// 返回值       : Status
//
///////////////////////////////////////////////////////////////////////
Status EnQueue(SqQueue &queue, QElemType element)
{
 //先判断是不是没满的队列
 if ((queue.rear + 1)  % MAXQSIZE == queue.front)
  return FALSE;
 queue.base[queue.rear] = element;

 queue.rear = (queue.rear + 1) % MAXQSIZE;

 return TRUE;
}


///////////////////////////////////////////////////////////////////////
//
// 函数名       : DeQueue
// 功能描述     : 删除队列的头结点
// 参数         : SqQueue &queue
// 参数         : QElemType &element
// 返回值       : Status
//
///////////////////////////////////////////////////////////////////////
Status DeQueue(SqQueue &queue, QElemType &element)
{
 //判断队列是不是空的
 if (queue.front == queue.rear)
  return FALSE;
 element = queue.base[queue.front];
 queue.front = (queue.front + 1) % MAXQSIZE;
 
 return TRUE;
}

Status  QueueEmpty(SqQueue queue)
{
 if (queue.front == queue.rear)
  return FALSE;
 else
  return TRUE;

}

邻接矩阵的深度遍历

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

#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20

typedef int VRType;
typedef int InfoType;
typedef char VertexType;
typedef int Status;

typedef struct ArcCell
{
 VRType adj;
 InfoType *info;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct
{
 VertexType vexs[MAX_VERTEX_NUM];
 AdjMatrix arcs;
 int vexnum, arcnum;
}MGraph;

bool visited[MAX_VERTEX_NUM];
Status (*VisitFunc)(int v);
int w;

void CreateGraph(MGraph &G);
void DFSTraverse(MGraph G, Status (*Visit)(int v));
Status printGraph(int v);
int FirstAdjVex(MGraph G, int v);
int NextAdjVex(MGraph G, int v, int w);
void DFS(MGraph G, int v);

void main( void )
{
 int i, j;
 MGraph G;
 
 CreateGraph(G);
 for(i = 0; i < G.vexnum; i++)
 {
  for(j = 0; j < G.vexnum; j++)
  {
   cout<<G.arcs[i][j].adj;
   cout<<" ";
  }
  cout<<endl;
 }
 DFSTraverse(G, printGraph);
}
void CreateGraph(MGraph &G)
{
 int weigh;
 int i, j = 0, k = 0;
 char hand, tide;
 
 cout<<"input the number for vexnum and arcnum:";
 cin>>G.vexnum>>G.arcnum;

 for(i = 0; i < G.vexnum; i++)
 {
  for(j = 0; j < G.vexnum; j++)
   G.arcs[i][j].adj = 88;
 }

 cout<<endl;
 cout<<"input"<<G.vexnum<<"char for vexs(use -enter- to change):";
 for(i=0; i < G.vexnum; i++)
  cin>>G.vexs[i];
 cout<<endl;
 cout<<"input"<<G.arcnum<<"arc(char -enter- char -enter- weigh):"<<endl;
 j = 0;
 k = 0;
 for(i=0; i < G.arcnum; i++)
 {
  cout<<i<<":";
  cin>>hand;
  cin>>tide;
  cin>>weigh;
  while (hand != G.vexs[j])
   j++;
  while (tide != G.vexs[k])
   k++;
  G.arcs[j][k].adj = weigh;
  G.arcs[k][j].adj = weigh;
  j = 0;
  k = 0;
  cout<<endl;
 }
}

void DFSTraverse(MGraph G, Status (*Visit)(int v))
{
 int j;
 VisitFunc = Visit;
 for( j=0; j<G.vexnum; j++)
  visited[j] = 0;
 for(j=0; j<G.vexnum; j++)
  if(!visited[j])
   DFS(G, j);
}

void DFS(MGraph G, int v)
{

 visited[v]=1;
 VisitFunc(v);
 for(w=FirstAdjVex(G, v); w; w=NextAdjVex(G, v, w))
  if(!visited[w])
   DFS(G, w);
}

int FirstAdjVex(MGraph G, int v)
{
 int j;
 for(j = 0; j < G.vexnum; j++)
 {
  if(G.arcs[v][j].adj != 88 && visited[j] != 1)
   return j;
 }
 return 0;
}

int NextAdjVex(MGraph G, int v, int w)
{
 int j;
 for(j = 0; j < G.vexnum; j++)
 {
  if(G.arcs[v][j].adj != 88 && j != w && visited[j] != 1)
   return j;
 }
 return 0;
}

Status printGraph(int v)
{
 printf("%c", v + 'a');
 cout<<endl;
 return 1;
}

相关文章：

相关软件：