学步园

一。图的储存结构

1.临接矩阵表示
易确认两任意顶点是否有边，要确定有多少条则要遍历全图
适合稠密图

#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 100
#define inf 2000000000
typedef char vertexType;
struct vertex
{
     int num;
     vertexType data;
};
typedef struct graph
{
     struct vertex vexs[MAXVEX];//vertex
     int edges[MAXVEX][MAXVEX];//adjacency matrix
}adjmax;

2.临接表
无向图有n个顶点，e条边，则临接表需要n个结点哥2e个表节点，适合稀疏图；
无向图中vi的度为第i个链表中的结点数;
有向图中vi的出度为第i个链表中的结点数，求入度需遍历全图，可建立逆临接表；
易找到任一顶点的第一哥邻接点和下一个临接点，但搜索vi和vj之间是否有边或弧需搜索第i个或第j个链表。

#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 100
#define inf 2000000000
typedef char vertexType;
struct edgeNode{
     int from;
     int weight;
     struct edgeNode *next;
     vertexType data;
};
typedef struct vexnode
{
     vertexType data;
     int No;
     struct edgeNode *link;
}adjlist[MAXVEX];

二。两种遍历

深搜：
类似于树的先根遍历

//deep first search
void dfs(adjlist adj,int v,int visited[])
//adj is a adjlist, v is the No. of first point,visited is a assistant array 
{
     int i;
     struct edgeNode *p;
     visited[v]=1;
     printf("[%d,%c]",v,adj[v].data);
     p=adj[v].link;
     while(p!=NULL)
     {
          if(visited[p->from]==0) dfs(adj,p->from,visited);
          p=p->next;
     }
}

宽搜
类似树的层次遍历
访问v之后依次访问各个未曾访问过的临接点，然后分别从这些临接点出发依次访问他们的临接点

//broad first search
void bfs(adjlist adj,int v,int visited[])
{
     struct edgeNode *p;
     visited[v]=1;
    int front=-1,rear=-1;
     int i;
    rear++;
    printf("[%d,%c]",v,adj[v].data);
    queue[rear]=v;
    while(front!=rear)
    {
         front=(front+1)%MAXVEX;
         i=queue[front];
         p=adj[i].link;
         while(p!=NULL)
         {
              if(visited[p->from]==0)
              {
                   printf("..%d,%d:\n",p->from,visited[p->from]);
                  visited[p->from]=1;
                  printf("[%d,%c]",p->from,adj[p->from].data);
                  rear=(rear+1)%MAXVEX;
                  queue[rear]=p->from;
              }
              p=p->next;
         }
    }


}