若干定义

一个图G = (V , E)由顶点集V和边集E组成，每条边就是一个点对

如果点对是有序的，那么就叫做有向图

边可能还具有第三种成分，权值

无向图种从每个顶点到其他每个顶点都存在至少一天路径，则称为图是连通的。具有这样性质的有向图称为强连通，如果不是强连通的，但它的基础图是连通的，则称为弱连通

图的表示

领接矩阵

- 使用一个二维数组表示- 对于每条边(u,v)，置A[u][v] = 1;

邻接表

- 用一个表来储存这个顶点的所有邻接点- 使用一个数组保存头单元- 每个头单元连接着所有顶点

拓扑排序

对有向无圈的顶点的一种排序，使得如果存在从vi到vj，那么在排序中vj必须出现在vi后面

实现

简单实现

从有向图中选取一个没有前驱(入度为0)的顶点，并输出之；

从有向图中删去此顶点以及所有以它为尾的弧(弧头顶点的入度减1)；

重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。

类型声明

typedef char VertexType ;typedef struct OutNode *Degree ;typedef struct GVertex *Vertex ;struct OutNode{    VertexType Date ;    Degree Next ;}struct GVertex{    int in ;    VertexType Date ;    Degree First ;}

主函数

int Getin(Vertex G){    int len = 0;    while((G++)->Data != '/0')        len ++ ;    return len ;}void TopSort(Vertex G){    int i,j,k ;    Degree P;    int VertexNum ;    VertexNum = Getin(G) ;    for(i = 0; i < VertexNum; i++)        for(j = 0;j < VertexNum; j++)            if(G[j].in === 0)            {                printf("%c ", G[j].data);                G[j].in = -1;                P = G[j].first ;                while(P != NULL)                {                    for( k=0; k
    
     data == G[k].data ) {                            G[k].in--;                            break;                        }                    P = P->next;                }                break ;            }}

无权单源最短路算法

基本思路：按照BFS的思路搜索图，并记下路径长

void Unweihted(Table T){    int CurrDist ;    Vertex V, W ;        for(Currist = 0; Currist < NumVertex; Currist++)        for each vertex V            if(!T[v].Known && T[v].Dist == Currist)            {                T[v].Known = True ;                for each W adjacent to V                    if(T[W].Dist == Infinity)                    {                        T[W].Dist = CurrDist + 1 ;                        T[W].Path = V ;                    }            }}

更高效率的

void Unweighted(Table T){    Queue Q ;    Vertex V, W ;        Q = CreateQueue(NumVertex) ;    MakeEmpty(Q) ;        while(!IsEmpty(Q))    {        V = Dequeue(Q) ;        T[V].Known = True ;                for each W adjacent to V            if(T[W].Dist == Infinity)            {                T[W].Dist == T[W].Dist + 1;                T[W].Path = V ;                Enqueue(W,Q) ;            }    }    DisposeQueue(Q) ;}