c語言有向圖
一個無向圖存在歐拉迴路，當且僅當該圖所有頂點度數都為偶數，且該圖是連通圖。
一個有向圖存在歐拉迴路，所有頂點的入度等於出度且該圖是連通圖。
可以用鄰接矩陣或者鄰接表，做一次DFS或者BFS訪問各個節點判斷入度出度就行。
(1)c語言有向圖擴展閱讀：
1、無向連通圖 G 是歐拉圖，當且僅當 G 不含奇數度結點( G 的所有結點度數為偶數)；
2、無向連通圖G 含有歐拉通路，當且僅當 G 有零個或兩個奇數度的結點；
3、有向連通圖 D 是歐拉圖，當且僅當該圖為連通圖且 D 中每個結點的入度=出度；
② 求如下有向圖的關鍵路徑以及任意兩點之間的最短距離
用CPM演算法求有向圖的關鍵路徑和用Dijkstra演算法求有向圖的最短路徑的C語言程序如下
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
#define MAX 20
#define INF 32767 // 此處修改最大值
#define nLENGTH(a) (sizeof(a)/sizeof(a[0]))
#define eLENGTH(a) (sizeof(a)/sizeof(char))/(sizeof(a[0])/sizeof(char))
typedef struct _graph{
char vexs[MAX]; // 頂點集合
int vexnum; // 頂點數
int edgnum; // 邊數
int matrix[MAX][MAX]; // 鄰接矩陣
}Graph, *PGraph;
// 邊的結構體
typedef struct _EdgeData{
char start; // 邊的起點
char end; // 邊的終點
int weight; // 邊的權重
}EData;
//指向節點的位置
int point_node(PGraph g,char c){
for(int i=0;i<g->vexnum;i++){
if(g->vexs[i]==c){
return i;
}
}
return -1;
}
PGraph create_graph(int b[][3],char a[],int n,int e){
char c1,c2; //邊的2個頂點
PGraph g; //矩陣
g=(PGraph)malloc(sizeof(Graph));
//memset()第一個參數 是地址，第二個參數是開辟空間的初始值，第三個參數是開辟空間的大小
memset(g, 0, sizeof(Graph));
printf("頂點個數: ");//頂點數
g->vexnum=n;
printf("%d ",g->vexnum);
printf("邊個數: ");//邊數
g->edgnum=e;
printf("%d ",g->edgnum);
//初始化頂點
for(int j=0;j<g->vexnum;j++){
g->vexs[j]=a[j];
}
for(int i=0;i<g->edgnum;i++){
int p1,p2;
c1=char(b[i][0]);
c2=char(b[i][1]);
p1=point_node(g, c1);
p2=point_node(g, c2);
if (p1==-1 || p2==-1){
printf("input error: invalid edge! ");
free(g);
continue;
}
g->matrix[p1][p2]=b[i][2];
}
for(int i=0;i<g->vexnum;i++){
for(int j=0;j<g->vexnum;j++){
if(g->matrix[i][j]==0)
g->matrix[i][j]=INF;
}
}
return g;
}
//關鍵路徑的最短時間
//關鍵路徑法（Critical Path Method，CPM）
void CPM_road(PGraph g){
int i,j;
int a[MAX]={0},b[MAX]={-10};
int max=0;//最長路徑
for( i=0;i<g->vexnum;i++){//列數遍歷
for( j=0;j<g->vexnum;j++){//行數遍歷
//如果g->matrix[j][i]大於0，說明此頂點有前頂點，由前邊的遍歷可知，前頂點的最長路徑a[j]，
//加上g->matrix[j][i]的路徑就是當前a[i]的路徑
if(g->matrix[j][i]!=INF && g->matrix[j][i]+a[j]>max){
max=g->matrix[j][i]+a[j];
a[i]=max;
}
}
max=0;
}
//顯示最長路徑
printf("第一個頂點到每一個頂點的最長路徑:");
printf(" ");
for(i=0;i<g->vexnum;i++){
printf("V%d ",i+1);
}
printf(" ");
for(i=0;i<g->vexnum;i++){
printf("%d ",a[i]);
}
printf(" ");
printf("最後一個頂點到每個頂點的最長路徑:");
for( i=g->vexnum-1;i>=0;i--){ //列數遍歷
for( j=g->vexnum-1;j>=0;j--){ //行數遍歷
//如果g->matrix[j][i]大於0，說明此頂點有前頂點，由前邊的遍歷可知，前頂點的最長路徑a[j]，
//加上g->matrix[j][i]的路徑就是當前a[i]的路徑
if(g->matrix[i][j]!=INF && g->matrix[i][j]+b[j]>max){
max=g->matrix[i][j]+b[j];
b[i]=max;
}
}
max=0;
}
//顯示最長路徑
printf(" ");
for(i=0;i<g->vexnum;i++){
printf("V%d ",i+1);
}
printf(" ");
for(i=0;i<g->vexnum;i++){
printf("%d ",b[i]);
}
printf(" ");
printf("關鍵路徑: ");
for(i=0;i<g->vexnum;i++){
if(a[i]==a[g->vexnum-1]-b[i]){
printf("V%c ",g->vexs[i]);
}
}
printf(" ");
}
void print_shortest_path(PGraph g,int* distance,int* path,int* used,int start,int end){
// 輸出最短距離並列印最短路徑
int i = 0, pre, inverse_path[g->vexnum];
char s1[3],s2[3];
sprintf(s1, "V%d", (start+1));
sprintf(s2, "V%d", (end+1));
printf("從%s頂點到%s頂點的最短距離: %d ", s1, s2, distance[end]);
inverse_path[i] = end;
pre = path[end];
if(pre == -1){
printf("沒有通路! ");
}else{
while(pre != start){
inverse_path[++i] = pre;
pre = path[pre];
}
inverse_path[++i] = start;
printf("從%s頂點到%s頂點的最短路徑: ", s1, s2);
for(; i > 0; i--){
sprintf(s1, "V%d", (inverse_path[i]+1));
printf("%s -> ", s1);
}
sprintf(s1, "V%d", (inverse_path[i]+1));
printf("%s ", s1);
}
return;
}
void shortest_path(PGraph g,int start, int end){ // 基於Dijkstra演算法的最短路徑函數
int distance[g->vexnum]; // 用於存放起始點到其餘各點的最短距離
int path[g->vexnum]; // 用於存放起始點到其餘各點最短路徑的前一個頂點
int used[g->vexnum] = { 0 }; // 用於標記該頂點是否已經找到最短路徑
int i, j, min_node, min_dis, pass_flag = 0;
for(i = 0; i < g->vexnum; i++){
distance[i] = g->matrix[start][i]; // 初始化距離數組
if(g->matrix[start][i] < INF){
path[i] = start; // 初始化路徑數組
}else{
path[i] = -1;
}
}
used[start] = 1;
path[start] = start;
for(i = 0; i < g->vexnum; i++){
min_dis = INF;
for(j = 0; j < g->vexnum; j++){
if(used[j] == 0 && distance[j] < min_dis){
min_node = j;
min_dis = distance[j];
pass_flag++; // 標記是否存在通路
}
}
if(pass_flag != 0){
used[min_node] = 1;
for(j = 0; j < g->vexnum; j++){
if(used[j] == 0){
if(g->matrix[min_node][j] < INF && distance[min_node] + g->matrix[min_node][j] < distance[j]){
distance[j] = distance[min_node] + g->matrix[min_node][j];
path[j] = min_node;
}
}
}
}
}
print_shortest_path(g,distance, path, used, start, end);
return;
}
int main(){
int i,j;
PGraph gp;
char a[]={'1', '2', '3', '4', '5', '6', '7'};
int b[][3]={{'1', '2',3},
{'1', '3',2},
{'1', '4',6},
{'2', '4',2},
{'2', '5',4},
{'3', '4',1},
{'3', '6',3},
{'4', '5',1},
{'5', '7',3},
{'6', '7',4}};
int n=nLENGTH(a);
int e=eLENGTH(b);
gp=create_graph(b,a,n,e);
//列印鄰接矩陣
printf("鄰接矩陣: ");
for (i = 0; i < gp->vexnum; i++){
for (j = 0; j < gp->vexnum; j++)
printf("%d ", gp->matrix[j][i]);
printf(" ");
}
CPM_road(gp);
printf(" ");
for(i=0;i<gp->vexnum;i++){
for(j=0;j<gp->vexnum;j++){
if(i!=j)
shortest_path(gp,i, j);
}
}
return 0;
}
運行結果
