待贴图。。。

DFS是一个递归算法,在遍历的过程中,先访问的点被压入栈底。拓扑有序是指如果点U到点V有一条弧,则在拓扑序列中U一定在V之前.深度优先算法搜索路径恰恰是一条弧,栈的输出是从最后一个被访问点开始输出,最后一个输出的点是第一个被访问的点.所以是逆的拓扑有序序列

STrongly Connected Components

作者网址

#include <stdio.h>
#include <stdlib.h>

#define MaxVertices 10 /* maximum number of vertices */
typedef int Vertex;    /* vertices are numbered from 0 to MaxVertices-1 */
typedef struct VNode *PtrToVNode;
struct VNode
{
    Vertex Vert;
    PtrToVNode Next;
};
typedef struct GNode *Graph;
struct GNode
{
    int NumOfVertices;
    int NumOfEdges;
    PtrToVNode *Array;
};

Graph ReadG()
{ /* details omitted */
    int a, b;
    Graph G = (Graph)malloc(sizeof(GNode));
    scanf("%d%d", &G->NumOfVertices, &G->NumOfEdges);
    G->Array = (PtrToVNode *)malloc(sizeof(PtrToVNode) * G->NumOfVertices);
    for (int i = 0; i < G->NumOfVertices; i++)
    {
        G->Array[i] = NULL;
    }
    for (int i = 0; i < G->NumOfEdges; i++)
    {
        scanf("%d%d", &a, &b);
        PtrToVNode p = (PtrToVNode)malloc(sizeof(VNode));
        p->Vert = b;
        p->Next = G->Array[a];
        G->Array[a] = p;
    }
    return G;
}

void PrintV(Vertex V)
{
    printf("%d ", V);
}

void StronglyConnectedComponents(Graph G, void (*visit)(Vertex V));

int main()
{
    Graph G = ReadG();
    StronglyConnectedComponents(G, PrintV);
    system("pause");
    return 0;
}

/* Your function will be put here */
void StronglyConnectedComponents(Graph G, void (*visit)(Vertex V))
{
    int mp[MaxVertices][MaxVertices] = {0}, num = G->NumOfVertices;
    int vis[MaxVertices] = {0};
    for (int i = 0; i < num; i++)
    {
        PtrToVNode p = G->Array[i];
        while (p)
        {
            mp[i][p->Vert] = 1;
            p = p->Next;
        }
    }
    //利用到floyd算法，得到两个点是否联通的关系。
    for (int k = 0; k < num; k++)
    {
        for (int i = 0; i < num; i++)
        {
            for (int j = 0; j < num; j++)
            {
                if (mp[i][k] && mp[k][j])
                    mp[i][j] = 1;
                //for(int l = 0;l < num;l ++) mp[i][j] |= mp[i][l] * mp[l][j]; //上一句可替换为这一句 可达矩阵的n - 1次方可以求出任意一点到另一点是否可达
            }
        }
    }
    for (int i = 0; i < num; i++)
    {
        if (vis[i])
            continue;
        visit(i);
        vis[i] = 1;
        for (int j = 0; j < num; j++)
        {
            if (!vis[j] && mp[i][j] && mp[j][i])
            {
                vis[j] = 1;
                visit(j);
            }
        }
        putchar('\n');
    }
}

地下迷宫探索

#include <iostream>
using namespace std;

int n;
int N[1111][1111];
int vis[1111] = {0};

int t = 0;
void dfs(int v)
{
    if (!t)
        cout << v;
    else
        cout << " " << v;
    t = 1;
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i] && N[v][i])
        {
            vis[i] = 1;
            dfs(i);
            cout << " " << v;
        }
    }
}

int main()
{
    for (int i = 0; i < 1111; ++i)
        for (int j = 0; j < 1111; ++j)
            N[i][j] = 0;
    int m, S;
    cin >> n >> m >> S;
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b;
        N[a][b] = N[b][a] = 1;
    }
    vis[S] = 1;
    dfs(S);
    for (int i = 1; i <= n; ++i)
    {
        if (!vis[i])
        {
            cout << " 0" << endl;
            break;
        }
    }
    return 0;
}

六度空间

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

int Graph[1111][1111];
int n;
int vis[1111];
int Sum;

void BFS(int S)
{
    vis[S] = 1;
    queue<int> q;
    q.push(S);
    int start = S, tail, step = 0;
    while (!q.empty())
    {
        int tmp = q.front();
        q.pop();
        for (int i = 1; i <= n; ++i)
        {
            if (!vis[i] && Graph[tmp][i])
            {
                vis[i] = 1;
                q.push(i);
                Sum++;
                tail = i;
            }
        }
        if (start == tmp)
        {
            start = tail;
            step++;
        }
        if (step == 6)
            break;
    }
}

int main()
{
    for (int i = 0; i < 1111; ++i)
        for (int j = 0; j < 1111; ++j)
            Graph[i][j] = 0;
    memset(vis, 0, sizeof(int) * 1111);
    int m;
    cin >> n >> m;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        Graph[a][b] = Graph[b][a] = 1;
    }
    for (int i = 1; i <= n; ++i)
    {
        Sum = 1;
        BFS(i);
        float ans = (float)Sum / n * 100;
        printf("%d: %.2f%%\n", i, ans);
        memset(vis, 0, sizeof(int) * 1111);
    }
    return 0;
}

社交网络图中结点的“重要性”计算

#include <iostream>
#include <cstdio>
#define INF 0x3f3f3f3f
#define maxn 11111
using namespace std;

int Graph[maxn][maxn];
int N, M;

int main()
{
    cin >> N >> M;
    //初始化
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 1; j <= N; ++j)
        {
            if (i == j)
                Graph[i][j] = 0;
            else
                Graph[i][j] = INF;
        }
    }
    //输入数据
    for (int i = 0; i < M; ++i)
    {
        int a, b;
        cin >> a >> b;
        Graph[a][b] = 1;
        Graph[b][a] = 1;
    }
    //多源路径Floyd更新
    for (int k = 1; k <= N; ++k)
    {
        for (int i = 1; i <= N; ++i)
        {
            for (int j = 1; j <= N; ++j)
            {
                if (Graph[i][j] > Graph[i][k] + Graph[k][j])
                {
                    Graph[i][j] = Graph[i][k] + Graph[k][j];
                }
            }
        }
    }
    //检验是否连通图
    bool flag = true;
    for (int i = 1; i <= N; ++i)
    {
        if (Graph[1][i] == INF)
        {
            flag = false;
            break;
        }
    }
    int K;
    cin >> K;
    while (K--)
    {
        int num;
        cin >> num;
        if (!flag)
        {
            printf("Cc(%d)=%.2f\n", num, 0);
        }
        else
        {
            double average = 0;
            for (int i = 1; i <= N; ++i)
            {
                average += Graph[num][i];
            }
            average = 1.0 / (average * 1.0 / (N - 1));
            printf("Cc(%d)=%.2f\n", num, average);
        }
    }
    system("pause");
    return 0;
}