1.已知一个连通图G采用数组存储法，其结点值为数值型，采用深度优先搜索方法，编程序将所有结点的值变为0。
2.已知一个连通图G采用数组存储法，其结点值为数值型，采用广度优先搜索方法，编程序将所有结点的值打印出来。
3.假设图G采用邻接表存储方式，，编程序求解每个一个顶点的入度: FindInDegree(G, indegree);
1.下面是深度优先搜索的程序，用于将图中所有结点的值变为0：
void dfs(int u, int G[][MAXN], int n)
{
// 将当前结点的值变为0
G[u][u] = 0;
// 遍历所有与当前结点相连的结点
for (int v = 0; v < n; v++)
{
// 如果v是u的相邻结点，则递归调用dfs
if (G[u][v] != 0)
{
dfs(v, G, n);
}
}
}
// 在主函数中调用dfs，遍历图中所有结点
void setAllValuesToZero(int G[][MAXN], int n)
{
for (int u = 0; u < n; u++)
{
dfs(u, G, n);
}
}
2.下面是广度优先搜索的程序，用于打印图中所有结点的值：
void bfs(int u, int G[][MAXN], int n)
{
// 创建一个队列来保存当前遍历到的结点
queue<int> q;
// 将当前结点加入队列
q.push(u);
// 循环遍历队列中的结点
while (!q.empty())
{
// 从队列中取出第一个结点
int u = q.front();
q.pop();
// 打印当前结点的值
printf("%d ", G[u][u]);
// 遍历所有与当前结点相连的结点
for (int v = 0; v < n; v++)
{
// 如果v是u的相邻结点，则将其加入队列
if (G[u][v] != 0)
{
q.push(v);
}
}
}
}
// 在主函数中调用bfs，遍历图中所有结点
void printAllValues(int G[][MAXN], int n)
{
for (int u = 0; u < n; u++)
{
bfs(u, G, n);
}
}
3.下面是使用邻接表存储图的程序，用于求解每个顶点的入度：
#include <stdio.h>
#include <stdlib.h>
#define MAXN 100
// 定义链表结点
struct ListNode
{
int val; // 结点的值
ListNode* next; // 指向下一个结点的指针
};
// 定义邻接表
struct AdjacencyList
{
ListNode* head; // 指向第一个结点的指针
int size; // 链表的长度
};
// 创建一个新的链表结点
ListNode* createListNode(int val)
{
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
node->val = val;
node->next = NULL;
return node;
}
// 初始化邻接表
void initAdjacencyList(AdjacencyList* list)
{
list->head = NULL;
list->size = 0;
}
// 向邻接表中加入新的结点
void addToAdjacencyList(AdjacencyList* list, int val)
{
// 创建新的结点
ListNode* node = createListNode(val);
// 将新结点插入到链表的头部
node->next = list->head;
list->head = node;
list->size++;
}
// 求解每个顶点的入度
void FindInDegree(AdjacencyList* G, int indegree[], int n)
{
// 初始化所有结点的入度为0
for (int u = 0; u < n; u++)
{
indegree[u] = 0;
}
// 遍历所有结点
for (int u = 0; u < n; u++)
{
// 遍历当前结点的所有相邻结点
ListNode* curr = G[u].head;
while (curr != NULL)
{
// 将当前结点的相邻结点的入度加1
indegree[curr->val]++;
curr = curr->next;
}
}
}
int main()
{
// 创建邻接表
AdjacencyList G[MAXN];
for (int i = 0; i < MAXN; i++)
{
initAdjacencyList(&G[i]);
}
// 加入边
addToAdjacencyList(&G[0], 1);
addToAdjacencyList(&G[0], 2);
addToAdjacencyList(&G[1], 2);
addToAdjacencyList(&G[2], 0);
addToAdjacencyList(&G[2], 3);
addToAdjacencyList(&G[3], 3);
// 求解每个结点的入度
int indegree[MAXN];
FindInDegree(G, indegree, MAXN);
// 打印每个结点的入度
for (int u = 0; u < MAXN; u++)
{
printf("%d: %d\n", u, indegree[u]);
}
return 0;
}
在这段程序中，我们使用了链表来存储邻接表，并在FindInDegree函数中遍历所有结点的所有相邻结点，将这些结点的入度加1。最后，我们在主函数中调用了FindInDegree函数，并打印了每个结点的入度。