图的建立 与 DFS、BFS

这一个程序写了好久，主要是对三个结构体同时操作时出现混乱。

本程序主要是关于图的创建和图的深度优先遍历DFS 和 广度优先遍历BFS。

其中，我把每个节点从a到z分别命名。这程序的输入是一个矩阵，如下：

0   11   0

11  0   13

0   13   0

由这个矩阵的对称性可以看出，它是一个无向图，当然本程序也可以处理有向图。

程序里，我是用邻接法来建立图的。有兴趣的朋友可以试试用 十字链表 来实现有向图，用 邻接多重表 来实现无向图。

但注意，我一开始限制了矩阵的维数为25 ，如需扩大，请修改Max_vertex_num的值。

对了，广度优先遍历我用的是非递归算法，深度优先遍历用的是递归算法，其它两种算法在接下去的日子里，我会补充的。

#include<iostream>
#include<queue>
using namespace std;

typedef int INFOTYPE;
typedef char VERTEXTYPE;
const INFOTYPE Max_vertex_num = 25; //定为25，则矩阵最多只能是25x25
int visited[Max_vertex_num];

typedef struct ArcNode
{
 int adjvex; //这条弧的下一个结点
 struct ArcNode *nextarc;
 INFOTYPE info; //弧上的数据
}ArcNode;

typedef struct VNode
{
 VERTEXTYPE data; //结点的数据
 ArcNode *firstarc; //与之连接的第一个链结点
}VNode, AdjList[Max_vertex_num];

typedef struct 
{
 AdjList vertices;
 int vexnum,arcnum;
 int kind; //1表示无向图
}ALGraph ;

//创建（初始化）这个图
void createGraph(ALGraph &graph, INFOTYPE data[Max_vertex_num][Max_vertex_num], int v) //data指传入的矩阵，v指矩阵的维数
{
 int i=0,j=0,arcnum=0,flag=1; //flag用来指示是否是无向图，1表示是。
 ArcNode *tempArc=NULL,*p=NULL;
 graph.vexnum = v;
 for(;i < v; i ++)
 {
  tempArc = (ArcNode*)malloc(sizeof(ArcNode));
  graph.vertices[i].firstarc = tempArc;
  graph.vertices[i].data = 'a' + i; //给结点编号，从a开始
  tempArc->nextarc = NULL;
  p = NULL;
  for(j = 0; j < v; j ++)
  {
   if(data[i][j] != 0)
   {
    arcnum ++;
    if(data[j][i] == 0) flag = 0;
    tempArc->adjvex = j;
    tempArc->info = data[i][j];
    if(p) p->nextarc = tempArc;
    p = tempArc;
    tempArc = tempArc->nextarc;
    tempArc = (ArcNode*)malloc(sizeof(struct ArcNode));
    tempArc->nextarc = NULL;
   }
  }
  free(tempArc);
 }
 graph.arcnum = flag?(arcnum/2):arcnum;
 graph.kind = flag;
}


//取得下标为i的第一个邻结点
int FirstAdjVex(ALGraph g, int i)
{
 return g.vertices[i].firstarc->adjvex;
}

//BFS取得下一个邻结点
int BFS_NextAdjVex(ALGraph g, int i, int w)
{
 ArcNode* arc = g.vertices[i].firstarc;
 while(arc->adjvex != w)
 {
  arc = arc->nextarc;
 }
 if(!arc->nextarc) return -1;
 return arc->nextarc->adjvex;
}

//DFS取得下一个邻结点
int DFS_NextAdjVex(ALGraph g, int i)
{
 ArcNode* arc = g.vertices[i].firstarc;
 //if(!g.vertices[i].firstarc) return -1;
 if(visited[arc->adjvex])
 {
  if(arc->nextarc) return arc->nextarc->adjvex;
  return -1;
 }
 return arc->adjvex;
}

//广度优先遍历
void BFS_traverse(ALGraph graph)
{
 int i=0,n=graph.vexnum;
 memset(visited,0,n*sizeof(int)); //先设为0，表示未访问过
 queue<int> q;
 int t,w; //临时变量，在队列操作中使用
 for(i=0; i<n; i++)
 {
  if(!visited[i])
  {
   visited[i] = 1;
   //开始访问
   cout<<graph.vertices[i].data<<endl;
   q.push(i);
   while(!q.empty())
   {
    t = q.front();
    q.pop();
    for(w = FirstAdjVex(graph,t); w > 0; w = BFS_NextAdjVex(graph,t,w))
    {
     if(!visited[w])
     {
      visited[w] = 1;
      //开始访问
      cout<<graph.vertices[w].data<<endl;
      q.push(w);
     }
    }
   }
  }
 }
}

//深度优先遍历
void DFS_traverse(ALGraph graph, int v) //v表示选取v结点开始访问
{
}

//深度优先遍历(递归)
void recursion_DFS_traverse(ALGraph graph, int v) //v表示选取v结点开始访问
{
 int i=0, n=graph.vexnum, w;
 visited[v] = 1;
 //开始访问
 cout<<graph.vertices[v].data<<endl;
 for(w = v; w >= 0; w = DFS_NextAdjVex(graph,w))
 {
  if(w>=0 && !visited[w]) recursion_DFS_traverse(graph, w);
 }
}

//把图打印出来
void printGraph(ALGraph g)
{
 int n = g.vexnum, visited[Max_vertex_num];
 ArcNode* arc;
 memset(visited,0,n*sizeof(int)); //先设为0，表示未访问过
 for(int i = 0; i < n; i ++)
 {
  arc = g.vertices[i].firstarc;
  printf("%c->%c", g.vertices[i].data, g.vertices[g.vertices[i].firstarc->adjvex].data);
  while(arc->nextarc)
  {
   printf("->");
   arc = arc->nextarc;
   printf("%c", g.vertices[arc->adjvex].data);
  }
  printf("\n");
 }
}

int main()
{
 int n,i,j;
 INFOTYPE data[Max_vertex_num][Max_vertex_num];
 ALGraph *graph = (ALGraph*)malloc(sizeof(ALGraph));
 cout<<"How many dimensions is the matrix:";
 cin>>n;
 memset(data,-1,n*n); //假定输入的弧数据不会是-1
 //开始输入矩阵
 cout<<"Input the matrix:"<<endl;
 for(i = 0; i < n; i ++)
  for(j = 0; j < n; j ++)
   cin>>data[i][j];
 createGraph(*graph,data,n);

 printGraph(*graph);

 BFS_traverse(*graph);

 memset(visited,0,n*sizeof(int)); //先设为0，表示未访问过
 recursion_DFS_traverse(*graph, 0);

 //cout<<graph->vertices[1].firstarc->info;
 return 0;
}