图论

坑!待填!

若干定义

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

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

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

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

图的表示

领接矩阵

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

邻接表

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

拓扑排序

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

实现

简单实现

  1. 从有向图中选取一个没有前驱(入度为0)的顶点,并输出之;
  2. 从有向图中删去此顶点以及所有以它为尾的弧(弧头顶点的入度减1);
  3. 重复上述两步,直至图空,或者图不空但找不到无前驱的顶点为止。

类型声明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 ;
}

主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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<VertexNum; k++ )
if( P->data == G[k].data ) {
G[k].in--;
break;
}
P = P->next;
}
break ;
}
}

无权单源最短路算法

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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 ;
}
}
}

更高效率的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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) ;
}

DFS深度优先搜索模板

void dfs(Vertex V)
{
    Visited[V] = True ;
    for each W adjacent to V
        if(!Visted[W])
            dfs(W) ;
}
``