课件我都有，这代码我自然就有了，不过等过两天我学到那里了在告诉你。

LCS 百度找找 很多

[quote]LCS 百度找找 很多[/quote]
LCS是最长公共子序列。。。 - -||||||

你是求什么最短路径？ bfs, dfs都可以求最短路径，同样dijkstra, floyd, bellman-ford也都可以。。。 求路径的话都要记录父节点位置的哦~

2.广度优先遍历 （breadth search）
n思想：从圈中某顶点V0出发，在访问了V0之后依次访
问V0的各个未曾访问过的邻接点，然后分别从这些邻接点出发广度优先遍历图，直至途中所有顶点都被访问到为止.
算法同样需要一个辅助数组visited[] 表示顶点是否被访问过.
 还需要一个队列,记正在访问的这一层和上一层的顶点.
 算法显然是非递归的.
template<NameType,DistType> 
void Graph<NameType,DistType> :: BFS(int v)
    {   int* visited=new int[NumVertices];
         for (int i=0; i<NumVertices; i++) visited[i]=0;
         count<<GetValue(v)<<‘’;
         visited[v]=1;
         queue<int> q;
         q.EnQueue(v);
         while(!q.IsEmpty())
            {  v=q.DeQueue();
                int w=GetFirstNeighbor(v);
                while (w!=-1)
                  {  if(!visited[w])
                        {  cout<<GetValue(w)<<‘’;
                            visited[w]=1;
                            q.EnQueue(w);
                         }
                      w=GetNextNeighbor(v,w);
                   }
             }
           delete[] visited;
       }
算法分析： 每个顶点进队列一次且只进一次，∴算法           
                   中循环语句至多执行n次。
    从具体图的存储结构来看：
1) 如果用邻接表：循环总时间代价为d0+d1+…+dn-1=O(e)                                            
                                                            其中di是顶点i的度
2) 如果用邻接矩阵: 对每个被访问过的顶点，循环检测矩    
    阵中n个元素，∴时间代价为 O(n2) 
[color=FF0000]把里面的队列改为用数组来实现[/color]！
完整代码过两天给你把，最近忙这考研，写个程序都老分很多次写。

程序写好了，很多代码是课件复制的，因为复制的代码可能没有调试过还有很多错误（现在是运行错误），也有很多不足。比如：
template <class DistType> class Edge       //边的定义
{ public:
     //friend class Graph <NameType,DistType>;
我原来的意思是想
template <class DistType> class Edge       //边的定义
{   
friend class Graph <NameType,DistType>;
可是没有想到这样会错
我贴出来仅供参考。
也希望各位高手能帮忙调试一下，指教指教!
#include<iostream>
using namespace std;
const int Defaultsize=10;
template<class NameType,class DistType> class Graph;
template<class NameType, class DistType> class Vertex;
template <class DistType> class Edge       //边的定义
{ public:
     //friend class Graph <NameType,DistType>;
     int dest;                     //边的另一顶点在顶点表中的位置
     DistType cost;                                         //边上的权
     Edge<DistType> *link;                 //下一条边的链指针
     Edge() {}                                                  //构造函数
     Edge(int D,DistType C):dest(D),cost(C),link(NULL){}
                                                                     //构造函数
     int operator != (const Edge<DistType> &E) const
          {return dest != E.dest; }
};
template<class NameType, class DistType> class Vertex{
     friend class Edge<DistType>;
     friend class Graph<NameType, DistType>;
     NameType data;                                         //顶点名字
     Edge<DistType> *adj;                           //出边表头指针
} ;
//图的类定义
template<class NameType,class DistType> class Graph
                                                                    //图的类定义
{ private:
     Vertex<NameType,DistType> *NodeTable;           //顶点表
     int NumVertices;                                //当前顶点 数
     int MaxNumVertices;                             //最大顶点个数
     int NumEdges;                                   //当前边数
     int GetVertexpos(const NameType &Verte);  //给出顶点Verte在图中的位置
     void DFS(int v, int visited[]);

  public:
     Graph(int sz);
     ~Graph();
     int GraphEmpty() const {return NumVertices==0;}//一下这些函数应该都是见名知意
     int GraphFull() const 
     {return NumVertices==MaxNumVertices;}
     int NumberOfVertices() {return NumVertices;}
     int NumberOfEdges() {return NumEdges;}
  NameType GetValue(const int i)
      {return i>=0 && i<NumVertices ? NodeTable[i].data: NULL;}
  void InsertVertex(const NameType &Vertex);
  void RemoveVertex(int v);
  void InsertEdge(int v1,int v2,DistType weight);
  void RemoveEdge(int v1,int v2);
  DistType Getweight(int v1,int v2);
  int GetFristNeighbor(int v);
  int GetNextNeighbor(int v1,int v2);
  void DFS();//深度遍历
  void  BFS(int v);//广度遍历
};
//构造函数
template<class NameType,class DistType>
Graph<NameType,DistType> :: Graph(int sz=Defaultsize) : NumVertices(0),
MaxNumVertices(sz),NumEdges(0)
{ int NumVert,k,j; 
   NameType name,tail,head;
   DistType weight;
   NodeTable=new Vertex<NameType,DistType>[MaxNumVertices] ;
   cout<<"请输入顶点数：";       
   cin>>NumVert;                                 //输入顶点数
   for( int i=0; i<NumVert; i++ )
      {  cout<<"请输入顶点"<<i<<"的数据：";
         cin>>name;
         InsertVertex(name);
      }
   cout<<"请输入边数：";
   cin>>NumEdges;                                      //输入边数
    for( i=0; i<NumEdges; i++)
    {    cout<<"请输入第"<<i<<"条边的数据（分别为tail，head，weight）：";
         cin>>tail>>head>>weight;
         k=GetVertexpos(tail);
         j=GetVertexpos(head);
         InsertEdge(k,j,weight);
      }
}

//析构函数
template<class NameType,class DistType>
Graph<NameType,DistType> ::~Graph()
{
    for(int i=0;i<NumVertices;i++)
    {
        Edge<DistType> *p=NodeTable[i].adj;
        while(p!=NULL)
        {
            NodeTable[i].adj=p->link;
            delete p;
            p=NodeTable[i].adj;
        }
    }
    delete []NodeTable;
}
template<class NameType,class DistType>//找到顶点位置
int Graph<NameType,DistType> :: GetVertexpos(const NameType &Verte)
     {   for( int i=0; i<NumVertices; i++)
              if (NodeTable[i].data==Verte) return  i;
               return -1;
     }
//n给出顶点V的第一个邻接顶点的位置

template<class NameType, class DistType>
int Graph<NameType, DistType> ::GetFristNeighbor(int v)
{  if (v>0&&v<MaxNumVertices)
     { Edge<DistType> * p =NodeTable[v].adj;
        if (p!=NULL) return p->dest;
     }
     return -1;
 }
template<class NameType,class DistType>
int Graph<NameType,DistType> ::GetNextNeighbor(int v1,int v2)
 {  if (v1!=-1)
        { Edge<DistType> *p=NodeTable[v1].adj;
               while (p!=NULL)
              { if(p->dest==v2 && p->link!=NULL)
                        return p->link->dest;
                      else p=p->link;
              }
        }
          return -1;
 }  
template<class NameType,class DistType>//插入顶点
void Graph<NameType,DistType> ::InsertVertex(const NameType &Verte)
{
    if(NumVertices==MaxNumVertices)return;
    NumVertices++;
    NodeTable[NumVertices].data=Verte;
    NodeTable[NumVertices].adj=NULL;

}
template<class NameType,class DistType>//删除顶点
void Graph<NameType,DistType> ::RemoveVertex(int v)
{
    if(v<0||v>=NumVertices) return ;
    Edge<DistType> *p=NodeTable[i].adj;
    
    while(p!=NULL)
    {   RemoveEdge(p->Dest,v);
        RemoveEdge(v,p->Dest);
        p=p->link;
    }
    for(int i=v;i<NumVertices-1;i++)
    {
        NodeTable[i].data=NodeTable[i+1].data;
        NodeTable[i].adj=NodeTable[i+1].adj;
    }
    NodeTable[NumVertices-1].adj=NULL;
    
}
template<class NameType,class DistType>//插入边
void  Graph<NameType,DistType> ::InsertEdge(int v1,int v2,DistType weight)
{   Edge<DistType> *p=new Edge<DistType>(v2,weight);//?????????????
    p->link=NodeTable[v1].adj;
    NodeTable[v1].adj=p;
}
template<class NameType,class DistType>//remove the edge
void Graph<NameType,DistType> ::RemoveEdge(int v1,int v2)
{
     Edge<DistType> *p=NodeTable[v1].adj;
     Edge<DistType> *q=p;
     while(p!=NULL&&p->Dest==v2)
     {q=p;p=p->link;}
     if(p!=NULL)
     {q->link=p->link;delete p;}
}
template<class NameType,class DistType>
DistType Graph<NameType,DistType> ::Getweight(int v1,int v2)//返回权值
{
    Edge<DistType> *p=NodeTable[v1].adj;
    while(p!=NULL&&p->Dest==v2)
    p=p->link;
    if(p!=NULL)
        return p->cost;
    else return;
}
template<class NameType,class DistType> 
void Graph<NameType,DistType> :: DFS()
{ 
    int *visited=new int[NumVertices];
    for ( int i=0; i<NumVertices; i++) visited[i]=0;
    DFS(0,visited);         //从顶点0开始深度优先搜索 
    delete[] visited;
}   
//子过程：
template<class NameType,class DistType>
void Graph<NameType,DistType> :: DFS(int v, int visited[])
{  cout<<GetValue(v)<<" ";
   visited[v]=1;
   int w=GetFristNeighbor(v);
   while (w!=-1)
   {  
       if(!visited[w]) DFS(w,visited);
       w=GetNextNeighbor(v,w);
    }
}
template<class NameType,class DistType> 
void Graph<NameType,DistType> :: BFS(int v)
{   
    int* visited=new int[NumVertices];
    for (int i=0; i<NumVertices; i++) visited[i]=0;
    cout<<GetValue(v)<<" ";
    visited[v]=1;
    int *queue=new int[NumVertices];
    int head,tail;
    head=tail=0;
    queue[tail]=v;
    tail++;//这两句相当于入队列
    while(head!=tail)//相当于判断队列非空
    { 
        v=queue[head];
        head++;//这两句相当于出队列
        int w=GetFristNeighbor(v);
        while (w!=-1)
        {  if(!visited[w])
           {  cout<<GetValue(w)<<" ";
              visited[w]=1;
              queue[tail]=w;
              tail++;//这两句相当于入队列
            }
            w=GetNextNeighbor(v,w);
        }
     }
    delete[] visited;
}

int main()
{
    Graph<char,int> graph(10);
    graph.DFS();
    graph.BFS(0);
    return 0;
}