<1>设计算法实现图的深度优先遍历。（递归算法） <2>设计算法实现图的广度优先遍历。（递归算法） <3>求顶点的度（入度或出度）。C语言

<> 图的深度优先遍历（递归算法）：

#define MAX_VERTEX_NUM 100
typedef struct {
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int vexnum,arcnum;
}Graph;

bool visited[MAX_VERTEX_NUM];
void DFS(Graph G, int v) {
    visited[v] = true;
    printf("%d ",v);
    for(int i=0; i<G.vexnum; i++) {
        if(G.arcs[v][i] && !visited[i]) {
            DFS(G, i);
        }
    }
}

void DFSTraverse(Graph G) {
    memset(visited, false, sizeof(visited));
    for(int i=0; i<G.vexnum; i++) {
        if(!visited[i]) {
            DFS(G, i);
        }
    }
}

<2> 图的广度优先遍历（递归算法）：

#define MAX_VERTEX_NUM 100
typedef struct {
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int vexnum,arcnum;
}Graph;

bool visited[MAX_VERTEX_NUM];
void BFS(Graph G, int v) {
    visited[v] = true;
    printf("%d ",v);
    queue<int> q;
    q.push(v);
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(int i=0; i<G.vexnum; i++) {
            if(G.arcs[u][i] && !visited[i]) {
                visited[i] = true;
                printf("%d ",i);
                q.push(i);
            }
        }
    }
}

void BFSTraverse(Graph G) {
    memset(visited, false, sizeof(visited));
    for(int i=0; i<G.vexnum; i++) {
        if(!visited[i]) {
            BFS(G, i);
        }
    }
}

<3> 求顶点的度（入度或出度）的C语言实现：

#define MAX_VERTEX_NUM 100
typedef struct {
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int vexnum,arcnum;
}Graph;

int GetInDegree(Graph G, int v) {
    int indegree = 0;
    for(int i=0; i<G.vexnum; i++) {
        if(G.arcs[i][v]) {
            indegree++;
        }
    }
    return indegree;
}

int GetOutDegree(Graph G, int v) {
    int outdegree = 0;
    for(int i=0; i<G.vexnum; i++) {
        if(G.arcs[v][i]) {
            outdegree++;
        }
    }
    return outdegree;
}